【信息技术 】非数值计算课件 -二分查找课件 高中信息技术教科版（2019）必修1

4.3非数值计算SUMMARYREPORTSUMMARYREPORT了解分治策略的概念壹掌握二分查找的算法思想贰在python中用二分法解决问题叁学习目标CONTENTSSUMMARYREPORT计算一定是数吗？除了数还有什么？这些属于数值计算吗？计算的对象可以是自然界和人类社会的一切事物。某些信息，如数据、文字、语言、图形、知识、事物的运动过程及思维过程。非数值计算更多探讨＂算法”问题。

在解决非数值类计算问题时，一些基础的思维方式可以借鉴，如分治、递归、解析等。非数值计算SUMMARYREPORT分治策略壹SUMMARYREPORT分治策略n（n较小）直接解决nn1（将这k个子问题的解合并）n2nk……解决原问题（分解）（递归地解决每个子问题）分治策略所能解决的问题的特征该问题的规模缩小到一定的程度就可以容易地解决。该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（前提）利用该问题分解出的子问题的解可以合并为该问题的解。（关键）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。分解将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题解决若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并将各个子问题的解合并为原问题的解。

分治法的基本步骤SUMMARYREPORT二分查找利用分治法解决问题的典型案例之一贰猜数字游戏老师将在心里说一个1~1000之间的数，同学们猜一猜这个数字是多少？（如果回答的数不对，老师将告知这个数比正确的数大还是小）。思考：怎样才能最快的找到正确答案？猜数字游戏500大小750250大875小大小625375125……………………每次取中间的数，仅仅需要10次即可找到答案猜数字游戏思考：如果是1~100，最多需要几次找到答案？如果是1~10000呢？27≈100210≈1000目标越大，优势越明显二分查找

二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后可以将查找区域缩小一半。第一次分割第二次分割第三次分割二分查找实际操作——翻页数比赛假设我们的信息技术书本为200页，目标为68页，记录下每次翻开的页数，看看谁找的最快。10050756268往前找往前找往后找往后找SUMMARYREPORT在python中用二分法解决问题ProblemsandSolutions如何判断一个数在已知数组中的位置？A=[1,5,3,7,36,12,68,79,2]A.sort()#先将数组变有序num=int(input(“请输入要查找的数”))left=0#left指的是范围最左边的下标right=len(list)-1#right指的是范围最右边的下标while(left<=right):#只要查找范围还没变为0就循环mid=(left+right)//2#范围中间那个数的下标ifnum>A[mid]:left=mid+1elifnum<A[mid]:right=mid-1else:print(“该数为数组中的第{}个数”.format(mid+1))思考：如果输入的数据不在范围内，会出现什么结果呢？程序还需要在哪些地方进行完善？如何判断一个数在已知数组中的位置？i=0foreinA:ifnum==e:……else:i++ifi==len(A):print(“该数字不存在于当前数组”)#遍历#i用来存放数值不相同的次数，如果遍历完成后发现全不相同，说明不存在拓展知识小游戏：如何找出1-1000之间的某个数？random.randint(1,10)random.random()random.uniform(1.1,5.4random.choice('tomorrow')random.randrange(1,100,2)importrandomx=random.randint(1,1000)while0<x<1000:y=int(input("请输入这个数："))ifx<y:print("大了")elifx>y:print("小了")else:print("就是",x)break课堂练习———补全翻字典程序Loremipsumdolorsitamet,consectetueradipiscingelit.Aeneancommodoligulaegetdolor.Loremipsumdolorsitamet,consectetueradipiscingelit.Aeneancommodoligulaegetdolor.课后作业———汉诺塔移动3个木盘的方法是：根据木盘叠放规则，要使A杆上最大的木盘（记为x)移动到C杆上（子问题1,如图第4步），必须先把x上方的所有木盘移动到B杆上（子问题2,如图4中的前3步），然后再将B杆上所有的木盘移动到C杆上（子问题3,如