初中信息技術(shù)-Python編程-算法-【分治算法查卡片】

1、初中信息技術(shù)Python編程一一算法【分治算法查卡片】在現(xiàn)實生活中，我們經(jīng)常會遇到一些查找問題，如從書架上找圖書如從衣 柜中找襯衣等。這些問題一般規(guī)模較小，用窮舉法就可以快速解決。信息世界里的問題規(guī)模要大很多，如在10億個網(wǎng)頁中查找包含單詞 Python的網(wǎng)頁，這時我們就需要找到更為高效的方法來縮短查找時間，提高 效率。分治算法那么是解決這類問題的高效算法之一。在本工程中，我們將一起探索基于分治算法的程序設(shè)計。分治算法的核心思想是分而治之。采用分治算法，可以逐步縮小問題的求 解范圍，從而加快問題的求解速度。通過本節(jié)的學習，你將掌握以下技能：*理解用分治算法查找的過程*學會用分治算法設(shè)計程序，提

2、高查找效率 專題一：邏輯推演抽查游戲?qū)W校開展親子閱讀活動，李明同學完成閱讀任務之后，媽媽會填寫一張李 明當天完成任務情況的計分卡并保存，爸爸會在每個月初檢查上個月李明的閱 讀任務完成情況。檢查時，爸爸會隨機指定一個日期（如29）,然后查看與它對 應的計分卡是否存在。假設(shè)每月的計分卡都是按照日期從小到大順序排放的，如何編寫一段程序 模擬快速查找呢?A. 1 B, 25 C. 26 D. 513、列表 nums=3 , 20 , 31 , 39,42 , 50 , 58 , 65中,最后一個元素的 序號是（）。A. 8 B. 7 C.O D.94、歹U表colors：red,yellow”,blu

3、e,“green”white”,中間有幾個元素暫時不知道，如何得到最后一個元素的序號？請用Python代碼語句表示。通過紙卡查找游戲，探尋分治算法的過程，結(jié)合親子閱讀抽查，推演分治 算法的邏輯程序。體驗紙卡游戲有9張疊放在一起的紙卡，從上到下編號依次為19 ,隨機指定其中 一個紙卡編號x ,比一比看誰能更快地找到它，看一看誰的方法與眾不同。在數(shù)量較少的情況下，分治算法的優(yōu)勢并不明顯?，F(xiàn)在把紙卡的數(shù)量擴大 到200個,還是自上而下依次從1到200進行編號，并隨機指定紙卡編號X。 請再次嘗試，看誰的查找方法速度更快。討論:在有9張卡片的情況下，如果x=7: :1 ,依次翻過前6張紙卡，直到第7次找

4、到目標紙卡，這種方法效率高嗎？為什1么？ ：2.在中間位置抽取1張紙卡，發(fā)現(xiàn)它的編號為5 ,應該繼續(xù)往上找還是往下：找？為什么？ 推演算法邏輯紙卡的尋找過程可以概括為在有序列表中查找指定值，親子閱讀抽查也屬于同類問題。這類問題一般分為兩種情況：如果可以找到目標值，求解結(jié)果為目標值在列表中的序號；如果無法找到目標值，求解結(jié)果返回-1。假設(shè)8月份李明共獲得12張計分卡，日期從小到大依次為1、5、7、8、12、15、18、21、27、29、30、31,李明媽媽已經(jīng)從1到12編好序號，李明 爸爸抽查的日期為X。如果x=29 ,將查找范圍的起始序號記作a、結(jié)束序號記作b ,中位序號記作m （ m的值等于

5、a, b平均數(shù)的整數(shù)局部），分治算法的執(zhí)行過程如下列圖所示。xs29標具為10由9 ：目標值為29時的查找過程在查找過程中：初始情況下（區(qū)域）,查找范圍為112。由于x取值大于中位元素值（m對應的列表項），查找范圍折半，取右側(cè)（ 區(qū)域），繼續(xù)查找。依次類推，直到查找范圍縮減為10-10 （區(qū)域）此時，x取值等于中位討論 如果x=7 ,分治算法的執(zhí)行過程是怎樣的?元素，確認求解結(jié)果為10。專題二：編程實現(xiàn)快速查找定義一個名為search的函數(shù)來實現(xiàn)分治算法。編寫分治算法函數(shù)代碼.自定義函數(shù)。為分治算法設(shè)計一個名稱為search的自定義函數(shù)，包括cards、X兩個輸 入?yún)?shù)。出cards對應升序列

6、表，x對應整數(shù)查找目標。.設(shè)置查找范圍。用a、b表示起始、結(jié)束序號，賦值代碼如下：a=lb=len（cards）- 1說明：Python中列表序號是從0開始的，但我們棄用0號元素，所以a的初值為 lo b的初值等于最后一個元素序號，即len（cards）-l。（a+b）2計算獲得中位序號。 是整除運算符號。.逐級分割查找范圍，縮小查詢規(guī)模。如果起始序號不大于結(jié)束序號，那么cards中取中位序號m對應的值 cardsm與x進行比擬。如果x等于cardsm,代表找到目標，返回mo如果x小于cardsm,令結(jié)束序號b等于m-1 ,往前尋找（折半取左側(cè)）。如果x大于cardsm,令開始序號a等于m+1

7、，往后尋找（折半取右側(cè)）。如果在cards中無法找到x ,那么返回程序代碼如下:123456789101112131415#search函數(shù)程序def search(cards=listx=int):a=lb=len(cards)-l#逐級分割查找范圍，縮小查詢規(guī)模while a = b:m=(a+b)/2print(m=Jm) #跟蹤中位序號 if x=cardsm:return melif x0:I print（“抽查日期的序號為:y）print（“恭喜，可獲得神秘禮物”）else:print （“抽查日期“，r不存在”）print。本月沒有神秘禮物，下月繼續(xù)努力哦！）在程序中：首先準備原

8、始數(shù)據(jù)，存儲在列表d中對應8月份李明的閱讀記分卡（棄用 0號元素，卡片編號從1開始），對應抽查日期。調(diào)用search函數(shù)，把列表d傳遞給參數(shù)cards，把r傳遞給參數(shù)x ,將返 回結(jié)果賦值給變量y0如果y大于0 ,證明在列表d中找到了抽查日期r,顯示序號；否那么，顯 示不存在。2.3運行完整程序，交流查詢結(jié)果觀察執(zhí)行結(jié)果，可以發(fā)現(xiàn)中位序號m的取值以及最終的求解結(jié)果，跟前文 邏輯推演情況完全一致034567891011121314151617181920212223242526#search函數(shù)程序def search(cards=listJx=int):a=lb=len(cards)-l#逐級

9、分割查找范圍，縮小查詢規(guī)模while a = b:m=(a+b)/2print(,m=,m) #跟蹤中位序號if x=cardsm: return m elif x, r）if y0:print（抽查日期J的序號為:y）prirrt（“恭喜，可獲得神秘禮物”）else:print （抽查日期二r不存在”）print（“本月沒有神秘禮物，下月繼續(xù)努力哦！ “）控制臺m= 6m= 9m= 11m= 10抽查Id期29的序號為10 恭喜,可獲得神秘禮物 程序運行結(jié)束請將查找目標r的值依次修改為7、28并執(zhí)行程序，觀察執(zhí)行結(jié)果與你的 邏輯推演情況是否一致。拓展閱讀分治算法執(zhí)行效率分析執(zhí)行一個算法所耗費

10、的時間，必須上機運行測試才能知道，但它的值與算 法中語句的執(zhí)行次數(shù)成正比，哪個算法中語句執(zhí)行次數(shù)少，耗費時間就少，耗 費時間較少的算法執(zhí)行效率高。同學們上面所學的分治算法，通常被稱作二分查找算法，也叫作折半查找 算法，是最為典型的一種分治算法，其優(yōu)點是執(zhí)行效率比擬高，缺點是對列表 有特殊要求（列表必須是有序排列的）。二分查找算法每次循環(huán)可以將查找規(guī)?？s小一半。當問題規(guī)模足夠大時， 如在2017年全國4442.06萬初中在校生中查找某個身份證號，最差的情況下 （在列表中不存在）循環(huán)比照次數(shù)不超過30次，與窮舉算法的4442.06萬次 相比，效率的提升是顯而易見的。鞏固與提高1、關(guān)于分治算法的說法錯誤的選項是（）。A.采用分治算法，可以逐步縮小問題的求解范圍B.二分查找法要求