走进递归经典——汉诺塔问题详解

简介: 问题👏汉诺塔问题是经典的递归问题。汉诺塔问题是一个经典的问题,汉诺塔(Hanoi Tower)又称河内塔,源于印度一个古老传说:大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘,问该如何操作。

image.png

思路👏

首先我们以最原始的模型开始,也就是一根柱子上三个环说起,过程如下:

image.png

而这其中包含了移动一个环和两个环的情况,所以规律总结如下:

通过分析以上 3 种情况的移动思路,可以总结出一个规律:对于 n 个圆盘的汉诺塔问题,移动圆盘的过程是:将起始柱上的 n-1 个圆盘移动到辅助柱上;起始柱上遗留的 1 个圆盘移动到目标柱上;最后将辅助柱上的所有圆盘移动到目标柱上。由此推演出n个环的场景思路就是拆分成 n-1个时的场景,n-2个时的场景……直到 1个环。

image.png

实现👏

递归的核心在于函数自己调用自己,是创建所需的变量,三根柱子,即创建三个字符类型A,B,C和代表次数的整型n;我用 printf函数模拟它的实验结果;在根据我们所需的计算要求自义定函数 Hanoi,接下来就是把我们的计算过程串联进去,加入魔法,注入灵魂。

#include<stdio.h>
void Hanoi(int n, char a, char b, char c)// 初始化自定义函数Hanoi
  {
    if (1 == n)// if语句首先踢出特殊情况环数为1
    {
      printf("Move %d:from %c to %c\n",n,a, b);// 为1时直接a到b
    }
    else
    {
      Hanoi(n - 1, a, b, c);//>1时,先将(n-1)个盘子从a借助b移到c
      printf("Move %d:from %c to%c\n",n, a, b);//将a上第n个移到b
      Hanoi(n - 1, c, a, b);//将c上的(n-1)个盘子从c借助a移到b
    }
  }
  int main()
  {
  int n = 0;//定义环数n
  printf("please input the number of disks:");
  scanf("%d", &n);
  printf("steps of moving the disks=%d\n", n);
  Hanoi(n, 'A', 'B', 'C');
  return 0;

执行结果如下:(这里假设环数为5)

image.png


相关文章
Multi-Agent Orchestrator:亚马逊开源AI智能体自动协作黑科技!重构人机交互逻辑,1秒精准分配任务
Multi-Agent Orchestrator 是亚马逊开源的多智能体框架,能够动态分配代理、维护上下文、支持多种代理类型,适用于客户服务、智能交通、物流配送等复杂场景。
162 9
Multi-Agent Orchestrator:亚马逊开源AI智能体自动协作黑科技!重构人机交互逻辑,1秒精准分配任务
计算机毕设-SpringBoot+VUE高效便捷的云存储平台——百度网盘
计算机毕设-SpringBoot+VUE高效便捷的云存储平台——百度网盘
342 0
Hive SQL on Flink 构建流批一体引擎
阿里巴巴开发工程师罗宇侠&方盛凯,在 Flink Forward Asia 2022 流批一体专场的分享。
19286 3
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等