4.3 非数值计算（课件）1

学易同步精品课堂 教科版（2019版） 信息技术（高中） 4.3 非数值计算 第4单元 计算与问题解决 必修1 数据与计算 学习目标 1.运用合适的算法形成解决问题的方案 2.了解算法设计中的分治思想，并运用二分查找解决实际问题 3.体验递归的方法，并结合具体问题开展编程实践 教学重点 理解二分思想、递归思想，运用二分算法解决实际问题 教学难点 理解递归算法 程序源代码及执行结果截图： 巧翻字典 PROJECT PEOFILE 4 假设一本字典有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