汉诺诺.c

递归调用的简单使用。

我们假设我们的初始问题是：有三个盘1、2、3，三个杆A、B、C，将所有盘从A移到C：

此处输入图片的描述

那么我们的解决思路：

1. 将盘1和盘2移动到B杆：

   

   此处输入图片的描述

2. 将盘3移动到C杆：

   

   此处输入图片的描述

3. 将盘1和盘2移动到C杆：

   

   此处输入图片的描述

在这个解决过程中，可以看到我们将汉诺塔问题分解成了规模更小但形式相同的子问题：

1. 将盘1和盘2移动到B杆时，我们可以看成是这样一个汉诺塔问题，有两个盘1、2，三个杆A、B、C，需要将所有盘从A杆移动到B杆，我们只需将B杆和C杆的名字换一下就变成了跟我们的初始问题形式一样的但规模跟小的问题了：

   

   此处输入图片的描述

2. 将盘3移动到C杆，我们可以看成这样一个汉诺塔问题，只有一个盘3，三个杆A、B、C，需要将盘3从A杆移动到C杆：

   

   此处输入图片的描述

3. 将盘1和盘2移动到C杆时，我们可以看成是这样一个汉诺塔问题，有两个盘1、2，三个杆A、B、C，需要将所有盘从B杆移动到C杆，我们只需将A杆和B杆的名字换一下就变成了跟我们的初始问题形式一样的但规模跟小的问题了：

   

   此处输入图片的描述

将上述思路整理成伪代码：

// n个盘，盘符由小到大为1——>N, 从A杆移动到C杆
void hanoi(n个盘，A杆， B杆，C杆)
{
   // 解决子问题一
   hanoi(n-1个盘，A杆，C杆，B杆)；
   // 解决子问题二
   hanoi(1个盘，A杆，B杆，C杆)；
   // 解决子问题三
   hanoi(n-1个盘，B杆，A杆，C杆);
}

加入基准情况，我们的汉诺塔函数实现如下：

// 汉诺塔函数，递归方式
// n个盘，n个盘，盘符由小到大为1——>N, 从A杆移动到C杆
// disk 为最大盘的盘符
void hanoi(int n, int disk, char A, char B, char C)
{
     // 基准情况
     if (1 == n) {
         move_single_disk(disk ,A, C);
     } else {
         // 解决子问题一
         hanoi(n-1, disk-1, A, C, B);
         // 解决子问题二
         hanoi(1, disk, A, B, C);
         // 解决子问题三
         hanoi(n-1, disk-1, B, A, C);
     }
}

完整代码(hanoi.c)：

/*
* file name : hanoi.c
*/
#include <stdio.h>

// 移动一个盘
// disk为需要移动的盘符，src为源杆，dest为目标杆
void move_single_disk(int disk, char src, char dest)
{
    static step = 1;
    fprintf(stdout, "step%d: disk%d %c --> %c\n", step++,disk,src,dest);    
}
// 汉诺塔函数，递归方式
// n个盘，n个盘，盘符由小到大为1——>N, 从A杆移动到C杆
// disk 为最大盘的盘符
void hanoi(int n, int disk, char A, char B, char C)
{
     // 基准情况
     if (1 == n) {
         move_single_disk(disk ,A, C);
     } else {
         // 解决子问题一
         hanoi(n-1, disk-1, A, C, B);
         // 解决子问题二
         hanoi(1, disk, A, B, C);
         // 解决子问题三
         hanoi(n-1, disk-1, B, A, C);
     }
}

int main(int argc, char *argv[])
{
    int n = atoi(argv[1]);
    fprintf(stdout, "=======hanoi(%d):\n", n);
    hanoi(n, n, 'A', 'B', 'C');
    fprintf(stdout, "=======hanoi finished\n");
    return 0;
}