资源简介

(共26张PPT)
高中信息技术 必修1 数据与计算
4.3 非数值计算
第二课时 神奇的递归
学习目标
01
02
运用合适的算法形成解决问题的方案；
了解算法中的分治思想；
03
体验递归算法，并结合具体问题开展编程实践。
4.3 非数值计算——神奇的递归
项目内容
本节我们将围绕“生活中的算法”项目，尝试用“算法的眼睛”看待生活，用“算法的思维”去解决实际问题。
项目任务
任务一：巧翻字典
任务二：玩转“汉诺塔”游戏
本节任务
玩“汉诺塔”游戏
“汉诺塔”游戏由来：有一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
4.3 非数值计算——神奇的递归
4.3 非数值计算——神奇的递归
“汉诺塔”游戏规则来：
1、有三根相邻的柱子，标号为A,B,C。
2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。
3、现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。
A
B
C
玩“汉诺塔”游戏
4.3 非数值计算——神奇的递归
请打开学案中的“汉诺塔”游戏，赶快体验一下吧！
玩“汉诺塔”游戏
4.3 非数值计算——神奇的递归
分析玩的过程
以3个木盘为例
A
B
C
A B
A C
4.3 非数值计算——神奇的递归
分析玩的过程
以3个木盘为例
A
B
C
C B
A C
4.3 非数值计算——神奇的递归
分析玩的过程
以3个木盘为例
C
B
A
B C
B A
4.3 非数值计算——神奇的递归
分析玩的过程
以3个木盘为例
A
B
C
A C
总结移动规律
三步移动
将A上面两个木盘从A B
将A最下面的一个木盘从A C
将B上面两个木盘从B C
将A上面一个木盘从A C
将B最下面一个木盘从A B
将C上面一个木盘从C B
将B上面一个木盘从B A
将B最下面一个木盘从B C
将A上面一个木盘从A C
3个木盘的移动问题成功解决了，
就可以解决更多木盘的移动问题了。
知识探究：递归
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。
知识探究：递归函数
递归函数是只用函数自身来定义该函数的方法。如斐波那契数列“1,1,2,3,5,8,13……”,可以递归定义为：
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
知识探究：递归的重要组成
递推关系是递归的重要组成；
边界条件是递归的另一要素（保证递归能在有限次计算后得出结果，而不会产生无限循环地情况）
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
边界条件
递推关系
知识探究：递归的基本思想
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。
1）分：将原有问题分解成K个子问题。
2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进 行下去，直到问题足够小时，就很容易求出子问题的解。
3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
递归可用“分”，“治”，“合”三个字概括
“汉诺塔”游戏程序实现
hanoi(盘子数，起始杆，过渡杆，目标杆)
hanoi(n,A,B,C)
从A移到C
hanoi(n-1,B,A,C)
hanoi(n-1,A,C,B)
前n-1个木盘从A移动到了B
前n-1个木盘从B移动到了C
汉诺塔递归过程图示
“汉诺塔”游戏程序实现
上机实践
“汉诺塔”游戏程序执行的过程
def move(n,s,m,t):
if n==1:
print(s,'-->',t)
move(n-1,s,t,m)
print(s,'-->',t)
move(n-1,m,s,t) move(3,'a','b','c')
move(3,'a','b','c')调用
move(2,'a','c','b')
print('a','-->','c')
move(2,'b','a','c')
move(1,'a','b','c')
print('a','-->','b')
move(1,'c','a','b')
move(1,'b','c','a')
print('b','-->','c')
move(1,'a','b','c')
输出：a-->c输出：a-->b
输出：c-->b输出：a-->c输出：b-->a
输出：b-->c输出：a-->c
else:
拓展练习
计算“汉诺塔”游戏移动的次数。
2个金片，移动几次
4个金片，移动几次
5个金片，移动几次
3个金片，移动几次
3次
15次
31次
7次
……
n个金片，移动几次
2n-1次
拓展练习
计算“汉诺塔”游戏移动的次数。
def f(n):
if n==0:
return 0
else:
return 2*f(n-1)+1
x=int(input("请输入塔的个数："))
print("需要移动",f(x),"次")
input("运行完毕，请按回车键退出...")
方法1
拓展练习
计算“汉诺塔”游戏移动的次数。
方法2
c=0
c=c+1
c=c+1
拓展知识
迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第N项的值为例，程序间的转换如表所示。
迭代与递归算法都需要重复执行某些代码，两者既有区另又有密切的联系。迭代是重复反馈过程的活动，其目的通常是逼迫所需目标或结果。递归是重复调用函数自身。递归满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。
拓展知识
迭代 递归
两种算法均需重复执行某些代码
一次次重复过程 从而接近或达到目标或结果 重复调用函数自己本身
层层化解为规模较小的同类问题
三步骤：确定迭代变量 建立迭代关系式 控制迭代过程 递归二要素：递推+回归
步骤：确定递推关系式
确定边界条件
用循环控制迭代进程 遇到边界条件时逐层返回
循环次数较大时，迭代效率明显高于递归
课堂小结
1. 理解递归思想。
2. 理解递归算法。
3. 结合具体问题开展编程实践。
课后作业
了解生活中的递归
有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？
学无止境 永攀高峰
感谢观看

展开更多......

收起↑