学过计算机的基本都对汉诺塔问题很熟悉了，即使没有学过计算机的的，想必也或多或少的了解汉诺塔问题，这篇文章通过数学的方式来求解这个问题。
汉诺塔
传说: 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
递归
这是一个非常经典的递归问题。 思路很简单： 假设有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格的麦粒，都赏给您的仆人吧！”国王觉得这个要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。
还有直线分割圆形，约瑟夫环问题等等。
写在最后
书到用时方恨少。
