资源简介

(共19张PPT)
4.3 非数值计算
—— 猜数字游戏
教 学
目 标
通过分析问题-设计算法-编程实现-测试运行的解决问题的过程，能够根据具体问题设计合适的算法形成解决问题的方案。
了解分治算法的优缺点及其在生活中的应用。
通过“猜数字小游戏”,了解分治思想，并运用二分查找解决实际问题。
课 前 复 习
1.random.randint(1,10)的作用是：（ ）
知识点检测
A.从1-10之间随机生成一个整数 B.生成1-10之间所有整数
C.从1-9之间随机生成一个整数 D.生成1-9之间所有整数
A
range(m,n)==>生成[m，n)之间的所有整数。
random 是一个生成随机数的模块，randint()是random 的一个函数，用于生成一个随机整数，使用之前需要导入random （import random）。
random.randint(m,n)=>从[m,n]之间随机生成一个整数。
猜 数 字 游 戏
运行”猜数字游戏“，尝试描述游戏功能及实现步骤
如何编写代码实现游戏？
1.系统随机生成一个数字
2.猜数字，猜对则跳出程序，否则继续猜测，直至5次后跳出，输出这个数字。
思考：
猜 数 字 游 戏
如何编写代码实现游戏？
1.计算机随机生成一个数
m=random.randint(1,100)
3.输入要猜的数字
t = int(input("请输入你猜的数："))
2.要猜几次？
for i in range(5):
4.比较m与t
若5次之内猜中，跳出循环
否则输出没有猜中，游戏结束。
终止循环语句
break
猜 数 字 游 戏
import ① # 导入随机数模块
m=random.randint(1,100)
for i in range(5):
t = int(input("请输入你猜的数："))
if t > m:
print("大了")
② t < m:
print("小了")
else:
print("恭喜你,答对了！")
③
if t!=m:
print("这个数是：",m)
print("5次没有猜中，游戏结束")
是
否
是
否
是
否
任务一：将程序补充完整
一
分 治 算 法
”猜数字游戏“，如何猜的又快又准
枚 举 算 法
二 分 查 找
效率低
一
分 治 算 法
二分查找实际上就是分治策略的典型运用
大事化小，小事化了
分 治 算 法
一
分 治 算 法
左边界low
右边界high
目标数x
中间数
mid=(low+high)//2
若中间数mid比目标数x大，则区间变为左半区间，右边界更新为high=mid-1, low不变。
左边界
low
右边界
high
目标数x
中间数
Mid
(low+high)//2
若中间数mid比目标数x小，则区间变为右半区间，左边界更新为low=mid+1, high不变。
一
分 治 算 法
目标数:9
1 2 3 4 5 6 7 8 9 10
low=1
high=10
mid=(1+10)//2=5 <9
6 7 8 9 10
low=mid+1 →6
high=10
mid=8 <9
9 10
low=mid+1→9
high=10
mid=9 =9
第一轮
第二轮
第三轮
最坏的情况需要查找n次满足: 2n>N(N为查找的总数量)
一
分 治 算 法
再次运行”猜数字游戏”，体验利用二分查找实现最快的找到数字“
任务二：
一
分 治 算 法
二分法查找最快需要几步？
x = int(input("请输入要查找的100以内的整数:"))
step = 0 # 记录查找次数
low = 1 # 目标区域左边界
high = 100 # 目标区域右边界
while(low <= high):
mid = (low+high)//2 # 中间值
step = step+1 # 查找次数加
if mid > x:
high = ① # 右边界前移
② mid < x:
low = mid+1 # 左边界后移
else:
break # 找到目标数据，退出循环
print("查找次数为：", ③)
任务三：将程序补充完整。统计二分法查找次数
二分查找的前提：
被查找的数据必须是有序的!
一
分 治 算 法
如何对一组无序的数据如何进行排序呢？
lst=[9，6 ，45，23，48，7]
优点：效率高
缺点：
二
递 归 算 法
lst=[9，6 ，45，23，48，7]
9
[6,7]
[45,23,48]
[ ]
[7]
[23,45,48]
[6,7]
[6,7,9,23,45,48]
6
45
[23]
[48]
1.取一个数作为基数：如9
2.将大于基数的数和小于基数的数分成两个数组：left=[6,7],right=[45,23,48]
3.分别对left和right重复执行1，2，直到列表元素小于等于一个元素为止
4.将left+基数+right 合并
----分
----治
----合
递 归 算 法
二
递 归 算 法
9
[6,7]
[45,23,48]
[ ]
[7]
[23,45,48]
[6,7]
[6,7,9,23,45,48]
6
45
[23]
[48]
直接或间接地调用自身的方法称为递归。可以将递归简单类比为具有自相似性重复的事物。
递 归
二
递 归 算 法
递归的基本思想是把规模较大的问题层层转化为规模较小的同类问题求解。可用“分”，“治”，“合”三个字概括
递归的基本思想
递推关系
递归的条件
边界条件
+
len(lst) <= 1
quickSort(left) + lst[0:1] + quickSort(right)
猜 数 字 游 戏
任务四：将程序补充完整，实现递归排序
def quickSort(lst):
right=[]
left=[]
if len(lst) ①:
return lst
for i in lst[1:]:
if i >= lst[0]:
right.append(i)
②:
left.append(i)
return quickSort(left) + lst[0:1] + quickSort(right)
lists = [4, 6, 9, 1, 8, 7, 2, 5, 4, 0]
print("排序前: " , lists)
print("排序后: " , ③)
课 堂 小 结
THE END

展开更多......

收起↑