算法及程序實踐習題解答8(遞歸)

1、算法與程序實踐習 題 解 答8遞歸讓我們來看看計算n 的階乘的計算機程序的寫法,很直接地我們會用一個循環(huán)語句將n 以下的數(shù)都乘起來: int n,m = 1; for(int i = 2; i <= n; i+) m *= i; printf(“%d 的階乘是%dn”, n, m); 因為n 的階乘定義為n 乘以n-1 的階乘，所以還可以用下面的方法來求n 的階乘： int factorial(int n) if(n <= 0) return(-1); if(n = 1) return 1; else return n*factorial(n - 1); 上面這兩種實現(xiàn)方式體現(xiàn)了兩

2、種不同的解決問題的思想方法。第一種通過一個循環(huán)語句來計算階乘，其前提是了解階乘的計算過程，并用語句把這個計算過程模擬出來。第二種解決問題的思想是不直接找到計算n 的階乘的方法，而是試圖找到n 的階乘和n-1 的階乘的遞推關系，通過這種遞推關系把原來問題縮小成一個更小規(guī)模的同類問題，并延續(xù)這一縮小規(guī)模的過程，直到在某一規(guī)模上，問題的解是已知的。這樣一種解決問題的思想我們稱為遞歸的思想。遞歸方法的總體思想是將待求解問題的解看作輸入變量x 的函數(shù)f(x)，通過尋找函數(shù)g，使得f(x) = g(f(x-1) ，并且已知f(0)的值，就可以通過f(0)和g 求出f(x)的值。這樣一個思想也可以推廣到多個

3、輸入變量x，y，z 等，x-1 也可以推廣到x - x1，只要遞歸朝著出口的方向走就可以了。CS81：菲波那契數(shù)列（來源： 2753，程序設計導引及在線實踐（李文新）例9.2 P198）問題描述：菲波那契數(shù)列是指這樣的數(shù)列: 數(shù)列的第一個和第二個數(shù)都為1，接下來每個數(shù)都等于前面2個數(shù)之和。給出一個正整數(shù)a，要求菲波那契數(shù)列中第a個數(shù)是多少。輸入：第1行是測試數(shù)據的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據占1行，包括一個正整數(shù)a(1 <= a <= 20)。輸出：輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數(shù)，為菲波那契數(shù)列中第a個數(shù)的大小。樣例輸入：452191樣例輸出：514

4、1811解題思路：這個題目要求很明確，因為a的規(guī)模很小，所以遞歸調用不會產生棧溢出的問題。設第n 項值為f(n)，則f(n) = f(n-1)+f(n-2)。已知f(1)=1，f(2)=1 ，則從第項開始，可以用公式求。參考程序：#include<stdio.h>int f(int a)if(a=1 | a=2) return 1;return f(a-1)+f(a-2);int main()int n;int i;scanf("%d",&n);for(i=1;i<=n;i+)int a;scanf("%d",&a);p

5、rintf("%dn",f(a);return 0;CS82：二叉樹（來源： 2756，程序設計導引及在線實踐（李文新）例9.3 P199）問題描述：圖8-1 滿二叉樹如圖8-1所示，由正整數(shù)1, 2, 3, .組成了一棵無限大的二叉樹。從某一個結點到根結點（編號是1的結點）都有一條唯一的路徑，比如從10到根結點的路徑是(10, 5, 2, 1)，從4到根結點的路徑是(4, 2, 1)，從根結點1到根結點的路徑上只包含一個結點1，因此路徑就是(1)。對于兩個結點x和y，假設他們到根結點的路徑分別是(x1, x2, . ,1)和(y1, y2, . ,1)（這里顯然有x =

6、x1，y = y1），那么必然存在兩個正整數(shù)i和j，使得從xi 和 yj開始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,. 現(xiàn)在的問題就是，給定x和y，要求xi（也就是yj）。輸入：輸入只有一行，包括兩個正整數(shù)x和y，這兩個正整數(shù)都不大于1000。輸出：輸出只有一個正整數(shù)xi。樣例輸入：10 4樣例輸出：2解題思路：這個題目要求樹上任意兩個節(jié)點的最近公共子節(jié)點。分析這棵樹的結構不難看出，不論奇數(shù)偶數(shù)，每個數(shù)對2做整數(shù)除法，就走到它的上層結點。我們可以每次讓較大的一個數(shù)（也就是在樹上位于較低層次的節(jié)點）向上走一個結點，直到兩個結點相遇。如果兩個節(jié)點位

7、于同一層，并且它們不相等，可以讓其中任何一個先往上走，然后另一個再往上走，直到它們相遇。設common(x, y) 表示整數(shù)x 和y 的最近公共子節(jié)點，那么，根據比較x 和y 的值，我們得到三種情況：1) x 與y 相等，則common(x, y) 等于x 并且等于y；2）x 大于y，則common(x, y) 等于common(x/2, y)； 3）x 大于y，則common(x, y) 等于common(x,y/2)；參考程序：#include<stdio.h>int common(int x,int y)if(x=y) return x;if(x>y) return c

8、ommon(x/2,y);return common(x,y/2);int main()int m,n;scanf("%d%d",&m,&n);printf("%dn",common(m,n);return 0;注意事項：問題一：有一種比較直觀的解法是對于兩個給定的數(shù)，分別求出它們到根節(jié)點的通路上的所有節(jié)點的值，然后再在兩個數(shù)組中尋找數(shù)碼最大的公共節(jié)點。這種做法的代碼比較繁瑣，容易在實現(xiàn)中出錯；問題二：代碼實現(xiàn)邏輯不明晰，造成死循環(huán)等錯誤，例如，有人只將其中一個數(shù)不停地除以2，而不理會另外一個數(shù)。CS83：逆波蘭表達式（來源： 2694，

9、程序設計導引及在線實踐（李文新）例9.4 P201）問題描述：逆波蘭表達式是一種把運算符前置的算術表達式，例如普通的表達式2 + 3的逆波蘭表示法為+ 2 3。逆波蘭表達式的優(yōu)點是運算符之間不必有優(yōu)先級關系，也不必用括號改變運算次序，例如(2 + 3) * 4的逆波蘭表示法為* + 2 3 4。本題求解逆波蘭表達式的值，其中運算符包括+ - * /四個。輸入：輸入為一行，其中運算符和運算數(shù)之間都用空格分隔，運算數(shù)是浮點數(shù)。輸出：輸出為一行，表達式的值?？芍苯佑胮rintf("%fn", v)輸出表達式的值v。樣例輸入：* + 11.0 12.0 + 24.0 35.0樣例輸

10、出：1357.000000解題思路：這個問題看上去有些復雜，如果只是簡單地模擬計算步驟不太容易想清楚，但是如果用遞歸的思想就非常容易想清楚。讓我們根據逆波蘭表達式的定義進行遞歸求解。在遞歸函數(shù)中，針對當前的輸入，有五種情況：1）輸入是常數(shù)，則表達式的值就是這個常數(shù)；2）輸入是+ ，則表達式的值是再繼續(xù)讀入兩個表達式并計算出它們的值，然后將它們的值相加；3）輸入是-；4）輸入是*； 5）輸入是/；后幾種情況與2）相同，只是計算從+ 變成-，*，/ 。參考程序：#include<stdio.h>#include<math.h>#include<stdlib.h>

11、double exp()char a10;scanf("%s",a);switch(a0)case '+': return exp()+exp();case '-': return exp()-exp();case '*': return exp()*exp();case '/': return exp()/exp();default: return atof(a);int main()double ans;ans=exp();printf("%f",ans);return 0;CS84：放

12、蘋果（來源： 1664，程序設計導引及在線實踐（李文新）例題9.5 P203）問題描述：把M個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法（用K表示）？注意：5，1，1和1，5，1 是同一種分法。輸入：第一行是測試數(shù)據的數(shù)目t（0 <= t <= 20）。以下每行均包含二個整數(shù)M和N，以空格分開。1<=M，N<=10。輸出：對輸入的每組數(shù)據M和N，用一行輸出相應的K。樣例輸入：17 3樣例輸出：8解題思路：所有不同的擺放方法可以分為兩類：至少有一個盤子空著和所有盤子都不空。我們可以分別計算這兩類擺放方法的數(shù)目，然后把它們加起來。對于至少空

13、著一個盤子的情況，則N個盤子擺放M個蘋果的擺放方法數(shù)目與N-1個盤子擺放M個蘋果的擺放方法數(shù)目相同。對于所有盤子都不空的情況，則N個盤子擺放M個蘋果的擺放方法數(shù)目等于N個盤子擺放M-N個蘋果的擺放方法數(shù)目。我們可以據此來用遞歸的方法求解這個問題。設f(m, n)為m個蘋果，n個盤子的放法數(shù)目，則先對n作討論，如果n>m，必定有n-m個盤子永遠空著，去掉它們對擺放蘋果方法數(shù)目不產生影響；即if(n>m) f(m,n) = f(m,m)。當n <= m 時，不同的放法可以分成兩類：即有至少一個盤子空著或者所有盤子都有蘋果，前一種情況相當于f(m , n) = f(m , n-1)

14、; 后一種情況可以從每個盤子中拿掉一個蘋果，不影響不同放法的數(shù)目，即f(m , n) = f(m-n , n)?？偟姆盘O果的放法數(shù)目等于兩者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)。整個遞歸過程描述如下： int f(int m , int n) if(n = | m = 0) return 1; if(n > m) return f (m, m); return f (m , n-1)+f (m-n , n); 出口條件說明：當n=時，所有蘋果都必須放在一個盤子里，所以返回；當沒有蘋果可放時，定義為種放法；遞歸的兩條路，第一條n會逐漸減少，終會到達出口n=1; 第二

15、條m會逐漸減少，因為n>m時，我們會return f(m , m) 所以終會到達出口m=0。參考程序：#include<stdio.h>int count(int x,int y)if(y=1 | x=0) return 1;if(x<y) return count(x,x);return count(x,y-1)+count(x-y,y);int main()int t,m,n;int i;scanf("%d",&t);for(i=0;i<t;i+)scanf("%d%d",&m,&n);print

16、f("%dn",count(m,n);return 0;注意事項：問題一：沒有想清楚如何遞歸，用循環(huán)模擬逐一枚舉的做法時考慮不周出錯；問題二：出口條件判斷有偏差，或者沒有分析出當盤子數(shù)大于蘋果數(shù)時要處理的情況；CS85：紅與黑（來源： 2816，程序設計導引及在線實踐（李文新）例9.6 P204）問題描述：有一間長方形的房子，地上鋪了紅色、黑色兩種顏色的正方形瓷磚。你站在其中一塊黑色的瓷磚上，只能向相鄰的黑色瓷磚移動。請寫一個程序，計算你總共能夠到達多少塊黑色的瓷磚。輸入：包括多個數(shù)據集合。每個數(shù)據集合的第一行是兩個整數(shù)W和H，分別表示x方向和y方向瓷磚的數(shù)量。W和H都不超

17、過20。在接下來的H行中，每行包括W個字符。每個字符表示一塊瓷磚的顏色，規(guī)則如下1）.：黑色的瓷磚；2）#：紅色的瓷磚；3）：黑色的瓷磚，并且你站在這塊瓷磚上。該字符在每個數(shù)據集合中唯一出現(xiàn)一次。當在一行中讀入的是兩個零時，表示輸入結束。輸出：對每個數(shù)據集合，分別輸出一行，顯示你從初始位置出發(fā)能到達的瓷磚數(shù)(記數(shù)時包括初始位置的瓷磚)。樣例輸入：6 9 .#. .# . . . . . #.# .#.#. 0 0樣例輸出：45解題分析：這個題目可以描述成給定一點，計算它所在的連通區(qū)域的面積。需要考慮的問題包括矩陣的大小，以及從某一點出發(fā)向上下左右行走時，可能遇到的三種情況：出了矩陣邊界、遇到.

18、、遇到# 。設f(x, y)為從點(x,y) 出發(fā)能夠走過的黑瓷磚總數(shù)，則f(x, y) = 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1) 這里需要注意，凡是走過的瓷磚不能夠被重復走過?？梢酝ㄟ^每走過一塊瓷磚就將它作標記的方法保證不重復計算任何瓷磚。參考程序：#include<stdio.h>int W,H;char z2121;int f(int x,int y)if(x<0 | x>=W | y<0 | y>=H) /如果走出矩陣范圍return 0;if(zxy='#'

19、;) /該塊瓷磚已被走過return 0;elsezxy='#'return 1+f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1);int main()int i,j,num;while(scanf("%d%d",&H,&W) && W != 0 && H != 0)num=0;for(i=0;i<W;i+) /讀入矩陣scanf("%s",zi);for(i=0;i<W;i+)for(j=0;j<H;j+)if(zij='')prin

20、tf("%dn",f(i,j);return 0;注意事項：問題一：走過某塊瓷磚后沒有將它標記，導致重復計算或無限遞歸；問題二：在遞歸出口條件判斷時，先判斷該網格點是否是#，再判斷是否出邊界，導致數(shù)組越界；問題三：讀入數(shù)據時，用scanf 一個字符一個字符讀入，沒有去掉數(shù)據中的行尾標記，導致數(shù)據讀入出錯。在上面放蘋果的例題中可以看出，在尋找從f(x) 向出口方向的遞歸方法時，我們是對可能的情況做了一步枚舉，即將所有可能情況劃分為至少有一個盤子空著和所有盤子至少有一個蘋果兩種情況。這種通過一步枚舉進行遞歸的方法是很常用的。例如在例題“紅與黑”中，我們枚舉了在一個方格點上的四種

21、可能的走法。例題“紅與黑”與前幾個例題不同的地方在于，在該問題中有一個記錄地圖的全局量，在每一個格點行走時，我們會改變這個全局量的狀態(tài)。我們在處理每個格點時按上下左右的順序依次走向相鄰格點，當我們走過左邊的格點時，改變了全局量的狀態(tài)，只是這種改變不影響我們繼續(xù)走向右邊的格點。但是對于另外一類問題，情況可能會不同，在我們嘗試了前面的分支情況后，要將全局量恢復成進入分支前的狀態(tài)，然后再嘗試其它的分支情況。下面的例題就是這種情況。CS86：八皇后問題（來源： 2754，程序設計導引及在線實踐（李文新）例9.7 P207）問題描述：會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋

22、子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇后問題。 對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a與之對應，即a=b1b2.b8，其中bi為相應擺法中第i行皇后所處的列數(shù)。已經知道8皇后問題一共有92組解（即92個不同的皇后串）。給出一個數(shù)b，要求輸出第b個串。串的比較是這樣的：皇后串x置于皇后串y之前，當且僅當將x視為整數(shù)時比y小。輸入：第1行是測試數(shù)據的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據占1行，包括一個正整數(shù)b(1 <= b <= 92)。輸出：輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數(shù)，是對應于b的皇后串。樣

23、例輸入：2192樣例輸出：1586372484136275數(shù)據分析：解題分析（1）：因為要求出92種不同擺放方法中的任意一種，所以我們不妨把92種不同的擺放方法一次性求出來，存放在一個數(shù)組里。為求解這道題我們需要有一個矩陣仿真棋盤，每次試放一個棋子時只能放在尚未被控制的格子上，一旦放置了一個新棋子，就在它所能控制的所有位置上設置標記，如此下去把八個棋子放好。當完成一種擺放時，就要嘗試下一種。若要按照字典序將可行的擺放方法記錄下來，就要按照一定的順序進行嘗試。也就是將第一個棋子按照從小到大的順序嘗試；對于第一個棋子的每一個位置，將第二個棋子從可行的位置從小到大的順序嘗試；在第一第二個棋子固定的情

24、況下，將第三個棋子從可行的位置從小到大的順序嘗試；依次類推。首先，我們有一個8*8的矩陣仿真棋盤標識當前已經擺放好的棋子所控制的區(qū)域。用一個有92行每行8個元素的二維數(shù)組記錄可行的擺放方法。用一個遞歸程序來實現(xiàn)嘗試擺放的過程?；舅枷胧羌僭O我們將第一個棋子擺好，并設置了它所控制的區(qū)域，則這個問題變成了一個7皇后問題，用與8皇后同樣的方法可以獲得問題的解。那我們就把重心放在如何擺放一個皇后棋子上，擺放的基本步驟是：從第1到第8個位置，順序地嘗試將棋子放置在每一個未被控制的位置上，設置該棋子所控制的格子，將問題變?yōu)楦∫?guī)模的問題向下遞歸，需要注意的是每次嘗試一個新的未被控制的位置前，要將上一次嘗試

25、的位置所控制的格子復原。參考程序（1）：#include <stdio.h>#include <math.h>int queenPlaces928; /存放92種皇后棋子的擺放方法int count=0; /記錄當前棋子擺放成功方案的個數(shù)int board88; /仿真棋盤void putQueen(int ithQueen); /遞歸函數(shù)，每次擺好一個棋子int abs(int a) /G+里沒有這個函數(shù)，需要加if(a<0)return -1*a;return a;int main()int n,i,j;for(i=0;i<8;i+) /初始化for(j

26、=0;j<8;j+)boardij=-1;for(j=0;j<92;j+)queenPlacesji=0;putQueen(0); /從第0個棋子開始擺放，運行的結果是將queenPlaces生成好scanf("%d",&n);for(i=0;i<n;i+)int ith;scanf("%d",&ith);for(j=0;j<8;j+)printf("%d",queenPlacesith-1j);printf("n");return 0;void putQueen(int i

27、thQueen)int i,k,r;if(ithQueen=8)count+;return;for(i=0;i<8;i+)if(boardiithQueen=-1)/找到可以擺放皇后的位置，擺放皇后boardiithQueen=ithQueen;/將其后所有的擺放方法的第ith個皇后都放在i+1的位置上，/在i增加以后，后面的第ith個皇后擺放方法會覆蓋此時的設置for(k=count;k<92;k+)queenPlaceskithQueen=i+1;/設置控制范圍for(k=0;k<8;k+)for(r=0;r<8;r+)if(boardkr=-1 &&

28、; (k=i | r=ithQueen | abs(k-i)=abs(r-ithQueen)boardkr=ithQueen;/向下級遞歸putQueen(ithQueen+1);/回溯，撤銷控制范圍for(k=0;k<8;k+)for(r=0;r<8;r+)if(boardkr=ithQueen)boardkr=-1;解題分析2：上面的方法用一個二維數(shù)組來記錄棋盤被已經放置的棋子的控制情況，每次有新的棋子放置時用了枚舉法來判斷它控制的范圍。還可以用三個一維數(shù)組來分別記錄每一列，每個45度的斜線和每個135度的斜線上是否已經被已放置的棋子控制，這樣每次有新的棋子放置時，不必再搜索它

29、的控制范圍，可以直接通過三個一維數(shù)組判斷它是否與已經放置的棋子沖突，在不沖突的情況下，也可以通過分別設置三個一維數(shù)組的相應的值，來記錄新棋子的控制范圍。參考程序2：#include<stdio.h>int record929,mark9,count=0; /record記錄全部解，mark記錄當前解bool range9,line117,line217; /分別記錄列方向，45度，135度方向上被控制的情況void tryToPut(int); /求全部解的過程int main()int i,testtimes,num;scanf("%d",&testtimes);for(i=0;i<=8;i+)rangei=true;for(i=0;i<17;i+)line1i=line2i=true;tryToPut(1);while(testtimes-)scanf("%d",&num);for(i=1;i<=8;i+)printf("%d",recordnum-1i);printf("n");return 0;void tryToPut(int i)int j,k;if(i>8) /如果最后一個皇后被放置完畢，將當前解復制到