汉诺塔问题是最经典的递归思想
题目:
“大梵天”创造世界的时候做了三根金刚石柱子(A、B、C)，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。“大梵天”命令“婆罗门”把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
要求:小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
问:64片圆盘移动完毕需要多少时间??
先说答案:64片圆盘柱子移动完毕就是世界毁灭之时!!!!!!!
解答:
我们假设有N个圆盘,则把原盘看出2部分
第一部分:第N个圆盘(也就是底部最大的那个圆盘)
第二部分:(N-1) 个圆盘
问题就简单化了,我们只需要做做三步就可以完成移动
1.将N-1个盘子从A柱子(经过C柱子)移动到B柱子
2.将第N个盘子从A柱子移动到C柱子
3.将N-1个盘子从B柱子(经过A柱子)移动到C柱子
因为一次只能移动1个盘子,所以除了步骤2;步骤1和步骤3,需要再细分成步骤1,2,3;
这样就形成了递归.
Object C的代码为:
/*
n: n个盘子
StartPoint:起点柱子
Passby:经过的柱子
EndPoint:结束的柱子
*/
- (void)hanoiMove:(int)n StartPoint:(NSString *)a Passby:(NSString *)b EndPoint:(NSString *)c
{
if (n == 1)
{
//第2部
NSLog(@"移动第 %d 个盘子 从 %@ 到 %@\n",n,a,c);
}else{
//第1步
[self hanoiMove:n-1 StartPoint:a Passby:c EndPoint:b];
NSLog(@"移动第 %d 个盘子 从 %@ 到 %@\n",n,a,c);
//第3步
[self hanoiMove:n-1 StartPoint:b Passby:a EndPoint:c];
}
}我们假设只有3个圆盘(N=3),来验证一下代码的准确性:
[self hanoiMove:3 StartPoint:@"A" Passby:@"B" EndPoint:@"C"];
/*
假如n=3,给盘子从上到下,依次编号1.2.3; 则3个盘子的移动顺序为
移动第 1 个盘子 从 A 到 C
移动第 2 个盘子 从 A 到 B
移动第 1 个盘子 从 C 到 B
移动第 3 个盘子 从 A 到 C
移动第 1 个盘子 从 B 到 A
移动第 2 个盘子 从 B 到 C
移动第 1 个盘子 从 A 到 C
与下边的代码打印结果一致
*/控制台打印输出:假设移动一个圆盘需要1秒,3个圆盘则需要7秒; 64个圆盘需要N万秒, 感性起的朋友可以尝试一下10个圆盘或者20个圆盘,看看多次秒...千万不要轻易尝试64个圆盘,你的电脑可能会卡
