当前课程知识点:C语言程序设计(下) >  第二周:函数(二) >  函数递归调用 >  6.5.5 汉诺塔讲解

返回《C语言程序设计(下)》慕课在线视频课程列表

6.5.5 汉诺塔讲解在线视频

6.5.5 汉诺塔讲解

下一节:6.5.6 汉诺塔程序运行

返回《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语言的环境下

来运行这个函数

C语言程序设计(下)课程列表:

第一周:函数(一)

-1.1 函数定义

--内容简介

--函数是什么

--例题演示

--知识点总结

-1.1 函数定义--作业

-1.2 模块化程序设计

--由生活中的例子介绍模块化概念

--模块化程序设计总结

-1.3 函数调用、声明和返回

--函数调用的过程

--函数嵌套调用

-1.4 函数间参数传递

--形参与实参值传递

--地址传递-数组名做函数参数

--函数返回语句和返回值

--小结

--html

-1.4 函数间参数传递--作业

第二周:函数(二)

-函数递归调用

--6.5.1 递归问题开场白

--6.5.2 递归定义和调用过程

--6.5.3 运行程序

--6.5.4 汉诺塔介绍

--6.5.5 汉诺塔讲解

--6.5.6 汉诺塔程序运行

--6.5.7 递归调用例题

--6.5.8 递归总结

--html

--html

--html

--html

--html

--html

-函数递归调用--作业

第三周:函数(三)

-3.1 变量存储属性

--开场

--局部变量全局变量

--静态存储与动态存储

--存储类别小结

--html

--html

--html

--html

--html

-3.1 变量存储属性--作业

-3.2 编译预处理

--编译预处理开头

--编译预处理内容

--库函数

--函数总结

--综合例子

--html

-3.2 编译预处理--作业

第四周:指针(一)

-4.1 指针的定义、初始化和引用

--本周内容简介

--从变量的地址理解指针(1)

--从变量的地址理解指针(2)

--从数据交换看指针的应用(1)

--从数据交换看指针的应用(2)

--从数据交换看指针的应用(3)

-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 结构数组

--7.2.1 结构体数组

--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

6.5.5 汉诺塔讲解笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。