汉诺塔问题-到底需要多少时间

向右看齐 2022-10-31 04:07 129阅读 0赞

学过计算机的基本都对汉诺塔问题很熟悉了，即使没有学过计算机的的，想必也或多或少的了解汉诺塔问题，这篇文章通过数学的方式来求解这个问题。

### 汉诺塔 ###

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

### 递归 ###

这是一个非常经典的递归问题。  
思路很简单：  
假设有n个金片，需要把这些金片从第一根宝石针移动到第三个宝石针中。

1.  首先需要把n-1个金片移动到第二根宝石针上
2.  再把最后一个也就是最大的那一个移动到第三根宝石针上
3.  最后再把那n-1个金片移动到第3根宝石针上

这是典型的递归问题, 定义f(n)是需要移动的次数

f(1) = 1  
f(2) = 3  
f(3) = 7  
…  
f(n) = 2f(n-1)+1

### 数学归纳法 ###

高中的时候接触了数学归纳法，如果忘记了也每关系，这里给出完整的"套路"。

根据以上内容，可知：  
f(0)=0 f(1) = 1 f(2) = 3 f(3) = 7 f(4) = 15 f(5) = 31 …  
好像有点规律， f(n) = 2^n -1

那么这个猜想正确吗?用数学归纳法证明一下。

#### 定义 ####

数学归纳法是证明某个命题关于整数n(对所有的n>=n0)成立的一种一般的方法。首先，当n为最小值n0时我们证明命题，这称为**基础**，然后假设对于包含再n0和n-1之间的所有值，已经证明命题成立，对于n>n0证明命题，这种方法称为数学归纳法。

#### 证明 ####

f(0) = 2^0 -1, 显然基础是正确的  
假设n-1取代n的时候上述猜想成立，且对于n>0建立归纳，  
f(n) = 2f(n-1) + 1 = 2(2^(n-1)-1)+1  
= 2^n-2+1  
= 2^n -1  
因此，对于n来说，上面的猜想依然成立，**至此证明完毕，鼓掌**。

### 到底需要多久 ###

对于汉诺塔问题，f(n) = 2^64-1  
这是一个什么概念, 即使是**每微秒**移动一次， 也需要**5000世纪的时间**， 到那个时候，世界也许真的将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

### 类似问题 ###

传说: 罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里赏给我一粒麦子，在第2个小格里给2粒，第3个小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。

还有直线分割圆形，约瑟夫环问题等等。

### 写在最后 ###

书到用时方恨少。

### 公众号 ###

更多内容，欢迎关注我的微信公众号:无情剑客。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlbGxvd29ybGRkbQ_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlbGxvd29ybGRkbQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/fcb60b18dfe544ad91d7c9f524ea0d7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlbGxvd29ybGRkbQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/067a47f482c0492b86160653bfb48306.png