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

ifn＝＝1orn＝＝2：

return1else：

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

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

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

B.25，36

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

B.遞歸迭代

C.迭代遞歸

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

B.sqrt函數C.max函數

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

B.查找法C.解析法

D.排序法CA同步訓練3.走樓梯的問題可以利用迭代算法來解決，解決該問題的正確順序應該是()①建立迭代關系式②讓迭代過程無休止地重復執行③對迭代過程進行控制④確定迭代變量A.④①③②

B.①②③C.④①③

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