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

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

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

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

4、rint(ijend= ,)print(“所有拍手數(shù)”)控制臺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 所有拍手數(shù) 程序運行結(jié)束在程序中：是取余運算，運算結(jié)果為兩數(shù)相除所得的余數(shù)。借助邏輯運算符“or”可以判斷多種情況。print默認輸出是換行的，如果要實現(xiàn)不換行需要在變量末尾加上end二一討論假設(shè)只需枚舉“暗7”，僅使用i%7=0并不能準確進行判斷，請討論還需要什么條;件來進行綜合判斷。I專題二：尋找水仙花數(shù)如果一個3位數(shù)等于其各位數(shù)字的立方和，那么稱這個數(shù)

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

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

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

8、尋找 答案?，F(xiàn)有足量的1克、2克、5克、10克祛碼，共允許取用40枚祛碼，現(xiàn)在有 100克食鹽，要求每種祛碼至少使用1枚，共有多少種稱量方案？L1分析問題，確定枚舉范圍枚舉對象可以確定為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)整?請說明原因。:I.如果要用for循環(huán)來構(gòu)造枚舉范圍，需要用幾重循環(huán)嵌套？： HYPERLINK l bookmark92 o Current Document 1L2確定枚舉條件，設(shè)計枚舉程序各種祛碼共計40枚，所以枚舉條件1為a+b+c+d=40o總質(zhì)量100克，所以枚舉條件2為10* a+5 x*b+2x*c+d=100o必須同時滿足1和2兩個條件才是正確的解決方案。請同學們動手，嘗試著編寫一下此程序吧。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)試運行調(diào)試運行枚舉程序，觀察結(jié)果。專題二：使用現(xiàn)代技術(shù)驗證古人智慧我國古代有很多經(jīng)典的數(shù)學問題，彰顯了中國人的智慧。公元5世紀末，我國古代數(shù)學家張丘建在算經(jīng)中有一道題：“雞翁一, 值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾 何？ ”意為：公雞每只5錢，母雞每只3錢，小雞3只工錢。用100

11、錢買100 只雞，問公雞、母雞、小雞各多少?分析問題，確定枚舉范公雞的數(shù)量x：最少1只，不超過20只。母雞的數(shù)量y：最少1只，不超過33只。小雞的數(shù)量z：最少3只，不超過100只。確定枚舉條件，設(shè)計枚舉程序一共需買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)控制臺s

12、ir d? eJT rx 又 rx.七二.hhh1111 周冬冬 8 14 1 18 147 8 8公雞：4母雞： 公雞：8母雞： 公雞：12母雞 程序運行結(jié)束2.3優(yōu)化程序，縮短運行時間以上程序雖然能求出結(jié)果，但仔細一想，用了三重循環(huán)，太耗時間了，能不 能有一種更好的解決方法呢？上面的條件還有優(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母雞 程序運行結(jié)束公雞：4母雞： 公雞：8母雞： 公雞：12母雞 程序運行結(jié)束1811：4GJ? .EJT .EJT rx rx. rxqI 1 亡 11 芻芻冬788184在程序中：print支持格式化輸出，d是格式化輸出整數(shù)。拓展閱讀枚舉法的基本思想：枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能狀態(tài)，并用問題給定的條 件檢驗?zāi)男┦切枰模男┦遣恍枰?。能使命題成立，即為其解。枚舉法的優(yōu)缺點：優(yōu)點：(1)由于枚舉算法一般是現(xiàn)實生活中問題的“直譯”，因此比擬直觀， 易于理解；(2

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

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

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

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

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

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

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

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

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

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

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

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

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

27、1小格1粒麥子，用2。表示；第2 小格2粒麥子，就用N表示；第3小格4粒麥子，就用22表示。依次類推，第64小格中的麥粒數(shù)就是263,總麥粒數(shù)自然就是20+21+22+263。根據(jù)每個格子中麥粒數(shù)的遞增規(guī)律，第n個格中的麥粒數(shù)為2自個，求n格中麥粒的總和，核心問題是:2+21+22+241的和。求乘方時，可以通過調(diào)用Python乘方函數(shù)pow()來幫助解決。髀Tn個格的麥?？倲?shù)程序from math import*#導入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、個格的和print(第2d格：d粒，當前總數(shù)%十%(301,s) #顯示過程數(shù)據(jù)print (當前d格尊共冰立“( k, s)控制臺前多少格？ 5第1格：工粒,當前總數(shù)1 第2格：2粒,當前總數(shù)3 第3格：4粒，當前總數(shù)7 第4格：8粒，當前總數(shù)15 第5格：16粒，當前總數(shù)31 當前5格總共31粒程序運行結(jié)束在程序中：from math import *語句是導入數(shù)學函數(shù)模塊，之后可直接使用里面的一些 數(shù)學函數(shù)。Input。默認接收到的是string類型，需使用int()函數(shù)把字符串型轉(zhuǎn)換為整 型。當前格的麥粒數(shù)是前一個格的2倍，這是一種迭代關(guān)系。計算前n個格的麥粒數(shù)時，可以用前n-1個格麥

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

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

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

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

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

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

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

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

37、長為成年兔，從 第3個月起一對成年免每個月都新生一對幼兔。每對兔子都經(jīng)歷這樣的出生、成 長、繁殖過程。假設(shè)所有兔子都不死，到第12個月時，該飼養(yǎng)場共有兔子多少 對？2.1迭代算法迭代算法的核心是通過將迭代表達式不斷重復(fù)執(zhí)行，用變量的舊值推出新值, 直到完成指定計算。#用迭代法求兔子數(shù)列#幼兔和成年兔第i月當月的數(shù)量分別用a、b表示a=l #幼兔第1月當月的數(shù)量(單位：對)b=0 #成年兔第1月當月的數(shù)量(單位：對)print(第 %d 個月兔子共 %d 對“(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個月兔子共計%d對“%(i,a+b)控制臺對對對對對又第1個月兔子共1 第2個月兔子共計 第3個月兔子共計 第4個月兔子共計 第5個月兔子共計 第6個月兔子共計 第7個月兔子共計 第8個月兔子共計 第9個月兔子共計 第10個月兔子共計 第11個月兔子共計 第12個月兔子共計 程序運行結(jié)束2.2遞歸算法兔子數(shù)列形如1, 1, 2, 3, 5, 8, 13, 21,34如果設(shè)f(i)為該數(shù)列的第i項,當i大于2時，f(i)的值是f(i-l)+f(i-2)。通過定義遞歸函數(shù)完成數(shù)列的推算，代碼例如如下圖。選擇

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

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

41、修改判斷條件，修改較多比擬麻煩。使 用自定義函數(shù)，可以屢次調(diào)用，簡捷、高效。1 #多人跳遠成績判斷程序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名學生的成績12 m = int(input(請輸入初一男生立定跳遠成績(單位：厘米)：”)13 print(等級：:f(m) #調(diào)用函數(shù)時參數(shù)m的值傳入函數(shù)內(nèi)部進行應(yīng)用控制臺請輸入初一男生立定跳遠成績(單位：厘米)：

42、100 等級：不及格請輸入初一男生立定跳遠成績(單位：厘米)：220 等級：優(yōu)秀請輸入初一男生立定跳遠成績(單位：厘米)：200 等級：良好請輸入初一男生立定跳遠成績(單位：厘米)：口鞏固與提高1、反復(fù)調(diào)用(引用)自身直到某個條件匹配的算法是()A.排序算法B.分治算法C.迭代算法D.遞歸算法2、以下函數(shù)名中不正確的選項是()A. abc() B. alb2c3() C. 123_abc D. abc_123()3、參考累乘問題的程序設(shè)計，使用遞歸算編寫一個程序，解決 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)實生活中，我們經(jīng)常會遇到一些查找問題，如“從書架上找圖書“從衣 柜中找襯衣等。這些問題一般規(guī)模較小，用窮舉法就可以快速解決。信息世界里的問題規(guī)模要大很多，如在10億個網(wǎng)頁中查找包含單詞Python 的網(wǎng)頁，這時我們就需要找到更為高效的方法來縮短查找時間，提高效率。分 治算法那么是解決這類問題的高效算法之一。在本工程中，我們將一起探索基于分治算法的程序設(shè)計。分治算法的核心思想是分而治之。采用分治算法，可以逐步縮小問題的求解 范圍，從而加快問題的求解速度。通過本節(jié)的學習，你將掌握以下技能：*理解用分治

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

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

46、月份李明共獲得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的值等于a、b平均數(shù)的整數(shù)局部），分治算法的執(zhí)行過程如以下圖所示。=1, bsl2, e=6標果為10目標值為29時的查找過程在查找過程中：初始情況下（區(qū)域），查找范圍為112。由于x取值大于中位元素值（m對應(yīng)的列表項），查找范圍折半，取右側(cè)（ 區(qū)域），繼續(xù)查找。依次類推，直到查找范圍縮減為1010 （區(qū)域）此時，x取值等于中位元 素，確認求解結(jié)果為

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

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

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

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

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

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

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

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

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