Day26：河内塔(Tower of Hanoi)

前言

终於结束了安全性演算法的部分，有兴趣的人可以进一步学习密码学，笔者想推荐一个课程：

课程讲解得很清楚，老师将复杂的观念分解为各个小议题进行教学，若是喜欢这个老师的课程，也可以选修其他的课程，支持认真开课的老师，大家一起让学习环境变得更好吧！

河内塔(Tower of Hanoi)

Hanoi是越南的首都，笔者曾经在越南旅行了一个月，尤其非常喜欢Hanoi这个地方。推荐一个到Hanoi必喝的饮料，「椰子冰沙咖啡」，为这个因为疫情暂时不能旅行的时期，提供一点不一样的能量。

河内塔(Tower of Hanoi)是移动圆盘的游戏，可以帮助轻松理解递回演算法(recursive algorithm)。先来看看河内塔是什麽：

执行次数：
假设解n个圆盘的河内塔，执行次数为T(n)，一个圆盘用一步就结束了，所以T(n)=1，n个圆盘时，首先要将上面的n-1个圆盘从A移动到B，为T(n-1)步，把最大的圆盘移动到C是一步，把位在B的n-1个圆盘移动到C是T(n-1)步，所以T(n)=2T(n-1)+1，可得T(n)=(2**n)-1，执行次数比这个还少的解法并不存在

Python

def hanoi(n, A, B, C):
    if n == 1:
        print(f"{A}->{C}")
    else:
        hanoi(n-1, A, C, B) 
        hanoi(1, A, B, C) 
        hanoi(n-1, B, A, C)

n = int(input())
hanoi(int(n), 'A', 'B', 'C')

JavaScript

function towerOfHanoi(n , start , target ,buffer){

    if(n>0){
        towerOfHanoi(n-1, start, buffer, target); 
        target.push(start.pop());   
        towerOfHanoi(n-1, buffer, target, start); 
    }
}

递回演算法(recursive algorithm)

递回演算法(recursive algorithm)是重复将问题分解为同类的子问题来解决问题的方法，可参考「合并排序」、「快速排序」。

递回的关键点在於这是一个「呼叫自己的函数」，这时候需要设置一个终止条件，将结果返回给呼叫者。

接下来看一个影片，影片内容是关於Python中的递回：

斐波那契数列(Fibonacci sequence)

Fibonacci sequence又称为黄金分割数列，是数学家Leonardoda Fibonacci以兔子繁殖为例子，延伸出来的有趣理论。这个理论内容如下：

如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在牠出生後的第三个月里，又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔开始，50个月後会有多少对兔子？
第一个月时，只有一对小兔子，过了一个月，那对兔子成熟了，在第三个月时便生下一对小兔子，这时有两对兔子。再过多一个月，成熟的兔子再生一对小兔子，而另一对小兔子长大，有三对小兔子。如此推算下去，我们便发现一个规律：
由此可知，从第一个月开始以後每个月的兔子总数是:
1,1,2,3,5,8,13,21,34,55,89,144,233…