函数的递归调用举例之汉诺塔问题模型

简介: 汉诺塔(Tower of Hanoi)问题模型

前言:

●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教!

正文

汉诺塔(Tower of Hanoi)问题模型:

假设有n个盘子,大盘在下,小盘在上。要求将所有盘子由A杆移动到C杆,可以借助B杆,但移动时必须满足以下要求:

(1)每次只能移动1个盘子;

(2)移动过程中,每个杆上的盘子必须保证大盘在下,小盘在上

image.gif编辑              image.gif编辑

汉诺塔玩具模型                                                    由4个圆盘构成的汉诺塔移动步骤

由3个盘子移动图解:

image.gif编辑

image.gif编辑

image.gif编辑

image.gif编辑

 综合可得到移动3个盘子的步骤为: ① A→C,A→B,C→B, ② A→C, ③ B→A,B→C,A→C。 共经历7步。

由此可推出: 移动n个盘子要经历(2n-1)步。

先分析A杆上3个盘子移到C杆上的过程:

① 将A杆上2个盘子移到B杆上(借助C杆)。

② 将A杆上1个盘子移到C杆上。

③ 将B杆上2个盘子移到C杆上(借助A杆)。 其中②可直接实现。①可递归分解为: 将A杆上1个盘子从A杆移到C杆; 将A杆上1个盘子从A杆移到B杆; 将C杆上1个盘子从C杆移到B杆。 第③步可以分解为: 将B杆上1个盘子从B杆移到A杆上; 将B杆上1个盘子从B杆移到C杆上; 将A杆上1个盘子从A杆移到C杆上。

分析可得:n个盘子(n>1)时,若将其从A杆上移至C杆上,需要借助B杆,可以分三步:

(1)将A最上面的n-1个盘子借助C移到B上,即Hn-1次;

(2)将A最下面的一个盘子移到C上,一次就好;

(3)将B上面的n-1个盘子借助A移到C上,即Hn-1次。        

很显然,汉诺塔问题是一个递归问题,可以编写递归函数来实现。

当n>1时,移动盘子的递归过程就是上述三个步骤;递归终止条件就是当n=1时,直接将盘子从A杆移至C杆即可。

汉诺塔问题程序如下:
#include <stdio.h>
void  main()
{ int nd;
  void hanoi(int,char,char,char); 
  printf("input the number of disks:");
  scanf("%d",&nd);
  printf("the step to moving %2d disks:\n",nd);
  hanoi(nd,'A','B','C'); 
}
void hanoi(int n,char a,char b,char c)
{ if(n==1)
    printf("%c-->%c\n",a,c); 
  else
  { hanoi(n-1,a,c,b);     
    printf("%c-->%c\n",a,c); 
    hanoi(n-1,b,a,c); 
  }
}

image.gif

运行结果:

image.gif编辑

注:函数的功能是按要求移动盘子,无需返回值,是void类型。函数的参数有4个,一个是盘子数n,另外三个是代表盘杆的字符变量a,b和c。

●由于作者水平有限,文章难免存在谬误之处,敬请读者斧正,俚语成篇,恳望指教!

相关文章
|
8月前
|
机器学习/深度学习 C语言
函数递归与迭代附n的阶乘+顺序打印一个整数的每一位数+求第n个斐波那契数
函数递归与迭代附n的阶乘+顺序打印一个整数的每一位数+求第n个斐波那契数
68 0
|
5月前
|
算法
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
135 0
|
算法 C语言
你会使用函数的递归和迭代吗?----------C语言函数学习(4)详解
你会使用函数的递归和迭代吗?----------C语言函数学习(4)详解
149 1
|
7月前
|
算法 C语言
汉诺塔问题(函数递归)
汉诺塔问题(函数递归)
91 0
|
8月前
|
C语言
【汇编语言实战】求两组给定数组最大值
【汇编语言实战】求两组给定数组最大值
22 0
|
8月前
|
算法 搜索推荐 程序员
第四十八练 请以递归方式实现反转字符串的函数
第四十八练 请以递归方式实现反转字符串的函数
45 2
|
8月前
|
算法 搜索推荐 程序员
第四十四练 请以递归方式实现计算阶乘的函数
第四十四练 请以递归方式实现计算阶乘的函数
60 1
|
8月前
|
机器学习/深度学习
利用函数递归求汉诺塔问题
利用函数递归求汉诺塔问题
68 0
|
8月前
|
自然语言处理 算法 编译器
编译原理复习四:编译器结构 消除左递归、左公因子 最右推导 寻找句柄讲解(附题目和答案)
编译原理复习四:编译器结构 消除左递归、左公因子 最右推导 寻找句柄讲解(附题目和答案)
192 0
AI助理

你好,我是AI助理

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