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

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

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

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

4、例 求方程求方程f(x)=x5-x-1=0 在在x0=1.5附近的根附近的根x*例.第第3章章 迭代和遞推算法迭代和遞推算法-迭代法例例2 用牛頓迭代公式用牛頓迭代公式 x=x0-f(x0)/f(x0)求解求解 sqrt(2) 設設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章章 迭代和遞推算法迭代和遞推算法-遞推法遞推法考察一個我們熟知的計算：考察一個我們熟知的計

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

6、方法。 設要求問題規(guī)模為設要求問題規(guī)模為N N的解，當的解，當N=1N=1時，解時，解或為已知，或能非常方便地得到解。或為已知，或能非常方便地得到解。.第第3章章 迭代和遞推算法迭代和遞推算法-遞推法遞推法 例例 要爬到一個小山的頂點，需要上要爬到一個小山的頂點，需要上100個臺階個臺階. 可以一可以一步上一個臺階，也可以一步上兩個臺階，有多少種不步上一個臺階，也可以一步上兩個臺階，有多少種不同的上山方式呢？同的上山方式呢？解解 設爬山的臺階數為設爬山的臺階數為n，上到第，上到第n個臺階的方式數為個臺階的方式數為an. 若只有一個臺階，上山方式只有一種，即若只有一個臺階，上山方式只有一種，即a

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

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

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

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

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

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

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

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

15、號)輸入項號輸入項號n。2. (是最初二項之一？是最初二項之一？)若若n3則輸出則輸出1，算法終止。，算法終止。3. (初始化初始化) a1，b1，c2，k3。4. (完成？完成？) 若若k=n則輸出則輸出c值，算法終止。值，算法終止。5. (從和計算從和計算) ab，bc， ca + b。6. (記錄當前項號記錄當前項號) kk + 1。7. (轉去計算下一項轉去計算下一項) 轉到轉到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、計算fi=fi-1+ fi-2;4、輸出fi.第第3章章 遞推算法遞推算法- 階乘計算階乘計算問題描述：對給定的n（n100），計算并輸出k的階乘k?。╧=1，2，n）的全部有效數字。00)!1(1!nnnnn.用遞推法求解階乘函數的思路是：先求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章章 遞推算法遞推算法有個智者和國王下棋，國王答應如果智者勝了可以得到他想要的任何東西。結果智者勝了，他的要求不高，就要國王在64格的棋盤棋盤上放放米米，第一格放一粒，第二格放兩粒，第三格放四粒以此類推，每格放的米粒數都是前一格的平方。國王以為這很容易，就答應了，結果發(fā)現他把國庫所有的米都放上都不夠。 .第第3章章 遞推算法遞推算法其實懂數學的都知道，第一格的米粒數可以寫成數學計算式=2的0次方，那么，第二格的米粒數是2的1次方，第三格的米粒數是2的2次方，第4格的米粒數是2的3

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