当前课程知识点:C语言程序设计(下) > 第二周:函数(二) > 函数递归调用 > 6.5.5 汉诺塔讲解
下面我们就来看
著名的汉诺塔问题
了解了这个规则
咱们就来分析这个问题
首先
汉诺塔问题是属于非数值型问题
那我们想最简单的情况
假如就一片盘
直接就可以将这片盘
从A杆搬到C杆上
那假如有两片呢
就像图中看到的这样
我们首先
将A杆上的小盘
移动到B杆上
然后再将A杆上的大盘
移动到C杆上
再将小盘
从B杆移到中间的C杆
这样完成了两片盘的移动
总结一下
两片盘的移动方法是
有了这种两片盘的解决思路了
下面我们把问题扩展到n片
显然
对于n片盘
咱们把它分成两组
第一组就是上边的n-1片
第二组就是最底下的
一个大的盘片
有了那个两片的思路
我们同样可以
首先将上面的
A杆上的n-1个盘片
搬到B杆上
然后将大盘片
从A杆移到C杆
再将B杆上的n-1个盘片
从B杆移到C杆
移动方法我们总结如下
有了这样的思路
咱们就来设计一下
汉诺塔问题的算法
首先解决思路是
我们要首先将问题化简
假设A杆上只有一个盘片
那么可将盘从A移到C
这样我们用C语言的语句写上
如果n恒为1
我们调用一个移动的函数
将这个盘片从第一根杆
A杆
移到第三根杆 C杆
如果n大于1
这时候就把问题
分成如下三个步骤
前面说的这样的三个步骤
我们就可以对应出
屏幕上大家看到的
三个函数的调用
首先我们定义汉诺塔的
算法
我们写这样的一个功能函数的作用是
将n片盘
从第一根杆
借助于第二根杆
移动到第三根杆上
当盘片大于1的时候
我们调用
这个函数本身
这就是递归
函数的参数
从n变成了n-1
刚才说了
我们把A杆上方的那n-1个盘片
从第一个杆
借助第三根杆
移到第二根杆上
那么就剩下
A杆上的一片大的盘片了
我们将其从第一根杆
移到第三根杆
也就是从A到C
接下来
在对应第二根杆
也就是B杆上的n-1个盘片
借助于第一根杆
移动到第三根杆上
显然
在上面这三个步骤中的
第一和第三步
具有与原问题相同的性质
只是在问题的规模上
比原问题有所缩小
这是非常典型的递归问题
那么这样的算法
写出来的程序
大家看
最上方的
定义的功能函数
实现的就是将一片盘
从一根杆上
移动到另外一根杆
第二个功能函数
就是我们刚才写的那个算法
它实现的是
将n个盘从第一根杆
借助第二根移动到第三根上
我们接下来定义主函数
从键盘输入一个整型数
意味着有多少个盘片
然后调用汉诺塔
这个算法的功能函数
具体的
搬运的过程
我们可以通过屏幕的显示能看到
那下面咱们就
在c语言的环境下
来运行这个函数
-1.1 函数定义
--内容简介
--函数是什么
--例题演示
--知识点总结
-1.1 函数定义--作业
-1.2 模块化程序设计
-1.3 函数调用、声明和返回
--函数调用的过程
--函数嵌套调用
-1.4 函数间参数传递
--形参与实参值传递
--小结
--html
-1.4 函数间参数传递--作业
-函数递归调用
--html
--html
--html
--html
--html
--html
-函数递归调用--作业
-3.1 变量存储属性
--开场
--局部变量全局变量
--存储类别小结
--html
--html
--html
--html
--html
-3.1 变量存储属性--作业
-3.2 编译预处理
--编译预处理开头
--编译预处理内容
--库函数
--函数总结
--综合例子
--html
-3.2 编译预处理--作业
-4.1 指针的定义、初始化和引用
--本周内容简介
-4.1 指针的定义、初始化和引用--作业
-4.2 指针与数组
--指针与数组
--Video
-4.2 指针与数组--作业
-5.1 指针与字符串
--本周开篇介绍
--指针与字符串
--指针与字符串小结
-5.1 指针与字符串--作业
-5.2 多维数组指针
--指针与多维数组
--html
--html
--html
--html
--html
--html
--html
--html
-5.2 多维数组指针--作业
-6.1指针与函数
--本周开篇介绍
--指针指向函数
--返回指针值的函数
--html
--html
--html
-6.1指针与函数--作业
-6.2指针与指针
--引入指针数组
--指针数组
--二级指针
--指针内容小结
--html
--html
--html
--html
-6.2指针与指针--作业
-7.1 结构的概念
--Video
--Video
--Video
--Video
--html
--html
-7.1 结构的概念--作业
-7.2 结构数组
--Video
--Video
--html
-7.2 结构数组--作业
-7.3 结构指针
--Video
--Video
--Video
--html
-7.3 结构指针--作业
-7.4 结构与函数
--Video
--html
-7.4 结构与函数--作业
-7.5 联合
--Video
--Video
--html
-7.5 联合--作业
-8.1 typedef自定义类型
--自定义类型
-8.1 typedef自定义类型--作业
-8.2 枚举类型
--枚举类型
-8.2 枚举类型--作业
-8.3 链表的概念
--为什么使用链表
--链表的定义和功能
-8.3 链表的概念--作业
-8.4 链表的基本操作
--创建链表的步骤
--创建链表的过程
--访问链表中的节点
--约瑟夫问题
--html
--html
-8.4 链表的基本操作--作业
-9.1 文件概述
--文件概念
--文件分类
-9.1 文件概述--作业
-9.2 文件型指针
--文件结构与指针
--设备文件
--html
-9.2 文件型指针--作业
-9.3 文件的打开与关闭
--文件读写方式
--文件读写操作
-9.3 文件的打开与关闭--作业
-9.4 文件的顺序读写
--字符串输入输出
--html
-9.4 文件的顺序读写--作业
-9.5 文件的随机读写
--文件随机读写
-9.5 文件的随机读写--作业
-9.6 文件检测
--文件检测
-9.6 文件检测--作业
-9.7 文件应用实例
--文件应用实例
--html
--html
-10.1 C语言知识总结
--程序调试概念
--软件测试方法
--程序跟踪调试
--C语言语法要点
--标识符及运算符
--程序设计流程
--数组、函数及指针
--结构和文件
-10.1 C语言知识总结--作业
-10.2 C语言练习
--程序设计方法
--图像合成例子
--html
-期末考试复习题
--html
-期末考试复习题答案
--html