早教吧作业答案频道 -->数学-->
有三根针和套在一根针上的20个金属片,按下列规则,把金属片从一根针上全部移到另一根针上的步骤是怎样的?
题目详情
有三根针和套在一根针上的20个金属片,按下列规则,把金属片从一根针上全部移到另一根针上的步骤是怎样的?
▼优质解答
答案和解析
汉诺塔问题
汉诺塔(又称河内塔)问题是印度的一个古老的传说.开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面.解答结果请自己运行计算,程序见尾部.面对庞大的数字(移动圆片的次数)18446744073709551615,看来,众僧们耗尽毕生精力也不可能完成金片的移动.
后来,这个传说就演变为汉诺塔游戏:
1.有三根杆子A,B,C.A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片:
如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C
此外,汉诺塔问题也是程序设计中的经典递归问题.
算法思路:
1.如果只有一个金片,则把该金片从源移动到目标棒,结束.
2.如果有n个金片,则把前n-1个金片移动到辅助的棒,然后把自己移动到目标棒,最后再把前n-1个移动到目标棒.
3.单纯对于有N个金片要挪动的步数求出,可以使用递推方法,满足递推方程
f(i) = f(i - 1) * 2 + 1.
汉诺塔(又称河内塔)问题是印度的一个古老的传说.开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面.解答结果请自己运行计算,程序见尾部.面对庞大的数字(移动圆片的次数)18446744073709551615,看来,众僧们耗尽毕生精力也不可能完成金片的移动.
后来,这个传说就演变为汉诺塔游戏:
1.有三根杆子A,B,C.A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片:
如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C
此外,汉诺塔问题也是程序设计中的经典递归问题.
算法思路:
1.如果只有一个金片,则把该金片从源移动到目标棒,结束.
2.如果有n个金片,则把前n-1个金片移动到辅助的棒,然后把自己移动到目标棒,最后再把前n-1个移动到目标棒.
3.单纯对于有N个金片要挪动的步数求出,可以使用递推方法,满足递推方程
f(i) = f(i - 1) * 2 + 1.
看了 有三根针和套在一根针上的20...的网友还看了以下:
一个双金属片由线膨胀系数为a1和a2的两个金属片组成,此两金属片的厚度均为d,在温度T1时长度均为 2020-05-22 …
阅读短文,回答问题:电熨斗如图1为生活中常用的电熨斗,图2是电熨斗结构图.电熨斗中有一个双金属片制 2020-06-27 …
6个人1个取平均数,其余5个按7:3分配一笔总额为20000元资金,怎么分?求计算公式5个人按7: 2020-08-01 …
计算机键盘是由两片金属切片组成的小电容器,该电容器的电容可用公式计算,式中ε=9×10-12,S为金 2020-11-03 …
如图所示,有的计算机键盘的每一个键下面连一小块金属片请勿答非所问有的计算机键盘的每一个键下面连一小块 2020-11-03 …
计算机键盘是由两片金属切片组成的小电容器.该电容器的电容可用公式C=εSd计算,式中ε=9×10-1 2020-11-03 …
如图所示,有的计算机键盘的每一个键下面连一小块金属片,与该金属片隔有一定空气隙的是另一片小的固定金属 2020-11-07 …
一个黄铜板,插着三根针,在第一根针上,从下到上穿着由大到小的64片中心有孔的金片.每天把金片从第一根 2020-11-08 …
指针式温度计的主要结构是双金属片,双金属片是由两根热膨胀程度不同的金属片制成.比如由铁和铜制成的爽金 2020-11-08 …
计算机键盘是由两片金属切片组成的小电容器,该电容器的电容可用公式C=计算,式中ε=9×10-12,S 2020-12-05 …