汉诺塔明

摘要：汉诺塔大家都知道怎么玩，就是n个圆盘从柱子A移到柱子C。在移动过程中，小盘一定要在大盘上面，所以用到起中转作用的柱子B。下面的代码中有三个解法，一个是递归的，另两个是非递归的。

稍微讲一下非递归的：

方法一、是由一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。
        首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。
        （1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
        （2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
        （3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。

方法二、通过二叉树

先看图，借用了凌云壮志文章汉诺塔与二叉树的图如下：

中序遍历这棵树就得到汉诺塔的操作过程：

1:one->three; => 2:one->two; => 1:three->two; => 3:one->three; =>1:two->one; => 2:two->three; => 1:one->three

View Code

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 
  6 namespace Hanoi
  7 {
  8     struct Disk
  9     {
 10         public const int MAX = 64;
 11 
 12         int top; //栈顶，用来最上面的圆盘
 13         char name; //柱子的名字，可以是A，B，C中的一个
 14 
 15         int[] s; //柱子上的圆盘存储情况
 16 
 17         public int[] S
 18         {
 19             get
 20             {
 21                 //初始化
 22                 if (s == null)
 23                     s = new int[MAX];
 24                 return s;
 25             }
 26             set
 27             {               
 28                 s = value;
 29             }
 30         }
 31 
 32         public int Top
 33         {
 34             get { return top; }
 35             set { top = value; }
 36         }
 37 
 38         public char Name
 39         {
 40             get { return name; }
 41             set { name = value; }
 42         }
 43 
 44         public bool IsEmpty()
 45         {
 46             return top == -1;
 47         }
 48         public int Peek()//取栈顶元素
 49         {            
 50             return s[top];
 51         }
 52         public int Pop()//出栈
 53         {
 54             return s[top--];
 55         }
 56         public void Push(int x)//入栈
 57         {
 58             s[++top] = x;
 59         }
 60     }
 61 
 62     class Node
 63     {
 64         int number;
 65         char first;
 66         char second;
 67         char third;
 68 
 69         public int Number
 70         {
 71             get { return number; }
 72             set { number = value; }
 73         }
 74         internal char First
 75         {
 76             get { return first; }
 77             set { first = value; }
 78         }
 79         internal char Second
 80         {
 81             get { return second; }
 82             set { second = value; }
 83         }
 84         internal char Third
 85         {
 86             get { return third; }
 87             set { third = value; }
 88         }
 89 
 90         public Node GetLeft()
 91         {
 92             if (number == 1)
 93                 return null;
 94             Node node = new Node();
 95             node.number=this.number-1;
 96             node.first = this.first;
 97             node.second = this.third;
 98             node.third = this.second;
 99             return node;
100         }
101         public Node GetRight()
102         {
103             if (number == 1)
104                 return null;
105             Node node = new Node();
106             node.number = this.number - 1;
107             node.first = this.second;
108             node.second = this.first;
109             node.third = this.third;
110             return node;
111         }
112     }    
113 
114     class Program
115     {
116         static void Main(string[] args)
117         {
118             Console.WriteLine("递归实现");
119             Hannoi(4, 'A', 'B', 'C');
120 
121             Console.WriteLine("非递归实现1");
122             int n = 4;
123             Disk[] ta = Creat(n); //给结构数组设置初值 
124             long max = Pow(2, n) - 1;//移动的次数应等于2^n - 1
125             Hannuota(ta, max);//移动汉诺塔的主要函数 
126 
127             Console.WriteLine("非递归实现2");
128             Hanoi(4, 'A', 'B', 'C');
129             Console.Read();
130         }
131 
132         #region 递归实现
133         static void Hannoi(int n, char a, char b, char c)
134         {
135             if (n == 1)
136                 Move(1, a, c);
137             else
138             {
139                 Hannoi(n - 1, a, c, b);
140                 Move(n, a, c);
141                 Hannoi(n - 1, b, a, c);
142             }
143         }
144         static void Move(int n, char x, char y)
145         {
146             Console.WriteLine("Move disk {0} from {1} to {2}", n, x, y);
147         }
148         #endregion
149 
150         #region 非递归实现1
151         static Disk[] Creat(int n)
152         {
153             Disk[] ta = new Disk[3];
154             ta[0].Name = 'A';
155             ta[0].Top = n - 1;
156             //把所有的圆盘按从大到小的顺序放在柱子A上
157             for (int i = 0; i < n; i++)
158             {
159                 ta[0].S[i] = n - i;
160             }
161             //柱子B，C上开始没有没有圆盘
162             ta[1].Top = ta[2].Top = -1;
163             for (int i = 0; i < n; i++)
164                 ta[1].S[i] = ta[2].S[i] = 0;
165             //若n为偶数，按顺时针方向依次摆放 A B C
166             if (n % 2 == 0)
167             {
168                 ta[1].Name = 'B';
169                 ta[2].Name = 'C';
170             }
171             else  //若n为奇数，按顺时针方向依次摆放 A C B
172             {
173                 ta[1].Name = 'C';
174                 ta[2].Name = 'B';
175             }
176             return ta;
177         }
178 
179         static long Pow(int x, int y)
180         {
181             long sum = 1;
182             for (int i = 0; i < y; i++)
183                 sum *= x;
184 
185             return sum;
186         }
187 
188         /// <summary>
189         /// 算法介绍：首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1。
190         /// 一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。
191         /// 首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。
192         /// （1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
193         /// （2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
194         /// （3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
195         /// </summary>
196         /// <param name="ta"></param>
197         /// <param name="max"></param>
198         static void Hannuota(Disk[] ta, long max)
199         {
200             Console.WriteLine("累计移动次数：{0}", max);
201             int k = 0; //累计移动的次数
202             int i = 0;
203             int ch;
204             while (k < max)
205             {
206                 //按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
207                 ch = ta[i % 3].Pop();
208                 ta[(i + 1) % 3].Push(ch);
209                 ++k;
210                 Console.WriteLine("Move dish {0} from {1} to {2}", ch, ta[i % 3].Name, ta[(i + 1) % 3].Name);
211 
212                 i++;
213                 //把另外两根柱子上可以移动的圆盘移动到新的柱子上
214                 if (k < max)
215                 {         //把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
216                     if (ta[(i + 1) % 3].IsEmpty() ||
217                         !ta[(i - 1) % 3].IsEmpty() &&
218                         ta[(i + 1) % 3].Peek() > ta[(i - 1) % 3].Peek())
219                     {
220                         ch = ta[(i - 1) % 3].Pop();
221                         ta[(i + 1) % 3].Push(ch);
222                         ++k;
223                         Console.WriteLine("Move dish {0} from {1} to {2}", ch, ta[(i - 1) % 3].Name, ta[(i + 1) % 3].Name);
224                     }
225                     else
226                     {
227                         ch = ta[(i + 1) % 3].Pop();
228                         ta[(i - 1) % 3].Push(ch);
229                         ++k;
230                         Console.WriteLine("Move dish {0} from {1} to {2}", ch, ta[(i + 1) % 3].Name, ta[(i - 1) % 3].Name);
231                     }
232                 }
233             }
234         }
235         #endregion
236 
237         #region 非递归实现2
238         static void Hanoi(int n,char a,char b,char c)
239         {
240             Stack<Node> s = new Stack<Node>();
241             Node p=new Node();
242             p.Number = n;
243             p.First = a;
244             p.Second = b;
245             p.Third = c;
246             int i = 0;
247             while (p != null || s.Count != 0)
248             {
249                 while (p != null)
250                 {
251                     s.Push(p);
252                     p = p.GetLeft();
253                 }
254                 if (s.Count != 0)
255                 {
256                     p = s.Pop();
257                     i++;
258                     Console.WriteLine("Move disk {0} from {1} to {2}", p.Number.ToString(), p.First.ToString(), p.Third.ToString());
259                     p = p.GetRight();
260                 }
261             }
262             Console.WriteLine("累计移动次数：{0}", i);
263         }
264         #endregion
265     }
266 }

网上找到汉诺塔操作可视化界面 http://figue.zdbit.com/cxzp.asp 。

Java递归简单实现

//汉诺塔
public class HanoiTest {
    public static void hanoi(int n, char A,char B,char C)
    {
        //何时结束，n=1（最后一块）
        if(n==1)
        {
            move(A,C);
            return;
        }
        //把n-1个从A->B
        hanoi(n-1,A,C,B);
        //最后1个充A->C
        move(A,C);
        //把n-1个从B->C
        hanoi(n-1,B,A,C);
    }

    public static void move(char point1,char point2)
    {
        System.out.println(String.format("%c -> %c",point1,point2));
    }

    public static void main(String[] args)
    {
        hanoi(3,'A','B','C');
    }
}

View Code

汉诺塔 明

汉诺塔明