利用函数递归求汉诺塔问题

简介: 利用函数递归求汉诺塔问题

1.汉诺塔问题的由来

       (感谢chatgpt)汉诺塔,又称河内塔,是一种传统的益智玩具和数学问题。据说其起源可以追溯到印度古代传说中的 Brahma 寺庙,从印度传播到东南亚、中国等地区。最早的正式记载出现在 19 世纪末的法国数学家 Edouard Lucas 发表于《科学》杂志上的一篇文章中。

       故事的情节大致是这样的:在 Brahma 所供奉的圆锥形塔庙里,有三根钉子,最初所有的圆盘都串在其中一根钉子上,大的在下,小的在上,形成一个由大到小的递减序列;路过此处的人们想试一下自己的本领,就开始实行“移魂换魄”的任务。用任何一根钉子作为中介,只允许在小盘子上面放大盘子,在三根钉子之间移动。目标是尽快完成把所有圆盘从初始位置移到某个其他钉子上的操作。如果能在数量较少的步骤中完成,則壓力減小,而如果得不出答案则不礼也不会武变態了!

       汉诺塔问题引入后在数学界得到了广泛的关注和研究。除了其本身作为益智游戏之外,汉诺塔问题在计算复杂度、基于规则的机器学习等领域都具有重要的意义。汉诺塔问题也被用来解释人类思维能力中的归纳、递推等抽象概念,成为了教育多尚方宝剑。

画图理解:

 

2.汉诺塔问题的求解(关于移动步数)

图片理解:

 

#include <stdio.h>
//汉诺塔问题(利用函数递归实现)
//函数定义部分
static int count = 1;
int hannuo(int n)
{
  if (n > 1)
  {
    count = count * 2 + 1;
    hannuo(n - 1);
  }
  else
    return count;
  return count;
}
int main()
{
  int n;
  printf("请输入圆盘个数:");
  scanf("%d",&n);
  int step = hannuo(n);
  printf("完成步骤为:%d步\n", step);
  return 0;
}

3.如何打印移动路径

//汉诺塔移动步骤
//定义move函数,来打印路径
void move(char s, char d)
{
  printf("%c -> %c \n", s, d);
}
//pos1:起始位置
//pos2:中转位置
//pos3:终点位置
void hannuo(int n, char pos1, char pos2, char pos3)
{
  if (1 == n)//如果只有一个盘子,直接移动即可
  {
    move(pos1, pos3);
  }
  else//多于一个盘子,用大事化小的思维
  {   
    hannuo(n - 1, pos1, pos3, pos2);//先将最大盘子之上的n-1个盘子经过c,转移到b上
    move(pos1, pos3);//再将最大的盘子转移到c,
    hannuo(n - 1, pos2, pos1, pos3);//最后将b上的n-1个盘子经a的中转转移到c上
  }
}
int main()
{
  int n;
  printf("请输入盘子的个数n:");
  scanf("%d", &n);
  //定义三个盘子分别为'A', 'B', 'C'
  hannuo(n, 'A', 'B', 'C');
  return 0;
}

4.总结:

       汉诺塔问题体现了数学思想中的递归,所谓递归,在笔者看来,就是求解拥有大量重复步骤问题的求解,最重要的思维是“大事化小”,将复杂的问题一步步拆分,化繁为简!

目录
相关文章
|
5月前
|
算法 C语言
汉诺塔问题(函数递归)
汉诺塔问题(函数递归)
42 0
|
6月前
|
Java Python
汉诺塔递归问题,递归思路详解
汉诺塔递归问题,递归思路详解
69 0
|
6月前
递归求解汉诺塔问题(超详解)
递归求解汉诺塔问题(超详解)
汉诺塔 递归问题
汉诺塔 递归问题
79 0
递归问题的实际运用:汉诺塔问题
递归问题的实际运用:汉诺塔问题
102 0
递归问题的实际运用:汉诺塔问题
|
机器学习/深度学习 算法 C语言
函数递归+青蛙跳台阶——“C”
函数递归+青蛙跳台阶——“C”
|
C++ C语言
你是真的“C”——函数递归详解汉诺塔
利用函数递归手把手求解汉诺塔
107 0
你是真的“C”——函数递归详解汉诺塔
|
C语言
你是真的“C”——函数递归详解青蛙跳台阶
手把手教学——函数递归详解汉诺塔+青蛙跳台阶问题
107 0
你是真的“C”——函数递归详解青蛙跳台阶