资源简介

(共34张PPT)
教科版（2019版） 信息技术（高中）
4.3 非数值计算
第4单元 计算与问题解决
必修1 数据与计算
学习目标
1.运用合适的算法形成解决问题的方案
2.了解算法设计中的分治思想，并运用二分查找解决实际问题
3.体验递归的方法，并结合具体问题开展编程实践
教学重点
理解二分思想、递归思想，运用二分算法解决实际问题
教学难点
理解递归算法
程序源代码及执行结果截图：
巧翻字典
PROJECT PEOFILE
假设一本字典有1000页，老师藏了一条秘密信息在其中一页。现在通过运行“找神秘信息.py”文件，找到相应页码中的这条信息！并告诉我你用几次找到的？
实践 统计查找次数
假设信息在第328页。如何去找到该页的信息呢。
实践 统计查找次数 P101
次数 翻至页码 下一步决策
第1次 500 往前 1-499
第2次 250 往后 251-499
第3次 375 往前 251-374
第4次 312 往后 313-374
第5次 343 往前 313-342
第6次 327 往后 328-342
第7次 335 往前 328-334
第8次 331 往前 328-330
第9次 329 往前 328-328
第10次 328
策略 1
找到区间的中位数
策略 2
根据情况确定更精确的区间
二分查找/折半查找 p101
二分思想：将数列有序排列，采用跳跃的方式查找数据。
分治策略
将难以直接解决的大问题，分割成较小的同类问题
方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。
找一半
按照顺序找一半，
一比较，舍一半。
继续找一半，
一半又一半，
快速找答案！
左边界
flag1
右边界
flag2
目标数
x
中间数
mid
！！！若中间数mid比目标数x大，则区间变为左半区间，右边界更新
左边界
flag1
右边界
flag2
目标数
x
中间数
mid
！！！若中间数mid比目标数x小，则区间变为右半区间，左边界更新
在有n个元素的有序序列中，利用二分查找大约需要log2n次。
二分查找/折半查找 p101
n = 1000 需要10次
二分思想：将数列有序排列，采用跳跃的方式查找数据。
程序编写
P 102
ABOUT US
统计二分查找次数的源代码和程序运行截图：
“汉诺塔”游戏源于一个古老的印度传说。如下图所示，在木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘。且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有的木盘从A杆全部移到C杆上。
课堂活动2
玩转“汉诺塔”游戏
COOPERATION
“汉诺塔”游戏源于一个古老的印度传说。木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘，且小的木盘只能叠在大的木盘上面。请设计算法，用尽可能少的次数把所有木盘从A杆全部移到C杆上。
移动方法：以移动3个木盘为例，根据木盘叠放规则，要使A杆上最大的木盘（记为x）移动到C杆上，必须先把x上方的所有木盘移动到B杆上，然后再将A杆上最大的木盘移到C上，最后再将B上所有的木盘移动到C杆上。
编程如下：
def hanno(n,s,m,t):
#定义一个函数,n层塔，将盘子从s借助m移动到t
if n==1:
print(s,'-->',t) #将一个盘子从s移动到t
else:
hanno(n-1,s,t,m) #将前n-1个盘子从s移动到m上
print(s,'-->',t) #将最底下的最后一个盘子从s移动到t上
hanno(n-1,m,s,t) #将m上的n-1个盘子移动到t上
#主程序
n=int(input('请输入汉诺塔的层数：'))#调用函数，将n个木盘从A借助B移动到C
hanno(n,'A','B','C')
input("运行完毕，请按回车键退出...")
以三个木盘为例
A
B
C
A B
A C
A
B
C
C B
A C
C
B
A
B C
B A
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
汉诺塔游戏源代码和运行界面截图：
总结：
生活中很很多类似这种具有自相似性重复的事物。
函数定义
def 函数名称(参数列表):
函数体
return [返回值]
无返回值 print()
有返回值 x=input()
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
递归是计算科学领域中一种重要的计算思维模式。它既是一种抽象表达的手段，也是一种问题求解的重要方法。
递归
递归函数是只用函数自身来定义该函数的方法。如斐波那契数列“1,1,2,3,5,8,13……”,可以递归定义为：
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
递归函数
递归的基本思想
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。对递归而言，递推与回归，二者缺一不可。
递归可用“分”，“治”，“合”三个字概括
1）分：将原有问题分解成K个子问题。
2）治：对这K个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进 行下去，直到问题足够小时，就很容易求出子问题的解。
3）合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
主程序
def f(n):
if n==1:
return #边界条件
else:
return #递推关系
1. 理解递归思想。
2. 理解递归算法。
3. 理解二分查找思想，运用二分算法解决实际问题。
课堂小结
结合4.2的知识，计算“汉诺塔”游戏移动的次数。
def f(n):
if n==0:
return 0
else:
return 2*f(n-1)+1
x=int(input("请输入塔的个数："))
print("需要移动",f(x),"次")
input("运行完毕，请按回车键退出...")
练习2
汉诺塔移动次数源代码和运行界面截图：
迭代程序可以转换成等价的递归程序。以上一节中计算斐波那契数列第N项的值为例，程序间的转换如表所示。
迭代与递归算法都需要重复执行某些代码，两者既有区另又有密切的联系。迭代是重复反馈过程的活动，其目的通常是逼迫所需目标或结果。递归是重复调用函数自身。递归满足终止条件的情况时逐层返回。迭代则通常使用计数器结束循环。
拓展知识
填空题
1. 二分查找又叫________，该方法主要将数列________排列，采用________的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。
折半查找
有序
跳跃式
在Python中，以下程序运行结果是（　　）
A．m15 B．m105 C．mm105 D．m10m5
B
THANKS
“
”

展开更多......

收起↑