终于理解汉诺塔

木子李工

1. /*
   
2. * 总体思路：
   
3. * 1.只考虑最后一步和上一步，其他的套壳来用
   
4. * 2.假如只有一层，那一定是x-》y
   
5. * 3.假如有两层，那么就是先x-》tmp，然后x-》y，再tmp-》y
   
6. * 4.假如有更多层，思路其实就是
   
7. * 5.首先将n-1曾看作一个整体，移动到tmp
   
8. * 6.然后将最底层移动到y
   
9. * 7.再然后将存放在tmp上的移动到y
   
10. * 8.tmp可以不用，例如只有一层
    
11. */
    
12. int cnt = 0;
    
13. void hano(int n, char x, char tmp, char y){
    
14. 
    
15. 
    
16.         if(n==1){
    
17.                 printf("\r\n 1.(%03d) %c ->> %c", cnt++, x, y);        //最后一层，将x直接移动到y
    
18.         }else{
    
19.                 hano(n-1, x, y, tmp);                                //先将除了最下面的一层移动到tmp上
    
20.                 printf("\r\n 2.(%03d) %c ->> %c", cnt++, x, y);        //然后将最下面的移动到y
    
21.                 hano(n-1, tmp, x, y);                                //再将刚刚移动到tmp上的移动到y上
    
22.         }
    
23. }
    
24. 
    
25. 
    
26. void main(void){
    
27.         int n;
    
28.         printf("\r\n please input hano num:");
    
29.         scanf("%d", &n);
    
30.         hano(n, 'x', 't', 'y');       
    
31. }

复制代码

参考资料：
1.如何理解汉诺塔的递归？ - IT边界的回答 - 知乎
2.如何理解汉诺塔的递归？ - Fireman A的回答 - 知乎

木子李工

http://www.hannuota.cn/