遞歸遞推測試題分析講解

1逆波蘭表達式問題描述：逆波蘭表達式是一種把運算符前置的算術表達式，例如普通的表達式2+3的逆波蘭表示法為+23。逆波蘭表達式的優(yōu)點是運算符之間不必有優(yōu)先級關系，也不必用括號改變運算次序，例如（2+3）*4的逆波蘭表示法為*+234。本題求解逆波蘭表達式的值，其中運算符包括+-*/四個。輸入數(shù)據(jù):輸入為一行，其中運算符和運算數(shù)之間都用空格分隔，運算數(shù)是浮點數(shù)。輸出要求：輸出為一行，表達式的值輸入樣例：*+11.012.0+24.035.0輸出樣例：1357.0000002分析解題思路：這個問題看上去有些復雜，如果只是簡單地模擬計算步驟不太容易想清楚，但是如果用遞歸的思想就非常容易想清楚，讓我們根據(jù)逆波蘭表達式的定義進行遞歸求解。在這個遞歸函數(shù)中，針對當前的輸入，有五種情況：1、輸入是常數(shù)，則表達式的值就是這個常數(shù)2、輸入的是‘

+’，則表達式的值是再繼續(xù)讀入兩個表達式并計算出它們的值3、輸入的是‘

-’；4、輸入的是‘*’；5、輸入的是‘

/’;后面幾種情況與2相同，只是計算從‘

+’變成‘

-’

‘*’

‘

/’。3#include<stdio.h>#include<math.h>doubleexp(){chara[10];scanf(“%s”,a);switch(a[0]){case’+’:returnexp()+exp();case’-’:returnexp()-exp();case’*’:returnexp()*exp();case’/’:returnexp()/exp();default:returnatof(a);}}voidmain(){doubleans;ans=exp();printf(“%f”,ans);}4實現(xiàn)中常見的問題問題一：不適應遞歸的思路，直接分析輸入的字符串，試圖自己寫進棧出棧的程序，寫得邏輯復雜，因考慮不周出錯。問題二：不會使用atof（）函數(shù)，自己處理浮點數(shù)的讀入，邏輯復雜出錯。5放蘋果問題描述：把M個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的放法？（用K表示）注意：5,1,1和1,5,1是同一種分法。輸入數(shù)據(jù)第一行是測試數(shù)據(jù)的數(shù)目t（0<=t<=20），以下每行均包含兩個整數(shù)M和N，以空格分開。1<=M，N<=10。輸出要求對輸入的每組數(shù)據(jù)M和N，用一行輸出相應的K。輸入樣例173輸出樣例86解題思路：1、所有不同的擺放方法可以分為兩類：至少有一個盤子空著和所有的盤子都不空。我們可以分別計算這兩類擺放方法的數(shù)目，然后把它們加起來。對于至少空著一個盤子的情況，則N個盤子擺放M個蘋果的擺放數(shù)目與N-1個盤子擺放M個蘋果的擺放方法數(shù)目相同。對于所有盤子都不空的情況，則N個盤子擺放M個蘋果的擺放方法數(shù)目等于N個盤子擺放M-N個蘋果的擺放方法數(shù)目。我們可以據(jù)此來用遞歸的方法求解這個問題。2、設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);后一種情況可以從每個盤子中拿掉一個蘋果，不影響不同放法的數(shù)目，即f(m,n)=f(m-n,n)?？偟姆盘O果的放法數(shù)目等于兩者的和，即f(m,n)=f(m,n-1)+f(m-n,n)。整個遞歸過程描述如下：intf(intm,intn){if(n==1||m==0)return1;if(n>m)returnf(m,m);returnf(m,n-1)+f(m-n,n)}3、出口條件說明：當n=1是，所有蘋果都必須放到一個盤子里，所有返回1，當沒有蘋果可放時，定義為1種放法。遞歸的兩條路，第一條n會逐漸減少，終會達到出口n==1；第二條m會逐漸減少，因為n>m時，我們會returnf(m,m)所以終會到達出口m==0.7#include<stdio.h>intcount(intx,inty){if(y==1||x==0)return1;if(x<y)returncount(x,x);returncount(x,y-1)+count(x-y,y);}voidmain(){intt,m,n;scanf(“%d”,&t);for(inti=0;i<t;i++){scanf(“%d%d”,&m,&n);printf(“%d\n”,count(m,n));}8實現(xiàn)中常見的問題問題一：沒有想清楚如何遞歸，用循環(huán)模擬逐一枚舉的做法時考慮不周出錯。問題二：出口條件判斷有偏差，或者沒有分析出當盤子大于蘋果時要處理的情況。9白與黑問題描述：有一間長方形的房子，地上鋪了白色、黑色兩種顏色的正方形瓷磚，你站在其中一塊黑色的瓷磚上，只能向相鄰的黑色瓷磚移動。請寫一個程序，計算你總共能夠達到多少塊黑色的瓷磚。輸入數(shù)據(jù)：包括多個數(shù)據(jù)集合，每個數(shù)據(jù)集合的第一行是兩個整數(shù)W和H，分別表示x方向和y方向瓷磚的數(shù)量。W和H都不超過20。在接下來的H行中，每行包括W個字符。每個字符表示一塊瓷磚的顏色，規(guī)則如下：1）’.’:黑色的瓷磚2）’#’:白色的瓷磚3）’@’:黑色的瓷磚，并且你站在這塊瓷磚上。該字符在每個數(shù)據(jù)集合中唯一出現(xiàn)一次當在一行中讀入的是兩個零時，表示輸入結束。輸出要求：對每個數(shù)據(jù)集合，分別輸出一行，顯示你從初始位置出發(fā)能到達的瓷磚數(shù)（記數(shù)時包括初始位置的瓷磚）。輸入樣例：69….#.…..#…………………………#@...#.#..#.00輸出樣例：4510分析解題思路：這個題目可以描述成給定一點，計算它所在的連通區(qū)域的面積。需要考慮的問題包括矩陣的大小，以及從某一點出發(fā)向上下左右行走時，可能遇到的三種:出了矩陣邊界、遇到‘.’、遇到’#’。設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)

這里需要注意，凡是走過的瓷磚不能夠被重復走過?？梢酝ㄟ^每走過一塊瓷磚就將其作標記的方法保證不重復計算任何瓷磚。11#include<stdio.h>intW,H;charz[21][21];intf(intx,inty){if(x<0||x>=W)||y<0||y>=H)

return0;if(z[x][y]==‘#’)return0;else{z[x][y]=‘#’;//將走過的瓷磚做標記

return1+f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)}}voidmain(){inti,j,num;while(scanf(“%d%d”,&H,&W)&&W!=0&&H!=0){num=0;for(i=0;i<W;i++)scanf(“%s”,z[i]);for(i=0;i<W;i++)for(j=0;j<H;j++)if(z[i][j]==‘’@)printf(“%d\n”,f(i,j));}}12實現(xiàn)中常見的問題問題一：走過某塊瓷磚后沒有把它標記，導致重復計算或無限遞歸。問題二：在遞歸出口條件判斷時，先判斷該網格點是否是‘#’，再判斷是否出邊界，導致數(shù)組越界。問題三：讀入數(shù)據(jù)時，用scanf一個字符一個字符讀入，沒有去掉數(shù)據(jù)中的行尾標記，導致數(shù)據(jù)讀入出錯。13八皇后問題問題描述：會下國際象棋的人都很清楚：皇后可以在橫豎斜線上不限步數(shù)地吃掉其他棋子，如何將8個皇后放在棋盤上（有8*8個方格），使他們誰也不能被吃掉！這就是著名的八皇后問題。對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a與之對應，即a=b1b2…b8，其中bi為相應擺法中第i行皇后所處的列數(shù)。已經知道8皇后問題一共有92組解（即92個、不同的皇后串）。給出一個數(shù)b，要求輸出第b個串。串的比較是這樣的：皇后串x置于皇后串y之前，當且僅當將x視為整數(shù)時比y小。輸入數(shù)據(jù)：第一行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入，每組測試數(shù)據(jù)占1行，包括一個正整數(shù)b（1<=b<=92）。輸出要求：n行，每行輸出對應一個輸入。輸出應是一個正整數(shù)，是對應于b的皇后串。輸入樣例：2192輸出樣例：1586372414解題思路：1、因為要求出92中不同的擺放方法中的任意一種，所有我們不妨把92中不同的擺放方法一次性求出來，存放在一個數(shù)組里。為求解這道題我們需要一個矩陣仿真棋盤，每次試放一個棋子時只能放在尚未被控制的格子上，一旦放置了一個新棋子，就在它所能控制的所有位置上設置標記，如此下去把八個棋子放好。完成一種擺放時，就要嘗試下一種。若要按照字典序將可行擺放方法記錄下來，就要按照一定的順序進行嘗試。也就是將第一個棋子按照從小到大的順序嘗試，對于第一個棋子的位置，將第二個棋子從可行的位置從小到大的順序嘗試；在第一和第二個棋子固定的情況下，將第三個棋子從可行的位置從小到大的順序嘗試；以此類推。2、首先，我們有一個8*8的矩陣仿真棋盤標識當前已經擺好的棋子所控制的區(qū)域。用一個92行每行8個元素的二維數(shù)組記錄可行的擺放方法。用一個遞歸程序實現(xiàn)嘗試擺放的過程?；舅枷刖褪羌僭O我們將第一個棋子擺好，并設置它的控制區(qū)域，則這個問題就變成了一個7皇后問題，用與8皇后同樣的方法可以獲得問題的求解。那我們就把重心放在如何擺放一個皇后棋子上，擺放的基本步驟是：從第1到第8個位置，順序地嘗試將棋子放置在每一個未被控制的位置，設置該棋子所控制的格子，將問題變成更小規(guī)模的問題向下遞歸，需要注意的是每次嘗試一個新的未被控制的位置前，要將上一次嘗試的位置所控制的格子復原。15#include<stdio.h>#include<math.h>intqueenPlaces[92][8];intcount=0;intboard[8][8];voidputQueen(intithQueen);//遞歸函數(shù)voidmain(){intn,i,j;for(i=0;i<8;i++){for(j=0;i<8;j++)board[i][j]=-1;for(j=0;j<92;j++)queenPlaces[j][i]=0;}putQueen(0);//從第0個棋子開始擺放

scanf(“%d”,&n);for(i=0;i<n;i++){intith;scanf(“%d”,&ith)for(j=0;j<8;j++)printf(“%d”,queenPlaces[ith][j]);printf(“\n”);}}16\voidputQueen(intithQueen){inti,k,r;if(ithQueen==8){count++;return;}for(i=0;i<8;i++){if(board[i][ithQueen]==-1){board[i]