4.3 非数值计算导学案-教科版（2019）高中信息技术必修一第四章

4.3 非数值计算 【学习目标】 1.了解算法设计中的分治思想。 2.运用二分查找解决实际问题。 3.体验二分查找算法解决实际问题的过程。 4.体验递归的方法，并结合具体问题开展编程实践。 【知识框架】 知识点1：分治思想 分治的设计思想，是将一个难以直接解决的大问题， 成一些较小的 问题，各个击破，最终达到解决问题的目的。 知识点2：二分法查找 二分查找又叫 查找，该方法主要将数列 排列，先以 的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为 ，否则为右半部分。每一次比较后都可以将查找区间 一半。它可以明显减少比较次数，提高查找效率。 在一个有n个元素的 序列中，利用二分查找大约需要log₂n次（向上取整）。 活动1：查找漏扫图书 为了更好地学习英语，小I和小T去阅览室借了20本英文原著，由于扫码时有一本漏扫引起了警报声。用二分法的方法来找这本书，最多要尝试多少次？ 4<log₂20<5，故最多要尝试 次。 活动2：查找英文单词 小I和小T在阅读《老人与海》。小I：“A man can be destroyed but not defeated”你知道defeat是什么意思吗？小T：我刚买了一本新字典有2346页呢，我来帮你查一下。如果你是小T，如何快速找到单词。（中间值取法是左+右的和再整除2） 流程如下： 翻到中间部分即 页，假设当前开头字母是h，故知道应该在左半边找。 重新找中间值为 页，假设该页开头字母是f，故继续找左半边。 重新找中间值为 页，假设该页开头字母是c，故继续找右半边。 重新找中间值为 页，假设该页字母是d了，此时可以根据本页内容确定defeat这个单词是在本页，还是继续查左边，还是继续查右边，重复二分法流程，直到找到这个单词。 活动3：寻找失主 小I和小T在阅览室角落里捡到了一本无名的读书笔记，如何在一个3600秒长度的监控录像中快速找到失主？先在一半的位置看看书是不是在那里，如果在将区间锁定在前半个小时，如果不在将区间锁定在后半个小时，然后继续选择中间位置排查，直到找到失主。（二分查找也叫折半查找） 查找区间为0——3600秒，假设目标值为1866秒，使用二分查找的方法，计算并记录每一步的边界值和中间值，然后分析边界变化的规律。 次数 左边界 右边界 中间值 比较结果 1 0 3600 1800 1800<1866 2 1801 3600 2700 2700>1866 3 1801 2699 2250 2250>1866 4 1801 2249 2025 2025>1866 5 1801 2024 1912 1912>1866 6 1801 1911 1856 1856<1866 7 1857 1911 1884 1884>1866 8 1857 1883 1870 1870>1866 9 1857 1869 1863 1863<1866 10 1864 1869 1866 1866=1866 规律总结：中间值> ， 移至中间值前一个值。 <目标值，左边界移至 后一个值。当中间值=目标值时查找结束。 程序代码： x=int(input("请输入要查找的3600以内的整数:")) step=0 flag1=1 flag2=3600 while(flag1<=flag2): mid= step=step+1 if mid>x: flag2=mid-1 elif mid<x: flag1= else: break print("查找次数为：", ) 知识点3：递归 递归是计算科学领域中一种重要的 模式，既是一种抽象表达的手段，也是一种问题求解的重要方法。 递归的基本思想是把规模 的问题层层转化为规模 的 问题求解。对递归而言，递推与回归，二者缺一不可。 1）分：将原有问题 成K个子问题。 2）治：对这K个子问题 求解。如果子问题的规模仍然不够小，重复第1步。 3）合：将小规模问题的解 为一个更大规模问题的解，自下而上逐步求出原解。 活动4：玩汉诺塔游戏 如图所示，在木板上有A、B、C三根杆，A杆上有若干木盘，规定每次移动一个木盘。且小的木盘只能叠在大的木盘上面。用尽可能少的次数把所有的木盘从A杆全部移到C杆上。 将N个木盘从A杆移动到C杆，需要借助中间的B杆，只要超过一个木盘，在移动过程中，总会存在起始杆、过渡杆及目标杆的问题。因此，定义函数时，用到了4个参数：haooi(n,s,m,t)，n表示需要移动的盘子数量，S表示盘子的 ，m表示中间 ，t表示 。 像这种直接或间接地调用 的方法称为 。 def hanno(n,s,m,t): #定义一个函数,n层塔，将盘子从s借助m移动到t if n==1: print(s,'-->',t) #将一个盘子从s移动到t else: (n-1,s,t,m) #将前n-1个盘子从s移动到m上 print(s,'-->',t) #将最底下的最后一个盘子从s移动到t上 (n-1,m,s,t) #将m上的n-1个盘子移动到t上 #主程序 n=int(input('请输入汉诺塔的层数：')) # 调用函数，将n个木盘从A借助B移动到C (n,'A','B','C') 知识点4：递归与迭代的关系 迭代与递妆算法都需要 某些代码，两者既有区别又有密切的联系。迭代是重复反馈 的活动，通常是逼迫所需目标或结果。迭代则通常使用 结束循环。递归是重复调用 。递归满足 的情况时逐层返回。 【课后练习】 1.在非数值计算中，贪心算法通常用于求解（ ） A.一般问题 B.最大化问题 C.确定性问题 D.非确定性问题 2.数据结构是一门研究非数值计算的程序设计问题中计算机数据元素以及它们之间的（ ）和运算等的学科。 A.结构 B.关系 C.运算 D.算法 3.斐波那契在《计算之书》中提出了一个有趣的兔子问题：假设一对兔子每个月可以生一对小兔子,一对兔子出生后第2个月就可以开始生小兔子。则一对兔子一年内繁殖成多少对？ 由于每个月兔子对数只跟前两个月有关，因此在用迭代法编写程序时，只需两个变量f1和f2分别记录上上月和上月的数据即可。 def fib(n): f2=f1=1 # 迭代变量 for i in ①:# 迭代控制 f1,f2=② #迭代关系 ③ n =int(input()) print(fib(n)) 4.下列程序实现用二分迭代法求解方程f(x)=x^3-x-1在(1,2)内的实数根。 def f(x): # 定义方程f(x)=x³-x-1 return x**3-x-1 xl=1 # 方程根的左边界值 x2=2 # 方程根的右边界值 mid=① # 求根的中间 while abs(f(mid))>=0.000001: if f(x1)*f(mid)<0: ② # 根据中间值修改根的右边界范围 else: ③ # 根据中间值修改根的左边界范围 mid=(xl+x2)/2 print(mid) 5.实现功能：用递归法求3!+5!+7!的值，打印输出结果。 def fac(n): if n ==1: return ① else: return n*fac(②) print("3!+5!+7!=",fac(3)+fac(5)+fac(7)) 6.用递归法求1+2+3+…+100的值，输出结果。 def s(n): if n==1: return ①else: return n+s(②) print("1+2+3+…+100=",s(100))input("运行完毕，请按回车键退出...") 7.完善程序实现功能∶用递归法求10!的值，并输出结果。 def f(n): if ①: return 1 else: return ②*f(n-1) print(f(③)) 【学案答案】 1.分割 2.同类 3.折半 4.有序 5.中点位置 6.左半部分 7.缩小 8.有序 9.5 10.1173 11.587 12.294 13.440 14.目标值 15.右边界 16.中间值 17.中间值 18.(flag1+flag2)//2 19.mid+1 20.step 21.计算思维 22.较大 23.较小 23.同类 24.分解 25.分别 26.合并 27.起始杆 28.过渡杆 29.目标杆 30.自身 31.递归 32.hanno 33.hanno 34.hanno 35.重复执行 36.过程 37.计数器 38.函数自身 39.终止条件 【课后答案】 1.答案：B解析：本题考查贪心算法的描述。贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望能够导致全局最优解的算法。它通常用于求解最优化问题，包括最小化问题和最大化问题。因此，选项B正确的。 2.答案：B解析：研究元素和元素之间的关系，故选B。 3.答案：range(3,n+1)、f2,f1+f2、return f2 解析：第一个是确定循环的次数，故填range(3,n+1)，表示[3,n]；第二个是迭代表达式，动态变化的过程表示，填f2,f1+f2；第三个是返回最后的兔子的对数，填return f2。 4.答案：(x1+x2)/2、x2=mid、x1=mid 解析：先求中间值(x1+x2)/2，然后根据中间值的函数值是否大于0（此处不能直接用0，要用0.000001或1e-6来表示，表示是一种逼近的状态），然后判断左右区间值乘积的符号，是负的，说明在两边，右边界左移，即把x2指向mid，如果是正的说明都是负数，把左边界右移，即x1指向mid。最终结论即为mid值。 5.答案：1、n-1 解析：当n为1时，返回1；其他时候返回n*fac(n-1)，表示为递归求阶乘 6.答案：1、n-1 解析：当只有1时，返回1；其他时候返回n+s(n-1)，表示递归求和 7.答案：n==1、n、10 解析：1.递归边界n==1；2.递归构造；3.按题调用 学科网（北京）股份有限公司 $$