遞歸專題
遞歸加上圖形按規(guī)律打印
/*
樣例輸入
1
6
樣例輸出
0
0 1 1
0 1 1 2 3
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34 55
*/
#include <iostream>
using namespace std;
//遞歸輸出中間值不是從中間輸出的1１取椭微！浊服，觀念性錯誤湿诊，應當從傳入的值入手
int f(int a){
if(a==0||a==1) return 1;
else return f(a-1)+f(a-2);
}
int main()
{
int n;
while(cin>>n){
for(int k=0;k<n;k++){
int num;
cin>>num;
for(int i=0;i<num;i++){
//一定要學會找規(guī)律啊~~，不能只想著把它們存在數(shù)組里一起輸出
for(int j=0;j<2*(num-1-i);j++)
cout<<" ";
if(i!=0){
cout<<"0 ";
for(int j=0;j<2*i-1;j++)
cout<<f(j)<<" ";
cout<<f(2*i-1)<<endl;
}
//特殊情況都得要考慮到
else cout<<0<<endl;
}
}
}
return 0;
}
另一種方向的遞歸
#include <cstdio>
int count;
void scheme(int a)
{
//出口是當a減成0
if(a==0)
{
count++;
return;
}
//每次都從最大處開始減少围橡，減少的方式不同
for(int i=1;i<=2&&i<=a;i++)
scheme(a-i);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
count=0;
scheme(n);
printf("%d\n",count);
}
return 0;
}
#include <iostream>
using namespace std;
//簡單的遞歸熬芜，主要是要理清楚邏輯，對于所有的物品曙强，都可以選擇放入或者不放入残拐，最后能使總和為40即為一種解~
int count,n,a[20];
//n要在此處定義的原因，作為界限
void search(int index,int sum){
if(sum==0)
{
//出口是最后可以完全拿滿40碟嘴，這才可以出去
count++;
return;
}
if(index>=n)
//如果n個值都遍歷完了溪食，還找不到那么就失敗了
return;
if(sum-a[index]>=0)
search(index+1,sum-a[index]);
//最關(guān)鍵的來了，一種方法失敗娜扇，則把index往后面進移動错沃，從后面開始計算，即使沒失敗袱衷，也要繼續(xù)往下試探
search(index+1,sum);
}
int main()
{
while(cin>>n){
count=0;
for(int i=0;i<n;i++)
cin>>a[i];
search(0,40);
cout<<count<<endl;
}
return 0;
}
循環(huán)遞歸+全排列
#include <iostream>
using namespace std;
int n;
//正確定義是集合
bool flag[20]={false};
int ans[20];
void combine(int cnt){
if(cnt==n){
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
printf("\n");
return;
}
for(int i=0;i<n;i++){
if(flag[i]==false){
//cnt計數(shù)的是以第幾個數(shù)打頭
ans[cnt]=i+1;
//訪問過
flag[i]=true;
combine(cnt+1);
//訪問完之后恢復
flag[i]=false;
}
}
}
int main()
{
while(cin>>n){
combine(0);
}
return 0;
}
//非遞歸方法捎废，還沒有研究透徹，但是調(diào)試有了進步
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> answer;
stack<int> process;
bool flag[20]={false};
int n;
void combine()
{
process.push(1);
answer.push_back(1);
flag[1]=true;
int visit;
bool pop=false;
while(!process.empty())
{
if(answer.size()==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",answer[i]);
}
printf("\n");
pop=true;
}
visit=-1;
for(int i=1;i<=n;i++)
{
if(flag[i]==false)
{
visit=i;
break;
}
}
if(visit==-1)
{
flag[process.top()]=false;
process.pop();
answer.pop_back();
pop=true;
continue;
}
if(pop)
{
bool search=false;
for(int i=process.top()+1;i<=n;i++)
{
if(flag[i]==false)
{
search=true;
visit=i;
break;
}
}
flag[process.top()]=false;
process.pop();
answer.pop_back();
if(search==false)
{
pop=true;
continue;
}
else
{
pop=false;
}
}
if(visit!=-1)
{
flag[visit]=true;
process.push(visit);
answer.push_back(visit);
}
}
}
int main()
{
while(cin>>n)
{
combine();
}
return 0;
}
求組合數(shù)遞歸
#include <iostream>
using namespace std;
int n;
int m;
//正確定義是集合
bool flag[20]={false};
int ans[20];
void combine(int x,int cnt){
//只能證明出口問題致燥，關(guān)鍵在于不知道如何分叉，返回數(shù)據(jù)
if(cnt==n){
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
printf("\n");
return;
}
//果然x是變化的排截，只是沒想到怎么變1嫌蚤！，可以帶參數(shù)的断傲，循環(huán)一次之后前面那個就不用參與循環(huán)
for(int i=x;i<=m;i++){
if(flag[i-1]==false){
//cnt計數(shù)的是以第幾個數(shù)打頭
ans[cnt]=i;
//訪問過
flag[i-1]=true;
//可以理解為記住了x的值Ｍ阎ā！往下走
combine(i,cnt+1);
//訪問完之后恢復
flag[i-1]=false;
}
}
}
int main()
{
while(cin>>m>>n){
combine(1,0);
}
return 0;
}
//非遞歸方法认罩，關(guān)鍵是什么時候入棧箱蝠，什么時候出戰(zhàn)，利用棧的特性，可以將一個數(shù)定住循環(huán)其他
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
int n,r;
void combine()
{
stack<int> process;
vector<int> answer;
process.push(1);
answer.push_back(1);
int elem;
bool pop=false;
while(!process.empty())
{
if(answer.size()==r)
{
for(int i=0;i<r;i++)
{
printf("%d ",answer[i]);
}
printf("\n");
pop=true;
}
elem=process.top();
//如果elem已經(jīng)達到最大值宦搬，就一定要出棧了牙瓢，不然沒得位置,并且后面不能繼續(xù)，直接跳過
if(elem==n)
{
process.pop();
answer.pop_back();
pop=true;
continue;
}
//后面的行為就是先出再進
if(pop)
{
process.pop();
answer.pop_back();
pop=false;
}
//只要初始的第一個值還沒到n间校，process就不會為空
if(elem<n)
{
process.push(elem+1);
answer.push_back(elem+1);
}
}
}
int main()
{
while(~scanf("%d %d",&n,&r))
{
combine();
}
return 0;
}
遞歸組合+判斷素數(shù)矾克，一加一減顯示遞歸的路徑
#include <cstdio>
#include <cmath>
using namespace std;
int n,k,count;
int number[25],sum;
bool isPrime(int n)
{
if(n<=1)
return false;
int sqr=(int)sqrt(1.0*n);
for(int i=2;i<=sqr;i++)
{
if(n%i==0)
return false;
}
return true;
}
void combine_judge(int pos,int level)
{
if(level==k)
{
if(isPrime(sum)==true)
{
count++;
}
return;
}
for(int i=pos;i<n;i++)
{
sum+=number[i];
combine_judge(i+1,level+1);
//回退之后減去，目的是換下一條路徑
sum-=number[i];
}
}
int main()
{
while(~scanf("%d %d",&n,&k))
{
for(int i=0;i<n;i++)
{
scanf("%lld",&number[i]);
}
count=0;
sum=0;
combine_judge(0,0);
printf("%d",count);
}
return 0;
}
八皇后遍歷全排列版+剪枝版
#include <iostream>
#include <cmath>
using namespace std;
const int maxn=26;
int n,p[maxn];
int cnt=0;
bool hashTable[maxn]={false};
//要類比全排列，找出所有n*n行元素的排列方式，就是皇后可能排列的位置
//要篩選出其中在對角線上的
void DFS(int index){
//遞歸邊界丹泉，表示已經(jīng)處理完1-n位
if(index==n+1){
bool flag=true;
//flag為true表示當前排列為合法方案
for(int i=1;i<=n;i++){
//遍歷任意兩個皇后蜡坊，判斷是否合法
for(int j=i+1;j<=n;j++){
//相當于兩個坐標(i,p[i)和(j,p[j])進行比較
//由于全排列行列肯定不一致，關(guān)鍵是看是否在同一對角線
if(abs(i-j)==abs(p[i]-p[j]))
flag=false;//表示不合法
}
}
if(flag){
for(int i=1;i<=n;i++){
cout<<p[i]<<" ";
}
cout<<endl;
}
return;
}
//此處是遞歸分叉
for(int i=1;i<=n;i++){
if(hashTable[i]==false){
//訪問未訪問
hashTable[i]=true;
//令p的第index位為i赠法，就是把i帶入當前排列
p[index]=i;
DFS(index+1);
//返回后如何進入下一個分叉
hashTable[i]=false;
}
}
}
int main()
{
while(cin>>n){
DFS(1);
}
return 0;
}
//剪枝版，可以去掉多余的遞歸,對于p[index]=i表示index列的行號為i
#include <iostream>
#include <cmath>
using namespace std;
const int maxn=26;
int n,p[maxn];
int cnt=0;
bool hashTable[maxn]={false};
//要類比全排列，找出所有n*n行元素的排列方式弓候，就是皇后可能排列的位置
//要篩選出其中在對角線上的
void DFS(int index){
//遞歸邊界，表示已經(jīng)處理完1-n位
if(index==n+1){
//出口不變洗做，判定的地方會變,能到這里的一定是合法的
for(int i=1;i<=n;i++){
cout<<p[i]<<" ";
}
cout<<endl;
return;
}
//此處是遞歸分叉
for(int i=1;i<=n;i++){
if(hashTable[i]==false){
bool flag=true; //表示當前皇后不會和之前的皇后沖突
for(int pre=1;pre<index;pre++){
//第index列皇后的行號為x弓叛，第pre列皇后的行號為p[pre]
if(abs(index-pre)==abs(i-p[pre])){
flag=false; //沖突，是與之前的皇后在對角線诚纸，而不是全部選出來再判斷
break;
}
}
if(flag){
//這里變成可以吧皇后放在第x行
hashTable[i]=true;
//令p的第index位為i撰筷，就是把i帶入當前排列
p[index]=i;
DFS(index+1);
//返回后如何進入下一個分叉
hashTable[i]=false;
}
}
}
}
int main()
{
while(cin>>n){
DFS(1);
}
return 0;
}
走迷宮-深度遍歷DFS版
//深度優(yōu)先遍歷解決迷宮問題
#include <iostream>
using namespace std;
//如果不想遞歸當中帶太多的內(nèi)容，就應該多定義全局變量
int m,n,last_x,last_y,start_x,start_y;
int atlas[20][20];
//存放矩陣
bool flag[20][20]={false}; //還是得要定義是否訪問過畦徘，不走回頭路
int direct[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int index,cnt; //記錄index是為了知道結(jié)果中有幾個點
int answer[250][2]; //存放x毕籽，y坐標的辦法
bool judge(int x,int y){
if(x==0||y==0||y>n||x>m)
return false;
//當前位置為0或者(x,y)已經(jīng)訪問過了或者越界返回false
if(atlas[x][y]==0||flag[x][y]==true)
return false;
return true;
}
void dispose(int x,int y,int index){
//出口地址
if(x==last_x&&y==last_y){
for(int i=0;i<index;i++){
//格式的問題，不要當成大問題
if(i!=index-1)
printf("(%d,%d)->",answer[i][0],answer[i][1]);
else
printf("(%d,%d)\n",answer[i][0],answer[i][1]);
}
cnt++;
return;
}
for(int i=0;i<4;i++){
int new_x=x+direct[i][0];
int new_y=y+direct[i][1];
if(judge(new_x,new_y)){
//表示已經(jīng)訪問
flag[new_x][new_y]=true;
answer[index][0]=new_x;
answer[index][1]=new_y;
dispose(new_x,new_y,index+1);
flag[new_x][new_y]=false;
//回退時候的操作
}
}
}
int main()
{
while(cin>>m>>n){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>atlas[i][j];
flag[i][j]=false;
}
}
cin>>start_x>>start_y;
cin>>last_x>>last_y;
//每次循環(huán)都要設(shè)定index和方案數(shù)位0井辆，對全局變量的處理
index=0;
cnt=0;
//入口也得要判斷處理
if(judge(start_x,start_y)){
flag[start_x][start_y]=true;
answer[index][0]=start_x;
answer[index][1]=start_y;
dispose(start_x,start_y,index+1);
if(cnt==0){
cout<<-1<<endl;
}
}
else{
cout<<-1<<endl;
}
}
return 0;
}
計算矩陣中含1塊-BFS版
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
4
#include <iostream>
#include <queue>
using namespace std;
const int maxn =100;
struct node{
int x,y; //坐標(x,y)
}Node;
int n,m; //矩陣大小
int matrix[maxn][maxn]; //01矩陣
bool inq[maxn][maxn]={false}; //記錄位置是否已經(jīng)入過隊
int X[4]={0,0,1,-1}; //增量數(shù)組关筒，表示上下左右位置
int Y[4]={1,-1,0,0};
bool judge(int x,int y){
//判斷坐標是否需要訪問，越界返回false
if(x>=n||x<0||y>=m||y<0) return false;
//是因為入隊了杯缺，所以暫時不訪問蒸播，當不在隊中的時候還是得要訪問
if(matrix[x][y]==0||inq[x][y]==true) return false;
return true;
}
void BFS(int x,int y){
queue<node> Q; //定義隊列
Node.x=x,Node.y=y; //當前結(jié)點的坐標
Q.push(Node); //將節(jié)點入隊，從隊尾進的
inq[x][y]=true;
while(!Q.empty()){
node top=Q.front(); //從隊首取出元素
Q.pop(); //取出就可以出棧了
for(int i=0;i<4;i++){
//循環(huán)四次得到四個相鄰位置萍肆，只能標識已經(jīng)入隊袍榆，不能標識已經(jīng)訪問
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(judge(newX,newY)){
//設(shè)置Node的新坐標
Node.x=newX,Node.y=newY;
Q.push(Node);
//廣義遍歷不用回溯走回頭路，去過了就去過了
inq[newX][newY]=true;
}
}
}
}
//求出給定矩陣若干個相鄰1構(gòu)成的塊個數(shù)
int main()
{
while(cin>>n>>m){
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
cin>>matrix[x][y];
}
}
int ans=0; //存放塊數(shù)
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
//循環(huán)所有元素塘揣，若元素為1且未入隊
if(matrix[x][y]==1&&inq[x][y]==false){
ans++;
BFS(x,y);
}
}
}
printf("%d\n",ans);
}
return 0;
}
BFS得出瑪雅人密碼交換次數(shù)
/*
瑪雅人密碼-BFS該怎么想
該題目的思路就是：
如何用隊列廣度優(yōu)先遍歷所有可能性（QUEUE） +
如何判別并標示某串是否訪問過（MAP） +
如何記錄某串已經(jīng)交換字符的次數(shù) +
子串2012是否存在
這幾個問題如果解決了我想你肯定能寫出來包雀。
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
map<string,int> mp; //mp[str]表示str交換次數(shù)
queue<string> q; //隊列用于BFS
string swapStr(string str,int i){
//分布思想，交換寫一個辦法
string newStr=str;
char tmp=newStr[i];
newStr[i]=newStr[i+1];
newStr[i+1]=tmp;
return newStr;
}
//再分步亲铡，判斷是否含有2012
bool judge(string str){
if(str.find("2012",0)==string::npos) return false;
else return true;
}
//廣度優(yōu)先搜索特點才写，擴展葡兑，遍歷所有結(jié)果
int BFS(string str){
string newStr;
mp.clear();
while(!q.empty()) q.pop();
q.push(str); //直接將初始字符串作為起點放入隊列
mp[str]=0; //初始交換次數(shù)
while(!q.empty()){
str=q.front();
q.pop();
//終于知道為啥要用BFS了，因為交換第一次算作第一層赞草，交換第二層算第二層
for(int i=0;i<str.size();i++){
newStr=swapStr(str,i);
if(mp.find(newStr)==mp.end()) //表示這個字符串沒有出現(xiàn)
{
mp[newStr]=mp[str]+1;
if(judge(newStr)) return mp[newStr];
else q.push(newStr);
}
else continue; //出現(xiàn)過的不用處理
}
}
return -1; //遍歷完成讹堤，沒發(fā)現(xiàn)符合要求的字符串
}
int main()
{
int n;
string str;
while(cin>>n){
cin>>str;
if(judge(str)) printf("0\n"); //一開始就符合要求
else{
int ans=BFS(str);
printf("%d\n",ans);
}
}
return 0;
}
廣度優(yōu)先-迷宮
5 5
. . . . .
. * . * .
. * S * .
. * * * .
. . . T *
2 2 4 3
11
#include <iostream>
#include <queue>
using namespace std;
const int maxn=100;
struct node{
int x,y;
int step;
//step是從起點S到達該位置的最少步數(shù)即層數(shù)
}S,T,Node;
int n,m;
char maze[maxn][maxn]; //迷宮信息
bool inq[maxn][maxn]={false}; //記錄位置(x,y)是否已經(jīng)入過隊
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
bool test(int x,int y){
if(x>=n||x<0||y>=m||y<0) return false;
if(maze[x][y]=='*') return false;
//墻壁或者已經(jīng)入過隊
if(inq[x][y]==true) return false;
return true;
}
int BFS(){
queue<node> q;
q.push(S); //將起點S入隊
while(!q.empty()){
node top=q.front(); //取出隊首元素
q.pop();
if(top.x==T.x&&top.y==T.y){
return top.step; //終點直接返回最少步數(shù)
}
for(int i=0;i<4;i++){
//檢查4個相鄰位置
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(test(newX,newY)){
//相當于創(chuàng)建新點了
Node.x=newX,Node.y=newY;
Node.step=top.step+1;
q.push(Node);
inq[newX][newY]=true;
}
}
}
return -1;
}
int main()
{
while(cin>>n>>m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>maze[i][j];
}
}
cin>>S.x>>S.y>>T.x>>T.y;
S.step=0;
cout<<BFS()<<endl;
}
return 0;
}
走巨石掉落迷宮，高級版
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
char a[8][9];
int dx[] = {0, 1, -1, 0, 0, -1, 1, -1, 1};
int dy[] = {0, 0, 0, 1, -1, 1, 1, -1, -1};
bool flag;
struct node{
int x, y;
int step;
}s, temp;
bool check(int x, int y)
{
if(x >= 8 || x < 0 || y >= 8 || y < 0)
return false;
return true;
}
void bfs()
{
int i, j;
s.x = 7;
s.y = 0;
s.step = 0;
queue<node>q;
q.push(s);
while(!q.empty())
{
s = q.front();
q.pop();
for(i = 0;i < 9; i++)
{
temp.x = s.x + dx[i];
temp.y = s.y + dy[i];
temp.step = s.step + 1;
/*因為我們記下來所走的步數(shù)為step房资，所以判斷點a[temp.x-temp.step+1][temp.y]是否為石頭即可知道所走的下一步是否為石頭
點a[temp.x-temp.step][temp.y]即為所走點的上面是否為石頭*/
if(check(temp.x, temp.y) && a[temp.x-temp.step][temp.y] != 'S' && a[temp.x-temp.step+1][temp.y] != 'S')
{
//用判斷是否走滿了八步來代替判重
if(a[temp.x][temp.y] == 'A' || temp.step > 8)
{
flag = 1;
return ;
}
q.push(temp);
}
}
}
return ;
}
int main()
{
int t, i, j, k;
scanf("%d", &t);
k = 1;
getchar();
while(t--)
{
for(i = 0; i < 8; i++)
{
scanf("%s", a[i]);
}
flag = 0;
bfs();
printf("Case #%d: ", k);
if(flag)
printf("Yes\n");
else
printf("No\n");
k++;
}
return 0;
}
