HannoiTower(汉诺塔)中的神奇之事

耿祥义

     本帖目的，介绍汉诺塔中的神奇之事（也算解开最近困扰自己的问题，去静心练习一首小提琴曲了），然后用非递归方式求解汉诺塔问题。

    假设三个塔的名字是A,B,C，初始时A塔有N个盘子（N>=1）,和尚需按规则（这里不表）把盘子移动到C塔。

一、和二进制的关联

      和尚每次需要移动一个盘子，盘子上都有号码（1至N），那么移动过程中就会形成一个盘号的序列，例如当N=3时，盘号序列是：

[1, 2, 1, 3, 1, 2, 1]

   盘号序列和自然数：1,2,...m（其中m等于2的N+1幂减1）的二进制的尾部连续出现的0的个数有关（偶数的二进制尾部是0，奇数是1），例如：盘号序列

[1, 2, 1, 3, 1, 2, 1]

对应的二进制：

1

10     1  （尾部 1 个 0）

11

100    2  （尾部 2 个 0）

101

110    1  （尾部 1 个 0）

111

1000   3  （尾部 3 个 0）

1001

1010   1  （尾部 1 个 0）

1011

1100   2  （尾部 2 个 0）

1101

1110   1  （尾部 1 个 0）

1111

如图：

而且神奇的是，尾部连续0个的个数，每隔一次，这个数目就是1。也就是说，和尚每隔一次，就要搬动一次1号盘（当然用归纳法也可证明）

二、总次数

    如果是N个盘子，需要移动的次数是2的N幂次减1次，例如3个盘子需要移动7次。

三、1号小盘的规律

   1.第1步和最后一步，和尚一定都是移动1号盘。

   2. 如果N是奇数，"和尚"手里拿着1号盘后，找目标塔的规律是CBA循环的次序。

       如果N是偶数，"和尚"手里拿着1号盘后，找目标塔的规律是BCA循环的次序.

      数学家或算法家也许不曾用过Java，甚至未能等到Java，但却为我们总结了很好的算法(我说的是第一条，第二条和第三条你我都可以发现)，这就是大师。我们只不过用特定的语言语法去描述而已，也许就是仅仅是检验一下自己会不会Java而已。如果不会Java,就用Python，如果啥也不会，您就下载个汉诺塔游戏，然后模仿和尚搬运盘子，体验一下这些算法，为以后学习编程积累经验。 

四、递归与迭代 

    递归的代码优美简练，但有时候非常难以理解。另外，递归，特别是非线性递归，空间复杂度是指数增长的，因为函数的每次递归调用都要占用内存，一直等到递归结束。迭代虽然省内存，但时间复杂度可能增加，因为要有略微的复杂的算法，但空间复杂度会降低。因为每次迭代后，都会释放所占的内存。

    比如，我们忘记了今天是星期几，就必要要知道昨天（不能越过昨天)，那就就需要向前（过去）翻日历，但不能撕掉日历，以便等到能算出今天的星期数（但不用你算，只要翻到有星期的，就自然知道今天的），递归好比一页一页向前翻，使得我们手里的日历越来越厚（这个空间复杂度还是线性的呢），一直翻到公元，知道了是星期几（比如是星期一），然后再一页一页的撕掉日历.此刻，日历上神奇地出现了星期（递归的奥妙），回到今天，知道了是星期几。

    迭代是知道了今天是星期几，需要算出100天以后是星期几？你可以直接算出，也可以一页一算，一页一撕，撕到第100天即可，手里每次只保留一页日历，显然手里节省了日历页，缺点是，算法可能不够简练，你自己要真算算才行。

    掌握递归，可以更好的理解迭代。数学家说过：

神能理解递归，人能理解迭代。

五、代码（迭代算法）及运行效果

DishSequence.java  返回盘号的序列，您可以学习怎样快速得到二进制，以及String的chatAt()方法。

public class DishSequence{  // 盘子号码组成序列

    public static int [] getStep(int N) {

        int step[] = new int[(int)Math.pow(2,N)-1];

        for(int i=1,m=0;i<=(int)Math.pow(2,N+1)-1;i++) {

            if(i%2==0){//偶数的二进制的尾部是0，奇数是1

                 String strBinaryDigit = Integer.toBinaryString(i);

                 int size = strBinaryDigit.length();

                 int zeroCounts =0;

                 for(int k =size-1;k>=0;k--) {

                    if(strBinaryDigit.charAt(k)=='0'){

                       zeroCounts++; 

                    }

                    else {

                       break;

                    }

                 }

                 step[m] =  zeroCounts;

                 m++;

             }

         }

         return step;

    }

 }

Tower.java      学习使用Stack类的实例

import java.util.Stack;

public class Tower extends Stack<Integer>{

    public String name;

    byte weight ;        //权重

    int N;               //盘子数目 

    public Tower(String name,int N) {

        this.name = name;

        this.N =N;

    }

    public int getWeight(){

        if(!empty())

            return peek();

        else

            return N+1;

    }

}

HannoiTower    学习综合地描述问题，学习使用Stack类Deque类的实例，即栈和队列来描述问题。

import java.util.*;

public class HannoiTower {

    Tower towerA,   //汉诺塔中的三个塔

          towerB,   

          towerC; 

    int N = 3;       //汉诺塔问题中的盘子数目

    Deque<Tower> deque;    //队列，存放小盘的目标塔的规律

    int step[];   //存放每步需要移动的盘子的盘号

    public HannoiTower(int N){

        this.N = N;

        towerA = new Tower("A",N);

        towerB = new Tower("B",N);

        towerC = new Tower("C",N);

        step = DishSequence.getStep(N);//存放需要移动的盘子号码 

        deque = new ArrayDeque<Tower>(); 

        if(N%2!=0) { //CBA入列

           deque.add(towerC);

           deque.add(towerB);

           deque.add(towerA);

        }

        else {

           deque.add(towerB);

           deque.add(towerC);

           deque.add(towerA);

        }

        init();

    }

    private void init(){ //初始状态，A塔N个盘子

        for(int i=N;i>=1;i--) {

            //初始状态，A塔有N个盘子

            towerA.push(i); 

        }

    }

    public void startMoveDish(){

        for(int i=0;i<step.length;i++){

           moveDish(step[i]);

        }

    }

    private void moveDish(int m){

         Tower tower = null;

         if(towerA.getWeight() == m) {

            tower = towerA;

         }

         else if(towerB.getWeight() == m){

            tower = towerB;

         }

         else if(towerC.getWeight() == m){

            tower = towerC;

         } 

         String name = tower.name;

         if(m==1){

             Tower target =deque.pollFirst();  //出列目标塔

             target.push(tower.pop()); 

             System.out.printf("移动%d从%s到%s\n",m,tower.name,target.name);

             deque.offerLast(target);         //重新入列 

         }

         else { //不是1号小盘只能有下列一种可能：

            if(towerC.getWeight()-m>0&&tower!=towerC){

                towerC.push(tower.pop());

                System.out.printf("移动%d从%s到%s\n",m,tower.name,towerC.name);

            }

            else if(towerB.getWeight()-m>0&&tower!=towerB){

                towerB.push(tower.pop());

                System.out.printf("移动%d从%s到%s\n",m,tower.name,towerB.name);

            }

            else if(towerA.getWeight()-m>0&&tower!=towerA){

                towerA.push(tower.pop());

                System.out.printf("移动%d从%s到%s\n",m,tower.name,towerA.name);

            }

         }

    }

}

App.java       主类，检验程序运行情况

import java.util.Arrays;

public class App {

    public static void main(String args[]){

        int N = 4;

        int step[] = DishSequence.getStep(N);

        System.out.println(Arrays.toString(step));

        HannoiTower hannoiTower = new HannoiTower(N);

        hannoiTower.startMoveDish();

        System.out.println("和递归算法比较:");

        AAA.hannoi(N,'A','B','C');

    }

}

AAA.java   经典的递归算法

public class AAA {

    public static void hannoi(int N,char A,char B,char C){

         if(N==1) {

             System.out.printf("移动%d从%c到%c\n",N,A,C);

         }

         else {

             hannoi(N-1,A,C,B);

             System.out.printf("移动%d从%c到%c\n",N,A,C);

             hannoi(N-1,B,A,C);

         }   

    }

} 

推荐阅读