---小“feng”子讲代码---

前言：小“feng”子系列课堂开课了！！！作为代码届冉冉升起的一个 小趴菜 。受到某位🐟的教唆，一时兴起想写出一篇自己的博客。毕竟是第一次嘛，也没幻想着有多少人能看到（要是能对他人有帮助当然也是极好），可能只是想给自己的青春时光留下一点点温暖而“羞涩”的回忆吧。

ps：心情还是有点激动哒@_@，好啦好啦，让我们来看看今天的问题吧！

目录

1.“汉诺塔”问题背景介绍；

2.“汉诺塔”问题思路详解；

3.两种解决“汉诺塔”问题的代码展示；

1.“汉诺塔”问题背景介绍；

汉诺塔问题的来源可谓是众说纷纭，其中我比较喜欢的一个版本是这样描述的：

在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

读完这个故事大家是不是完全不信呢，嘿嘿，但我要说的是这个故事并非没有道理哦，故事的谜底就让我们学习完今天的“汉诺塔”问题后在来解答吧！

2.“汉诺塔”问题思路详解；

首先，对于这个问题，我们可以从特殊到一般：

特例：当我们只有两个盘子时，我们从上到下分别做好下标1、2；

      第一步：我们需要将起始柱上的1移动到辅助柱上 ；

      第二步：将起始柱上的2移动到目标柱上；

      第三步：将1放回目标柱上，这样就完成了哇；

接下来就是最关键的一步：

使用递归的思想将大事化小，那我们应该如何做到呢？
我们一步一步来想；

当盘子个数为3时，先将上面两个盘子转移到辅助柱（方法和上面特例一样），然后将最大的盘子转移到目标柱，最后将辅助柱上的盘子转移到目标柱上（方法和上面特例一样），这样我们的目的就达成了！ 

那么以此类推......

当盘子个数为n时我们可以转化为，先将n-1个盘子的摆放好问题，而n-1个盘子又可以想象成先将n-2个盘子摆放好的问题，像这样不断向下，最后会演变成将2个盘子的摆放好的问题；

则找出以下规律：

2层：摆放3次

3层：摆放3+1+3次

......

n层：摆放（n-1）+1+（n-1）次；

得出规律为：2^n-1；

3.两种解决“汉诺塔”问题的代码展示；

推出了上面的结论后，我们可以进行代码的编写（有不足之处欢迎各位大佬指出啊）；

公式法：

#include<stdio.h>
#include<math.h>
typedef unsigned long long ll;int main()
{ll n,sum;//n表示汉诺塔层数,sum表示为移动的步数scanf("%llu",&n);sum=pow(2,n)-1;printf("%llu",sum);return 0;
}

递归法：

#include<stdio.h>
typedef unsigned long long ll;unsigned long long Hanoi(int x)//函数申明
{if(x==1) return 1;//创立函数停止递归条件，防止死循环else {return  2*Hanoi(x-1)+1;//递归}	
}int main()
{ll n,sum;//n表示汉诺塔层数,sum表示为移动的步数scanf("%llu",&n);printf("%llu",Hanoi(n));//调用函数return 0;
}

最后，回到我们最初提出的问题，当六十四层摆放完成后，世界正的会毁灭吗？

经过计算我们完成64层的转移大概需要18446744073709551615步，而我们假设每完成一步需要一秒，换算成年就是584942417355年（5000亿年），恐怖如斯~

而正常情况下太阳系的寿命为100亿年左右，这样想想我们似乎不可能见证到那一刻啦！