C语言----汉诺塔问题----小白的试探与复盘

标签: c语言

C语言—汉诺塔----小白的试探与复盘

问题:
汉诺塔问题是一个著名的问题,初始模型如图所示。其来源据说是在约19世纪末欧洲的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆自上而下、由小到大顺序串着64个圆盘构成的塔,游戏的目的是将最左边A杆上的圆盘,借助最右边的C杆,全部移动到中间的B杆上,条件是一次仅能移动一个盘,且不允许大盘放在小盘的上面。
在这里插入图片描述
第一步:
把n-1个木块,从A移动到B;
把第N个木块,从A移动到C;
第二部:
把n-1个木块,从B移动到C(与从A移动到B其实是一样的,只不过是换了个杆子)
借鉴通过阅读各位前辈的总结,递归的步骤可以分为大致下面三个步骤
一.明确这个函数的木器
二.寻找函数的终止条件(结束函数调用,防止死循环)
三.寻找递归结束条件

参考文章:《为什么你学不会递归?告别递归,谈谈我的一些经验》
在本篇文章中,作者告诉我们,不要试图在脑海中将大型递归的执行过程全部模拟,这是不现实的。
因此,也就有了我们解树形递归题的三部曲:

找整个递归的终止条件:递归应该在什么时候结束?
找返回值:应该给上一级返回什么信息?
本级递归应该做什么:在这一级递归中,应该完成什么任务?

参考文章:《三道题彻底搞定:套路口二觉递归问题》

代码实现:

# include <stdio.h>
int cnt = 0;
void move(int id,char from ,char to)
{
  printf("step%d:move %d from %c-------------->%c\n",++cnt,id,from,to);
}
void hannota(int n,char string_1,char string_2,char string_3)//函数目的:完成移动
  {
  if(n=0)
    return ;//寻找终止条件,终止条件一定要在递归调用的上面以防止递归不遇到终止条件而无限调用。
   hannota(n-1,x,z,y);//等价第一步:将n-1个块移动到另一个杆子
   move(n,x,y,z);//将n移动到目标杆子
   hannota(n-1,y,z,x);//将n-1杆子移动回去
  }
  int main (void)
  {
  int n;
  cnt =0;
  scanf("%d",&n);
  hannota(n,a,b,c);
  return 0;
  }

利用后面的函数等价条件(类似于第n部等于前一步加上几个动作完成)逐渐缩小n的范围,对结束条件进行逼近。
数学归纳法:(1)证明n=1时成立
(2)假设n时成立
(3)证明n+1成立
递归:(1)结束条件
(2)假设第n-1个问题已经被解决了(在头脑中假设,所以我们并不用管2-(n-1)项,因为他们执行完了)
(3)第n个问题和第n-1个问题建立一个关系。

版权声明:本文为mstcoder原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/mstcoder/article/details/109396182