文档章节

poj 1958 Strange Towers of Hanoi

locusxt
 locusxt
发布于 2014/11/29 11:42
字数 815
阅读 28
收藏 0
Strange Towers of Hanoi
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 2513 Accepted: 1667

Description

Background 
Charlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard Tower of Hanoi problem, which bores Charlie to death! 

The teacher points to the blackboard (Fig. 4) and says: "So here is the problem: 
  • There are three towers: A, B and C. 
  • There are n disks. The number n is constant while working the puzzle. 
  • All disks are different in size. 
  • The disks are initially stacked on tower A increasing in size from the top to the bottom. 
  • The goal of the puzzle is to transfer all of the disks from tower A to tower C. 
  • One disk at a time can be moved from the top of a tower either to an empty tower or to a tower with a larger disk on the top.

So your task is to write a program that calculates the smallest number of disk moves necessary to move all the disks from tower A to C." 
Charlie: "This is incredibly boring—everybody knows that this can be solved using a simple recursion.I deny to code something as simple as this!" 
The teacher sighs: "Well, Charlie, let's think about something for you to do: For you there is a fourth tower D. Calculate the smallest number of disk moves to move all the disks from tower A to tower D using all four towers." 
Charlie looks irritated: "Urgh. . . Well, I don't know an optimal algorithm for four towers. . . " 
Problem 
So the real problem is that problem solving does not belong to the things Charlie is good at. Actually, the only thing Charlie is really good at is "sitting next to someone who can do the job". And now guess what — exactly! It is you who is sitting next to Charlie, and he is already glaring at you. 
Luckily, you know that the following algorithm works for n <= 12: At first k >= 1 disks on tower A are fixed and the remaining n-k disks are moved from tower A to tower B using the algorithm for four towers.Then the remaining k disks from tower A are moved to tower D using the algorithm for three towers. At last the n - k disks from tower B are moved to tower D again using the algorithm for four towers (and thereby not moving any of the k disks already on tower D). Do this for all k 2 ∈{1, .... , n} and find the k with the minimal number of moves. 
So for n = 3 and k = 2 you would first move 1 (3-2) disk from tower A to tower B using the algorithm for four towers (one move). Then you would move the remaining two disks from tower A to tower D using the algorithm for three towers (three moves). And the last step would be to move the disk from tower B to tower D using again the algorithm for four towers (another move). Thus the solution for n = 3 and k = 2 is 5 moves. To be sure that this really is the best solution for n = 3 you need to check the other possible values 1 and 3 for k. (But, by the way, 5 is optimal. . . )

Input

There is no input.

Output

For each n (1 <= n <= 12) print a single line containing the minimum number of moves to solve the problem for four towers and n disks.

Sample Input

No input.

Sample Output

REFER TO OUTPUT.

Source

TUD Programming Contest 2002, Darmstadt, Germany


汉诺塔的解法是一个递归,假设有ABC三个柱子,A柱上有n个盘子。将A上盘子移到C,相当于先把A上n-1个挪到B,再把A上剩余的一个挪到C,现在问题变为了将B上n-1个盘子挪到C。所以有递推公式f(n)=2*f(n-1)+1。
题目中的是加了一根柱子,根据题目的提示,有递推公式g(n)=min{2*g(n-k)+f(k)},即g(n)=min{2*g(n-k)+2^k-1}。可以用dp来做。

#include <cstdio>
#include <cstdlib>
#define MAXN 15
#define INF 100000000

int main()
{
	int dp[MAXN] = {0};
	dp[1] = 1;
	dp[0] = 0;

	for (int i = 2; i <= 12; ++i)
	{
		int my_min = INF;
		for (int j = 1; j <= i; ++j)
		{
			int tmp = (dp[i - j] << 1) + (1 << j) - 1;
			if (my_min > tmp)
			{
				my_min = tmp;
			}
		}
		dp[i] = my_min;
	}

	for (int i = 1; i <= 12; ++i)
	{
		printf("%d\n", dp[i]);
	}
	return 0;
}



© 著作权归作者所有

locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
汉诺塔算法

有A、B和C 3跟柱子,在A上从下往上按照从小到大的顺序放着64个圆盘,以B为中介,把盘子全部移动到C上。移动过程中,要求任意盘子的下面要么没有盘子,要么只能有比它大的盘子。 package cgli...

一贱书生
2016/11/17
14
0
第伍章學題 Lisp 3rd Edition, Winston & Horn

5-1: Ignoring the existence of NTHCDR, the primitive supplied by LISP itself, write a tail recursive, SKIP-FIRST-N that trims off the first n elements from a list and return the......

莊博堯
2012/01/19
213
0
发现Tapestry5 MaxLength Validator bug

今天在使用字符串长度验证时发现bug,于是乎 google ,发现这个问题3个月前就有人问过了。 有位老外回答: http://tapestry.1045711.n5.nabble.com/A-strange-error-with-MaxLength-Validat...

神勇小白鼠
2012/06/21
160
1
预言世界末日来临的算法,C语言经典算法之河内之塔

河内之塔 说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及这个故事,据说...

这个人很懒什么都没留下
03/27
0
0
HT for Web 3D游戏设计设计--汉诺塔(Towers of Hanoi)

在这里我们将构造一个基于HT for Web的HTML5+JavaScript来实现汉诺塔游戏。 汉诺塔的游戏规则及递归算法分析请参考http://en.wikipedia.org/wiki/TowerofHanoi。 知道了汉诺塔的规则和算法,...

xhload3d
2015/01/12
265
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 磁盘不足异常

linux 报 No space left on device 异常 ,则是磁盘不足 ,导致异常 运行 df -h 命令查询磁盘使用率,如果有100%,则查找目录大日志文件删除 1.磁盘不足导致系统应用写入文件失败,如系统日志...

zaolonglei
40分钟前
3
0
即学即用的 30 段 Python 实用代码

☞ 分享:最全最新的Python学习大礼包 ☜ 点击查看 编译:Pita & AI开发者,作者:Fatos Morina Python是目前最流行的语言之一,它在数据科学、机器学习、web开发、脚本编写、自动化方面被许...

Object_Man
41分钟前
5
0
The server time zone value 'EDT' is unrecognized or represents more than one time zone.

2019-10-14 18:07:43.714 ERROR 74363 --- [Druid-ConnectionPool-Create-1855026648] com.alibaba.druid.pool.DruidDataSource : create connection SQLException, url: jdbc:mysql://10.30......

yizhichao
54分钟前
8
0
html加载顺序以及影响页面二次渲染额的因素

本文转载于:专业的前端网站➱html加载顺序以及影响页面二次渲染额的因素 浏览器请求发往服务器以后,返回HTML页面,页面内容开始渲染,具体的执行顺序为: 1. 浏览器开始载入html代码,发现<...

前端老手
56分钟前
9
0
BeginnersBook JSP、JSTL、Servlet 教程

来源:ApacheCN BeginnersBook 翻译项目 译者:飞龙 协议:CC BY-NC-SA 4.0 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 请您勇敢地去翻译和改进翻译。虽然我们追求卓越,但我们并...

ApacheCN_飞龙
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部