54对分查找解区间和最优解-浙江省瑞安市上海新纪元高级中学高中信息技术浙教版选修1课件(共26张PP

对分查找最优解问题瑞安市上海新纪元高级中学1.对分查找最优解问题基本特征；2.对分查找最优解问题常见题型；3.对分查找最优解问题变例分析。学习内容4.对分查找最优解问题综合应用。阶段一：理解了基本代码结构，但不知还有其他变例；阶段二：总结了几种变例模型，但只会死套公式解题；阶段三：忘记了众多变例模型，但抓住内在逻辑关系。重要关键词：枚举区间和枚举变量（L，R，m）解区间和最优解复习回顾：对分查找二叉树小马想请你帮他买一款手机。小马手头比较宽裕，可以承受3000元以上价位的手机，但他同时也是一个低调的人，认为没必要用太贵的手机。所以他心仪的目标是不低于3000元，尽可能便宜的手机。一.解区间与最优解小王也想请你帮他买一款手机。小王身上仅有3000元，但他愿意把所有的钱都花在手机上。所以他心仪的目标是不高于3000元，尽可能贵的手机。已知长度为8的数组a:(10,20,30,30,30,40,50,60)，查找第一个不小于key的元素下标，若a(n)key，则输出n+1。二.对分查找最优解问题的执行过程对比：顺序查找最优解问题的执行过程已知数组a(1ton)为非递减序列，输出第一个不小于key的元素下标，若a(n)key，则输出n+1。可推广到求满足条件的最小值问题（解区间的最小值）。对比：顺序查找最优解问题基本模型一PrivateSubCommand1_Click()key=Val(Text2.Text)L=1:R=nDoWhileL=RIfThen‘L位于非解区间，寻找最优解L=L+1Else‘此时L指向最优解ExitDoEndIfLoopPrintEndSubPrivateSubCommand2_Click()key=Val(Text2.Text)L=1:R=nDoWhileL=RIfThen‘R位于解区间，寻找更优解R=R-1Else‘此时R+1指向最优解ExitDoEndIfLoopPrintEndSuba(L)keyLa(R)=keyR+1顺序查找：从左向右扫描顺序查找：从右向左扫描已知长度为8的数组a:(10,20,30,30,30,40,50,60)，查找第一个不小于key的元素下标，若a(n)key，则输出n+1。二.对分查找最优解问题的执行过程已知数组a(1ton)为非递减序列，输出第一个不小于key的元素下标，若a(n)key，则输出n+1。可推广到求满足条件的最小值问题（解区间的最小值）。三.对分查找最优解问题基本模型一PrivateSubCommand3_Click()key=Val(Text2.Text)L=1:R=nDoWhileL=Rm=(L+R)\2IfThen‘m位于解区间，寻找更优解Else‘m位于非解区间，寻找最优解EndIfLoopPrintEndSuba(m)=keyL‘或R+1R=m-1L=m+1能否写做m=(L+R+1)\2?问题的关键不在于m左偏还是右偏，而在于：1.不能出现死循环，即不能出现L或R原地不动的情况。2.枚举不能出现遗漏，即m要能指向所有可能的位置。能否写做Printm?能否写做R=m或L=m?已知数组a(1ton)为非递减序列，输出第一个不小于key的元素下标，若a(n)key，则输出n+1。下列代码段能实现该功能，但部分语句有错误，请改正。四.模型一变式PrivateSubCommand4_Click()key=Val(Text2.Text)L=1:R=nDoWhileLRm=(L+R)\2Ifa(m)=keyThen'm位于解区间，寻找更优解R=m'R指向最优解ElseL=m+1'L指向最优解EndIfLoopPrintL‘能否写做PrintR？EndSubPrivateSubCommand4_Click()key=Val(Text2.Text)L=1:R=nDoWhileLRm=(L+R+1)\2Ifa(m)=keyThen'm位于解区间，寻找更优解R=m-1'R+1指向最优解ElseL=m'L+1指向最优解EndIfLoopPrintL+1‘能否写做PrintR+1？EndSubR=n+1L=0问题的关键不在于m左偏还是右偏，也不在于……而在于：1.不能出现死循环，即不能出现L或R原地不动的情况。2.枚举不能出现遗漏，即m要能指向所有可能的位置。key=Val(Text2.Text)L=1:R=n+1DoWhileLRm=(L+R)\2Ifkey=a(m)ThenExitDoElseIfkeya(m)ThenR=m‘能否写做R=m-1？ElseL=m+1‘能否写做L=m？EndIfLoopIfLRThenLabel1.Caption=Str(m)ElseLabel1.Caption=未找到EndIfkey=Val(Text2.Text)L=1:R=n+1DoWhileLRm=(L+R)\2Ifa(m)=keyThenR=m‘能否写做R=m-1？ElseL=m+1‘能否写做L=m？EndIfLoopIfL=nThenLabel1.Caption=第一个不小于&key&的元素下标：&LElseLabel1.Caption=不存在不小于&key&的元素EndIf可以，但缺乏美感！不可以，出现死循环！不可以，出现死循环！不可以，枚举出现遗漏！1.被查找的数据（满足条件的解）必须是有序的。2.不仅仅要找到满足条件的解，而且要找到最优解，因此不能中途跳出循环，而是要等到循环正常结束后才能确认找到的解为最优解。3.根据最优解在序列中的位置，可分为查找满足条件的最小值或最大值问题。五.对分查找最优解问题的特征例3.对分插入排序：先使用对分查找算法确定插入位置j，再向右移位腾出空位，插入待排序元素。请将缺失的代码补充完整。Constn=20Dima(0Ton)AsIntegerPrivateSubCommand3_Click()Fori=2Ton'插入排序tmp=a(i)j=BinarySearch(tmp,1,i-1)'确定插入位置jFork=iToj+1Step-1a(k)=a(k-1)Nextka(j)=NextiEndSubtmp1,2,2,2,3,4,5,6,2对分查找返回第一个大于key的元素位置‘对分查找返回第一个大于key的元素位置，L和R分别代表待查找区域的左右边界FunctionBinarySearch(ByValkeyAsInteger,ByValLAsInteger,ByValRAsInteger)AsIntegerDimmAsIntegerDoWhileL=Rm=(L+R)\2Ifa(m)keyThenR=ElseL=EndIfLoopBinarySearch=EndFunctionL‘或R+1m-1m+1已知数组a(1ton)为非递减序列，输出最后一个不大于key的元素下标，若a(1)key，则输出0。可推广到求满足条件的最大值问题（解区间的最大值）。六.对分查找最优解问题基本模型二PrivateSubCommand1_Click()key=Val(Text2.Text)L=1:R=nDoWhileL=RIfThen‘L位于解区间，寻找更优解L=L+1Else‘此时L-1指向最优解ExitDoEndIfLoopPrintEndSubPrivateSubCommand2_Click()key=Val(Text2.Text)L=1:R=nDoWhileL=RIfThen‘R位于非解区间，寻找最优解R=R-1Else‘此时R指向最优解ExitDoEndIfLoopPrintEndSuba(L)=keyL-1a(R)keyR顺序查找：从左向右扫描顺序查找：从右向左扫描模型一：已知数组a(1ton)为非递减序列，输出第一个不小于key的元素下标，若a(n)key，则输出n+1。可推广到求满足条件的最小值问题（解区间的最小值）。二者在解区间的分布、算法思想和代码结构上均具有对称性！！我们可以重点研究“求满足条件的最小值问题”的算法思想和代码结构，再通过对称性原理，自行推导出“求满足条件的最大值问题”的代码。两类基本模型比较：模型二：已知数组a(1ton)为非递减序列，输出最后一个不大于key的元素下标，若a(1)key，则输出0。可推广到求满足条件的最大值问题（解区间的最大值）。已知数组a(1ton)为非递减序列，输出最后一个不大于key的元素下标，若a(1)key，则输出0。可推广到求满足条件的最大值问题（解区间的最大值）。六.对分查找最优解问题基本模型二PrivateSubCommand3_Click()key=Val(Text2.Text)L=1:R=nDoWhileL=Rm=(L+R)\2IfThen‘m位于解区间，寻找更优解Else‘m位于非解区间，寻找最优解EndIfLoopPrintEndSuba(m)=keyR‘或L-1R=m-1L=m+1能否写做m=(L+R+1)\2?问题的关键不在于m左偏还是右偏，而在于：1.不能出现死循环，即不能出现L或R原地不动的情况。2.枚举不能出现遗漏，即m要能指向所有可能的位置。已知数组a(1ton)为非递减序列，输出最后一个不大于key的元素下标，若a(1)key，则输出0。下列代码段能实现该功能，但部分语句有错误，请改正。七.模型二变式PrivateSubCommand4_Click()key=Val(Text2.Text)L=1:R=nDoWhileLRm=(L+R+1)\2Ifa(m)=keyThen'm位于解区间，寻找更优解L=m'L指向最优解ElseR=m-1'R指向最优解EndIfLoopPrintR‘能否写做PrintL？EndSubPrivateSubCommand4_Click()key=Val(Text2.Text)L=1:R=nDoWhileLRm=(L+R)\2Ifa(m)=keyThen'm位于解区间，寻找更优解L=m+1'L-1指向最优解ElseR=m'R-1指向最优解EndIfLoopPrintR-1EndSubL=0R=n+1例2.用二分查找的方法求不等式2^x+3*x-5=n(n=0)的最大正整数解，编写VB程序如下：PrivateSubCommand1_Click()DimnAsInteger,xAsInteger,LAsInteger,RAsIntegern=Val(Text1.Text):L=1:R=n+1DoWhile①x=(L+R)\2If2^x+3*x-5=nThenL=x+1ElseR=x-1LoopLabel1.Caption=方程的最大正整数解为：+②EndSub要使程序实现上述算法思想，则方框中的语句是（）A①LR②Str(L)B①LR②Str(R)C①L=R②Str(L)D①L=R②Str(R)D当n=0时，最优解为1，故最大的可能解R=n+1Python算法之旅：《对分查找算法模型分类及示例分析》例3.已知数组a的长度为n，其元素按照非递减序排列，请编写程序查找与给定值key最接近的元素值，若有2个值满足条件，则输出较小值。下列代码能实现相关功能，请将缺失的代码补充完整：PrivateSubCommand1_Click()key=Val(Text1.Text):L=1:R=nIfkey=a(L)Thenans=a(L)ElseIfkey=a(R)Thenans=a(R)ElseDoWhileL=Rm=(L+R)\2Ifa(m)keyThenL=m+1ElseR=m–1LoopIfa(L)-keykey-a(R)Thenans=①Elseans=②EndIfLabel1.Caption=最接近的元素：&ansEndSub①a(L)，②a(R)Key=3610,20，30,40，50,60例4.已知数组a的长度为n，其元素按照非递减序排列，请编写程序查找与给定值key最接近的元素值，若有2个值满足条件，则输出较小的值。请将缺失的代码补充完整：