《Cracking the Coding Interview》——第3章：栈和队列—

《Cracking the Coding Interview》——第3章：栈和队列——题目4

2014-03-18 05:28

题目：你肯定听过汉诺威塔的故事：三个柱子和N个从小到大的盘子。既然每次你只能移动放在顶上的盘子，这不就是栈操作吗？所以，请用三个栈来模拟N级汉诺威塔的玩法。放心，N不会很大的。

解法：递归着玩儿吧，还挺容易写的。要是迭代，我估计够呛。

代码：

  1 // 3.4 Implement Hanoi Tower with three stacks.
  2 #include <cstdio>
  3 #include <stack>
  4 using namespace std;
  5 
  6 class Solution {
  7 public:
  8     void initHanoiTower(int n) {
  9         int i;
 10         
 11         clearHanoiTower();
 12         
 13         for (i = n; i >= 1; --i) {
 14             s[0].push(i);
 15         }
 16     }
 17     
 18     void moveHanoiTower(int n, int from, int to) {
 19         if (from == to) {
 20             return;
 21         }
 22         
 23         if ((int)s[from].size() < n) {
 24             return;
 25         }
 26         
 27         if (n == 1) {
 28             s[to].push(s[from].top());
 29             s[from].pop();
 30             return;
 31         }
 32         
 33         int i;
 34         for (i = 0; i < 3; ++i) {
 35             b[i] = false;
 36         }
 37         b[from] = true;
 38         b[to] = true;
 39         int other;
 40         for (i = 0; i < 3; ++i) {
 41             if (!b[i]) {
 42                 other = i;
 43                 break;
 44             }
 45         }
 46 
 47         moveHanoiTower(n - 1, from, other);
 48         moveHanoiTower(1, from, to);
 49         moveHanoiTower(n - 1, other, to);
 50     }
 51     
 52     void clearHanoiTower() {
 53         int i;
 54         
 55         for (i = 0; i < 3; ++i) {
 56             while (!s[i].empty()) {
 57                 s[i].pop();
 58             }
 59         }
 60     }
 61     
 62     void printHanoiTower() {
 63         stack<int> ss[3];
 64         int i;
 65         
 66         for (i = 0; i < 3; ++i) {
 67             ss[i] = s[i];
 68             printf("Tower %d:", i + 1);
 69             while (!ss[i].empty()) {
 70                 printf(" %d", ss[i].top());
 71                 ss[i].pop();
 72             }
 73             printf("
");
 74         }
 75     }
 76 private:
 77     stack<int> s[3];
 78     int b[3];
 79 };
 80 
 81 int main()
 82 {
 83     int n;
 84     Solution sol;
 85     
 86     while (scanf("%d", &n) == 1 && n > 0) {
 87         sol.initHanoiTower(n);
 88         
 89         printf("At the beginning:
");
 90         sol.printHanoiTower();
 91         printf("
");
 92 
 93         sol.moveHanoiTower(n, 0, 2);
 94         
 95         printf("At the end:
");
 96         sol.printHanoiTower();
 97         printf("
");
 98     }
 99     
100     return 0;
101 }