汉诺塔的问题

参考: http://baike.baidu.com/view/191666.htm?fr=aladdin

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定: 在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

 

假设圆盘数量n

n=1,Move(n)A---->C;

n>1时,

Move(n-1)A--->B,　　　　//将n-1个盘由A移至B

Move(n)A--->C,　　　　　//将第n个盘由A移至C

Move(n-1)B--->C;　　　　//将n-1个盘由B移至C

即

H⑴ = 1

H(n) = 2*H(n-1）+1

===>H(n)=2^n-1

C# 代码

        static int i;       //步骤统计

        
        static void Move (int x, string source, string target)        //移动过程
        {
            i++;
            Console.WriteLine ("Step {3} : {0} From {1} ---> {2}", x, source, target,i);
        }

        /// <summary>
        /// 核心算法部分
        /// </summary>
        /// <param name="x">圆盘数</param>
        /// <param name="source">起始圆柱</param>
        /// <param name="temp">中转圆柱(临时圆柱)</param>
        /// <param name="target">目标圆柱</param>
        static void Hanno (int x, string source, string temp, string target)     //核心
        {
            if ( x == 1 )          
            {
                Move (x, source, target);                //仅有一个时直接将source移至target
            }
            else                              
            {
                Hanno (x - 1, source, target, temp);        //将n-1个移至临时圆柱(temp)           
                Move (x, source, target);                   //将第 source 个从A移到 target
                Hanno (x - 1, temp, source, target);        //将第n-1个从 temp 移至 target
            }

        }

        static void Main (string[] args)
        {
            Hanno (4, "A", "B", "C");

            Console.ReadKey ();
        }