成人高考政治試題及答案下(專升本)

1、.計(jì)算機(jī)算法設(shè)計(jì)與分析（第計(jì)算機(jī)算法設(shè)計(jì)與分析（第3版）版）王通王通天津工程師范學(xué)院計(jì)算機(jī)系天津工程師范學(xué)院計(jì)算機(jī)系.第第3章章 迭代和遞推算法迭代和遞推算法教學(xué)目標(biāo)：理解迭代法及其特點(diǎn)理解什么是遞推法及其特點(diǎn)用遞推法設(shè)計(jì)算法的基本過程能夠根據(jù)具體問題的要求，學(xué)會(huì)用遞推法實(shí)現(xiàn)算法編寫程序.第第3章章 迭代和遞推算法迭代和遞推算法 給你一張足夠大的厚為給你一張足夠大的厚為0.1毫米的紙，你所要做毫米的紙，你所要做的是重復(fù)這樣的動(dòng)作的是重復(fù)這樣的動(dòng)作: 對(duì)折，不停地對(duì)折。對(duì)折，不停地對(duì)折。我的問題就是，折疊多少次后超過世界屋脊珠穆我的問題就是，折疊多少次后超過世界屋脊珠穆朗瑪峰的高度朗瑪峰的高度8

2、848米？米？當(dāng)你把這張紙對(duì)折了當(dāng)你把這張紙對(duì)折了51次的時(shí)候，所達(dá)到的厚度次的時(shí)候，所達(dá)到的厚度有多少？有多少？ .第第3章章 迭代和遞推算法迭代和遞推算法-迭代法 求方程求方程f(x)=x3-x-1=0 在在x0=1.5附近的根附近的根x*.第第3章章 迭代和遞推算法迭代和遞推算法-迭代法迭代法迭代法 求方程或方程組近似根的一種常用算法。求方程或方程組近似根的一種常用算法。步驟：步驟： 1、選一個(gè)方程的近似根，賦給、選一個(gè)方程的近似根，賦給x0 2、將、將x0保存在變量保存在變量x1中，然后計(jì)算中，然后計(jì)算x0=g(x1) 3、當(dāng)、當(dāng)x0 與與x1差的絕對(duì)值還不小于指定的精度差的絕對(duì)值還不

3、小于指定的精度要求時(shí)，重復(fù)計(jì)算。否則結(jié)束。要求時(shí)，重復(fù)計(jì)算。否則結(jié)束。 .第第3章章 迭代和遞推算法迭代和遞推算法-迭代法 x0=初始近似根；初始近似根； do x1=x0; x0=g(x1); /*按特定的方程計(jì)算新的近似根按特定的方程計(jì)算新的近似根*/ While(fabs(x0-x1)E) printf(方程的近似根是方程的近似根是%fn，x0)； .第第3章章 迭代和遞推算法迭代和遞推算法-迭代法難點(diǎn)：難點(diǎn)： 1、方程無解、方程無解 2、方程有解，但迭代公式選擇不當(dāng)，或初、方程有解，但迭代公式選擇不當(dāng)，或初始近似根選擇不合理，會(huì)導(dǎo)致迭代失敗。始近似根選擇不合理，會(huì)導(dǎo)致迭代失敗。 舉例舉

4、例 求方程求方程f(x)=x5-x-1=0 在在x0=1.5附近的根附近的根x*例.第第3章章 迭代和遞推算法迭代和遞推算法-迭代法例例2 用牛頓迭代公式用牛頓迭代公式 x=x0-f(x0)/f(x0)求解求解 sqrt(2) 設(shè)設(shè)sqrt(2)=x sqrt(2)=x 即即 x x2 2-2=0 -2=0 則令則令 f(x)=xf(x)=x2 2-2 -2 所以所以 f(x)=2x f(x)=2x 所以有迭代公式所以有迭代公式 x=1/2x=1/2* *(x0+2/x0) (x0+2/x0) .第第3章章 迭代和遞推算法迭代和遞推算法-遞推法遞推法考察一個(gè)我們熟知的計(jì)算：考察一個(gè)我們熟知的計(jì)

5、算：4 * 9。這種從頭開始一步步遞推出問題最終結(jié)果這種從頭開始一步步遞推出問題最終結(jié)果的方法，就是遞推的方法，就是遞推(recurrence)(recurrence)方法。方法。遞推是序列計(jì)算中的一種常用方法。它是遞推是序列計(jì)算中的一種常用方法。它是按照一定的規(guī)律來計(jì)算序列中的每個(gè)項(xiàng)，按照一定的規(guī)律來計(jì)算序列中的每個(gè)項(xiàng)，通常是通過計(jì)算前面的一些項(xiàng)來得出序列通常是通過計(jì)算前面的一些項(xiàng)來得出序列中的指定項(xiàng)的值。中的指定項(xiàng)的值。 .第第3章章 迭代和遞推算法迭代和遞推算法-遞推法遞推法遞推法是利用問題本身所具有的一種遞推關(guān)遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。系求問題解的一種

6、方法。 設(shè)要求問題規(guī)模為設(shè)要求問題規(guī)模為N N的解，當(dāng)?shù)慕猓?dāng)N=1N=1時(shí)，解時(shí)，解或?yàn)橐阎?，或能非常方便地得到解?；驗(yàn)橐阎?，或能非常方便地得到解?第第3章章 迭代和遞推算法迭代和遞推算法-遞推法遞推法 例例 要爬到一個(gè)小山的頂點(diǎn)，需要上要爬到一個(gè)小山的頂點(diǎn)，需要上100個(gè)臺(tái)階個(gè)臺(tái)階. 可以一可以一步上一個(gè)臺(tái)階，也可以一步上兩個(gè)臺(tái)階，有多少種不步上一個(gè)臺(tái)階，也可以一步上兩個(gè)臺(tái)階，有多少種不同的上山方式呢？同的上山方式呢？解解 設(shè)爬山的臺(tái)階數(shù)為設(shè)爬山的臺(tái)階數(shù)為n，上到第，上到第n個(gè)臺(tái)階的方式數(shù)為個(gè)臺(tái)階的方式數(shù)為an. 若只有一個(gè)臺(tái)階，上山方式只有一種，即若只有一個(gè)臺(tái)階，上山方式只有一種，即a

7、l1。 若有兩個(gè)臺(tái)階，可以兩小步若有兩個(gè)臺(tái)階，可以兩小步(每步一個(gè)臺(tái)階每步一個(gè)臺(tái)階)上去，也可上去，也可以一大步以一大步(上兩個(gè)臺(tái)階上兩個(gè)臺(tái)階)上去，即上去，即a22。.第第3章章 迭代和遞推算法迭代和遞推算法-遞推法遞推法若有三個(gè)臺(tái)階，可以全用小步上去，也可一大一小，若有三個(gè)臺(tái)階，可以全用小步上去，也可一大一小，或一小一大，因此，或一小一大，因此，a33。若有若有n個(gè)臺(tái)階，上到第個(gè)臺(tái)階，上到第n個(gè)臺(tái)階的方式數(shù)為個(gè)臺(tái)階的方式數(shù)為an, 可分成可分成兩類，第一類是從第兩類，第一類是從第n一一1個(gè)臺(tái)階邁一小步上去的，個(gè)臺(tái)階邁一小步上去的，共有共有an-1種；第二類是從第種；第二類是從第n-2個(gè)臺(tái)階

8、邁一大步上個(gè)臺(tái)階邁一大步上去的，共有去的，共有an-2種。由于最后一步的上法不同，所種。由于最后一步的上法不同，所以這兩類上法是不同的。所以這樣求得的上山方式以這兩類上法是不同的。所以這樣求得的上山方式數(shù)為數(shù)為 an an-1 + an-2 一直算下去，當(dāng)然可以得到一直算下去，當(dāng)然可以得到a100a100的值，這就是問題的的值，這就是問題的解。解。.第第3章章 遞推算法遞推算法能采用遞推法構(gòu)造算法的問題有重要的能采用遞推法構(gòu)造算法的問題有重要的遞推性質(zhì)遞推性質(zhì)，即，即當(dāng)?shù)玫絾栴}規(guī)模為當(dāng)?shù)玫絾栴}規(guī)模為i-1i-1的解后，由問題的遞推性質(zhì)，的解后，由問題的遞推性質(zhì)，能從已求得的規(guī)模為能從已求得的規(guī)

9、模為1 1，2 2，i-1i-1的一系列解，的一系列解，構(gòu)造出問題規(guī)模為構(gòu)造出問題規(guī)模為I I的解。這樣，程序可從的解。這樣，程序可從i=0i=0或或i=1i=1出發(fā)，重復(fù)地，由已知至出發(fā)，重復(fù)地，由已知至i-1i-1規(guī)模的解，通過遞規(guī)模的解，通過遞推，獲得規(guī)模為推，獲得規(guī)模為i i的解，直至得到規(guī)模為的解，直至得到規(guī)模為N N的解。的解。難點(diǎn)：遞推法關(guān)鍵是找遞推關(guān)系，并確定初值。難點(diǎn)：遞推法關(guān)鍵是找遞推關(guān)系，并確定初值。 編程時(shí)遞推向前傳遞變量值的時(shí)序，不能顛倒。編程時(shí)遞推向前傳遞變量值的時(shí)序，不能顛倒。.第第3章章 遞推算法遞推算法 如何建立遞推關(guān)系？目前尚未總結(jié)出一個(gè)一般如何建立遞推關(guān)系

10、？目前尚未總結(jié)出一個(gè)一般的方法，只能具體問題，具體分析。的方法，只能具體問題，具體分析。建立遞推關(guān)系，必須對(duì)所提出的問題，進(jìn)行深建立遞推關(guān)系，必須對(duì)所提出的問題，進(jìn)行深入細(xì)致的分析。入細(xì)致的分析。 先從最簡(jiǎn)單的情況分析入手，看先從最簡(jiǎn)單的情況分析入手，看n1，n2，時(shí)的情況如何，這就是先建立初條件。時(shí)的情況如何，這就是先建立初條件。 .第第3章章 遞推算法遞推算法而后，從而后，從nk - 1(有時(shí)用到有時(shí)用到nk - 2，nk - 3，)時(shí)，去推出時(shí)，去推出nk的情況，這種推測(cè)就的情況，這種推測(cè)就是建立在先驗(yàn)印象的基礎(chǔ)上的。因此，便于是建立在先驗(yàn)印象的基礎(chǔ)上的。因此，便于摸清變化規(guī)律，而得出正

11、確的遞推關(guān)系摸清變化規(guī)律，而得出正確的遞推關(guān)系. 斐波那契兔子問題.公元公元12021202年，商人出身的意大利數(shù)學(xué)家斐波那契（年，商人出身的意大利數(shù)學(xué)家斐波那契（FiFibonaccibonacci，1170117012501250），完成了一部偉大的論著），完成了一部偉大的論著算法之書算法之書。在書中，提出以下有趣問題：。在書中，提出以下有趣問題：假定一對(duì)剛出生的小兔一個(gè)月后就能長成大兔，再過假定一對(duì)剛出生的小兔一個(gè)月后就能長成大兔，再過一個(gè)月便能生下一對(duì)小兔，并且此后每個(gè)月都生一對(duì)一個(gè)月便能生下一對(duì)小兔，并且此后每個(gè)月都生一對(duì)小兔。一年內(nèi)沒有發(fā)生死亡，問一對(duì)剛出生的兔子，小兔。一年內(nèi)沒有

12、發(fā)生死亡，問一對(duì)剛出生的兔子，一年內(nèi)繁殖成多少對(duì)兔子？一年內(nèi)繁殖成多少對(duì)兔子？(假定以上兔子都是雌雄成假定以上兔子都是雌雄成對(duì)對(duì))？ 第第3章章 遞推算法遞推算法-斐波那契兔子問題斐波那契兔子問題.其中其中A表示一對(duì)大兔子，表示一對(duì)大兔子，B表示一對(duì)小兔子表示一對(duì)小兔子第第3章章 遞推算法遞推算法-斐波那契兔子問題斐波那契兔子問題.逐月推算，我們可以得到前面提過的數(shù)列：逐月推算，我們可以得到前面提過的數(shù)列：1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，8989，144144，233233。這個(gè)數(shù)。這個(gè)數(shù)列后來便以斐波那契的名字命名。數(shù)列的每一項(xiàng)，則稱為

13、斐波列后來便以斐波那契的名字命名。數(shù)列的每一項(xiàng)，則稱為斐波那契數(shù)。那契數(shù)?！钡谑坏撵巢瞧鯏?shù)，即為一對(duì)剛出生的小兔，第十三位的斐波那契數(shù)，即為一對(duì)剛出生的小兔，一年內(nèi)所能繁殖成的兔子的對(duì)數(shù)，這個(gè)數(shù)字為一年內(nèi)所能繁殖成的兔子的對(duì)數(shù)，這個(gè)數(shù)字為233233。從斐波那契數(shù)的構(gòu)造明顯看出：斐波那契數(shù)列從第三項(xiàng)起，每從斐波那契數(shù)的構(gòu)造明顯看出：斐波那契數(shù)列從第三項(xiàng)起，每項(xiàng)都等于前面兩項(xiàng)的和。假定第項(xiàng)都等于前面兩項(xiàng)的和。假定第n n項(xiàng)斐波那契數(shù)為項(xiàng)斐波那契數(shù)為fnfn，于是我，于是我們有：們有：321)2() 1(11)(nnnnFnFnF第第3章章 遞推算法遞推算法-斐波那契兔子問題斐波那契兔子問題

14、.算法描述：算法描述：按照斐波那契數(shù)列中各項(xiàng)的關(guān)系，可以使用四按照斐波那契數(shù)列中各項(xiàng)的關(guān)系，可以使用四個(gè)變量個(gè)變量a、b、c和和k來計(jì)算，這四個(gè)變量的用途來計(jì)算，這四個(gè)變量的用途如下：如下：a 存貯存貯Fk-2。 b 存貯存貯Fk-1。c 存貯存貯Fk ，可以通過，可以通過a+b，從，從Fk-2和和Fk-1來計(jì)算來計(jì)算Fk 。k 記錄變量記錄變量c中存貯的當(dāng)前項(xiàng)的項(xiàng)號(hào)。中存貯的當(dāng)前項(xiàng)的項(xiàng)號(hào)。第第3章章 遞推算法遞推算法-斐波那契兔子問題斐波那契兔子問題.第第3章章 遞推算法遞推算法-斐波那契兔子問題斐波那契兔子問題.下面是用自然語言描述的算法：下面是用自然語言描述的算法：1. (輸入項(xiàng)號(hào)輸入項(xiàng)

15、號(hào))輸入項(xiàng)號(hào)輸入項(xiàng)號(hào)n。2. (是最初二項(xiàng)之一？是最初二項(xiàng)之一？)若若n3則輸出則輸出1，算法終止。，算法終止。3. (初始化初始化) a1，b1，c2，k3。4. (完成？完成？) 若若k=n則輸出則輸出c值，算法終止。值，算法終止。5. (從和計(jì)算從和計(jì)算) ab，bc， ca + b。6. (記錄當(dāng)前項(xiàng)號(hào)記錄當(dāng)前項(xiàng)號(hào)) kk + 1。7. (轉(zhuǎn)去計(jì)算下一項(xiàng)轉(zhuǎn)去計(jì)算下一項(xiàng)) 轉(zhuǎn)到轉(zhuǎn)到4。第第3章章 遞推算法遞推算法-斐波那契兔子問題斐波那契兔子問題.第第3章章 遞推算法遞推算法Main() scanf(“%d”,&n ) ; If (n3) printf(“%d”,1 ) ; in

16、t f1=1;f2=1;i=3;while(i=n) fi=f1+f2 f1=f2; f2=fi; i+; printf(“%d”,fi ) 算法描述：1、定義初值2、變量i從3增到n3、計(jì)算fi=fi-1+ fi-2;4、輸出fi.第第3章章 遞推算法遞推算法- 階乘計(jì)算階乘計(jì)算問題描述：對(duì)給定的n（n100），計(jì)算并輸出k的階乘k！（k=1，2，n）的全部有效數(shù)字。00)!1(1!nnnnn.用遞推法求解階乘函數(shù)的思路是：先求fac(1)，再求fac(2)，,直到求出fac(n)Main() Int n; Int facn=0 Int m=1; for(int i=1;i=n;i+) m=

17、m*i faci=m; for(int i=1;i=n;i+) Cout faciendl;. 棋盤放米問題.第第3章章 遞推算法遞推算法有個(gè)智者和國王下棋，國王答應(yīng)如果智者勝了可以得到他想要的任何東西。結(jié)果智者勝了，他的要求不高，就要國王在64格的棋盤棋盤上放放米米，第一格放一粒，第二格放兩粒，第三格放四粒以此類推，每格放的米粒數(shù)都是前一格的平方。國王以為這很容易，就答應(yīng)了，結(jié)果發(fā)現(xiàn)他把國庫所有的米都放上都不夠。 .第第3章章 遞推算法遞推算法其實(shí)懂?dāng)?shù)學(xué)的都知道，第一格的米粒數(shù)可以寫成數(shù)學(xué)計(jì)算式=2的0次方，那么，第二格的米粒數(shù)是2的1次方，第三格的米粒數(shù)是2的2次方，第4格的米粒數(shù)是2的3

18、次方，那么，第n個(gè)格的米粒數(shù)就是2的（n-1）次方，.第第3章章 遞推算法遞推算法棋盤只有64個(gè)格子，算出來的數(shù)字竟然是2的63次方等于9,223,372,036,854,780,000粒，那還只是第64格所放米粒的數(shù)量,如果全部累計(jì),則總共需要18,446,744,073,709,600,000粒, 如果1000粒米有1克重，那么第64格的米就是9,223,372,036噸,全部相加就是18,446,744,073,709噸.從上述圖示中，我們可以知道這是一個(gè)等比級(jí)數(shù)20+21+22+23+24+263求和的數(shù)學(xué)問題。.棋盤放米問題.第第3章章 遞推算法遞推算法問題：給你一張足夠大的厚為0.1毫米的紙，你所要做的是重復(fù)這樣的動(dòng)作: 對(duì)折，不停地對(duì)折。我的問題問題就是，折疊多少次后超過世界屋脊珠穆朗瑪峰的高度8848米？當(dāng)你把這張紙對(duì)折了51次的時(shí)候，所達(dá)到的厚度有多少？ .流程圖.第第3章章 遞推算法遞推算法如果一張報(bào)紙厚度是0.1毫米，連疊51次后就有2的51次方張報(bào)紙，大概等于10的15.3次方，0.1毫米等于10的-