递归专题
递归加上图形按规律打印
/*
样例输入
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++){
//一定要学会找规律啊~~，不能只想着把它们存在数组里一起输出
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]);
//最关键的来了，一种方法失败，则把index往后面进移动，从后面开始计算，即使没失败，也要继续往下试探
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;
}
循环递归+全排列
#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计数的是以第几个数打头
ans[cnt]=i+1;
//访问过
flag[i]=true;
combine(cnt+1);
//访问完之后恢复
flag[i]=false;
}
}
}
int main()
{
while(cin>>n){
combine(0);
}
return 0;
}
//非递归方法，还没有研究透彻，但是调试有了进步
#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;
}
求组合数递归
#include <iostream>
using namespace std;
int n;
int m;
//正确定义是集合
bool flag[20]={false};
int ans[20];
void combine(int x,int cnt){
//只能证明出口问题，关键在于不知道如何分叉，返回数据
if(cnt==n){
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
printf("\n");
return;
}
//果然x是变化的，只是没想到怎么变1！，可以带参数的，循环一次之后前面那个就不用参与循环
for(int i=x;i<=m;i++){
if(flag[i-1]==false){
//cnt计数的是以第几个数打头
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;
}
//非递归方法，关键是什么时候入栈，什么时候出战，利用栈的特性，可以将一个数定住循环其他
#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已经达到最大值，就一定要出栈了，不然没得位置,并且后面不能继续，直接跳过
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;
}
递归组合+判断素数，一加一减显示递归的路径
#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){
//递归边界，表示已经处理完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])进行比较
//由于全排列行列肯定不一致，关键是看是否在同一对角线
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){
//递归边界，表示已经处理完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版
//深度优先遍历解决迷宫问题
#include <iostream>
using namespace std;
//如果不想递归当中带太多的内容，就应该多定义全局变量
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是为了知道结果中有几个点
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)已经访问过了或者越界返回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)){
//表示已经访问
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;
//每次循环都要设定index和方案数位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}; //记录位置是否已经入过队
int X[4]={0,0,1,-1}; //增量数组，表示上下左右位置
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; //当前结点的坐标
Q.push(Node); //将节点入队，从队尾进的
inq[x][y]=true;
while(!Q.empty()){
node top=Q.front(); //从队首取出元素
Q.pop(); //取出就可以出栈了
for(int i=0;i<4;i++){
//循环四次得到四个相邻位置，只能标识已经入队，不能标识已经访问
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(judge(newX,newY)){
//设置Node的新坐标
Node.x=newX,Node.y=newY;
Q.push(Node);
//广义遍历不用回溯走回头路，去过了就去过了
inq[newX][newY]=true;
}
}
}
}
//求出给定矩阵若干个相邻1构成的块个数
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; //存放块数
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
//循环所有元素，若元素为1且未入队
if(matrix[x][y]==1&&inq[x][y]==false){
ans++;
BFS(x,y);
}
}
}
printf("%d\n",ans);
}
return 0;
}
BFS得出玛雅人密码交换次数
/*
玛雅人密码-BFS该怎么想
该题目的思路就是：
如何用队列广度优先遍历所有可能性（QUEUE） +
如何判别并标示某串是否访问过（MAP） +
如何记录某串已经交换字符的次数 +
子串2012是否存在
这几个问题如果解决了我想你肯定能写出来。
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
map<string,int> mp; //mp[str]表示str交换次数
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;
}
//广度优先搜索特点，扩展，遍历所有结果
int BFS(string str){
string newStr;
mp.clear();
while(!q.empty()) q.pop();
q.push(str); //直接将初始字符串作为起点放入队列
mp[str]=0; //初始交换次数
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()) //表示这个字符串没有出现
{
mp[newStr]=mp[str]+1;
if(judge(newStr)) return mp[newStr];
else q.push(newStr);
}
else continue; //出现过的不用处理
}
}
return -1; //遍历完成，没发现符合要求的字符串
}
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;
}
广度优先-迷宫
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到达该位置的最少步数即层数
}S,T,Node;
int n,m;
char maze[maxn][maxn]; //迷宫信息
bool inq[maxn][maxn]={false}; //记录位置(x,y)是否已经入过队
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;
//墙壁或者已经入过队
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; //终点直接返回最少步数
}
for(int i=0;i<4;i++){
//检查4个相邻位置
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(test(newX,newY)){
//相当于创建新点了
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;
/*因为我们记下来所走的步数为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;
}
