摘要：汉诺塔大家都知道怎么玩，就是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 Program115 {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 - 1125 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 else138 {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 #endregion149 150 #region 非递归实现1151 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 C166 if (n % 2 == 0)167 {168 ta[1].Name = 'B';169 ta[2].Name = 'C';170 }171 else //若n为奇数，按顺时针方向依次摆放 A C B172 {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 /// 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 /// 196 /// 197 /// 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 else226 {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 #endregion236 237 #region 非递归实现2238 static void Hanoi(int n,char a,char b,char c)239 {240 Stack s = new Stack ();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 #endregion265 }266 } 网上找到汉诺塔操作可视化界面 。
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'); }}