初中信息技術(shù)-Python編程-第五單元-【用算法讓程序更高效】

1、第五單元用算法讓程序更高效在現(xiàn)實(shí)生活中，當(dāng)我們要完成任務(wù)時(shí)，需要考慮應(yīng)該先做什么后做什么，每 個(gè)決定都將影響整個(gè)任務(wù)的進(jìn)度和效率。這些看似生活和學(xué)習(xí)生活中才會(huì)出現(xiàn)的 情況，其實(shí)在計(jì)算機(jī)編程時(shí)也會(huì)遇到。在利用計(jì)算機(jī)根據(jù)實(shí)際需要處理問題時(shí), 人們一直在試圖尋找更高效的方法，當(dāng)前我們可以使用枚舉、迭代、遞歸、分治 燈算法進(jìn)行程序設(shè)計(jì)從而更高效地尋找到各種問題的解決方案。算法是程序設(shè)計(jì) 的靈魂，完美高校的算法一直是程序設(shè)計(jì)者們努力追求的目標(biāo)。通過本章的學(xué)習(xí)，你將能夠掌握：算法的基本概念以及流程圖的使用枚舉算法迭代算法遞歸算法分治算法微工程1流程圖描述算法日常生活中，我們經(jīng)常面臨一些問題的困擾。例如，課

2、桌內(nèi)圖書較多時(shí)，應(yīng) 如何擺放才能做到存取自如;組織班級(jí)活動(dòng)時(shí)，大家如何分工協(xié)作才能更好地完 成任務(wù);如何合理安排時(shí)間，才能更高效地完成作業(yè)，等等。這些問題都可以歸 結(jié)為算法問題。算法在人們生活中發(fā)揮著重要作用，它不僅可以解決眼前的各種具體問題, 還能夠幫助我們發(fā)現(xiàn)問題解決的規(guī)律。通過本節(jié)的學(xué)習(xí)，你將掌握以下技能：通過生活案例體驗(yàn)算法的用途，了解算法的基本概念掌握算法有什么特點(diǎn)與用途學(xué)會(huì)用算法解決計(jì)算機(jī)問題，并能用流程圖描述算法專題一：用算法提高效率探究生活中的算法同學(xué)們?cè)谶@個(gè)年齡已經(jīng)能夠幫助父母做一一些力所能及的家務(wù)活了，如炒菜、 泡茶等。有一些家務(wù)活做下來，往往需要經(jīng)歷一個(gè)相對(duì)復(fù)雜的過程，這

3、其中是否有方123456#明7”判斷程序n=100for i in range(ln+l):if 7 in str(i):print(i,end=) print(以上為明7數(shù)字”)控制臺(tái)7 17 27 37 47 57 67 70 71 72 73 74 75 76 77 78 79 87 97 以上為明 7教字程序運(yùn)行結(jié)束3.增加條件，同時(shí)判斷“暗7”。不僅要判別出“明7”，還要判斷“暗7”，即找出被7整除的數(shù)。借助if 語句添加條件，就可以同時(shí)判斷是否是“暗7。123456#明7判斷程序n=100for i in range(ln+l):if 7 in str(i) or i%7=0: p

4、rint(ijend= ,)print(“所有拍手?jǐn)?shù)”)控制臺(tái)7 14 17 21 27 28 35 37 42 47 49 56 57 63 67 70 71 72 73 74 75 76 77 78 79 84 87 91 97 98 所有拍手?jǐn)?shù) 程序運(yùn)行結(jié)束在程序中：是取余運(yùn)算，運(yùn)算結(jié)果為兩數(shù)相除所得的余數(shù)。借助邏輯運(yùn)算符“or”可以判斷多種情況。print默認(rèn)輸出是換行的，如果要實(shí)現(xiàn)不換行需要在變量末尾加上end二一討論假設(shè)只需枚舉“暗7”，僅使用i%7=0并不能準(zhǔn)確進(jìn)行判斷，請(qǐng)討論還需要什么條;件來進(jìn)行綜合判斷。I專題二：尋找水仙花數(shù)如果一個(gè)3位數(shù)等于其各位數(shù)字的立方和，那么稱這個(gè)數(shù)

5、為水仙花數(shù)。例如:153 = 1A3 + 5A3 + 3A3,因此153就是一個(gè)水仙花數(shù)。請(qǐng)嘗試補(bǔ)全下面程序代碼中缺少的枚舉范圍和判定條件，借助枚舉算法尋找 1000以內(nèi)的水仙花數(shù)。for i in range(l,10):#枚舉百位for j in rang():#枚舉十位for k in rang():#枚舉個(gè)位x=i*100+j*10+kif ：#判定條件print(x)在程序中：可使用“*”運(yùn)算符完成幕運(yùn)算，如2*3=8。請(qǐng)嘗試輸入以上程序，并查看運(yùn)行結(jié)果，體驗(yàn)枚舉算法的神奇和計(jì)算機(jī)強(qiáng)大 的計(jì)算能力。拓展閱讀枚舉在數(shù)學(xué)中的應(yīng)用枚舉算法起源于原始的計(jì)數(shù)方法，即數(shù)數(shù)。當(dāng)我們面臨的問題存在大

6、量的可能答案(或中間過程)而暫時(shí)又無法用邏輯方 法排除這些可能答案中的大局部時(shí)，就不得不采用逐一檢驗(yàn)這些答案的策略，也 就是利用枚舉算法來解題。鞏固與提高1、從所有候選答案中搜索正確結(jié)果，來解決問題的算法是()A.排序算法B.枚舉算法C.遞歸算法D.迭代算法2、在程序中，循環(huán)結(jié)構(gòu)通過()函數(shù)控制枚舉范圍。A. print( ) B. range( ) C. str( ) D. input()3、()是取余運(yùn)算，運(yùn)算結(jié)果為兩數(shù)相除所得的余數(shù)。A. %B./ C. 4-D./4、一個(gè)五位數(shù)，其中兩個(gè)數(shù)字被遮擋了，變成了 15-2,這五位數(shù) 是36的倍數(shù)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序，輸出所有滿足條件的數(shù)。for

7、 i in range():for j in range(X=(3)ifprint(x)微工程3稱重方案我來列經(jīng)過上一節(jié)的學(xué)習(xí)，我們已經(jīng)了解了什么是枚舉算法，并能用枚舉算法來求 解一些簡單的問題，在本工程中，我們將繼續(xù)研究枚舉算法，通過進(jìn)一步對(duì)枚舉 對(duì)象、范圍、條件的構(gòu)造，深入理解枚舉算法解決問題的思想。本工程學(xué)習(xí)過程中請(qǐng)重點(diǎn)分析枚舉算法擅長解決哪一類問題，并嘗試編寫 枚舉算法的程序來解決實(shí)際問題。通過本節(jié)的學(xué)習(xí)，你將掌握以下技能：*能準(zhǔn)確確定枚舉對(duì)象、枚舉范圍和判定條件*能夠利用枚舉算法程序解決實(shí)際問題。專題一：列舉可行的稱重方案日常生活中，一些問題的解決往往具有多種方案組合，可以用枚舉算法

8、尋找 答案?，F(xiàn)有足量的1克、2克、5克、10克祛碼，共允許取用40枚祛碼，現(xiàn)在有 100克食鹽，要求每種祛碼至少使用1枚，共有多少種稱量方案？L1分析問題，確定枚舉范圍枚舉對(duì)象可以確定為4種質(zhì)量的祛碼。每種祛碼至少使用1枚，因此數(shù)量都 不小于1,以以下出大概取值范圍。用a表示10克祛碼的枚數(shù)，大概取值范圍是1 10。用b表示5克祛碼的枚數(shù)，大概取值范圍是20。用c表示2克祛碼的枚數(shù)，大概取值范圍是140。用d表示1克硅碼的枚數(shù)，大概取值范圍是40。 TOC o 1-5 h z HYPERLINK l bookmark19 o Current Document 討論;.每種祛碼枚數(shù)的取值范圍是否

9、可以調(diào)整?請(qǐng)說明原因。:I.如果要用for循環(huán)來構(gòu)造枚舉范圍，需要用幾重循環(huán)嵌套？： HYPERLINK l bookmark92 o Current Document 1L2確定枚舉條件，設(shè)計(jì)枚舉程序各種祛碼共計(jì)40枚，所以枚舉條件1為a+b+c+d=40o總質(zhì)量100克，所以枚舉條件2為10* a+5 x*b+2x*c+d=100o必須同時(shí)滿足1和2兩個(gè)條件才是正確的解決方案。請(qǐng)同學(xué)們動(dòng)手，嘗試著編寫一下此程序吧。12345678910#祛碼稱量方案程序j=0 #記錄稱量方案數(shù)量for a in rangeClll):#10克硅碼的范圍for b in range(l, 21): #5克磋

10、碼的范圍for c in range(l, 41): #2克注碼的范圍for d in range(l)41): #1 克祛碼的范圍if a+b+c+d=40 and 10*a+5*b+2*c+d=100:print(a,b,c,d) #輸出稱量方案III J+=lprint(j)調(diào)試運(yùn)行調(diào)試運(yùn)行枚舉程序，觀察結(jié)果。專題二：使用現(xiàn)代技術(shù)驗(yàn)證古人智慧我國古代有很多經(jīng)典的數(shù)學(xué)問題，彰顯了中國人的智慧。公元5世紀(jì)末，我國古代數(shù)學(xué)家張丘建在算經(jīng)中有一道題：“雞翁一, 值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾 何？ ”意為：公雞每只5錢，母雞每只3錢，小雞3只工錢。用100

11、錢買100 只雞，問公雞、母雞、小雞各多少?分析問題，確定枚舉范公雞的數(shù)量x：最少1只，不超過20只。母雞的數(shù)量y：最少1只，不超過33只。小雞的數(shù)量z：最少3只，不超過100只。確定枚舉條件，設(shè)計(jì)枚舉程序一共需買100只雞，所以枚舉條件1為x+y+z=100總共有100錢，所以枚舉條件2為5*x+3*y+z/3= 100#百錢買百雞for x in range(l,20):for y in range(l,33):for z in range(1100):if x+y+z=100 and 5*x+3*y+z/3=100:print(公雞：%d 母雞：%d 雛雞：%dH%(x,y,z)控制臺(tái)s

12、ir d? eJT rx 又 rx.七二.hhh1111 周冬冬 8 14 1 18 147 8 8公雞：4母雞： 公雞：8母雞： 公雞：12母雞 程序運(yùn)行結(jié)束2.3優(yōu)化程序，縮短運(yùn)行時(shí)間以上程序雖然能求出結(jié)果，但仔細(xì)一想，用了三重循環(huán)，太耗時(shí)間了，能不 能有一種更好的解決方法呢？上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉兩種雞(X, y),第三種雞就可以根據(jù)約束條件求得(z=100-x-y),這樣就縮小了枚舉范圍。#百錢買百雞*優(yōu)化for x in range。，20):for y in range(l,33):4if 5*x+3*y+(100-x-y)/3=100:5pri

13、nt(公雞：%d 母雞：%d 雛雞：%d”%(x,y,：L00-x-y)公雞：4母雞： 公雞：8母雞： 公雞：12母雞 程序運(yùn)行結(jié)束公雞：4母雞： 公雞：8母雞： 公雞：12母雞 程序運(yùn)行結(jié)束1811：4GJ? .EJT .EJT rx rx. rxqI 1 亡 11 芻芻冬788184在程序中：print支持格式化輸出，d是格式化輸出整數(shù)。拓展閱讀枚舉法的基本思想：枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能狀態(tài)，并用問題給定的條 件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的。能使命題成立，即為其解。枚舉法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：(1)由于枚舉算法一般是現(xiàn)實(shí)生活中問題的“直譯”，因此比擬直觀， 易于理解；(2

14、)由于枚舉算法建立在考察大量狀態(tài)，甚至是窮舉所有狀態(tài)的基礎(chǔ) 上，所以算法的正確性比擬容易證明；缺點(diǎn)：枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)，因此效率比擬低枚舉算法的優(yōu)化：枚舉算法的時(shí)間復(fù)雜度為狀態(tài)總數(shù)*單個(gè)狀態(tài)的耗時(shí)。(1)提取有效信息；(2)減少重復(fù)計(jì)算；(3)將原問題化為更小的問題；(4)引進(jìn)其他算法。鞏固與提高1、(多項(xiàng)選擇題)要使用枚舉算法，首先要確定()。A.枚舉對(duì)象B.枚舉范圍C.驗(yàn)證結(jié)果D.判斷條件2、枚舉1100的程序如下，請(qǐng)?zhí)顚憆ange函數(shù)的參數(shù)。n=100 for i in range():print(i)3、箱子里有紅、黃、綠三種顏色的小球，其中紅球5

15、個(gè)，黃球3個(gè)，綠球10個(gè)。每次從箱子里拿出12個(gè)小球，采用枚舉算法設(shè)計(jì)程序并調(diào)試運(yùn)行，得出小 球的所有顏色搭配情況。提示：紅球取值范圍05,黃球取值范圍03,綠球取值范圍010o微工程4運(yùn)動(dòng)量化做比擬生活中存在著許多迭代現(xiàn)象，如民間游戲疊羅漢、蕩秋千的過程中就蘊(yùn)含著 迭代?！暗痹跐h語詞典中解釋為“更替、輪換”。而在編程中，迭代是用舊值 重復(fù)推出新值的過程。每一-次迭代得到的結(jié)果會(huì)作為下一次迭代的初始值，如 此一步步逼近所尋求的目標(biāo)或得到需要的結(jié)果。在本工程中，我們將一起應(yīng)用迭代算法探究數(shù)據(jù)序列的變化規(guī)律，通過觀察 數(shù)據(jù)累加的迭代算法，分析迭代過程，觀察迭代關(guān)系，體驗(yàn)迭代功能，揭開迭 代算法

16、的神秘面紗。通過本節(jié)的學(xué)習(xí)，你將掌握以下技能：理解什么是迭代算法能夠快速準(zhǔn)確確實(shí)定迭代變量和迭代關(guān)系式學(xué)會(huì)用循環(huán)結(jié)構(gòu)程序控制迭代過程能夠利用迭代算法解決實(shí)際問題專題一：觀察數(shù)據(jù)累加的迭代算法迭代的本質(zhì)但凡對(duì)代碼的重復(fù)執(zhí)行都叫作“迭代”嗎？那可不一定！需要看這個(gè)重復(fù)的過程是否運(yùn)用了前面迭代的結(jié)果來依次求出 后面的迭代結(jié)果。用鍵盤輸人100個(gè)數(shù)不是迭代算法，輸人過程中同步求出已經(jīng) 輸入數(shù)的和就可以采用迭代的方式一個(gè)一個(gè)累加。觀察數(shù)據(jù)中的累加規(guī)律跳繩是一項(xiàng)簡單易行的體育運(yùn)動(dòng)。為了增強(qiáng)體質(zhì)，甲乙兩位同學(xué)各自制訂 了循序漸進(jìn)的鍛煉方案。甲同學(xué)決定第一天跳繩100下，第二天開始每天增加5下。乙同學(xué)也決定第

17、一天跳繩100下，以后每隔一天增加10下。兩位同學(xué)按照上述方案鍛煉30天，各自的總運(yùn)動(dòng)量是多少下?看看誰的總運(yùn) 動(dòng)量大。請(qǐng)觀察比擬甲乙兩位同學(xué)的訓(xùn)練日志，討論第5天兩人各自的跳繩數(shù)是多少、 前5天誰的總運(yùn)動(dòng)量大。乙同學(xué)訓(xùn)練日志第一天：100第二天：100第三天：110第四天:.甲同學(xué)訓(xùn)練日志第一天：100第二天:105第三天：110第四天:初步設(shè)計(jì)迭代算法程序.模擬第一次迭代?？紤]簡單的情況，用程序計(jì)算前三天每人的運(yùn)動(dòng)量。用順序結(jié)構(gòu)設(shè)計(jì)程序就 非常容易實(shí)現(xiàn)。甲同學(xué)每天的跳繩次數(shù)（用a表示）：Al=100#第 1 天a2=al+5#第 2 天a3=a2+5#第 3 天可見，甲同學(xué)當(dāng)天的數(shù)量是前一

18、天數(shù)量加5,每天的結(jié)果迭代了前一天的數(shù) 量。乙同學(xué)每天的跳繩次數(shù)（用b表示）：bl=100 #第 1 天b2=bl #第 2 天b3=b2+10 #第 3 天可見，乙同學(xué)當(dāng)天的數(shù)量是前一天數(shù)量不變或再加10,且均間隔一天出現(xiàn)， 雖然增加的數(shù)量不同，但最終結(jié)果也是迭代了前面的數(shù)量。.體驗(yàn)迭代算法程序。把上面的程序語句連起來,再進(jìn)行數(shù)據(jù)輸出，三天的總運(yùn)動(dòng)量就能計(jì)算出來。請(qǐng)調(diào)試下面的程序，并找出迭代的程序代碼行，體會(huì)迭代的思想。#用順序結(jié)構(gòu)求解運(yùn)動(dòng)量程序#甲同學(xué)每天的跳繩次數(shù) TOC o 1-5 h z al=100#第1天a2=al+5#第2天a3=a2+5#第3天#乙同學(xué)每天的跳繩次數(shù)bl=10

19、0#第1天b2=bl#第2 天b3=b2+10#第3 天10 print（甲同學(xué)3天共跳繩：1al+a2+a3J下”）11 print （乙同學(xué)3天共跳繩：:bl+b2+b3, ”下）控制臺(tái)甲同學(xué)3天共跳繩：315下 乙同學(xué)3天共跳繩：310下 程序運(yùn)行結(jié)束嘗試?yán)^續(xù)編寫程序計(jì)算前10天的跳繩總數(shù)量，程序需要編寫多少行？討論:怎樣編寫程序能提高迭代算法的效率。專題二：用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)自動(dòng)迭代使用順序結(jié)構(gòu)描述迭代雖然直觀，但編程及程序運(yùn)行效率低。當(dāng)?shù)螖?shù)較 多時(shí)，使用順序結(jié)構(gòu)就顯得力不從心。可以嘗試采用循環(huán)結(jié)構(gòu)程序?qū)崿F(xiàn)迭代算法，累計(jì)跳繩總數(shù)。在構(gòu)造循環(huán)結(jié)構(gòu) 程序之前，需要分析出迭代關(guān)系，這樣才能設(shè)

20、計(jì)出相應(yīng)的迭代程序。2.1分析數(shù)據(jù)的迭代關(guān)系1.每天的跳繩數(shù)迭代關(guān)系。甲乙兩位同學(xué)每天的跳繩數(shù)規(guī)律比擬好找，在順序程序設(shè)計(jì)中已經(jīng)有體驗(yàn), 其迭代關(guān)系式可如下表示：甲同學(xué)每天跳繩數(shù)量迭代關(guān)系式：ai=ai-i+5 （i=2）乙同學(xué)每天跳繩數(shù)量迭代關(guān)系式：apai-i （i為偶數(shù)，i=2）和ai=ai-i+10 （i為 法、經(jīng)驗(yàn)可以總結(jié)呢?例如，炒菜從準(zhǔn)備到完成，通常包括擇菜、洗菜、切菜、熱鍋、放食用油、 放香料、加菜、翻炒、放鹽、出鍋等環(huán)節(jié)。討論：I.舉例說明，炒不同菜品的每個(gè)環(huán)節(jié)的時(shí)間、順序是否相同?其中有需要?jiǎng)h減或增加;的環(huán)節(jié)嗎？，.討論在泡茶的“洗茶具、燒水、泡茶”流程中，可以有哪些不同順

21、序，怎樣統(tǒng)籌;實(shí)施才更節(jié)約時(shí)間？那么，泡茶有哪些環(huán)節(jié)呢？我們發(fā)現(xiàn)，雖然炒不同菜品的各個(gè)環(huán)節(jié)、時(shí)序不盡相同，但要做出色香味俱 全的菜品，都要掌握一定的操作方法與步驟。這些操作方法與步驟就是生活中的 “算法”。算法通過調(diào)整、優(yōu)化可以提高效率。例如，當(dāng)要炒的菜品種類較多時(shí)， 可以統(tǒng)籌安排、優(yōu)化過程，既節(jié)約時(shí)間，又能保證菜品的質(zhì)量。1.2根據(jù)生活法那么探究算法的價(jià)值在工作和生活中，人們會(huì)利用經(jīng)驗(yàn)積累、專項(xiàng)研究等方式，總結(jié)形成一些法 那么，用來提高工作效率。下面以“37%法那么”為例，體會(huì)算法的作用。假設(shè)有多人申請(qǐng)一個(gè)學(xué)生會(huì)的職位，而你是面試官。你不知道如何評(píng)分，但是可以判斷 誰更優(yōu)秀。每次只能面試一個(gè)

22、人且不允許重復(fù)面試，要當(dāng)場做出是否錄用的判斷，一旦選定 某個(gè)人那么面試結(jié)束。過早或過晚終止遴選程序，都可能錯(cuò)過優(yōu)秀的人選，從而讓遴選工作無 法得到理想結(jié)果。你將如何選擇？如何選定一個(gè)優(yōu)秀的面試者，看起來并無章法可循。數(shù)學(xué)家們憑借多年的研 究卻給出了一個(gè)相對(duì)有效的選擇方案，這就是37%法那么。要選定優(yōu)秀的面試者, 需要一個(gè)“觀察”期，在這段時(shí)間通過觀察、收集很多數(shù)據(jù)，為做出最終選擇提 供依據(jù)。隨著面試者人數(shù)不斷增加，當(dāng)觀察的面試者人數(shù)到達(dá)總數(shù)的37%之后, 只要出現(xiàn)一位比前面所有面試者優(yōu)秀的人選，就要毫不猶豫地選擇他。這是數(shù)學(xué) 家們通過概率分析給出的最正確方案。無數(shù)事實(shí)證明，這個(gè)法那么能夠有效地

23、提高 奇數(shù)，i=3)2.當(dāng)天的跳繩累計(jì)總數(shù)迭代過程。每人跳繩總數(shù)如下圖。由此圖很容易發(fā)現(xiàn)其計(jì)算規(guī)律是以前的總數(shù)加當(dāng)天的數(shù)量；如，甲同學(xué)跳繩總數(shù)的迭代關(guān)系式為Xi=XML+ai(i=2) o2.2分析迭代過程的程序代碼根據(jù)迭代關(guān)系，就能找到可以重復(fù)執(zhí)行的過程，即可迭代的過程。1.每天的跳繩數(shù)迭代過程。甲同學(xué)第一天跳繩100下，第2天開始每天增加5下；乙同學(xué)第一天跳繩 100下，每隔一天增加10下。用a表示甲同學(xué)每天的跳繩數(shù)，b表示乙同學(xué)每 天的跳繩數(shù)。每天的跳繩數(shù)迭代過程為：a=a+5#甲同學(xué)每天都增加5次if i%2=l:#當(dāng)前天數(shù)為奇數(shù)時(shí)b=b+10#乙同學(xué)的跳繩次數(shù)增加102.新一天的跳繩

24、累計(jì)總數(shù)迭代過程。用x表示新一天甲同學(xué)的總跳繩數(shù)，y表示新一天乙同學(xué)的總跳繩數(shù)，新一 天的跳繩累計(jì)總數(shù)迭代關(guān)系為：x=x+ay=y+b由此，我們用a、b、x、y四個(gè)變量描述這個(gè)過程，建立了兩組迭代過程的 程序代碼。這四個(gè)變量都稱作迭代變量。在迭代過程中，它們不斷由舊值推出新 值。2.2用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)自動(dòng)迭代可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來確定在什么時(shí)候結(jié)束迭代過程，在此過程中 應(yīng)用迭代公式讓迭代變量自動(dòng)迭代，計(jì)算出結(jié)果。運(yùn)行完整的迭代程序，體驗(yàn)迭代的過程。計(jì)算出n天后甲、乙兩位同學(xué)各自 的總運(yùn)動(dòng)量，比擬誰的運(yùn)動(dòng)量更大、誰的訓(xùn)練更加科學(xué)。#跳繩總量的計(jì)算程序a=100 #甲同學(xué)第1天跳繩次數(shù)b=10

25、0 #乙同學(xué)第1天跳繩次數(shù)x=a #甲同學(xué)第1天累計(jì)跳繩次數(shù)y=b #乙同學(xué)第1天累計(jì)跳繩次數(shù)n=30#跳繩總天數(shù)for i in range（2,n+l）: #從第2天開始迭代計(jì)算a=a+5#甲同學(xué)每天都增加5次if i%2=l: #當(dāng)前天數(shù)為奇數(shù)時(shí)|b=b+10#乙同學(xué)的跳繩次數(shù)增加10次x=x+a#甲同學(xué)跳繩的累計(jì)次數(shù)y=y+b#乙同學(xué)跳繩的累計(jì)次數(shù)print（“甲同學(xué)”，nJ天跳繩1x,下）print （“乙同學(xué)，n，“天跳繩“，y J下”）控制臺(tái)甲同學(xué)30天跳繩5175下 乙同學(xué)30天跳繩5100下程序運(yùn)行結(jié)束專題三：Python中數(shù)學(xué)函數(shù)的使用在印度民間流傳著一個(gè)有趣的故事。據(jù)說，

26、印度的舍罕王打算獎(jiǎng)賞國際象棋 的創(chuàng)造人一一宰相西薩班達(dá)依爾。國王問他想要什么，他對(duì)國王說：“陛下，請(qǐng) 您在這張棋盤的第1個(gè)格中，賞給我1粒麥子，在第2個(gè)小格子里給2粒，第 3個(gè)小格里給4粒，以后每一小格都比前一小格多1倍。請(qǐng)您如此這般擺滿棋盤 上所有64格的麥粒，都賞給我吧！”國王覺得宰相的這個(gè)要求太容易滿足了，就 下令賞給他這些麥粒。當(dāng)人們把一袋袋麥粒搬來開始如數(shù)擺放時(shí)，國王這才發(fā)現(xiàn): 就是把全印度的麥粒都拿來，也滿足不了那位宰相的要求。任意前n個(gè)棋盤格的麥?？倲?shù)到底需要多少麥粒呢？要算出總數(shù)，先要知道每個(gè)格子中的麥粒數(shù)。故事中，有一句很關(guān)鍵的話“每 一小格都比前一小格多一倍”。也就是說，第

27、1小格1粒麥子，用2。表示；第2 小格2粒麥子，就用N表示；第3小格4粒麥子，就用22表示。依次類推，第64小格中的麥粒數(shù)就是263,總麥粒數(shù)自然就是20+21+22+263。根據(jù)每個(gè)格子中麥粒數(shù)的遞增規(guī)律，第n個(gè)格中的麥粒數(shù)為2自個(gè)，求n格中麥粒的總和，核心問題是:2+21+22+241的和。求乘方時(shí)，可以通過調(diào)用Python乘方函數(shù)pow()來幫助解決。髀Tn個(gè)格的麥?？倲?shù)程序from math import*#導(dǎo)入math膜塊s=0k=int(input(前多少格？)for n in range(l,k+l):m=int(pow(2g,n-l)# 調(diào)用 pow()函數(shù)s+=m#累加求前n

28、個(gè)格的和print(第2d格：d粒，當(dāng)前總數(shù)%十%(301,s) #顯示過程數(shù)據(jù)print (當(dāng)前d格尊共冰立“( k, s)控制臺(tái)前多少格？ 5第1格：工粒,當(dāng)前總數(shù)1 第2格：2粒,當(dāng)前總數(shù)3 第3格：4粒，當(dāng)前總數(shù)7 第4格：8粒，當(dāng)前總數(shù)15 第5格：16粒，當(dāng)前總數(shù)31 當(dāng)前5格總共31粒程序運(yùn)行結(jié)束在程序中：from math import *語句是導(dǎo)入數(shù)學(xué)函數(shù)模塊，之后可直接使用里面的一些 數(shù)學(xué)函數(shù)。Input。默認(rèn)接收到的是string類型，需使用int()函數(shù)把字符串型轉(zhuǎn)換為整 型。當(dāng)前格的麥粒數(shù)是前一個(gè)格的2倍，這是一種迭代關(guān)系。計(jì)算前n個(gè)格的麥粒數(shù)時(shí)，可以用前n-1個(gè)格麥

29、粒數(shù)的和再加上第n個(gè)格 的麥粒數(shù)，這也是一種迭代關(guān)系。print(第d格：%d粒，當(dāng)前總數(shù)d%(n, m, s)語句采用了輸出格式。%d 表示輸出最右邊之后的對(duì)應(yīng)整數(shù)或整數(shù)變量。%2d是將整數(shù)按寬度2,采用右 對(duì)齊方式輸出，假設(shè)數(shù)據(jù)位數(shù)不到2位，那么左邊補(bǔ)空格。討論查閱資料，討論麥粒總數(shù)計(jì)算的公式，如整個(gè)棋盤的麥粒總數(shù)可以用264；計(jì)算。這是數(shù)學(xué)推導(dǎo)公式，將用到高年級(jí)才能涉及的數(shù)學(xué)知識(shí)，此處僅作討論。3.2計(jì)算前n格麥?？倲?shù)的質(zhì)量假如一粒麥粒大約0.01克，棋盤麥粒問題中如何預(yù)計(jì)前n格共多少千克或 多少噸麥粒呢？請(qǐng)學(xué)習(xí)小組討論思考，補(bǔ)全下面的程序，并嘗試調(diào)試程序，完成計(jì)算。from math

30、import* # 導(dǎo)入 math 模塊s=0k=int(input(前多少格?)for n in range(l, k+1):m= int(pow(2, n-1)s=s+m#累加求和print(第d格:%d粒，當(dāng)前總數(shù)d%(n, m, s)#顯示過程數(shù)據(jù)al=s*0.01#計(jì)算多少克a2=al/1000 #計(jì)算多少千克a3=#計(jì)算多少噸if alc=a, b, c, dt=iter(c)#iter用列表c創(chuàng)立一個(gè)迭代器對(duì)象tprint(next()#next調(diào)用迭代器對(duì)象ta print(next(t) b如果獲取了最后一個(gè)數(shù)據(jù)，再次調(diào)用next。函數(shù)會(huì)出現(xiàn)Stopiteration的異常。

31、迭代器是用來幫助我們記錄每次迭代訪問到的位置，當(dāng)我們對(duì)迭代器使用 next。函數(shù)的時(shí)候，迭代器會(huì)向我們返回它所記錄的下一個(gè)位置的數(shù)據(jù)。鞏固與提高1、以下關(guān)于迭代算法的描述正確的選項(xiàng)是()A.但凡對(duì)代碼的重復(fù)執(zhí)行都叫做“迭代B.輸入10個(gè)6是迭代算法C.在迭代算法中，每一次迭代得到的結(jié)果不一定作為下一次迭代的初始值D.輸入10個(gè)數(shù)，輸入過程中同步求出已經(jīng)輸入的數(shù)的和，可以采取迭代的方式 一個(gè)一個(gè)累加。2、Python內(nèi)置函數(shù)中，表示乘方的函數(shù)是()A. pow() B. abs() C. max() D. min()3、求1至U 100的和，即1+2+3+4+99+100=?請(qǐng)完善程序并上機(jī)運(yùn)行

32、。思考：（1）迭代變量是什么？（2）迭代關(guān)系式是什么？s=ofor in range()print (s)（3）如何控制迭代過程？微工程5兔子總數(shù)有多少你有沒有站在兩面相對(duì)的鏡子中間，嘗試一下同時(shí)照兩面鏡子會(huì)出現(xiàn)什么情 景？鏡子里會(huì)有千百個(gè)“你”，而真實(shí)的你只有一個(gè)，那千百個(gè)“你”都來源于 你的存在，這是一種“遞歸”現(xiàn)象。生活中應(yīng)用遞歸思想的例子也有很多，如益智玩具九連環(huán)、漢諾塔等。在本工程中，我們將圍繞遞歸算法的程序?qū)崿F(xiàn)，探究遞歸的基本工作機(jī)制, 嘗試優(yōu)化程序。在程序設(shè)計(jì)中，使用遞歸算法通常需要定義遞歸函數(shù)，通過對(duì)該函數(shù)的調(diào)用 來獲得最終解。通過本節(jié)的學(xué)習(xí)，你將掌握以下技能：了解遞歸思想的基

33、本思路和運(yùn)行過程掌握遞歸函數(shù)的定義方法會(huì)用遞歸算法解決實(shí)際問題專題一：跟蹤遞歸的運(yùn)行過程通過將問題重復(fù)分解為同類的子問題來解決問題的方法，稱為遞歸。常見的遞歸都是經(jīng)過屢次分解把問題轉(zhuǎn)化為有直接解法的特殊情況，得到解 后再回歸到更大問題求解，最終得到較大或更大問題的答案。1.1遞歸過程下面通過一個(gè)累乘過程的數(shù)據(jù)跟蹤檢測小實(shí)驗(yàn)，來體會(huì)遞歸算法是如何工作 的。假設(shè)一個(gè)自然數(shù)n,累乘是將從1到n的所有自然數(shù)相乘，乘積m=lx2x3x4x5x.xno23456前前前前前前前前前前前前前積序 當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)當(dāng)乘程n=n=乘乘乘乘乘乘m=運(yùn)7 6 5 4 3 2工八八八八八八 , 1、 二 二 i

34、- - 1- - - 1- - - 1束 結(jié) 一仃1 #用遞歸累乘def fact(n):#自定義函數(shù)prirrtC當(dāng)前n) #跟蹤顯示n,可省略if n=l:#終止條件return1#結(jié)束遞歸else:#遞歸條件f=n*fact(n-l) #調(diào)用遞歸print(”當(dāng)前乘積：”、)#跟蹤顯示累乘的積return f #返回乘積10 print(乘積巾=:fact(7) #調(diào)用遞歸控制臺(tái)在程序中：deffact(n)是自定義函數(shù)的頭部，定義以下縮進(jìn)的程序完成特定功能。n是 函數(shù)的參數(shù)。自定義函數(shù)可以利用print語句顯示其執(zhí)行結(jié)果，也可以在表達(dá)式運(yùn)算中 使用。通過程序的運(yùn)行，觀察變量跟蹤檢測點(diǎn)的

35、設(shè)置及數(shù)據(jù)變化，會(huì)發(fā)現(xiàn)求解過 程如下：fact(7)7* fact(6)7*(6* fact(5)7*(6* fact(5* fact(4)7*(6* fact(5* fact(4* fact(3)7*(6* fact(5* fact(4* fact(3*fact(2)7*(6* fact(5* fact(4* fact(3* fact(2* fact(l)然而，計(jì)算累乘的過程卻是按2*1再到3*2、4*6這樣的順序進(jìn)行的。討論1 ,遞歸中，自定義函數(shù)如何深入展開?2 ,數(shù)據(jù)運(yùn)算順序有何特點(diǎn)？1.2遞歸算法的條件遞歸算法解決問題的核心在于遞歸函數(shù)的構(gòu)建。程序運(yùn)行時(shí)，由于遞歸函數(shù) 不斷調(diào)用自身，

36、如果沒有設(shè)置終止條件，遞歸調(diào)用會(huì)形成無限循環(huán)。規(guī)范的遞歸函數(shù)必須由兩個(gè)條件組成：終止條件和遞歸條件。符合終止條件 終止函數(shù)調(diào)用，符合遞歸條件那么函數(shù)繼續(xù)調(diào)用自身。遞歸函數(shù)的規(guī)范形式如下：def函數(shù)名（參數(shù)列表）:if條件表達(dá)式：#終止條件語句return值（或表達(dá)式）#可省略else:#遞歸條件包含自身函數(shù)名（參數(shù)列表）的語句遞歸函數(shù)的終止條件和遞歸條件，沒有固定的先后順序，只要保證具備這兩 個(gè)條件即可。專題二：探究遞歸算法的優(yōu)勢使用遞歸優(yōu)化程序，會(huì)讓程序代碼變得直觀簡潔、一目了然。著名的斐波那契數(shù)列，又稱為兔子數(shù)列，因以兔子繁殖為例而得名。某飼養(yǎng)場引進(jìn)一對(duì)剛出生的新品種兔子，這種兔子第2個(gè)月

37、長為成年兔，從 第3個(gè)月起一對(duì)成年免每個(gè)月都新生一對(duì)幼兔。每對(duì)兔子都經(jīng)歷這樣的出生、成 長、繁殖過程。假設(shè)所有兔子都不死，到第12個(gè)月時(shí)，該飼養(yǎng)場共有兔子多少 對(duì)？2.1迭代算法迭代算法的核心是通過將迭代表達(dá)式不斷重復(fù)執(zhí)行，用變量的舊值推出新值, 直到完成指定計(jì)算。#用迭代法求兔子數(shù)列#幼兔和成年兔第i月當(dāng)月的數(shù)量分別用a、b表示a=l #幼兔第1月當(dāng)月的數(shù)量(單位：對(duì))b=0 #成年兔第1月當(dāng)月的數(shù)量(單位：對(duì))print(第 %d 個(gè)月兔子共 %d 對(duì)“(l,a+b)n=12#總月數(shù)for i in range(2n+l):t=b#先把上月成年兔數(shù)量存一下910910b=a+b#本月成年兔

38、數(shù)量;上月幼兔數(shù)量+成年兔數(shù)量a=t#本月新生幼兔數(shù)量=上月成年兔數(shù)量11prints第%d個(gè)月兔子共計(jì)%d對(duì)“%(i,a+b)控制臺(tái)對(duì)對(duì)對(duì)對(duì)對(duì)又第1個(gè)月兔子共1 第2個(gè)月兔子共計(jì) 第3個(gè)月兔子共計(jì) 第4個(gè)月兔子共計(jì) 第5個(gè)月兔子共計(jì) 第6個(gè)月兔子共計(jì) 第7個(gè)月兔子共計(jì) 第8個(gè)月兔子共計(jì) 第9個(gè)月兔子共計(jì) 第10個(gè)月兔子共計(jì) 第11個(gè)月兔子共計(jì) 第12個(gè)月兔子共計(jì) 程序運(yùn)行結(jié)束2.2遞歸算法兔子數(shù)列形如1, 1, 2, 3, 5, 8, 13, 21,34如果設(shè)f(i)為該數(shù)列的第i項(xiàng),當(dāng)i大于2時(shí)，f(i)的值是f(i-l)+f(i-2)。通過定義遞歸函數(shù)完成數(shù)列的推算，代碼例如如下圖。選擇

39、的正確率。討論：I!現(xiàn)實(shí)生活中還有哪些法那么可以指導(dǎo)我們的學(xué)習(xí)、生活。：I專題二：探究算法的應(yīng)用合理的算法能夠有效地幫助我們解決工作和生活中的問題。2.1圖書的分類存放.書庫圖書的分類存放。以三國演義為例，根據(jù)中國圖書館分類法，該書應(yīng)該歸屬于“社會(huì) 科學(xué)”“文學(xué)” “中國文學(xué)” “小說” “古代作品” “章回小說”類。為了方便圖書管理和讀者借閱，圖書館會(huì)按照預(yù)定規(guī)那么對(duì)每本圖書進(jìn)行編碼。 新書人庫時(shí)，圖書管理員會(huì)先完 成圖書編碼，再把它放置到規(guī)定位置。.圖書檢索。根據(jù)需求進(jìn)行初步觀察判斷 （或通過計(jì)算機(jī)查詢檢索）后,讀者 即可直接去相應(yīng)區(qū)域取書。由此可見，圖書館對(duì)圖書的分類存放就是一種良好的算

40、法，圖書館藏書分類書架 既能夠方便圖書的日常管理，也2.2網(wǎng)絡(luò)信息傳輸中的身份確認(rèn)算法在日常生活中，你給不熟悉的人打 的過程是怎樣的呢?最普遍的做法是, 先完成身份確認(rèn)，再進(jìn)行主題交流。#用遞歸算法求“兔子數(shù)列def f(n):if n=211:print （優(yōu)秀”）elif x=195:print （良好”）elif x=155:print （“及格”）else:print （不及格”）控制臺(tái)請(qǐng)輸入初一男生立定跳遠(yuǎn)成績（單位：厘米）：160 及格程序運(yùn)行結(jié)束2 .定義函數(shù)實(shí)現(xiàn)多人成績判斷。進(jìn)行多名學(xué)生成績判斷時(shí)，判斷條件要屢次重復(fù)使用，程序語句過多會(huì)出現(xiàn) 閱讀不便、程序冗長易出錯(cuò)等問題。如果

41、修改判斷條件，修改較多比擬麻煩。使 用自定義函數(shù)，可以屢次調(diào)用，簡捷、高效。1 #多人跳遠(yuǎn)成績判斷程序2 def f(x):345678910if x = 211:return 11 優(yōu)秀, elif x = 195:return 1,良好11elif x = 155:return 及格else:return ”不及格11 for i in range(ll):#主程序，判斷10名學(xué)生的成績12 m = int(input(請(qǐng)輸入初一男生立定跳遠(yuǎn)成績(單位：厘米)：”)13 print(等級(jí)：:f(m) #調(diào)用函數(shù)時(shí)參數(shù)m的值傳入函數(shù)內(nèi)部進(jìn)行應(yīng)用控制臺(tái)請(qǐng)輸入初一男生立定跳遠(yuǎn)成績(單位：厘米)：

42、100 等級(jí)：不及格請(qǐng)輸入初一男生立定跳遠(yuǎn)成績(單位：厘米)：220 等級(jí)：優(yōu)秀請(qǐng)輸入初一男生立定跳遠(yuǎn)成績(單位：厘米)：200 等級(jí)：良好請(qǐng)輸入初一男生立定跳遠(yuǎn)成績(單位：厘米)：口鞏固與提高1、反復(fù)調(diào)用(引用)自身直到某個(gè)條件匹配的算法是()A.排序算法B.分治算法C.迭代算法D.遞歸算法2、以下函數(shù)名中不正確的選項(xiàng)是()A. abc() B. alb2c3() C. 123_abc D. abc_123()3、參考累乘問題的程序設(shè)計(jì)，使用遞歸算編寫一個(gè)程序，解決 1+2+3+4+5+.+100=?的問題。Def add(n)If#終止條件return 1#結(jié)束遞歸else:住#調(diào)用遞歸p

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

44、算法查找的過程*學(xué)會(huì)用分治算法設(shè)計(jì)程序，提高查找效率專題一：邏輯推演抽查游戲?qū)W校開展親子閱讀活動(dòng)，李明同學(xué)完成閱讀任務(wù)之后，媽媽會(huì)填寫一張李明 當(dāng)天完成任務(wù)情況的計(jì)分卡并保存，爸爸會(huì)在每個(gè)月初檢查上個(gè)月李明的閱讀任 務(wù)完成情況。檢查時(shí)，爸爸會(huì)隨機(jī)指定一個(gè)日期（如29）,然后查看與它對(duì)應(yīng)的計(jì) 分卡是否存在。假設(shè)每月的計(jì)分卡都是按照日期從小到大順序排放的，如何編寫一段程序模 擬快速查找呢？通過紙卡查找游戲，探尋分治算法的過程，結(jié)合親子閱讀抽查，推演分治算 法的邏輯程序。體驗(yàn)紙卡游戲有9張疊放在一起的紙卡，從上到下編號(hào)依次為19,隨機(jī)指定其中一 個(gè)紙卡編號(hào)X,比一比看誰能更快地找到它，看一看誰的方法

45、與眾不同。在數(shù)量較少的情況下，分治算法的優(yōu)勢并不明顯?，F(xiàn)在把紙卡的數(shù)量擴(kuò)大到 200個(gè)，還是自上而下依次從1到200進(jìn)行編號(hào)，并隨機(jī)指定紙卡編號(hào)X。請(qǐng)?jiān)?次嘗試，看誰的查找方法速度更快。:討論；在有9張卡片的情況下，如果x=7：:L依次翻過前6張紙卡，直到第7次找到目標(biāo)紙卡，這種方法效率高嗎？為什么？：2.在中間位置抽取1張紙卡，發(fā)現(xiàn)它的編號(hào)為5,應(yīng)該繼續(xù)往上找還是往下找？為：什么？推演算法邏輯紙卡的尋找過程可以概括為在有序列表中查找指定值，親子閱讀抽查也屬 于同類問題。這類問題一般分為兩種情況：如果可以找到目標(biāo)值，求解結(jié)果為目 標(biāo)值在列表中的序號(hào)；如果無法找到目標(biāo)值，求解結(jié)果返回-1。假設(shè)8

46、月份李明共獲得12張計(jì)分卡，日期從小到大依次為1、5、7、8、12、 15、18、21、27、29、30、31,李明媽媽已經(jīng)從1到12編好序號(hào)，李明爸爸抽 查的日期為X。如果x=29,將查找范圍的起始序號(hào)記作a、結(jié)束序號(hào)記作b,中位序號(hào)記作 m（m的值等于a、b平均數(shù)的整數(shù)局部），分治算法的執(zhí)行過程如以下圖所示。=1, bsl2, e=6標(biāo)果為10目標(biāo)值為29時(shí)的查找過程在查找過程中：初始情況下（區(qū)域），查找范圍為112。由于x取值大于中位元素值（m對(duì)應(yīng)的列表項(xiàng)），查找范圍折半，取右側(cè)（ 區(qū)域），繼續(xù)查找。依次類推，直到查找范圍縮減為1010 （區(qū)域）此時(shí)，x取值等于中位元 素，確認(rèn)求解結(jié)果為

47、10。討論；如果x=7,分治算法的執(zhí)行過程是怎樣的？：I專題二：編程實(shí)現(xiàn)快速查找定義一個(gè)名為search的函數(shù)來實(shí)現(xiàn)分治算法。編寫分治算法函數(shù)代碼.自定義函數(shù)。為分治算法設(shè)計(jì)一個(gè)名稱為search的自定義函數(shù)，包括cards、X兩個(gè)輸入 參數(shù)。出cards對(duì)應(yīng)升序列表，x對(duì)應(yīng)整數(shù)查找目標(biāo)。.設(shè)置查找范圍。用a、b表示起始、結(jié)束序號(hào)，賦值代碼如下：a=lb=len（cards）-1說明：Python中列表序號(hào)是從0開始的，但我們棄用。號(hào)元素，所以a的初值為1。b 的初值等于最后一個(gè)元素序號(hào)，即len（cards）3 （a+b）2計(jì)算獲得中位序號(hào)。是整除運(yùn)算 符號(hào)。.逐級(jí)分割查找范圍，縮小查詢規(guī)模

48、。如果起始序號(hào)不大于結(jié)束序號(hào)，那么cards中取中位序號(hào)m對(duì)應(yīng)的值cardsm 與x進(jìn)行比擬。如果x等于cardsm,代表找到目標(biāo)，返回m。如果x小于cardsm,令結(jié)束序號(hào)b等于m-1,往前尋找（折半取左側(cè)）。如果x大于cardsm,令開始序號(hào)a等于m+1,往后尋找（折半取右側(cè)）。如果在cards中無法找到x,那么返回-1。程序代碼如下：#search函數(shù)程序def search(cards=listx=int):a=l456789101112131415456789101112131415b=len(cards)-l#逐級(jí)分割查找范圍，縮小查詢規(guī)模 while a = b:m=(a+b)/

49、2print(nm=,m) #跟蹤中位序號(hào)if x=cardsm:return melif xcardsm:b=m-lelse:a=m+lreturn -1 #找不到目標(biāo)，返回-12.2編寫主程序，應(yīng)用查找函數(shù)、，以親子閱讀為例，按照8月份李明的閱讀情況定義列表來存儲(chǔ)相應(yīng)的日期 數(shù)據(jù)，令查找目標(biāo)r=29,調(diào)用search函數(shù)，針對(duì)求解結(jié)果打印閱讀抽查情況。#查找主程序#d作為cards的原始數(shù)據(jù)。棄用0號(hào)元素，卡片編號(hào)從x開始d=-99,1,5,7,8,12,15,18,21,27,29,30,31r=29y=search（dr）if y0：Print（“抽查日期的序號(hào)為“,y）Print（“

50、恭喜，可獲得神秘禮物else:Print（抽查日期不存在IPrint（“本月沒有神秘禮物，下月繼續(xù)努力哦！ ）在程序中：首先準(zhǔn)備原始數(shù)據(jù)，存儲(chǔ)在列表d中對(duì)應(yīng)8月份李明的閱讀記分卡（棄用 。號(hào)元素，卡片編號(hào)從1開始），對(duì)應(yīng)抽查日期。調(diào)用search函數(shù)，把列表d傳遞給參數(shù)cards,把r傳遞給參數(shù)x,將返回結(jié)果賦值給變量y。如果y大于0,證明在列表d中找到了抽查日期r,顯示序號(hào)；否那么，顯 示不存在。2.3運(yùn)行完整程序，交流查詢結(jié)果觀察執(zhí)行結(jié)果，可以發(fā)現(xiàn)中位序號(hào)m的取值以及最終的求解結(jié)果，跟前文 邏輯推演情況完全一致。#search函數(shù)程序def search(cards=listJx=int)

51、:34567891011121314151617181920212223242526a=lb=len(cards)-l#逐級(jí)分割查找范圍，縮小查詢規(guī)模 while a = b:m=(a+b)/2print#跟蹤中位序號(hào)if x=cardsm: return m elif x, r）if y0:print（抽查日期J的序號(hào)為:y）prirrt（“恭喜，可獲得神秘禮物”）else:print （抽查日期: r J不存在）print（“本月沒有神秘禮物，下月繼續(xù)努力哦！ “）控制臺(tái)m= 6m= 9m= 11m= 10抽查日期29的序號(hào)為10 恭喜,可獲得神秘禮物 程序運(yùn)行結(jié)束請(qǐng)將查找目標(biāo)r的值依次修

52、改為7、28并執(zhí)行程序，觀察執(zhí)行結(jié)果與你的邏 輯推演情況是否一致。拓展閱讀分治算法執(zhí)行效率分析執(zhí)行一個(gè)算法所耗費(fèi)的時(shí)間，必須上機(jī)運(yùn)行測試才能知道，但它的值與算法 中語句的執(zhí)行次數(shù)成正比，哪個(gè)算法中語句執(zhí)行次數(shù)少，耗費(fèi)時(shí)間就少，耗費(fèi)時(shí) 間較少的算法執(zhí)行效率高。同學(xué)們上面所學(xué)的分治算法，通常被稱作二分查找算法，也叫作折半查找算 法，是最為典型的一種分治算法，其優(yōu)點(diǎn)是執(zhí)行效率比擬高，缺點(diǎn)是對(duì)列表有特 殊要求（列表必須是有序排列的）。二分查找算法每次循環(huán)可以將查找規(guī)模縮小一半。當(dāng)問題規(guī)模足夠大時(shí)，如 在2017年全國4442.06萬初中在校生中查找某個(gè)身份證號(hào)，最差的情況下（在 列表中不存在）循環(huán)比照

53、次數(shù)不超過30次，與窮舉算法的4442.06萬次相比， 效率的提升是顯而易見的。鞏固與提高1、關(guān)于分治算法的說法錯(cuò)誤的選項(xiàng)是（ ）oA.采用分治算法，可以逐步縮小問題的求解范圍B.二分查找法要求列表可以是無需排列的C,分支算法的核心思想是分而治之D.二分查找算法每次循環(huán)可以將查找范圍縮小一半2、商品猜價(jià)格游戲中，商品價(jià)格在151元之間（包括1元和51元）, 如果猜的價(jià)格大于真是價(jià)格，游戲提示“高了”，如果小于真實(shí)價(jià)格，游戲提示 “低了”。為了快速猜到價(jià)格，我們采用二分查找算法思想。那么第一次所采價(jià) 格應(yīng)該是（）元。A. 1 B. 25 C. 26 D. 513、列表nums=3, 20, 31

54、, 39, 42, 50, 58, 65中，最后一個(gè)元素的序號(hào) 是（）。A. 8 B. 7 C.O D.94、列表 colors=red,yellow,blue,greenwhite”,中間有幾個(gè)元素暫時(shí)不知道，如何得到最后一個(gè)元素的序號(hào)？請(qǐng)用Python代碼語句表示。打 .模擬打 中的身份確認(rèn)。你問：“你好，請(qǐng)問您是張Xx先生嗎？對(duì)方回答：“你好，我是，您是哪位?”你再問：“我是山東的XXX啊，方便請(qǐng)教一個(gè)問題嗎？”對(duì)方回答：“你好，可以的J.網(wǎng)絡(luò)傳輸身份確認(rèn)算法。我們使用互聯(lián)網(wǎng)應(yīng)用程序，如即時(shí)通信軟件、瀏覽器等，都需要通過網(wǎng)絡(luò)設(shè) 備進(jìn)行數(shù)據(jù)交換。進(jìn)行網(wǎng)絡(luò)信息傳輸時(shí)，都要遵循一定的規(guī)那么（協(xié)

55、議）進(jìn)行，如 在網(wǎng)絡(luò)上兩臺(tái)設(shè)備如果沒有相互進(jìn)行身份確認(rèn)就盲目發(fā)送數(shù)據(jù)，會(huì)造成數(shù)據(jù)喪失。嚴(yán)重的數(shù)據(jù)喪失將 導(dǎo)致聯(lián)系中斷，造成無法登錄網(wǎng)站、下載文件失敗、無法上網(wǎng)等。為了保證數(shù)據(jù)交換的可靠性，現(xiàn)在的網(wǎng)絡(luò)傳輸采用的是被稱為“三次握手” 的身份確認(rèn)算法。正如我們打 時(shí)的問候一樣，發(fā)送端說“你好”，接收端確 認(rèn)并回復(fù)“你好”，發(fā)送端對(duì)回復(fù)進(jìn)行確認(rèn)。如果接收端收到這第三條回復(fù)的消 息，那么不需要進(jìn)一步確認(rèn)，雙方就可以開始發(fā)送算法數(shù)據(jù)了。網(wǎng)絡(luò)傳輸?shù)摹叭挝帐帧笔疽鈭D接收端專題三：算法的特征及描述方式使用計(jì)算機(jī)解決問題，需要經(jīng)歷分析問題、設(shè)計(jì)算法、編寫代碼、運(yùn)行程序 四個(gè)主要階段。其中，算法設(shè)計(jì)是非常重要的一環(huán)。為保證能夠順利處理問題,就需要設(shè)計(jì)符合計(jì)算機(jī)規(guī)范的算法。3.1算法的基本特征.有窮性。一個(gè)算法必須在有限步驟內(nèi)結(jié)束，不能無限循環(huán)。.確定性。算法的每一個(gè)步驟必須具有確定含義，不能有任何歧義。.輸入、輸出。輸入的數(shù)據(jù)是算法加工處理的對(duì)象，輸出的數(shù)據(jù)是算法解決 問題的結(jié)果。一