递归和汉诺塔问题~!!!!!

fanxiaobao

昨天下午看了甲鱼兄递归解决汉诺塔问题的视频后,至今大脑还在一个死循环跳不出来怎么办?求大神帮忙啊,好痛苦,夜不能寐啊...............

谭斌谭斌

贴出代码，不然谁知道你的问题是什么

仰望天上的光

这个本质上说不是C语言本身的问题，而在于原先你是否能看懂数学定义，很多数学上的定义，如费泼拉契数列都不直接描述如何得到该数列的，而是通过递归的方式定义问题。而C语言的递归仅仅是提供了一种类似的方式而已。

fishc_hz

贴代码           

fanxiaobao

经过这两天的无限循环终于找到出口了,并且做了一个数组版的过程演示和简单的步骤提示,需要的新手可以看一下,老鸟可以飘过.....
网盘:http://pan.baidu.com/s/1sjHE4Cd

andalousie

用堆栈吧

1. #include <iostream>
   
2. #include <cstdlib>
   
3. #include <limits>
   
4. using namespace std;
   
5. 
   
6. #define STYPE int
   
7. 
   
8. #define        EMPTY    -2
   
9. #define        FULL     -1
   
10. #define        PUSH_OK   1
    
11. #define        CAPACITY  32767
    
12. 
    
13. class Stack {
    
14.     int top;
    
15.     STYPE element [CAPACITY];
    
16. public:
    
17.     Stack ();
    
18.     ~Stack ();
    
19.     int num (void);
    
20.     int push (STYPE new_elem);
    
21.     STYPE pop (void);
    
22.     STYPE snoop (void);
    
23. };
    
24. 
    
25. Stack::Stack (void)
    
26. {
    
27.     top = -1;
    
28.     for (int i=0; i<CAPACITY; i++)
    
29.         element[i] = 0;
    
30. }
    
31. 
    
32. Stack::~Stack (void)
    
33. {
    
34.     // nothing
    
35. }
    
36. 
    
37. int Stack::num (void)
    
38. {
    
39.     return (top + 1);
    
40. }
    
41. 
    
42. STYPE Stack::pop (void)
    
43. {
    
44.     STYPE x;
    
45.     if (top >= 0) {
    
46.         x = element[top];
    
47.         element[top] = 0;
    
48.         top--;
    
49.         return x;
    
50.   } else
    
51.       return EMPTY;
    
52. }
    
53. 
    
54. STYPE Stack::snoop (void)
    
55. {
    
56.     if (top >= 0)
    
57.         return element[top];
    
58.     else
    
59.         return EMPTY;
    
60. }
    
61. 
    
62. int Stack::push (STYPE new_elem)
    
63. {
    
64.     if (top < CAPACITY - 1) {
    
65.         top++;
    
66.         element[top] = new_elem;
    
67.         return PUSH_OK;
    
68.     } else
    
69.         return FULL;
    
70. }
    
71. 
    
72. int main (int argc, char **argv)
    
73. {
    
74.     STYPE N, _N, _P, _T, _F, _R;
    
75. 
    
76.     if (argc != 2) {
    
77.         cerr << "usage: " << argv[0] << " N\n";
    
78.         exit(1);
    
79.     }
    
80. 
    
81.     N = (STYPE)strtol(argv[1], (char **)NULL, 10);
    
82. 
    
83.     /* a bit of error checking, LONG_XXX should be there in limits.h */
    
84.     if (N == LONG_MIN || N == LONG_MAX || N <= 0) {
    
85.         cerr << "illegal value for number of disks\n";
    
86.         exit(2);
    
87.     }
    
88. 
    
89.     Stack s;
    
90.     s.push(N);
    
91.     s.push(1);
    
92.     s.push(3);
    
93.     s.push(0);
    
94. 
    
95.     while (s.num() != 0) {
    
96.         _P = s.pop();
    
97.         _T = s.pop();
    
98.         _F = s.pop();
    
99.         _N = s.pop();
    
100.         _R = 6 - _F - _T;
     
101.         if (_P == 0) {
     
102.             if (_N == 1)
     
103.             cout << "move " << _F << " --> " << _T << "\n";
     
104.             else {
     
105.                 s.push(_N);
     
106.                 s.push(_F);
     
107.                 s.push(_T);
     
108.                 s.push(1);
     
109.                 s.push(_N-1);
     
110.                 s.push(_F);
     
111.                 s.push(_R);
     
112.                 s.push(0);
     
113.             }
     
114.         } else {
     
115.             cout << "move " << _F << " --> " << _T << "\n";
     
116.             s.push(_N-1);
     
117.             s.push(_R);
     
118.             s.push(_T);
     
119.             s.push(0);
     
120.         }
     
121.     }
     
122. }

复制代码

fanxiaobao

andalousie 发表于 2014-1-26 10:22

                               
登录/注册后可看大图

用堆栈吧

堆栈虽然我还看不懂,但还是感谢你这么长的代码!!