汉诺塔问题的简易理解

15195775117

如果汉诺塔只有3层，显然容易移动
现在图中有8层，将4-8层视为底座的一部分，即不动的，1-3层则可以移动到中间，这时4可以移动到右边，这时，左边的5-8和右边的4都视为固定的，则中间的1-3可以移动到右边，这时我们发现，已经顺利地把1-4移到右边了，而5-8从未动过。
可见，1-4层的塔可以在3个位置自由移动，虽然移动的过程很复杂
这时，我们把1-4塔移动到中间，5盘移到右边，再把1-4塔压在5盘之上，这样就实现了1-5塔的右移。所以，6-7层不动时，1-5塔可以在3个位置随意挪动。
按此规律，可以移动任意层的塔。

Eegle

你这是在学python的问题吗

15195775117

Eegle 发表于 2018-5-8 10:56
你这是在学python的问题吗

算法是独立于语言的

15195775117

汉诺塔移动次数递推公式：
如果左边有n+1个盘子，那么先要将上面n个盘子挪到中间位置，再把底盘放右边，然后把中间的塔压右边，设n个盘子的整体移动需要的移动次数是f(n)，那么这次搬动的移动次数，即f(n+1)=2*f(n)+1
这是个求数列通项公式的典型题目：
变形：
f(n+1)+1=2*f(n)+1+1=2*(f(n)+1)
设g(n)=f(n)+1，则g(n+1)=2*g(n)，显然g(n)是个公比为2的等比数列，且g(1)=f(1)+1=2
......
结果为f(n)=2^n-1
可见汉诺塔问题跟象棋格子放稻子有一拼，阿三的数学有一套！