經(jīng)典算法應(yīng)用同步復(fù)習(xí)課件-2024-2025學(xué)年教科版（2019）高中信息技術(shù)必修一

五、經(jīng)典算法應(yīng)用學(xué)科大概念二：算法目錄五、經(jīng)典算法應(yīng)用(一)解析算法(二)枚舉算法(三)二分查找算法(四)迭代算法(五)遞歸算法(六)算法的優(yōu)劣五、經(jīng)典算法應(yīng)用信息技術(shù)解析算法是指用解析的方法找出表示問(wèn)題的前提條件與結(jié)果之間關(guān)系的數(shù)學(xué)表達(dá)式，并通過(guò)表達(dá)式的計(jì)算來(lái)實(shí)現(xiàn)問(wèn)題求解。解析法解決問(wèn)題的步驟：分析問(wèn)題、抽象建模、解析表達(dá)式、解決問(wèn)題。解析式是用運(yùn)算符號(hào)和括號(hào)把數(shù)字和字母按一定規(guī)則連接成式子。比如利用海倫公式求三角形的面積等。知識(shí)梳理(一)解析算法知識(shí)梳理答案：x＝(v*v－v0*v0)/(2*a)或x＝(v**2－v0**2)/(2*a)枚舉算法又稱窮舉法，是一種最為直接，實(shí)現(xiàn)最為簡(jiǎn)單，同時(shí)又最為耗時(shí)的解決問(wèn)題的算法思想。通常采用“循環(huán)＋判斷”把所有可能的答案一一列舉，合適就保留，不合適就丟棄。?枚舉算法的三要素：枚舉對(duì)象、枚舉范圍和判斷條件。?枚舉解決問(wèn)題的一般結(jié)構(gòu)：循環(huán)＋判斷。其優(yōu)勢(shì)在于正確性容易證明。?枚舉算法的經(jīng)典應(yīng)用：百錢(qián)百雞和模糊數(shù)字。知識(shí)梳理(二)枚舉算法知識(shí)梳理【試一試】一張單據(jù)上有一個(gè)5位數(shù)的編碼，因?yàn)楸９懿簧?，其百位?shù)字已經(jīng)變得模糊不清，即為19？88，但知道這個(gè)數(shù)是2和3的倍數(shù)，有________個(gè)這樣的數(shù)。答案：3解析：百位上的數(shù)字可能為0—9十個(gè)數(shù)字，因?yàn)樵摂?shù)的末尾為8，所以肯定是2的倍數(shù)，只要對(duì)百位上的數(shù)據(jù)進(jìn)行枚舉(0—9)，如果該5位數(shù)各位數(shù)字之和為3的倍數(shù)，則滿足條件，滿足條件的數(shù)字是1，4和7。經(jīng)窮舉，這樣的數(shù)有19188，19488，19788三個(gè)數(shù)。二分查找又叫折半查找，主要將數(shù)列有序排列，采用跳躍式的方式查找數(shù)據(jù)。二分查找是一種高效的查找方法，可以明顯減少比較次數(shù)，提高查找效率。以遞增數(shù)列為例，先以中間位置的元素作為比較對(duì)象，如果要找的元素小于該中間位置的元素，則待查序列縮小為左半部分，如果大于該中間位置的元素，則為右半部分。每次比較后都可以將查找區(qū)間縮小一半，直至找到。知識(shí)梳理(三)二分查找算法知識(shí)梳理例如：在列表nums＝[1，7，10，13，29，37，57，71，97，100]中查找x＝10過(guò)程如下表所示。查找x＝10左邊界Left右邊界Right中間位置Mid比較x與nums[Mid]相應(yīng)操作第1輪09410<29Right＝Mid－1第2輪03110>7Left＝Mid＋1第3輪23210＝10查找成功！知識(shí)梳理注：①二分查找的前提條件是被查找的數(shù)據(jù)必須是有序的。②二分查找中左、右邊界的設(shè)置和調(diào)整很關(guān)鍵。此外，要注意二分查找條件的限定(Left<Right)。③二分查找的時(shí)間復(fù)雜度：對(duì)長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，所需時(shí)間最長(zhǎng)為O(log2n)。迭代法也稱輾轉(zhuǎn)法，每一次對(duì)過(guò)程的重復(fù)稱為一次“迭代”，而每一次迭代得到的結(jié)果用來(lái)作為下一次迭代的初始值，通常是為了接近并到達(dá)所需的目標(biāo)或結(jié)果。使用迭代算法解決問(wèn)題，有三個(gè)關(guān)鍵步驟：①確定迭代變量；②建立迭代關(guān)系式；③對(duì)迭代過(guò)程進(jìn)行控制。知識(shí)梳理(四)迭代算法典型例題【例1】猴子吃桃：一只猴子摘了若干桃子，每天吃現(xiàn)有桃子數(shù)的一半多一個(gè)，到第6天時(shí)就只剩下一個(gè)桃子，求原來(lái)一共有多少個(gè)桃子？#不要更改源程序結(jié)構(gòu)，刪除原題里的①②③。填寫(xiě)正確的代碼，完善程序。x＝1foriinrange(2，__①__)：x＝__②__print(x)答案：①7②(x＋1)*2解析：設(shè)第n天的桃子為xn，就是前一天的桃子的二分之一減去一，即xn＝xn－1/2－1，則使用后一天的桃子數(shù)推出前一天的桃子數(shù)的迭代關(guān)系式為xn－1＝(xn＋1)*2，現(xiàn)已知第6天的桃子數(shù)，求解第1天的桃子數(shù)，往前推算5次即可，所以循環(huán)次數(shù)為5次。遞歸是用于設(shè)計(jì)算法的一種思想方法，也是計(jì)算機(jī)科學(xué)中一個(gè)十分重要的概念。它通常是把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，通過(guò)構(gòu)建遞歸關(guān)系式，將解決小問(wèn)題作為解決大問(wèn)題的入口，由此，大問(wèn)題也就“迎刃而解”。知識(shí)梳理(五)遞歸算法知識(shí)梳理1.一個(gè)問(wèn)題能夠適用遞歸方法解決，必須符合兩個(gè)條件：(1)一個(gè)規(guī)模較大的問(wèn)題可以分解為若干性質(zhì)相同的規(guī)模較小的問(wèn)題，這些規(guī)模較小的問(wèn)題仍然可以進(jìn)一步分解，分解出的新問(wèn)題的解法和原問(wèn)題的解法相同，只是處理對(duì)象的規(guī)模不同。(2)必須有一個(gè)明確的結(jié)束遞歸的條件，不得無(wú)限遞歸。遞歸不僅僅是設(shè)計(jì)算法的一種思想方法，也是一種簡(jiǎn)化問(wèn)題的思維方式。典型例題【例2】已知n！＝1*2*3*......*(n－1)*n，利用遞歸法求5！。#不要更改源程序結(jié)構(gòu)，刪除原題里的①②③。填寫(xiě)正確的代碼，完善程序。x＝1deff(n)：ifn＝＝1：return__①__else：return__②__print(”5?。健保琠_③__)典型例題答案：①1②n*f(n－1)③f(5)解析：遞歸算法有重要的特點(diǎn)：(1)把規(guī)模較大的問(wèn)題分解為若干性質(zhì)相同的小問(wèn)題，構(gòu)建遞歸關(guān)系式f(n)＝n*f(n－1)；(2)必須有一個(gè)結(jié)束條件，當(dāng)n＝1時(shí)，n?。?；(3)遞歸包括遞推和回歸兩個(gè)過(guò)程(具體過(guò)程如圖所示)。知識(shí)梳理2.迭代和遞歸的關(guān)系①相同點(diǎn)：迭代算法與遞歸算法都需要重復(fù)執(zhí)行某些代碼。②不同點(diǎn)：迭代是重復(fù)反饋過(guò)程的活動(dòng)，其目的是逼近所需目標(biāo)或結(jié)果，通常使用計(jì)數(shù)器結(jié)束循環(huán)。遞歸是重復(fù)調(diào)用函數(shù)自身，遇到滿足終止條件的情況時(shí)逐層返回。知識(shí)梳理③迭代程序和遞歸程序可以等價(jià)轉(zhuǎn)換，以計(jì)算斐波那契數(shù)列第n項(xiàng)的值為例，程序間的轉(zhuǎn)換如下表所示：遞歸迭代deffib1(n)：#遞歸求Fibonacci數(shù)列的第n個(gè)數(shù)

ifn＝＝1orn＝＝2：

return1else：

returnfib1(n－1)＋fib1(n－2)deffib2(n)：#迭代求Fibonacci數(shù)列的第n個(gè)數(shù)f1＝f2＝1foriinrange(3，n＋1)：

f1，f2＝f2，f1＋f2returnf2同一問(wèn)題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法；一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮。1.時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。一般來(lái)說(shuō)，計(jì)算機(jī)算法是問(wèn)題規(guī)模n的函數(shù)f(n)，算法的時(shí)間復(fù)雜度也因此記做T(n)＝Ο(f(n))，因此，問(wèn)題的規(guī)模n越大，算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度(AsymptoticTimeComplexity)。知識(shí)梳理(六)算法的優(yōu)劣知識(shí)梳理2.空間復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間。其計(jì)算和表示方法與時(shí)間復(fù)雜度類(lèi)似，一般都用復(fù)雜度的漸近性來(lái)表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡(jiǎn)單得多。3.正確性算法的正確性是評(píng)價(jià)一個(gè)算法優(yōu)劣的最重要的標(biāo)準(zhǔn)。知識(shí)梳理4.可讀性算法的可讀性是指一個(gè)算法可供人們閱讀的容易程度。5.健壯性健壯性是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。典型例題【例3】素?cái)?shù)：(1)素?cái)?shù)又叫質(zhì)數(shù)，是指除了1與本身以外沒(méi)有其他因數(shù)的數(shù)，2是自然數(shù)中最小的素?cái)?shù)。(2)請(qǐng)?zhí)羁胀晟圃摮绦?，?shí)現(xiàn)功能：鍵盤(pán)輸入一個(gè)自然數(shù)n(n<1000)，輸出1至n范圍內(nèi)的所有素?cái)?shù)。n＝int(input(”輸入自然數(shù)n＝”))foriinrange(2，n＋1)：#枚舉范圍內(nèi)的每一個(gè)數(shù)字flag＝0forjinrange(2，__①__)：if__②__：#判斷i是否為素?cái)?shù)flag＝1__③__#退出循環(huán)ifflag＝＝0：print(i，end＝′′)典型例題答案：①i或int(i**0.5)＋1②i%j＝＝0③break解析：本程序通過(guò)窮舉法判斷2—n(使用變量i枚舉)中素?cái)?shù)，判斷i是否為素?cái)?shù)的標(biāo)準(zhǔn)是2—(i－1)(使用變量j枚舉)均不是i的約數(shù)，若j為i的約數(shù)，則標(biāo)識(shí)flag賦值為1，并跳出循環(huán)(break)，所以②的答案為i%j＝＝0，③的答案為break，①的答案為i，這個(gè)程序的運(yùn)行時(shí)間為3*10－7s。程序優(yōu)化：因?yàn)橐粋€(gè)數(shù)的因數(shù)是成對(duì)出現(xiàn)的，其中一個(gè)因數(shù)在開(kāi)方后的前面，一個(gè)在開(kāi)方后的后面，所以只需判斷它前面的數(shù)就可以了，這樣①的答案可以為int(i**0.5)＋1，這樣修改之后程序的運(yùn)行程序?yàn)?*10－7s，從時(shí)間復(fù)雜度角度考慮，第二個(gè)算法更優(yōu)。程序進(jìn)一步優(yōu)化方案：因?yàn)?—n中，有近一半的偶數(shù)，除2以外，其他的偶數(shù)均不為素?cái)?shù)，所以可以先去除偶數(shù)再進(jìn)行判斷，但是該方案需要修改程序結(jié)構(gòu)，不采用。典型例題【例4】輸入已知三角形三條邊的長(zhǎng)a，b，c，利用海倫公式s＝sqrt(p*(p－a)*(p－b)*(p－c))[其中p為半周長(zhǎng)，即p＝(a＋b＋c)/2]求三角形面積。該算法屬于()A.枚舉算法B.遞歸算法C.迭代算法D.解析算法答案：D解析：本題考查的是解析算法。解析算法為在分析具體問(wèn)題的過(guò)程中，抽取出一個(gè)數(shù)學(xué)模型，用若干個(gè)解析表達(dá)式表示，再計(jì)算表達(dá)式來(lái)實(shí)現(xiàn)問(wèn)題的求解。而本題利用海倫公式計(jì)算三角形的面積即為解析算法。典型例題【例5】下列適合使用枚舉算法解決的是()A.計(jì)算三角形的面積

B.判斷2023年是否為閏年C.找出1000以內(nèi)所有的素?cái)?shù)D.計(jì)算班級(jí)男生的平均身高答案：C解析：本題考查的是枚舉算法。枚舉算法又稱為窮舉法，通過(guò)把所有可能的答案一一列舉，逐一判斷每個(gè)可行解是否符合要求，從而得到問(wèn)題的答案。選項(xiàng)C就是通過(guò)枚舉法一一判斷1000以內(nèi)的每一個(gè)數(shù)是否為素?cái)?shù)，從而解決問(wèn)題。典型例題【例6】報(bào)名參加跳遠(yuǎn)比賽的某5位同學(xué)的編號(hào)為5，11，25，36，50，利用二分查找法查找36號(hào)同學(xué)的過(guò)程中，依次被訪問(wèn)到的編號(hào)為()A.5，11，25，36

B.25，36

C.11，36D.11，25，36答案：B解析：本題考查的二分查找算法。初始狀態(tài)：左邊界為0，右邊界為4，中間值的下標(biāo)為(0＋4)//2＝2，對(duì)應(yīng)的值為25；經(jīng)過(guò)判斷25<36，調(diào)整左邊界為3，右邊界依然為4，中間值的下標(biāo)為(3＋4)//2＝3，對(duì)應(yīng)的值正好是36，因此訪問(wèn)的編號(hào)順序?yàn)?5，36。典型例題【例7】________是重復(fù)反饋過(guò)程的活動(dòng)，其目的通常是逼近所需目標(biāo)或結(jié)果。________是直接或間接地調(diào)用函數(shù)自身。()A.枚舉遞歸

B.遞歸迭代

C.迭代遞歸

D.遞歸迭代答案：C解析：本題考查的知識(shí)點(diǎn)是迭代和遞歸的區(qū)別。迭代是重復(fù)反饋過(guò)程的活動(dòng)，其目的是逼近所需目標(biāo)或結(jié)果，通常使用計(jì)數(shù)器結(jié)束循環(huán)。遞歸是重復(fù)調(diào)用函數(shù)自身，遇到滿足終止條件的情況時(shí)逐層返回。所以選項(xiàng)C為正確答案。典型例題【例8】已知遞歸式為F(n)＝F(n－1)＋2，且F(1)＝5，則當(dāng)n＝3時(shí)，F(xiàn)的值為()A.7B.9C.11D.13答案：B解析：本題考查的知識(shí)點(diǎn)是遞歸。根據(jù)遞歸式可以知道F(3)＝F(2)＋2＝F(1)＋2＋2＝5＋2＋2＝9，所以選項(xiàng)B為正確答案。同步訓(xùn)練1.numpy是一個(gè)科學(xué)計(jì)算包，其中包含很多數(shù)學(xué)函數(shù)，以下哪一個(gè)函數(shù)返回最大值()A.sum函數(shù)

B.sqrt函數(shù)C.max函數(shù)

D.arange函數(shù)2.四葉玫瑰數(shù)是指四位數(shù)各位上的數(shù)字的四次方之和等于本身的數(shù)。如果要求出所有的玫瑰花數(shù)，下列算法最合適的是()A.枚舉法

B.查找法C.解析法

D.排序法CA同步訓(xùn)練3.走樓梯的問(wèn)題可以利用迭代算法來(lái)解決，解決該問(wèn)題的正確順序應(yīng)該是()①建立迭代關(guān)系式②讓迭代過(guò)程無(wú)休止地重復(fù)執(zhí)行③對(duì)迭代過(guò)程進(jìn)行控制④確定迭代變量A.④①③②

B.①②③C.④①③

D.①④③C同步訓(xùn)練D同步訓(xùn)練5.運(yùn)用分治策略將一個(gè)難以直接解決的大問(wèn)題分割成規(guī)模較小的子問(wèn)題分別解決，最終達(dá)到解決大問(wèn)題的目的。這要求原問(wèn)題和子問(wèn)題的()A.問(wèn)題性質(zhì)相同，問(wèn)題規(guī)模相同B.問(wèn)題性質(zhì)不同，問(wèn)題規(guī)模相同C.問(wèn)題性質(zhì)相同，問(wèn)題規(guī)模不同D.問(wèn)題性質(zhì)不同，問(wèn)題規(guī)模不同C同步訓(xùn)練6.小明和小華玩猜數(shù)字的游戲，所猜數(shù)字不超過(guò)800，小明首先猜400，小華說(shuō)大了，小明又猜200，當(dāng)小華再次說(shuō)大了，小明猜100，當(dāng)小華說(shuō)小了，小明猜150，以此類(lèi)推，直到猜到正確的數(shù)字。上述方法中蘊(yùn)含的算法思想是