11. Python | 递归函数_引申_汉诺塔游戏策略总结

汉诺塔游戏，是个佷益智的游戏,其中也蕴含了一些数学的知识，故事的背景甚至蕴含了一些古人对宇宙的思考。今天我们来聊下这个游戏，仅仅从游戏的方法和策略的总结上对这个游戏进行一下解剖：

游戏简介

汉诺塔_益智游戏

`由来与传说：`

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

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一
根针上，并且始终保持上小下大的顺序。这需要多少次移动呢？这里需要递归的方
法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。
此后不难证明f(n)=2^n-1。n=64时，

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有
31622400秒，平均每年31556952秒，计算一下：
                                        18446744073709551615秒

这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系
的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，
至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

游戏的目的

• 很多人最初接触到这个益智游戏，都是直接用5个以上圆盘开始游戏的，但是又不太清楚具体的移动规律，导致玩儿了半天也没有将所有圆盘成功移动到C柱子上，甚至玩过以后就得出了一个结论，这游戏太没意思了。。。

• 实际上这种益智类的游戏，往往都是具有一定的方法和规律可循的，因为这类游戏的目的就是让人开发思维，启迪智慧。通常这类游戏或者玩具是最适合给孩子玩的。

• 既然这个游戏有益智的作用，我们就应该掌握玩这种游戏的方法或者至少我们应该学会教孩子如何玩这个游戏，才能让这个益智游戏开发孩子的思维启迪孩子的智慧啊！

游戏的策略

在这一部分，我们要分为两点去讲：1. 推导和归纳；2. Python代码的实现。

1. 推导和归纳

说到归纳和总结，我们可以参照数学上的归纳方法。
举个例子：

`                     1 = 1                               `
`                   1×2 = 2                               `
`                 1×2×3 = 6                               `
`               1×2×3×4 = 24                              `
`             1×2×3×4×5 = 120                             `
`                 ...                                     `
`     1×2×3×...×(n-1)×n = f(n)                            `

上面的归纳的是一个函数，也就是阶乘，表达式为：
f（n） = n! = n * (n-1) * ... * 1 = n * (n-1)!
归纳之后便形成了一个比较抽象、但是很容易记住的方法——公式。

通过归纳和演绎，用一些简单的、易操作的数字和步骤进行推演，形成适用于更广范围的通行公式。

• 我们来看一下汉诺塔如何推演
  要求：将圆盘从 <起点A柱子>借助<缓冲B柱子>移动到<终点C柱子>
  分析：为了更好的解释说明操作步骤，我们讲圆盘从小到大依次取名为1、2、3、4、5...
  步骤：

  1. 当A柱子上有1个圆盘时
     A-->C表示将1移到C：1-->C：圆盘为奇数时，第一步指向终点C柱

  2. 当A柱子上有2个圆盘时
     ①A-->B表示将1移到B：1-->B：圆盘为偶数时，第一步指向缓冲B柱
     ②A-->C表示将2移到C：2-->C：最下面的圆盘，移动到终点C柱
     ③B-->C表示将1移到C：1-->C：缓冲柱上的圆盘，移动到终点C柱

  3. 当A柱子上有3个圆盘时
     ①A-->C表示将1移到C：1-->C：圆盘为奇数时，第一步指向终点C柱
     ①A-->B表示将2移到B：2-->B：将2号圆盘移到缓冲B柱
     ①C-->B表示将1移到B：1-->B：将1号圆盘移到缓冲B柱
     ②A-->C表示将3移到C：3-->C：最下面的圆盘，移到到终点C柱
     ③B-->A表示将1移到A：1-->A：将1号圆盘移到起点A柱
     ③B-->C表示将2移到C：2-->C：将2号圆盘移到终点C柱
     ③A-->C表示将1移到C：1-->C：将1号圆盘移到终点C柱

• 根据上面写的3个推演步骤，我们进行归纳如下：

  1. 整个移动过程（排除只有一个圆盘的特殊情况），可以分为三个阶段，用①②③表示。
  2. ①阶段，把 n-1个圆盘移到缓冲B柱；
     ②阶段，把第n个圆盘移到终点C柱；
     ③阶段，把 n-1个圆盘移到终点C柱。
  3. 其中，第②阶段，是在最中间的一步，第①阶段和第③阶段的移动步数是一样多的。
  4. 第一步的移动方向，根据圆盘的个数不同而定
     奇数个圆盘，第一步一定是移到终点C柱
     偶数个圆盘，第一步一定是移到缓冲B柱
     别小瞧这个方向的定位，以后每次移动1、2圆盘时，都是按照这个方向定位的。
  5. 我们把移动圆盘的过程分为n轮，每一轮都要移动1、2、1和另一个圆盘；
     并且每一轮移动1、2、1圆盘的时候，都是按照固定的规律去移动的。
     我们会以1、2圆盘同时所在的柱子为视角做定位，判断移动的方向。下面有一个图，上面详细写了具体的移动顺序和方法：
     
  6. 要想明白具体是如何做的，只用眼睛看是很难理解的，当你跟着我写的步骤操作几次之后，你一定会豁然开朗，原来移动起来是这么简单~

2. Python代码的实现
当然了用文字，或者截图去描述这个过程，无论如何都算不上简单明了。Python语言中，用函数将这个游戏的移动方法，定义成了一个递归函数，写法竟然非常的简单：

# 请编写 `move(n, a, b, c)`函数，它接收参数 n，表示3个柱子A、B、C中
# 第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法
# -*- coding: utf-8 -*-
def move(n, a, b, c):

    if n == 1:
        print(a, '-->', c)
    # 下面else的部分是需补全的代码,也就是移动方法
    else:
        move(n-1,a,c,b)   # 思考一下为什么要这样写?
        move(1,a,b,c)   # 想一下，这是哪个阶段？
        move(n-1,b,a,c)   # 你知道，这最后的一步，是什么意思吗？
# 有3个圆盘时
move(3, 'A', 'B', 'C')
# 换行
print('\n')
# 有4个圆盘时
move(4, 'A', 'B', 'C')

# 这是有3个圆盘时的【期待输出结果】:
#     A --> C
#     A --> B
#     C --> B
#     A --> C
#     B --> A
#     B --> C
#     A --> C

你可以复制一下这段代码，去验证一下结果是不是和你自己移动的结果一样！