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

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

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

3、d+1 ，否則 flag_right=mid-1把待查序列一分為二進行判斷，如此周而復(fù)始，直到找出這個數(shù)。開始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#取新序列中點元素print(m

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

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

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

7、=mid+1開始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#取新序列中點元素print(mid)4、程序編寫的常見問題mid=(flag_left+flag_right)/2#取新序列中點元素print(mid)開始x!=midxmid