二儿八月 / 代码 / 汉诺诺.c

分享

   

汉诺诺.c

2020-05-01  二儿八月

递归调用的简单使用。

我们假设我们的初始问题是:有三个盘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;
}

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>