金融网站模板源代码,net网站是国际域名吗,深圳龙华建设发展公司,贵阳网站推广介绍
汉诺塔是源于印度的一个古老传说的小游戏#xff0c;简单来说就是有三根柱子#xff0c;开始的时候#xff0c;第一根柱子上圆盘由大到小#xff0c;自下往上排列。这个小游戏要实现的目的呢#xff0c;就是要把第一根柱子上的圆盘移到第三根的柱子上去#xff1b;…介绍
汉诺塔是源于印度的一个古老传说的小游戏简单来说就是有三根柱子开始的时候第一根柱子上圆盘由大到小自下往上排列。这个小游戏要实现的目的呢就是要把第一根柱子上的圆盘移到第三根的柱子上去条件呢就是在移动过程当中不能将大的圆盘放在小的圆盘上面我们可以利用中间第二根柱子作为桥梁来承接我们要移动的圆盘。
而在这个传说当中一共有64块圆盘假设我们使用递归的方法我们也得用18446744073709551615的步数来实现我们的目的换算成时间呢我们得花5845.42亿年来实现这个过程。
算法思路
实现这个小游戏的算法思路是什么呢
我们一定要将最大的那块圆盘放到C柱那里去那么我们的目的就很明确我们倒着思考一下最后那几步的时候我们是要将上面的n-1块圆盘移动到中间的柱子上最后再将n-1块圆盘放到C柱上的。 假设我们这里有三块圆盘我们先将A盘上的两块小圆盘移到B盘上去 再将A柱上最大的圆盘移动到C柱上 再将B柱上的圆盘放回C住上最后大功告成 那在这一步的前一步呢那不就是n-2块了吗对于前面的步骤都是和最后的类似那最后一步我们走了几步呢假设我们有一个表达式能描述移动的步数那么
为什么会有这个表达式呢我们先移动了n-1块盘到B柱再将n-1块盘到C柱这里我们就可以得到我们还将最下面的那个盘子放到了C盘这里所以我们在这里得加一。
最后我们可以得到步数的结果为
其它方法
美国学者曾提出过一种更为简洁的方法首先把三根柱子按顺序排成品字型把所有的圆盘按从大到小的顺序放在柱子A上根据圆盘的数量确定柱子的排放顺序
若n为偶数按顺时针方向依次摆放 A B C若n为奇数按顺时针方向依次摆放 A C B
步骤 按顺时针方向把圆盘1从现在的柱子移动到下一根柱子即当n为偶数时若圆盘1在柱子A则把它移动到B若圆盘1在柱子B则把它移动到C若圆盘1在柱子C则把它移动到A。 接着把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上当两根柱子都非空时移动较小的圆盘。这一步没有明确规定移动哪个圆盘你可能以为会有多种可能性其实不然可实施的行动是唯一的。 反复进行⑴⑵操作最后就能按规定完成汉诺塔的移动。 代码实现
python
def f(n):if n0:return 0else:return 2*f(n-1)1
xint(input(请输入片的个数))
print(需要移动,f(x),次)
def hanoi(n, a, b, c):if n 1:print(a, --, c)else:hanoi(n - 1, a, c, b)print(a, --, c)hanoi(n - 1, b, a, c)
# 调用
hanoi(5, A, B, C)
cpp
#include iostream using namespace std; void hanoi(int n, char source, char help, char target){static int step 0; if (n 1)std::cout (step) : source ---- target endl; else{// move n-1 disks from source to help hanoi(n-1, source, target, help); std::cout (step) : source ---- target endl; hanoi(n-1, help, source, target);}
}
int main(void){hanoi(10, a, b, c);return 0;
}C
#include stdio.h
#include windows.h
void Hanoi(int n, char a,char b,char c);
void Move(int n, char a, char b);
int count;
int main()
{int n8;printf(汉诺塔的层数:\n);scanf( %d,n);Hanoi(n, A, B, C);Sleep(20000);return 0;
}
void Hanoi(int n, char a, char b, char c)
{if (n 1){Move(n, a, c);}else{Hanoi(n - 1, a, c, b);Move(n, a, c);Hanoi(n - 1, b, a, c);}
}
void Move(int n, char a, char b)
{count;printf(第%d次移动 Move %d: Move from %c to %c !\n,count,n,a,b);
}
