版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、4.3 非数值计算第4单元 计算与问题解决学 习 目 标3.体验递归算法,并结合具体问题开展编程实践。2.了解算法设计中的分治思想,并运用二分查找解决实际问题。1.运用合适的算法形成解决问题的方案。二分查找法的理解和运用二分法解决实际问题。 (重点)递归算法的实际应用,并针对具体问题开展编程实践。 (难点) 运行Python编写的“猜数字”游戏,计算机在01000中随机产生一个数,试试看你要多少次才能猜中。 假设一本书大约300页,目标信息在第132页。请在下表记录你的翻页过程,和同学们比一比,看谁翻的次数最少。次数翻至页码下一步决策第1次第2次第3次第4次 分治策略 分治的设计思想,是将一个
2、难以直接解决的大问题,分割成一些较小的同类问题,各个击破,最终达到解决问题的目的。二分查找实际上就是分治策略的一种典型运用。二分查找 二分查找又叫折半查找,该方法主要将数列有序排列,采用跳跃式的方式查找数据。二分查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。 以递增数列为例,先以中点位置的元素作为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。每一次比较后都可以将查找区间缩小-半。 二分法查找的前提条件是被查找的数据必须是有序的。查找的基本算法有: 顺序查找、二分查找、 分块查找、哈希查找等 有了翻书的经验,我们尝试完善下面的二分查找程序
3、。x=int(input(请输入要查找的1000以内的整数:)step=0 #记录查找次数flag1=1 #目标区域左边界flag2=1000 #目标区域左边界while( ): #区间数据范围小于1则结束循环 mid=( ) #中间值 ( ) #查找次数加1 if midx: ( ) #右边界前移 elif midx: ( ) #左边界后移 else: breakprint(查找次数为:,step) #找到目标数据,退出循环input(运行完毕,请按回车键退出.) #输出次数(flag1,t) #将一个盘子从s移动到t else: hanno(n-1,s,t,m) #将前n-1个盘子从s移动
4、到m上 print(s,-,t) #将最底下的最后一个盘子从s移动到t上 hanno(n-1,m,s,t) #将m上的n-1个盘子移动到t上#主程序n=int(input(请输入汉诺塔的层数:)#调用函数,将n个木盘从A借助B移动到Channo(n,A,B,C)input(运行完毕,请按回车键退出.)递归输入不同的层数,查看运行结果递归计算“汉诺塔”游戏移动的次数。参考答案: def f(n): if n=0: return 0 else: return 2*f(n-1)+1 x=int(input(请输入塔的个数:) print(需要移动,f(x),次) input(运行完毕,请按回车键退出.) 递归根据提示输入不同的塔数,查看移动的次数递归 迭代算法与递归算法都需要重复执行某些代码,两者既有区别又有密切的联系。 迭代 重复方式:是重复反馈过程的活动,其目的通常是逼迫所需目标或结果。 结束方式:通常使用计数器结束循环。 递归 重复方式是重复调用函数自身。 结束
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年材料能源行业技能考试-汽车电瓶蓄电池笔试参考题库含答案
- 密封圈项目可行性研究报告及运营方案|瑞克咨询|2024年编制|
- 2024年操作工技能考核考试-中央空调工笔试参考题库含答案
- C++面向对象程序设计(第4版)-课件 CH2
- 2024年岗位知识竞赛-营改增热点问题知识竞赛笔试参考题库含答案
- 2024年山西住院医师-山西住院医师内科笔试参考题库含答案
- 2024年安全知识安全生产知识竞赛-工程技术质量知识竞赛笔试参考题库含答案
- 2024年大学试题(财经商贸)-货币金融学笔试参考题库含答案
- 执业药师之西药学专业二高分题库
- 中级银行从业资格之中级银行管理全真模拟考试试卷A卷含答案
- GB/T 18283-2008商品条码店内条码
- 工程资料收发文登记表-模板
- 重庆市2023届高三一诊英语试题(含音频)
- 手机拍照技巧大全课件
- 中学数学基本教学技能课件
- 脊柱损伤操作评分表
- iso19011;管理体系审核指南课件
- 医学生实验设计大赛ppt模板
- 简化字总表(正规版)
- 裂隙灯显微镜检课件
- 送达地址确认书(诉讼类范本)
评论
0/150
提交评论