转载

汉诺塔问题（用栈替代递归）

汉诺塔问题

古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子

，盘子大小不等，大的在下，小的在上（如图）。有一个和尚

想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子

，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘

在上。在移动过程中可以利用B座，要求输出移动的步骤。

汉诺塔问题递归解法

C++代码

 1 //By LYLtim  2 //2015.2.8  3   4 #include <iostream>  5   6 using namespace std;  7   8 void hanoi(int n, char src, char mid, char dst) {  9     if (n == 1) 10         cout << src << "->" << dst << endl; 11     else { 12         hanoi(n-1, src, dst, mid); 13         cout << src << "->" << dst << endl; 14         hanoi(n-1, mid, src, dst); 15     } 16 } 17  18 int main() 19 { 20     int n; 21     cin >> n; 22     hanoi(n, 'A', 'B', 'C'); 23  24 }

以输入3个盘子为例输出

A->C

A->B

A->C

C->B

B->C

B->A

A->C

Java代码

 1 //By LYLtim  2 //2011.11.12  3   4 public class hanoi {  5   6     public static void main(String[] args) {  7         movdDisk(3, 1, 3, 2);  8     }  9  10     static void movdDisk(int n, int start, int end, int mid) { 11         if (n == 1) 12             System.out.println("move disk 1 from post " + start + " to post " + end ); 13         else { 14             movdDisk(n - 1, start, mid, end); 15             System.out.println("move disk " + n + " from post " + start + " to post " + end); 16             movdDisk(n - 1, mid, end, start); 17         } 18     } 19 }

汉诺塔问题非递归解法

汉诺塔问题手工解法(三个盘子）

信封堆，每个信封放一个待解决的问题

汉诺塔问题（用栈替代递归）

后进先出，用栈模拟。

 1 //By LYLtim  2 //2015.2.8  3   4 #include <iostream>  5 #include <stack>  6   7 using namespace std;  8   9 struct Problem 10 { 11     int n; 12     char src, mid, dst; 13     Problem(){} 14     Problem(int n, char s, char m, char d) : n(n), src(s), mid(m), dst(d) {} 15 }; 16  17 int main() 18 { 19     int n; 20     cin >> n; 21     stack<Problem> stk; 22     Problem curPrb; 23     stk.push(Problem(n, 'A', 'B', 'C')); 24     while (!stk.empty()) { 25         curPrb = stk.top(); 26         stk.pop(); 27         if (curPrb.n == 1) 28             cout << curPrb.src << "->" << curPrb.dst << endl; 29         else { 30             stk.push(Problem(curPrb.n-1, curPrb.mid, curPrb.src, curPrb.dst)); 31             cout << curPrb.src << "->" << curPrb.dst << endl; 32             stk.push(Problem(curPrb.n-1, curPrb.src, curPrb.dst, curPrb.mid)); 33         } 34     } 35 }