資源簡介 4.3 《非數(shù)值計算—二分查找》任務(wù)單學(xué)校_________ 班級________ 姓名______________學(xué)習(xí)目標(biāo)1.了解算法設(shè)計中的分治思想。2.運用二分查找解決實際問題。3.體驗二分查找算法解決實際問題的過程。游戲體驗:誰是“臥底”游戲規(guī)則:從十三張撲克牌中抽取七張,七位同學(xué)每人手里一張紙牌,按A—K排序,其中一人手里有一張紙牌做了明顯標(biāo)記,看誰能最快選中“臥底”?項目 :新品上市,猜定價“贏”棉衣活動1.寒冬將至,某公司正在推出一款棉衣,為促進棉衣的銷售,成功打入市場,現(xiàn)舉行猜定價“贏”棉衣的活動。價格范圍在1—400元之間。看看哪位同學(xué)能以最快的速度猜出棉衣的實際定價。知識點:二分查找法二分查找又叫折半查找,將數(shù)列有序排列,采用跳躍式查找數(shù)據(jù);以遞增數(shù)列為例,先以中點位置的元素作為比較對象,如果要找的元素值小于該中點元素,則將待查序列縮小為左半部分,否則為右半部分;每一次比較后都可以將查找區(qū)間縮小一半。二分查找法是一種高效的查找方法。它可以明顯減少比較次數(shù),提高查找效率。在一個有n個元素的有序序列中,利用二分查找大約需要_____次,但是,二分法查找的前提條件是被查找的數(shù)據(jù)必須是_________。活動2:根據(jù)流程圖補充代碼并調(diào)試運行程序。x=int(input("請輸入要查找的400以內(nèi)的整數(shù):"))step=0flag1=1flag2=400while(flag1<=flag2):mid=(flag1+flag2)//2step=step+1if___________:flag2=__________elif midflag1=__________else:breakprint("查找次數(shù)為:",step)input("運行完畢,請按回車鍵退出...")拓展練習(xí)1.若提示還是高了,則第三次猜12,依次類推;……。這種每次縮小一半查找范圍而達到迅速確定目標(biāo)的算法稱為( )。A.排序法 B.順序查找法 C.解析法 D.二分查找法2.二分查找又稱折半查找,是一種應(yīng)用于有序數(shù)列的高效查找算法。下列數(shù)列中適合二分查找算法的是( )A.85 78 59 53 19 18B.67 62 68 4 1 17C.11 99 4 25 3 39D.43 71 78 81 6 553.小I在閱覽室讀到了有趣的故事:國王有18枚金幣,其中摻進去一枚較輕的假幣,要求數(shù)學(xué)家使用一個沒有砝碼的天平三次找到假幣。如果你是數(shù)學(xué)家,如何按照要求找到假幣?課后反思(共11張PPT)4.3 非數(shù)值計算— 二分查找框架完整·扁平化呈現(xiàn)·絕對專業(yè)·超級吸睛游戲:誰是“臥底”游戲規(guī)則:七位同學(xué)每人手里一張紙牌,按A—K排序,其中一人手里有一張紙牌做了明顯標(biāo)記,看誰能最快選中“臥底”?項目:猜定價“贏”棉衣PROJECT PEOFILEPROJECT PEOFILE活動1.寒冬將至,某公司正在推出一款棉衣,為迎接雙11購物節(jié),成功打入市場,現(xiàn)舉行“猜定價,‘贏’棉衣”的活動。價格范圍在1—400元之間。看看哪位同學(xué)能以最快的速度猜出棉衣的實際定價。二分查找/折半查找 p101二分思想:將數(shù)列有序排列,采用跳躍的方式查找數(shù)據(jù)。分治策略將難以直接解決的大問題,分割成較小的同類問題方法:以遞增數(shù)列為例,以中點位置元素作為比較對象,若要查找元素值小于該中點元素,將待查找序列縮小為左半部分,否則為右半部分。每次比較后都能將查找區(qū)間縮小一半。找一半按照順序找一半,一比較,舍一半。繼續(xù)找一半,一半又一半,快速找答案!左邊界flag1右邊界flag2目標(biāo)數(shù)x中間數(shù)mid!!!若中間數(shù)mid比目標(biāo)數(shù)x大,則區(qū)間變?yōu)樽蟀雲(yún)^(qū)間,右邊界更新左邊界flag1右邊界flag2目標(biāo)數(shù)x中間數(shù)mid!!!若中間數(shù)mid比目標(biāo)數(shù)x小,則區(qū)間變?yōu)橛野雲(yún)^(qū)間,左邊界更新在有n個元素的有序序列中,利用二分查找大約需要log2n次。二分查找/折半查找 p101n = 1000 需要10次二分思想:將數(shù)列有序排列,采用跳躍的方式查找數(shù)據(jù)。活動2:補充代碼ABOUT US活動2.填充代碼,調(diào)試程序。x=int(input("請輸入要查找的400以內(nèi)的整數(shù):"))step=0flag1=1flag2=400while(flag1<=flag2):mid=(flag1+flag2)//2step=step+1if ①:flag2=②elif midflag1=③else:breakprint("查找次數(shù)為:",step)input("運行完畢,請按回車鍵退出...")① mid>x②mid-1③ mid+1在有序數(shù)組中查找某一特定元素的搜索方法。查找過程從數(shù)組的中間元素開始,如果中間元素正好是要查找的元素,則搜索過程結(jié)束;如果某一特定元素大于或小于中間元素,則在數(shù)組大于或小于中間元素的那一半中查找,重復(fù)前面的操作繼續(xù)從中間元素開始比較。二分法的使用規(guī)則凡治眾如治寡,分?jǐn)?shù)是也。——《孫子兵法》課堂小結(jié) 展開更多...... 收起↑ 資源列表 4.3 非數(shù)值計算.pptx 4.3非數(shù)值計算學(xué)案(第1課時)學(xué)案.docx 縮略圖、資源來源于二一教育資源庫