首页 > 代码库 > 【C语言】汉诺塔问题

【C语言】汉诺塔问题

2024-07-04 09:15:21   219人阅读

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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);
}

　众所周知，“递归程序总是可以转换成执行相同计算的非递归性程序。” 递归到非递归的转换，由堆栈来实现，此处不再赘述，感兴趣的可以看看这个网站：http://hawstein.com/posts/3.4.html

 


联系
我们