汉诺塔的确切解

高冷宅小胖妞

大家好，我叫陈墨仙，毕业于西安电子科技大学，就职于网龙天晴在线任务设计部，是一名脚本程序员

（服务器端）。

我似乎发现了汉诺塔的确切解。目前先把猜想发上来，一会儿我将写一个程序来证明。

假设

1
2
3
——  —— ——
1柱子 2柱子3柱子


要把这1到3号从1柱子移到3柱子。

目标柱子：3
本身柱子：1
中间柱子：2

本身柱子上的数量是3。

3mod2=1

所以第一个1号盘子，要移到目标柱子上。

2
3            1
——  —— ——
1柱子 2柱子3柱子

接下来，目标柱子是空的，本身柱子上的数量是2。

2mod2=0

所以本身柱子上，最上面的2号盘，要移到中间柱子上。

3      2     1
——  —— ——
1柱子 2柱子3柱子


接下来，目标柱子和中间柱子都有盘子。本身柱子1上的数量为1。
1mod2=1。
所以目前要把目标柱子上的盘子往中间柱子移。
这时候，
第二层
目标柱子：2
本身柱子：3
中间柱子：1

本身柱子3上的数量为1，
1mod2=1
所以要把3柱子上的1号盘子往目标柱子上移。
       1
3      2     
——  —— ——
1柱子 2柱子3柱子

等到第二层本身柱子3空了，又恢复成

目标柱子：3
本身柱子：1
中间柱子：2

好了，目前本身柱子上的盘子数量为1
1mod2=1。
所以1柱子上的3盘子，要移到目标柱子3上。
       1
       2    3
——  —— ——
1柱子 2柱子3柱子

这时候，本身柱子1空了，目标，本身，中间再次变化。

本身柱子：2
目标柱子：3
中间柱子：1

本身柱子盘子数量2，
2mod2=0
所以2号柱子上的1号盘子，要移到中间柱子上。

      
  1    2    3
——  —— ——
1柱子 2柱子3柱子

本身柱子盘子数量1，
1mod2=1
所以2号柱子上的2号盘子，要移到目标柱子上。
            2
  1         3
——  —— ——
1柱子 2柱子3柱子

本身柱子空了，本身，目标，中间柱子再次变化。

由2->3变为1->3

本身柱子1号柱子的数量为1
1mod2=1
所以，将1号柱子上的1号盘，移到目标柱子上。

            1
            2
  1         3
——  —— ——
1柱子 2柱子3柱子

综上所述，若本身柱子数量对2取模，值为1，则移到目标柱子上，若值为0，则移到中间柱子上。

若本身柱子盘子数为0，则变换目标和本身，中间柱子。

1->3变为2->3

若目标柱子和中间柱子都有盘子，则进入第二层目标，本身，中间柱子。

若第一层本身柱子数量对2取模，值为1，则第二层目标柱子为第一层的中间柱子，第二层本身柱子为第

一层的目标柱子。
若值为0，则反过来。

还有一种更方便的判断方法，即看柱子上的盘子大小来判断目标柱子和本身柱子。

高冷宅小胖妞

排版有点乱……

核心思路就是 本身柱子的数量mod2若为1，则将最上方的盘子移到目标柱子，若为0，则移到中间柱子。

至于本身柱子是哪个，目标柱子是哪个，肉眼可以看出来。但是具体的量化规则，得让我想想。

高冷宅小胖妞

我们现在来看看6个盘子的情况。

1
2
3
4
5
6
——  —— ——
1柱子 2柱子3柱子

用倒推法，要把6个盘子移到3柱子上，则
需要
        1
        2
        3
        4
6       5
——  —— ——
1柱子 2柱子3柱子

             1
             2
             3      
6       5    4
——  —— ——
1柱子 2柱子3柱子

        1
5       2            
6       3     4
——  —— ——
1柱子 2柱子3柱子


4        
5            1      
6       3    2
——  —— ——
1柱子 2柱子3柱子

2
3
4        
5                  
6       1   
——  —— ——
1柱子 2柱子3柱子

也就是说5号盘要移到2号柱子上，4号盘要移到3号柱子上，3号盘2号，2号盘3号，1号盘2号。规律是n号盘，(6-n)mod2,若为1，则中间柱子，2号，若为0，则目标柱子，3号。

而移动的方法，就是我刚才用123个盘子进行移动的方法。

高冷宅小胖妞

:lol不知道我讲清楚没有。

按我说的方法，玩文曲星上的汉诺塔，是可以通关的。（十几年前的游戏了吧！）

:Q:Q

高冷宅小胖妞

怎么获取具体某一步的移法？

还是以6个盘子为例，假设我们想知道3号盘子第二次移动，是从哪移到哪。

首先（6-3）mod2=1，则3号盘子第一次移动应该是中间柱子，2号，即1->2

这个时候，柱子为

4        
5            1      
6       3    2
——  —— ——
1柱子 2柱子3柱子

那么接下来与三号盘无关的移动直到

        1
5       2            
6       3     4
——  —— ——
1柱子 2柱子3柱子

（3-3)mod2=0，即3号盘要移到目标柱子3号柱子。
所以3号盘第二次移动是，2->3。

高冷宅小胖妞

所以1号盘的第一次移动是
(6-1)mod2=1,移到中间位置，1->2
本身柱子与中间柱子互换，目标柱子不变
第二次一定是移到目标位置，2->3
本身柱子与目标柱子互换，中间柱子不变
第三次移到中间位置，3->1
本身柱子与中间柱子互换，目标柱子不变
第四次移到目标位置，1->2



也即是说奇数次，移到中间位置，偶数次移到目标位置。移动之后，本身柱子与中间或目标柱子互换身份。

高冷宅小胖妞

我们再抽象归纳一下。

6个盘子，1号盘的第n次是怎么移动的函数设为（f,k）(n)
f为源位子，k为目标位子。

f(1)=1
f(n)=k(n-1)
k(n)=3-((n mod 3-2)mod 3)

高冷宅小胖妞

编辑掉………………

高冷宅小胖妞

从上面我们可以得知，如果盘号的奇偶性一样的话，那么他们前n次移动的顺序是一样的。

高冷宅小胖妞

从上面我们可以得知，如果盘号的奇偶性一样的话，那么他们前n次移动的顺序是一样的。

所以我们又可以简化为，若总共有偶数个盘子，偶数号盘的第n次是怎么移动的。
或者，若总共有奇数个盘子，奇数号盘的第n次是怎么移动的。

k(n,总共偶数，盘号偶数）= 3-((n mod 3)-1)mod3
k(n,总共偶数，盘号奇数）= 3-((n mod 3)-2)mod3