(
课件网) 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重复执 ... ...
