《【信息技术 】非数值计算课件 —二分查找课件 高中信息技术教科版（2019）必修1.pptx》由会员分享，可在线阅读，更多相关《【信息技术 】非数值计算课件 —二分查找课件 高中信息技术教科版（2019）必修1.pptx（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.3 非数值计算SUMMARY REPORT SUMMARY REPORT 了解分治策略的概念壹掌握二分查找的算法思想贰在python中用二分法解决问题叁学习目标CONTENTSSUMMARY REPORT 计算一定是数吗？除了数还有什么？这些属于数值计算吗？计算的对象可以是自然界和人类社会的一切事物。某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。非数值计算更多探讨 算法”问题。在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。非数值计算SUMMARY REPORT 分治策略壹SUMMARY REPORT 分治策略n（n较小）直接解决nn1（将
2、这k个子问题的解合并）n2nk解决原问题（分解）（递归地解决每个子问题）分治策略所能解决的问题的特征所能解决的问题的特征该问题的规模缩小到一定的程度就可以容易地解决。该问题可以分解为若干个规模较小的相同问题，即该问题具有最优 子结构性质。（前提）利用该问题分解出的子问题的解可以合并为该问题的解。（关键）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。分解分解将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题解决解决若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并合并将各个子问题的解合并为原问题的解。分治法的基本步骤分治法的基本步骤SUMM
3、ARY REPORT 二分查找利用分治法解决问题的典型案例之一贰猜数字游戏 老师将在心里说一个11000之间的数，同学们猜一猜这个数字是多少？（如果回答的数不对，老师将告知这个数比正确的数大还是小）。思考：怎样才能最快的找到正确答案？猜数字游戏500大小750250大875小大小625375125每次取中间的数，仅仅需要10次即可找到答案猜数字游戏思考：如果是1100，最多需要几次找到答案？如果是110000呢？271002101000目标越大，优势越明显二分查找二分查找 二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，
4、如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后可以将查找区域缩小一半。第一次分割第二次分割第三次分割二分查找二分查找实际操作翻页数比赛假设我们的信息技术书本为200页，目标为68页，记录下每次翻开的页数，看看谁找的最快。10050756268往前找往前找往后找往后找SUMMARY REPORT 在python中用二分法解决问题Problems and Solutions如何判断一个数在已知数组中的位置？A=1,5,3,7,36,12,68,79,2A.sort()#先将数组变有序num=int(input(“请输入要查找的数”)left=0#left指
5、的是范围最左边的下标right=len(list)-1#right指的是范围最右边的下标while(leftAmid:left=mid+1 elif numAmid:right=mid-1 else:print(“该数为数组中的第个数”.format(mid+1)思考：如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？如何判断一个数在已知数组中的位置？i=0for e in A:if num=e:else:i+if i=len(A):print(“该数字不存在于当前数组”)#遍历#i 用来存放数值不相同的次数，如果遍历完成后发现全不相同，说明不存在拓展知识小游戏：如何找
6、出1-1000之间的某个数？random.randint(1,10)random.random()random.uniform(1.1,5.4random.choice(tomorrow)random.randrange(1,100,2)import randomx=random.randint(1,1000)while 0 x1000:y=int(input(请输入这个数：)if xy:print(小了)else:print(就是,x)break课堂练习补全翻字典程序Lorem ipsum dolor sit amet,consectetuer adipiscing elit.Aenean
7、commodo ligula eget dolor.Lorem ipsum dolor sit amet,consectetuer adipiscing elit.Aenean commodo ligula eget dolor.课后作业汉诺塔汉诺塔 移动3个木盘的方法是：根据木盘叠放规则，要使A杆上最大的木盘（记为x)移动到C杆上（子问题1,如图第4步），必须先把 x上方的所有木盘移动到B杆上（子问题2,如图4中的前3步），然后再将B杆上所有的木盘移动到C杆上（子问题3,如图中的后3步）。课堂小结Thank You For Your Leadership And ColleaguesSUMMARY REPORT 凡治众如治寡，分数是也。孙子兵法