資源簡介

專題16　算法思想
學(xué)業(yè)要求 知　識　點(diǎn) 學(xué)業(yè)水平等級
1.理解迭代算法的思想，應(yīng)用迭代算法處理實(shí)際的問題 4
2.理解遞歸算法的思想，應(yīng)用遞歸算法處理實(shí)際的問題 4
知識點(diǎn)　遞歸算法
【知識梳理】
1.迭代算法思想：讓計(jì)算機(jī)重復(fù)執(zhí)行一組________(或一些步驟)，這組指令(或這些步驟)每執(zhí)行一次，都會讓變量從________遞推出一個新值。
2.利用迭代算法處理問題需要考慮三個方面：(1)確定____________；(2)建立____________；(3)控制____________。
3.為求解規(guī)模為N的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解中方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法。當(dāng)________到達(dá)某個邊界，能直接得到解。
4.遞歸是指在函數(shù)的定義中調(diào)用________自身的方法，這里的調(diào)用分兩種：直接調(diào)用與間接調(diào)用。遞歸就是有去有回：“有去”指遞歸問題必須可以分解為若干個規(guī)模較小且與原問題相同的子問題，這些子問題可以用相同的________思路來解決；“有回”指這些問題的演化過程是一個從大到小、由近及遠(yuǎn)的過程，并且存在一個明確的終點(diǎn)(臨界點(diǎn))，一旦到達(dá)這個臨界點(diǎn)，就不用再往更小、更遠(yuǎn)的方向走下去。最后，從這個臨界點(diǎn)開始，原路返回到原點(diǎn)，解決原問題。
5.利用遞歸算法解決問題的關(guān)鍵步驟：(1)抽象建立________，確定________；
(2)確定________(即遞歸結(jié)束條件)。
算法復(fù)雜度又分為算法的時間復(fù)雜度和空間復(fù)雜度，其中時間復(fù)雜度反映了算法執(zhí)行所需要的時間，而空間復(fù)雜度反映了算法執(zhí)行所需要占用的存儲空間。
【經(jīng)典案例】
時間復(fù)雜度常用符號O表述，不包括低階項(xiàng)和首項(xiàng)系數(shù)。時間復(fù)雜度從低到高可以分為常量階O(1)、對數(shù)階O(log2n)，線性階O(n)、平方階O(n2)等。迭代算法是用計(jì)算機(jī)處理問題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對一組指令(或一定步驟)進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令(或這些步驟)時，都從變量的原值推出它的一個新值，是要解決上次計(jì)算與下次計(jì)算之間數(shù)據(jù)傳遞的問題。遞歸算法設(shè)計(jì)三步曲：①函數(shù)的參數(shù)和返回值。這個遞歸函數(shù)的功能是什么，怎樣調(diào)用這個函數(shù)，即設(shè)計(jì)好遞歸函數(shù)的返回值和參數(shù)列表。②找到遞歸出口。什么時候應(yīng)該結(jié)束這個遞歸，它的邊界條件(出口)是什么(邊界條件)。③設(shè)計(jì)遞推公式。一層遞歸的邏輯。在非邊界情況時，怎樣從第n層轉(zhuǎn)變成第n＋1層。
【例1】 定義如下函數(shù)：
def rf(n)：
if n<3：
return n
return rf(n－1)＋rf(n－3)
執(zhí)行語句v＝rf(5)，函數(shù)rf被調(diào)用的次數(shù)是(　　)
A.11 B.5
C.7 D.15
思維點(diǎn)撥
明考向 本題考查遞歸算法思想
精點(diǎn)撥 當(dāng)參數(shù)n大于等于3時，兩次遞歸調(diào)用，否則直接返回值。①rf(5)＝rf(4)＋rf(2)，調(diào)用rf函數(shù)2次；②rf(4)＝rf(3)＋rf(1)，調(diào)用rf函數(shù)2次；③rf(3)＝rf(2)＋rf(0)，調(diào)用rf函數(shù)2次；再加上v＝rf(5)本身調(diào)用的一次，共7次
聽課筆記：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【變式1】 定義如下函數(shù)：
def f(a，s)：
if a>＝s：
return a
else：
return f(a＋1，s－a)
執(zhí)行語句k＝f(6，21)后，k的值為(　　)
A.6 B.7
C.8 D.9
【例2】 有一堆桃子，猴子第一天吃掉其中的一半，并再多吃一個。之后每天猴子都吃掉剩余桃子的一半，再多吃一個。假設(shè)到第十天時，猴子發(fā)現(xiàn)只剩下了一個桃子，問原來這堆桃子最初有多少個。實(shí)現(xiàn)上述問題的兩段Python程序如下：
#程序1 def eat_peach(day)： s＝1 for i in range(9，day－1，－1)： s＝(s＋1)*2 return s print(eat_peach(1))
#程序2 def eat_peach(day)： if day＝＝10： return 1 else： return (eat_peach(day＋1)＋1)*2 print(eat_peach(1))
下列說法不正確的是(　　)
A.程序1和程序2的輸出結(jié)果相同，均為第1天的桃子數(shù)量
B.程序2使用遞歸算法，函數(shù)eat_peach的調(diào)用次數(shù)為10次
C.將程序1的劃線語句修改為range(day，10)，輸出結(jié)果發(fā)生改變
D.將程序2的劃線語句修改為print(eat_peach(8))，輸出的結(jié)果為10
思維點(diǎn)撥
明考向 本題考查迭代與遞歸算法思想
精點(diǎn)撥 程序1迭代算法循環(huán)9－day＋1次，計(jì)算得到第day天桃子的數(shù)量，day＝1時即第1天桃子數(shù)量。程序2遞歸算法實(shí)現(xiàn)計(jì)算第1天桃子的數(shù)量。程序2為了計(jì)算eat_peach(1)，第一次調(diào)用函數(shù)，應(yīng)執(zhí)行計(jì)算調(diào)用(eat_peach(2)＋1)*2，引起對函數(shù)的第二次調(diào)用(遞歸調(diào)用)，重新進(jìn)入函數(shù)，這一過程重復(fù)直到參數(shù)累加到10為止，函數(shù)調(diào)用了10次；程序1的劃線語句修改為range(day，10)，循環(huán)執(zhí)行次數(shù)為9－day＋1，執(zhí)行次數(shù)不變，輸出結(jié)果不發(fā)生改變；將程序2的劃線語句修改為print(eat_peach(8))，計(jì)算的是第8天剩余的桃子數(shù)量，輸出的結(jié)果為10
聽課筆記：____________________________________________________________
______________________________________________________________________
【變式2】 定義如下兩個函數(shù)，fac_1和fac_2：
def fac_1(n)： res＝1 for i in range(1，n＋1)： res *＝i return res
def fac_2(n)： if n＝＝1： return 1 else： return n*fac_2(n－1)
下列說法正確的是(　　)
A.fac_1和fac_2都采用遞歸算法
B.執(zhí)行fac_1(4)和fac_2(4)時，兩個函數(shù)被調(diào)用次數(shù)不同
C.fac_1(4)和fac_2(4)的返回值不同
D.fac_2函數(shù)的算法時間效率遠(yuǎn)大于fac_1
1.下列關(guān)于算法效率的描述，正確的是(　　)
A.算法效率指的是算法的時間復(fù)雜度
B.通常，隨著問題規(guī)模n的增大，函數(shù)值增長較慢的算法較優(yōu)
C.時間復(fù)雜度a常用符號T來表示，如2*n*(n－1)，其時間復(fù)雜度可以表示為T(n2)
D.常見時間復(fù)雜度耗費(fèi)時間的大小關(guān)系為：常數(shù)階<對數(shù)階<指數(shù)階<平方階
2.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法效率的描述，不正確的是(　　)
A.隊(duì)列和棧都是一種線性表，但兩者有不相同的特性
B.采用相同公式求解n！，使用迭代算法比遞歸算法的算法效率高
C.使用數(shù)組結(jié)構(gòu)在進(jìn)行數(shù)據(jù)插入和刪除操作時，一定會引起數(shù)據(jù)移動
D.某單向鏈表(節(jié)點(diǎn)數(shù)>2)設(shè)有頭尾指針，在刪除該鏈表尾節(jié)點(diǎn)時需要遍歷多個
節(jié)點(diǎn)
3.有關(guān)遞歸算法及其應(yīng)用，下列說法正確的是(　　)
A.遞歸算法的執(zhí)行過程分遞推和回歸兩個階段
B.計(jì)算機(jī)在執(zhí)行遞歸程序時，通過隊(duì)列的調(diào)用來實(shí)現(xiàn)
C.使用上述遞歸算法求斐波那契數(shù)列，時間復(fù)雜度為O(n)
D.求斐波那契數(shù)列的第6項(xiàng)fibo(5)時，fibo(3)被調(diào)用了3次
4.定義如下函數(shù)：
def f(n)：
if n<＝1：
return 1
elif n＝＝2：
return 2
return f(n－1)＋f(n－2)＋f(n－3)
執(zhí)行語句v＝f(5)，變量v的值是(　　)
A.13 B.17
C.24 D.31
5.定義如下函數(shù)
def mep(n)：
if n＝＝1：
return 1
else：
return (mep(n－1)＋1)*2
執(zhí)行語句t＝mep(5)，t的值為(　　)
A.22 B.23
C.45 D.46
6.定義如下函數(shù)：
def pell(n)：
if n＝＝1：
return 0
elif n＝＝2：
return 1
elif n>2：
return pell(n－1)*2＋pell(n－2)
下列說法不正確的是(　　)
A.執(zhí)行語句print(pell(3))，輸出2
B.函數(shù)pell體現(xiàn)了遞歸的算法思想
C.當(dāng)n>＝3時，函數(shù)pell的被調(diào)用次數(shù)為n*(n－1)//2次
D.執(zhí)行語句pell(3)，判斷條件“n＝＝2”共執(zhí)行了2次
7.有如下Python程序段：
def fac(n)：
ans＝1
for i in range(2，n＋1)：
ans *＝i
return ans
def Com(n，m)：
return fac(n)//fac(n－m)//fac(m)
print(Com(5，3))
執(zhí)行該程序段后，下列說法不正確的是(　　)
A.Com()函數(shù)運(yùn)用了遞歸思想
B.fac()函數(shù)一共被調(diào)用了3次
C.輸出結(jié)果是10
D.將Com(5，3)改為Com(5，2)，運(yùn)行結(jié)果不變
8.對于如下兩個Python程序段：
程序a a＝2 res＝1 n＝int(input()) for i in range(n)： res＝res*a print(res) 程序b def powr(a，n)： if n＝＝1： return a elif n＝＝0： return 1 else： tmp＝powr(a，n//2) return tmp*tmp a＝2 n＝int(input()) print(powr(a，n))
下列說法錯誤的是(　　)
A.若輸入n＝8，程序a，b都將輸出256
B.若輸入n＝10，程序a，b都將輸出1024
C.程序a的算法時間復(fù)雜度是O(n)
D.程序b的算法時間復(fù)雜度是O(log2n)
9.定義如下函數(shù)：
def move(n，a，b，c)：
if n＝＝1：
print(a，″→″，c)
return
move(n－1，a，c，b)
move(1，a，b，c)
move(n－1，b，a，c)
執(zhí)行語句move(2，″A″，″B″，″C″)，輸出的第一行內(nèi)容是(　　)
A.a→c B.A→C
C.a→b D.A→B
10.已知：任取兩個自然數(shù)，其互質(zhì)(沒有大于1的共同因數(shù))的概率是6/(π*π)，小藍(lán)據(jù)此編寫了程序：
from math import sqrt
from random import randint
def fun(a，b)：
if b＝＝0：
return a
else：
return fun(b，a % b)
cnt＝0
n＝1000；m＝100000
for i in range(n)：
a＝randint(1，m)
b＝randint(1，m)
if fun(a，b)＝＝1：
　　　　cnt＋＝1
print(sqrt(6*n/cnt))
程序模擬1000次產(chǎn)生2個[1，m]之間的隨機(jī)數(shù)，計(jì)算這兩個數(shù)互質(zhì)的次數(shù)cnt和頻率cnt/n，用頻率估計(jì)概率6/(π*π)，以驗(yàn)證該結(jié)論的準(zhǔn)確性，則以下說法正確的是(　　)
A.程序輸出結(jié)果就是6/(π*π)的近似值
B.該程序所描述算法的時間復(fù)雜度為O(n)
C.函數(shù)fun()用遞歸算法求兩個正整數(shù)的最小公倍數(shù)
D.要想提高程序結(jié)果的精確度，可以擴(kuò)大n和m的范圍
專題16　算法思想
知識點(diǎn)
知識梳理
1.指令　原值
2.(1)迭代變量　(2)迭代關(guān)系式　(3)迭代過程
3.遞歸
4.函數(shù)　解題
5.(1)遞歸模型　遞歸公式　(2)臨界條件
經(jīng)典案例
例1　C
變式1　C　[本題考查遞歸函數(shù)的應(yīng)用。遞歸算法包含遞推和回歸兩部分，函數(shù)f(6，21)的值為 f(7，15)，而f(7，15)的值為 f(8，8)，函數(shù)f(8，8)的值為8，依次回歸，最終函數(shù)的值為8。]
例2　C
變式2　B　[本題考查迭代與遞歸的算法思想。兩處程序的功能均為求n的階乘。A選項(xiàng)程序fac_1體現(xiàn)迭代算法思想。B選項(xiàng)fac_1(4)只調(diào)用1次，而fac_2(4)要調(diào)用4次。C選項(xiàng)返回值均為24。D選項(xiàng)均循環(huán)了n次，因此算法效率一樣。]
當(dāng)堂過關(guān)檢測
1.B　[本題考查算法效率的計(jì)算。A選項(xiàng)算法效率包括時間復(fù)雜度和空間復(fù)雜度。B選項(xiàng)時間復(fù)雜度與n的最高次冪有關(guān)，且和系數(shù)無關(guān)。C選項(xiàng)時間復(fù)雜度的常用符號是大寫的O。D選項(xiàng)正確的關(guān)系是：常數(shù)階<對數(shù)階<平方階<指數(shù)階。]
2.C　[本題考查不同數(shù)據(jù)結(jié)構(gòu)的特性和算法描述。A選項(xiàng)隊(duì)列先進(jìn)先出，棧先進(jìn)后出。B選項(xiàng)遞歸求n！要遞推和回歸兩個階段，迭代算法的效率高于遞歸算法。D選項(xiàng)修改尾節(jié)點(diǎn)前驅(qū)指針區(qū)域值為－1，需遍歷多個節(jié)點(diǎn)。]
3.A　[本題考查遞歸算法。A選項(xiàng)遞歸函數(shù)中包含一個遞推公式，先依次調(diào)用自己，再進(jìn)行回歸。B選項(xiàng)通過棧調(diào)用來實(shí)現(xiàn)。C選項(xiàng)以第6項(xiàng)fibo(5)為例，可以畫出二叉樹來表示，若根節(jié)點(diǎn)為n，則樹的高度為n，深度為n的滿二叉樹的節(jié)點(diǎn)數(shù)量(函數(shù)的調(diào)用次數(shù))為n2－1，因此時間復(fù)雜度為O(n2)。D選項(xiàng)fibo(3)被調(diào)用了2次。fibo(5)＝fibo(4)＋fibo(3)；fibo(4)＝fibo(3)＋fibo(2)。]
4.A　[本題考查遞歸算法思想。f(5)＝f(4)＋f(3)＋f(2)，f(4)＝f(3)＋f(2)＋f(1)，f(3)＝f(2)＋f(1)＋f(0)＝4，f(4)＝7，f(5)＝7＋4＋2。]
5.D　[本題考查對遞歸函數(shù)的理解。mep(5)＝(mep(4)＋1)*2；mep(4)＝(mep(3)＋1)*2；mep(3)＝(mep(2)＋1)*2；mep(2)＝(mep(1)＋1)*2；mep(1)＝1。]
6.C　[本題考查遞歸算法思想。B選項(xiàng)pell函數(shù)內(nèi)部調(diào)用了自身，因此屬于遞歸算法思想。遞歸算法包含遞推和回歸兩個過程，pell(3)＝pell(2)*2＋pell(1)＝1*2＋0＝2，pell(2)被調(diào)用了2次，因此判斷條件“n＝＝2”共執(zhí)行了2次，AD選項(xiàng)正確。C選項(xiàng)當(dāng)n分為3和4時，調(diào)用次數(shù)為3，5，并不符合n*(n－1)//2次。]
7.A　[本題考查自定義函數(shù)知識。A選項(xiàng)遞歸函數(shù)是函數(shù)調(diào)用本身，但函數(shù)Com并未調(diào)用本身。]
8.B　[本題考查遞歸程序的閱讀與算法復(fù)雜度的計(jì)算。對于A、B選項(xiàng)根據(jù)輸入的值模擬運(yùn)行得到相應(yīng)的值。C選項(xiàng)程序a的循環(huán)次數(shù)是n次，算法時間復(fù)雜度是O(n)。D選項(xiàng)調(diào)用過程是：powr(a，n)→powr(a，n/2)→powr(a，n/4)→powr(a，n/8)→…→powr(a，1)，調(diào)用的次數(shù)約為log2n次，因此復(fù)雜度是O(log2n)。]
9.D　[本題考查遞歸函數(shù)的應(yīng)用。執(zhí)行語句move(2，″A″，″B″，″C″)，分別調(diào)用move(1，″A″，″C″″B″，)，move(1，″A″，″B″，″C″)，move(1，″B″，″A″，″C″)，因此分別輸出A→B、A→C、B→C。]
10.D　[本題考查遞歸函數(shù)和算法復(fù)雜度的估算。A選項(xiàng)根據(jù)題目要求頻率等于概率，cnt/n＝6/(π*π)，(π*π)＝6*n/cnt，該公式計(jì)算圓周率的近似值。B選項(xiàng)本段代碼的算法復(fù)雜度，除了for循環(huán)，還要考慮函數(shù)fun的復(fù)雜度。函數(shù)fun是用歐幾里得算法求二個數(shù)的最大公約數(shù)。復(fù)雜度是O(log(mix(a，b))。最終的算法復(fù)雜度是O(log(mix(a，b)*n)。C選項(xiàng)是求二個數(shù)的最大公約數(shù)。D選項(xiàng)樣本規(guī)模越大概率的方法求近似值越接近。]

展開更多......

收起↑