2018-3-10

之前在一個網站上看到了一些遞歸題目的合集，題目來源是：
http://bailian.openjudge.cn/，
是北京大學ACM訓練和相關程序課程在線考試系統。
我先列出所有的題目編號，具體代碼會在下面：

題目名稱/題目ID 菲波那契數列 2753 二叉樹 2756 逆波蘭表達式 2694 放蘋果 1664 紅與黑 2816 八皇后問題 2754 木棍問題 2817 城堡 2815 分解因數 2749 迷宮 2790 算24 2787 文件結構"圖" 2775 小游戲 2802 碎紙機 2803 棋盤分割 1191 棋盤問題 1321

1.斐波那契數列
這個對我們來說應該并不陌生，f(n)=f(n-1)+f(n-2)，初始化f(1)=1，f(2)=1，當n比較大的時候，我們會發現有些f(m)會被我們計算了多次，那么我們可以先將它們存到數組里，如果我們需要用的話直接去數組里面取就可以了。

#include<iostream> #include<cstring> using namespace std;const int N = 20; int fib[N+1];int dfs(int p){if (fib[p]) return fib[p];fib[p]=dfs(p-1)+dfs(p-2);return fib[p]; }int main(){memset(fib,0,sizeof(fib));fib[1]=1;fib[2]=1;int t,n;cin>>t;while(t--){cin>>n;if (fib[n]) cout<<fib[n]<<endl;else cout<<dfs(n)<<endl;}return 0; }

2.二叉樹
這個題目讓我們找到兩個節點的最大公共節點，我們不難發現二叉樹的性質，父節點的值是子節點值的1/2，利用這個特點我們可以一步步的向上找。

#include<iostream> using namespace std;int x,y;int dfs(int i,int j){if (i==j) return i;if (i>j){return dfs(i/2,j);}else{return dfs(i,j/2);} }int main(){while (cin>>x>>y){cout<<dfs(x,y)<<endl;}return 0; }

3.逆波蘭表達式
說實話，我覺得這個題目本身就很神奇，我在想這個題目的時候在糾結輸入到底應該如何處理，后來在小伙伴的提醒之下寫出了答案。
我們可以在函數里面等待輸入，當輸入的是運算符的時候，我會等待輸入兩個數字來進行運算，如果輸入的還是運算符，我們可以繼續等待，直至輸入數字，返回結果與相應的運算符進行運算。

#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std;char x[10];double dfs(){cin>>x;switch(x[0]){case '+':{return dfs()+dfs();break;}case '-':{return dfs()-dfs();break;}case '*':{return dfs()*dfs();break;}case '/':{return dfs()/dfs();break;}default:return atof(x);} }int main(){printf ("%f\n",dfs());return 0; }

4.放蘋果
這道題目老早就見過，但是在這一次寫的時候又出現了 一個問題，我知道如果第n個盤子不用的話就等同于m個蘋果放在n-1個盤子中，但是如果我們第n個盤子用了呢？那我們就得把所有的n個盤子里面都放一個才可以，因為我們這個是不考慮順序的，我們必須保證得到的兩個是完全沒有交集的，我們不能把相同的情況計算多遍！如果說我們沒有把n個盤子都放一個的話，那么我們在f(m,n-1)里面也會出現空的盤子，那可能就出現重復的情況了。

#include<iostream> using namespace std;int dfs(int m,int n){if (m<0||n<0){return 0;}if (m==1||n==1||m==0||n==0) return 1;return dfs(m,n-1)+dfs(m-n,n); }int main(){int t;cin>>t;while (t--){int m,n;cin>>m>>n;cout<<dfs(m,n)<<endl;}return 0; }

5.紅與黑
這種題目應該屢見不鮮了，就是走迷宮類的題目，實現起來的套路似乎差不多。

#include<iostream> #include<cstring> using namespace std;const int N = 20; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; char x[N+1][N+1]; int res;void dfs(int p,int q){for (int k=0;k<4;k++){int ii=p+dx[k],jj=q+dy[k];if (x[ii][jj]=='.'){x[ii][jj]='#';res++;dfs(ii,jj);}} }int main(){int p,q,w,h;while (cin>>w>>h){if (w==0&&h==0){break;}memset(x,0,sizeof(x));res=0;for (int i=1;i<=h;i++){for (int j=1;j<=w;j++){cin>>x[i][j];if (x[i][j]=='@'){p=i;q=j;}}}dfs(p,q);cout<<res+1<<endl;}return 0; }

6.八皇后問題
n皇后問題之前在藍橋杯集訓的時候有位學長給我們講過，有一種聽過了就再也忘不了的感覺。。。

#include<iostream> #include<cstring> using namespace std;const int N = 8; bool h[N+1],z[2*N+1],y[2*N+1]; int r[N+1]; int res,n; bool flag;bool isvalid(int i,int j){if (h[j]||z[i-j+N]||y[i+j]) return false;return true; }void dfs(int step){if (flag) return ;if (step==N+1){res++;if (res==n){for (int i=1;i<=N;i++){cout<<r[i];}cout<<endl;flag=true;}return ; }for (int j=1;j<=N;j++){if (isvalid(step,j)){h[j]=true;z[step-j+N]=true;y[j+step]=true;r[step]=j;dfs(step+1);h[j]=false;z[step-j+N]=false;y[j+step]=false;}} }int main(){int t;cin>>t;while (t--){cin>>n;res=0;flag=false;memset(h,false,sizeof(h));memset(z,false,sizeof(z));memset(y,false,sizeof(y));dfs(1);}return 0; }

7.木棍問題
說一下我思路的轉變？！
首先我們得知道可能的答案的范圍，應該是木棒的最大長度max與木棒長度之和sum之間，我們需要對這之間的值進行枚舉直到找到滿足條件的即可。
對于某一個特定的長度p，q=sum/p即為根數，我們需要求出給定的木棒能不能組合成q根長度為p的木棒即可。
我一開始覺得只要像八皇后那樣即可，看能不能找到q個和為p的木棒即可，后來我發現，這是不可行的，因為我們在回溯的時候只有在當前循環都不滿足條件（或者都計算過了）才會返回至上一層，那么我們必然會使用之前已經有過的木棒了，這當然是不可行的，比如說1,2,3,4,8,8,8…，當我們的p為11，q為3時，我們到1,2,8時是滿足s=p=11的，然后我們就來到了第二個8，也滿足，然后來到了第三個8也滿足，我們會發現這里的1,2,被我們使用了多次，這當然是不可行的。那我們肯定會想我們把當前使用到的都存起來，然后在滿足s=p=11時對這些值進行標記，以后不能再使用了，如果還是用當前的這個方法當然是不可行的，因為不難發現即使我們對它們進行了標記也晚了。不僅要解決上面的問題，就算我們對它們進行了標記，我們標記的那些也可能再次失去標記，比如說我們只是求得了s=p的一個情況，剩下的也不一定可以滿足條件，反之，我們可以再換一種組合方式才可以使剩下的滿足條件，這需要我們再一次進行回溯，大概應該就是這么個意思吧！

1.以一個小棒為開頭，用dfs看看能否把這個小棒拼湊成p長，如果可以，用f[i]記錄下用過的小棒，然后繼續以另外一個小棒為開頭，以此類推。2.小棒的長度從大到小排序。3.如果當前最長的小棒不能拼成p長，那么就返回前一步，更改前一步的最長小棒的組合情況（這里不能是全部退出），不用再繼續搜索下去了。 #include<iostream> #include<algorithm> #include<cstring> using namespace std;const int N = 64; int n,x[N+1]; bool flag,f[N+1];bool cmp(int a,int b){return a>b; }bool dfs(int total,int unused,int left,int len){if (unused==0&&left==0) return true;if (left==0) left=len;for (int i=0;i<total;i++){if (f[i]) continue;if (x[i]>left) continue;f[i]=true;if (dfs(total,unused-1,left-x[i],len)){return true;}f[i]=false;if (x[i]==left||left==len) break;}return false; }int main(){while (cin>>n){if (n==0) break;int su=0;for (int i=0;i<n;i++){cin>>x[i];su+=x[i];}sort(x,x+n,cmp);for (int i=x[0];i<=su;i++){memset(f,false,sizeof(f));if (su%i!=0) continue;if (dfs(n,n,0,i)){cout<<i<<endl;break;}}}return 0; }

8.城堡
比較簡單的一個題目，可以進行處理的是：它給我們的是1,2,4,8分別對應數二進制表示的第0,1,2,3位，所以我們在判斷的時候只要作相應的位運算就可以判斷那個方向有沒有墻了。

#include<iostream> #include<cstring> using namespace std;const int N = 50; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; int num[4]={2,8,1,4}; int x[N+1][N+1]; bool f[N+1][N+1]; int sum,m,n;bool isvalid(int i,int j){if (i<1||j<1||i>m||j>n) return false;return true; }void dfs(int i,int j){for (int k=0;k<4;k++){int ii=i+dx[k],jj=j+dy[k];if (isvalid(ii,jj)&&(x[i][j]&num[k])==0&&!f[ii][jj]){f[ii][jj]=true;sum++;dfs(ii,jj);}} }int main(){while (cin>>m>>n){int res=0,num=0;memset(f,false,sizeof(f));for (int i=1;i<=m;i++){for (int j=1;j<=n;j++){cin>>x[i][j];}}for (int i=1;i<=m;i++){for (int j=1;j<=n;j++){if (!f[i][j]){f[i][j]=true;num+=1;sum=1;dfs(i,j);res=max(sum,res);}}}cout<<num<<endl<<res<<endl;}return 0; }

9.分解因數
如果說某個數i能夠被n整除的話那么它就是n的一個因數，然后我們只要再找到n=n/i的因數就可以了，這是一個遞歸的想法，由于題目要求1 < a1 <= a2 <= a3 <= … <= an，那么我們得記住當前的ai，下一個ai+1必須滿足大于等于ai即可，當然，遞歸結束的條件是n=1。

#include<iostream> using namespace std;int num;void dfs(int m,int n){if (n<=0) return ;if (n==1){num++;return ;}for (int i=m;i<=n;i++){if (n%i==0){dfs(i,n/i);}} }int main(){int t,n;cin>>t;while (t--){num=0;cin>>n;dfs(2,n);cout<<num<<endl;}return 0; }

10.迷宮
類似的題目，唯一需要注意的是：如果起點或者終點有一個不能通行(為#)，則看成無法辦到。

#include<iostream> using namespace std;const int N = 100; char x[N+1][N+1]; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; int n,ha,la,hb,lb; bool flag;bool isvalid(int i,int j){if (i<0||j<0||i>=n||j>=n) return false;return true; }void dfs(int i,int j){if (flag) return ;if (i==hb&&j==lb){flag=true;return ;}for (int k=0;k<4;k++){int ii=i+dx[k],jj=j+dy[k];if (isvalid(ii,jj)&&x[ii][jj]=='.'){x[ii][jj]='#';dfs(ii,jj);}} }int main(){int t;cin>>t;while (t--){flag=false;cin>>n;for (int i=0;i<n;i++){for (int j=0;j<n;j++){cin>>x[i][j];}}cin>>ha>>la>>hb>>lb;if (x[ha][la]=='#'||x[hb][lb]=='#'){cout<<"NO"<<endl;continue;}dfs(ha,la);if (flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0; }

11.算24
說實話，我覺得這個題目蠻好的。遞歸真的是個神奇的東西，我們不妨假設x[i]和x[j]是參加運算的兩個數，且我們假設i是小于j的，只要我們在進行x[i]-x[j]的時候同時也進行一次x[j]-x[i]就可以了，我們將每次x[i]和x[j]操作后的值放在x[i]里面，那么我們每次進行num-1的操作時，需要將num-1對應的值保存在x[j]里面，因為我們每次i是從0到num-1進行遍歷的，如果不保存的話我們將要失去它。當然，我們還要進行回溯來恢復x[i]和x[j]的值。

#include<iostream> #include<cmath> #define eps 1e-5 using namespace std;const int N = 4; double x[N+1];int dfs(int num){if (num==1){if (fabs(x[0]-24)<eps) return 1;return 0;}for (int i=0;i<num-1;i++){for (int j=i+1;j<num;j++){double p=x[i],q=x[j];x[j]=x[num-1];x[i]=p+q;if (dfs(num-1)) return 1;x[i]=p-q;if (dfs(num-1)) return 1;x[i]=q-p;if (dfs(num-1)) return 1;x[i]=p/q;if (dfs(num-1)) return 1;x[i]=q/p;if (dfs(num-1)) return 1;x[i]=p*q;if (dfs(num-1)) return 1;x[i]=p;x[j]=q;}}return 0; }int main(){while (cin>>x[0]>>x[1]>>x[2]>>x[3]){if (x[0]==0&&x[1]==0&&x[2]==0&&x[3]==0) break;if (dfs(4)){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0; }

12.棋盤問題
先說最后一個棋盤問題，感覺這個像是八皇后題目的變形，其實思想都是差不多的，唯一需要我們注意的是，不是所有的地方都任由我們放置棋子了，當然如果我們用列的視角來看這個題目的話，換言之就會存在某一列的任意位置都不能放置棋子的問題了，所以說如果我們輸入的k大于n的話是一定沒有滿足題意的解的，這時我們不能只用一個參數step來標記當前列了，我們需要兩個參數，一個是當前列，另一個是當前放置的棋子的個數，如果說在l列有滿足條件的，那么我們就step+1，l+1,但是如果說某一列不存在滿足條件的，那么我們就step不變，再去下一列尋找即可。

#include<iostream> #include<cstring> using namespace std;const int N = 8; char x[N+1][N+1]; bool h[N+1],flag; int n,k,sum,p;void dfs(int step,int l){if (step==k){sum++;return ;}if (l>n) return ;for (int i=1;i<=n;i++){if (!h[i]&&x[i][l]!='.'){h[i]=true;dfs(step+1,l+1);h[i]=false;}}dfs(step,l+1); }int main(){while (cin>>n>>k){if (n==-1&&k==-1){break;}memset(h,false,sizeof(h));for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){cin>>x[i][j];}}if (k>n){cout<<0<<endl;continue;}sum=0;dfs(0,1);cout<<sum<<endl;}return 0; }

13.小游戲
在TLE了n多次之后還是沒有AC…
我覺得思路還是比較明確的，有三個值得我們注意的地方：

（1）輸入里面是有空格的，而scanf在遇到空格時會結束輸入。 （2）我們求的次數等同于需要拐彎的次數，而不是經過的空白區域的個數，所以我們需要兩個數來標記當前是從哪一個方向的格子過來的，但是我們經過觀察可以發現，只要用一個數（0~3）就能表示了。 （3）這個題目橫縱坐標可能和我們平時的不太一樣（我是這么覺得的）。

雖然還是TLE，還是要附上代碼的。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int N = 80; char x[N+1][N+1]; bool f[N+1][N+1]; int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; int w,h,x1,y1,x2,y2,res;void dfs(int i,int j,int sum,int pp){if (sum>=res) return ;if (i==y2&&j==x2){if (sum<res) res=sum;return ;}for (int k=0;k<4;k++){int ii=i+dx[k],jj=j+dy[k];if (ii>=0&&jj>=0&&ii<=h+1&&jj<=w+1&&!f[ii][jj]&&x[ii][jj]!='X'){f[ii][jj]=true;if (pp==k){dfs(ii,jj,sum,k);}else{dfs(ii,jj,sum+1,k);}f[ii][jj]=false;}} }int main(){int n1=1;while (scanf ("%d%d",&w,&h)!=EOF){if (!w&&!h) break;for (int i=1;i<=h;i++){getchar();for (int j=1;j<=w;j++){x[i][j]=getchar();}}printf ("Board #%d:\n",n1++);int n2=1;while (scanf ("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF){if (!x1&&!y1&&!x2&&!y2) break;memset(f,false,sizeof(f));if (x[y1][x1]==' '||x[y2][x2]==' '){printf ("Pair %d: impossible.\n",n2++);continue;}res=10000;x[y2][x2]=' ';dfs(y1,x1,0,-1);x[y2][x2]='X';if (res==10000){printf ("Pair %d: impossible.\n",n2++);}else{printf ("Pair %d: %d segments.\n",n2++,res);}}printf ("\n");}return 0; }

14.碎紙機
大體的意思就是讓你把一串數字隨便分開來，給出能夠組成小于給定數字的最大的組合方式。
遞歸的回溯真是一個神奇的東西，首先我們要把給的那個數拆分開來。如果每一位上的數字之和都大于給定的m的話，那么是無解的；如果說對于某一個已經求得的滿足條件的最大小于m的和，存在與他相等的，就把flag=true，也就是說這是是大于一個滿足條件的，如果再存在比它大的滿足條件的，就把flag再置為false，因為我們的值已經被更新過了。
我們得用一個數標記我們來到了第幾個數，當來到最后一個數的時候我們就要進行判斷了。

#include<iostream> #include<cstring> using namespace std;const int N = 6; int x[N+1],r[N+1],p[N+1]; int m,n,num,res_long,res_sum; bool flag;bool cut(int a){int sum=0;num=1;while (a){x[num++]=a%10;sum+=a%10;a/=10;}if (sum>m) return false;return true; }void dfs(int step,int sum_now,int k){if (sum_now>m) return ;if (step==0){if (sum_now>res_sum){memcpy(r,p,sizeof(p));res_long=k-1;res_sum=sum_now;flag=false;return;}if (sum_now==res_sum){flag=true;return ;}return ;}int tmp=0;for (int i=step;i>=1;i--){tmp=10*tmp+x[i];p[k]=tmp;dfs(i-1,sum_now+tmp,k+1);} }int main(){while (cin>>m>>n){if (m==0&&n==0) break;if (m==n){cout<<m<<" "<<m<<endl;continue;}if (!cut(n)){cout<<"error"<<endl;continue;}flag=false;res_long=0;res_sum=0;dfs(num-1,0,1);if (flag){cout<<"rejected"<<endl;}else{cout<<res_sum<<" ";for (int i=1;i<res_long;i++){cout<<r[i]<<" ";}cout<<r[res_long]<<endl;}}return 0; }

棋盤分割和文件結構”圖” 這兩道題暫時還沒有解決…

總結

以上是生活随笔為你收集整理的递归算法思路以及题目总结（未完待续...）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。