4.3非數(shù)值計(jì)算（第一課時(shí)） (1) 課件-高中信息技術(shù)必修1

1、高一年級(jí)教科版信息技術(shù)第四單元4.3非數(shù)值計(jì)算-分治策略與二分查找一、分治策略分治的設(shè)計(jì)思想，是將一個(gè)難以直接解決的大問(wèn)題，分割成一些較小的同類(lèi)問(wèn)題，各個(gè)擊破，最終達(dá)到解決問(wèn)題的目的。28=232322=884=256二、二分查找待查序列是有序的以待查序列中點(diǎn)位置元素作為比較對(duì)象如果小于中點(diǎn)位置元素，則將待查序列縮小為左半部分，否則為右半部分。把待查序列一分為二進(jìn)行判斷，如此周而復(fù)始，直到找出這個(gè)數(shù)。.flag_leftflag_right以遞增數(shù)列為例編寫(xiě)二分查找程序編程練習(xí)：X是一個(gè)100以?xún)?nèi)的正整數(shù)，請(qǐng)你使用二分查找編程找出X.mid=(flag_left+flag_right)/2fl

2、ag_leftflag_rightmid=(flag_left+flag_right)/2flag_leftflag_right如果 xmid:待查序列在中點(diǎn)位置元素的右邊待查序列為(mid+1,flag_right)if xmid:flag_left=mid+1以遞增數(shù)列為例.flag_leftflag_rightmid=(flag_left+flag_right)/2如果 xmid:待查序列在中點(diǎn)位置元素的左邊待查序列為(flag_left, mid-1)mid=(flag_left+flag_right)/2flag_leftflag_rightif xmid, flag_left=mi

3、d+1 ，否則 flag_right=mid-1把待查序列一分為二進(jìn)行判斷，如此周而復(fù)始，直到找出這個(gè)數(shù)。開(kāi)始x!=midxmidflag_left,flag_right,mid,x=?NNYY以遞增數(shù)列為例flag_left=mid+1flag_right=mid-1mid=(flag_left+flag_right)/2print(mid)結(jié)束while x!=mid:#執(zhí)行二分查找的條件 if xmid:flag_left=mid+1#左邊界調(diào)整 else:flag_right=mid-1#右邊界調(diào)整mid=(flag_left+flag_right)/2#取新序列中點(diǎn)元素print(m

4、id)程序編寫(xiě)的常見(jiàn)問(wèn)題mid=(flag_left+flag_right)/2#取新序列中點(diǎn)元素print(mid)x!=midxmid結(jié)束flag_left,flag_right,mid,x=?NNYYflag_left=mid+1flag_right=mid-1mid=(flag_left+flag_right)/2print(mid)開(kāi)始以遞增數(shù)列為例小結(jié)分治的設(shè)計(jì)思想，是將一個(gè)難以直接解決的大問(wèn)題，分割成一些較小的同類(lèi)問(wèn)題，各個(gè)擊破，最終達(dá)到解決問(wèn)題的目的。二分查找的數(shù)列必須有序。以遞增數(shù)列為例，先以中點(diǎn)位置元素作為比較對(duì)象，如果要找的元素值小于中點(diǎn)元素，則將待查序列縮小為左半部分，

5、否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。查找范圍比較對(duì)象1-100501-49251-241213-231813-171516-171、下列選項(xiàng)中不屬于使用分治特征的是（）A.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的同類(lèi)問(wèn)題B.子問(wèn)題的解可以合并為該問(wèn)題的解C.子問(wèn)題必須是一樣的D.子問(wèn)題之間不包含公共的子問(wèn)題1、下列選項(xiàng)中不屬于使用分治特征的是（ C）A.該問(wèn)題可以分解為若干個(gè)規(guī)模較小的同類(lèi)問(wèn)題B.子問(wèn)題的解可以合并為該問(wèn)題的解C.子問(wèn)題必須是一樣的D.子問(wèn)題之間不包含公共的子問(wèn)題解析：子問(wèn)題不必都一樣。性質(zhì)相同的子問(wèn)題即可。2.下列數(shù)列中適合二分查找算法的是（）A. 85785953

6、1918B. 6762684117C. 1199425339D. 437178816552.下列數(shù)列中適合二分查找算法的是（A）B. 6762684117C. 1199425339D. 43717881655A. 857859531918解析：二分查找的序列是有序的，只有A才是有序的。3、補(bǔ)全二分查找程序flag_ left = mid+1#左邊界調(diào)整mid=(flag_left+flag_right)/2#取新序列中點(diǎn)元素 print(mid)whilex!=mid:#執(zhí)行二分查找的條件 if xmid:flag_right=mid-1 #右邊界調(diào)整else:以遞減數(shù)列為例flag_left

7、=mid+1開(kāi)始x!=midxmid結(jié)束flag_left,flag_right,mid,x=?Nflag_right=mid-1NYYmid=(flag_left+flag_right)/2print(mid)while x!=mid:#執(zhí)行二分查找的條件 if xmid:flag_left=mid+1#左邊界調(diào)整 else:flag_right=mid-1#右邊界調(diào)整mid=(flag_left+flag_right)/2#取新序列中點(diǎn)元素print(mid)4、程序編寫(xiě)的常見(jiàn)問(wèn)題mid=(flag_left+flag_right)/2#取新序列中點(diǎn)元素print(mid)開(kāi)始x!=midxmid