【C语言】汉诺塔问题

浏览数：21 / 时间：2015年06月08日

之前遇见这个问题，非常费劲地理解了，并写出代码，然后过段时间，再遇见这个问题，又卡住了，如此反反复复两三次，才发现自己对递归的理解依然很肤浅。今天无聊，重温《算法：c语言实现》一书，又遇见了这个问题，心头一紧，担心要费些时间才能写出代码，没想到的是，再理解了书中对递归的定义，蒙住源代码动手写，发现很快就写出来了，甚至都没有费力去模拟整个汉诺塔移动过程，只是根据递归的要领（数学归纳法）分析了一下问题，便得出了一个递归形式，照此写代码，竟然没错。由此也醒悟到，很多时候，用递归写代码并不难，但却常常受困于一种恐惧和自惭的心理而畏葸不前。

下面是源代码，在此之前，阐述一下自己对递归的理解，“对于我们编写的每个递归函数，都必须能够进行有效的归纳证明。”这是《算法：c语言实现》中让我恍然大悟的一句话。这句话的意思是：根据数学归纳的形式，总是能够倒推出完整的递归形式的。数学归纳法的形式非常清晰，其过程通常为先试验初始条件n=1，验证某假设或公理是否成立，再设n=k，假设成立，由n=k推出n=k+1的时候，该假设是否成立。具体分析汉诺塔问题，其最原始的思想是：”从某根桩移动N个盘子到后边桩上，接着以此类推，移动剩下N-1个盘（放在第N个盘上）。“

#include <stdio.h>
#include <stdlib.h>
 
#define ALL  6
enum 
DIRECT{left = 1, mid = 2, right = 3};
void 
hanoi(int 
N, int 
pos, int 
dst);
void 
shift(int 
N, int 
pos, int 
direct);
 
 
int 
main()
{
        hanoi(4,  left,  mid);
        return 
0;
}
 
 
void 
hanoi(int 
N,  int 
pos, int 
dst)
{
        if( 0 == N) return 
;
        hanoi(N-1, pos, ALL-dst-pos);
        shift(N, pos, dst);
        hanoi(N-1, ALL-dst-pos, dst);
 
}
 
void 
shift(int 
N, int 
pos, int 
direct)
{
        printf("move %d from pillar %d to pillar %d\n", N, pos, direct);
}