递归与递推

• • 递归实现指数型枚举？1~n任意选取
  • 递归实现排列型枚举？1~n随机打乱
  • 递归实现组合型枚举？n中选m个
  • • 递归改成非递归
  • 一个数表示整个棋盘的状态？开关动否=取不取？飞行员兄弟
  • 带分数
  • • 全排列分割
    • dfs嵌套，叶子节点进入另一搜索树的root节点
  • 二进制枚举每行开关状态？费解的开关

递归实现指数型枚举？1~n任意选取

递归逻辑
n的规模由n-1规模 计算得到
计算法则：
1、第n个取或不取 （ 二进制位运算 | 数组存储 ）
解释为从1~n 进行枚举
二进制位运算 | 数组存储，记录取或不取的状态
2152^{15}215 = 32768
216 = 65536
220 约等于106
263 约等于 108
2、以 n=1 为基本状态，解释为情况组合

#include 
using namespace std;
int n;
void dfs(int u,int state){//2^15 = 32768 state不超过 32768
//	state第i个二进制位代表 i取不取 if(u==n+1){for(int i=1;i<=n;i++){if((state >> (i-1)) & 1){cout<cin>>n;dfs(1,0);return 0;
} 

#include 
using namespace std;
int n;
const int N=20;
bool st[N];
void dfs(int u){if(u==n+1){for(int i=1;i<=n;i++){if(st[i])cout<cin>>n;dfs(1);return 0;
} 

递归实现排列型枚举？1~n随机打乱

#include 
using namespace std;
int n;
const int N=20;
bool st[N];
int res[N];
void dfs(int u){if(u==n+1){for(int i=1;i<=n;i++){cout<//第u个数为i if(!st[i]){res[u]=i;st[i]=true;dfs(u+1);st[i]=false;}	}
}
int main(){cin>>n;dfs(1);return 0;
} 

递归实现组合型枚举？n中选m个

#include 
using namespace std;
int n,m;
const int N=20;
bool st[N];
void dfs(int u,int s){//从u开始取 u~n中，已经取了s个if(s+n-u+1for(int i=1;i<=n;i++){if(st[i])cout<n)return;
//	要求由小到大输出，那么小的数要先选 st[u]=true;dfs(u+1,s+1);st[u]=false;dfs(u+1,s);
}
int main(){cin>>n>>m;dfs(1,0);return 0;
} 

#include 
using namespace std;
int n,m;
void dfs(int u,int sum,int state){//2^15 = 32768 state不超过 32768
//	state第i个二进制位代表 i取不取 if(sum+n-u+1for(int i=1;i<=n;i++){if((state >> (i-1)) & 1){cout<cin>>n>>m;dfs(1,0,0);//从1开始 ,已经选了0个，0代表选择的状态 return 0;
} 

递归改成非递归

状态为参数保存在栈节点中 可行√

#include 
#include 
using namespace std;
int n,m;
struct node{int pos;//在递归中的位置int u,sum,state;//在栈中的内容 
};
stack stk; 
void dfs(int u,int sum,int state){//2^15 = 32768 state不超过 32768
//	state第i个二进制位代表 i取不取 
//	0:if(sum+n-u+1for(int i=1;i<=n;i++){if((state >> (i-1)) & 1){cout<cin>>n>>m;
//	dfs(1,0,0);//从1开始 ,已经选了0个，0代表选择的状态 stk.push({0,1,0,0});while(!stk.empty()){node t=stk.top();stk.pop();int u=t.u;int sum=t.sum;int state=t.state;if(t.pos==0){if(sum+n-u+1for(int i=1;i<=n;i++){if((state >> (i-1)) & 1){cout<0,u+1,sum+1,state | (1<<(u-1))});}else if(t.pos==1){t.pos=2;stk.push(t);stk.push({0,u+1,sum,state});}else continue;}return 0;
} 

状态存放在数组中 不科学× （因为递归写法，按照当前状态执行完接下来的步骤，而非递归状态，每个节点所依仗的当前状态不同，后出栈的节点等到出栈时，当前状态早已被覆盖改变）

#include 
#include 
using namespace std;
int n,m;
const int N=20;
bool st[N];
struct node{int pos;//在递归中的位置int u, s;//在栈中的内容 
};
stack stk; 
void dfs(int u,int s){//从u开始取 u~n中，已经取了s个
// 0: if(s+n-u+1for(int i=1;i<=n;i++){if(st[i])cout<n)return;
//	要求由小到大输出，那么小的数要先选 st[u]=true;dfs(u+1,s+1);
//	1:	st[u]=false;	dfs(u+1,s);
//	2:
}
int main(){cin>>n>>m;
//	dfs(0,0);stk.push({0,0,0});//第一个参数0 表示 从0位置进去while(!stk.empty()){node t=stk.top();stk.pop();int u=t.u;int s=t.s;if(t.pos==0){if(s+n-u+1for(int i=1;i<=n;i++){if(st[i])cout<n)continue;t.pos=1;stk.push(t);//继续往下走st[u]=true;stk.push({0,u+1,s+1});//相当于dfs(u+1,s+1);}else if(t.pos==1){t.pos=2;stk.push(t);//继续往下走st[u]=false;stk.push({0,u+1,s});//相当于dfs(u+1,s);}else continue;} return 0;
} 

每个递归对应一个栈

一个数表示整个棋盘的状态？开关动否=取不取？飞行员兄弟

1、用一个整数表示整个棋盘的状态
2、操作集合，暴力枚举所有动作方案
3、操作一个开关，本需要异或该行该列所有的数，利用change数组记录九个数的异或值（因为异或具有结合律，state ^ ( a1 ^ a2 ^……a9）

#include 
#include 
using namespace std;
const int N=10;
int change[N][N];
int get(int x,int y){return 4*x+y;
}
#define  PII pair
vector res;
int main(){string line;int state=0;for(int i=0;i<4;i++){cin>>line;for(int j=0;j<4;j++){if(line[j]=='+')state+=(1<<(get(i,j)));}}//计算 (i,j)开关时 影响九个值的异或值for(int i=0;i<4;i++){for(int j=0;j<4;j++){for(int k=0;k<4;k++){change[i][j]+= (1<//暴力枚举所有动作方案 int now=state;vector tmp;for(int i=0;i<16;i++){if((k>>i)&1){int x=i/4;int y=i%4;tmp.push_back({x,y});now^=change[x][y];}} if(!now && (res.size()==0 ||res.size()>tmp.size() )){res=tmp;}}cout<cout<

#include 
#include 
#include using namespace std;
const int N=15;
bool vis[N];
int v[N];
int n;
int cnt;
int cal(int l,int r){int value=0;for(int i=l;i<=r;i++)value=value*10+v[i];return value;
}
void dfs(int u){if(u>9){for(int i=1;i<=7;i++){//【1，9】分成3段 1~i i+1~j j+1~9 for(int j=i+1;j<=8;j++){int a=cal(1,i);int b=cal(i+1,j);int c=cal(j+1,9);//abc都不能为0，j最多只取到第8位，第9位留给c if(n*c==a*c+b){cnt++;} }}return ;}for(int i=1;i<=9;i++){if(!vis[i]){vis[i]=true;v[u]=i;dfs(u+1);vis[i]=false;		}}
}
int main(){cin>>n;
//n=a+b/c,枚举a，b，c，通过该等式判断枚举的组合是否ok 
//除法转为乘法(带除法式子判断时可能会因为1/999=0因精度致错) 
//n*c=a*c+b,dfs(1); cout<

#include 
#include 
#include using namespace std;
const int N=1500;
bool vis[N];
bool vis_tmp[N];
//int v[N];
int n;
int cnt;
bool check(int b){memcpy(vis_tmp,vis,sizeof(vis));while(b){int t=b%10;b/=10;if(vis_tmp[t]||t==0)return false;	//是否重复 vis_tmp[t]=true;}for(int i=1;i<=9;i++){if(!vis_tmp[i])return false;//是否充分 }return true;
}
void dfs_c(int u,int a,int c){if(u>8)return ;int b=n*c-a*c;if(!a||!b||!c){
//		return;}else{	if(check(b))cnt++;
//		return;}
//这里不要轻易return，除了9位数已经全部用完
//c的位数不确定，c要继续dfs出别的值 	for(int i=1;i<=9;i++){if(!vis[i]){vis[i]=true;dfs_c(u+1,a,c*10+i);vis[i]=false;}} 
}
void dfs_a(int u,int a){//对a的搜索，已用多少位，a的值 if(u>7)return ;//至少留两位分别给bc if(a>=n)return;//n*c=a*c+b 不能搞出负数 if(a){dfs_c(u,a,0);
//		return;a要继续dfs出别的值 }for(int i=1;i<=9;i++){if(!vis[i]){vis[i]=true;dfs_a(u+1,a*10+i);vis[i]=false;}} 
}
int main(){cin>>n;
//n=a+b/c,枚举a，b，c，通过该等式判断枚举的组合是否ok 
//除法转为乘法(带除法式子判断时可能会因为1/999=0因精度致错) 
//n*c=a*c+b,dfs_a(0,0); cout<

#include 
#include 
#include using namespace std;
int n;
const int N=10;
const int inf=0x3f3f3f3f;
//string light[N];
//string str[N];
char  light[N][N];
char  str[N][N];
int res=inf;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};void flip(int x,int y){for(int i=0;i<5;i++){int cx=dx[i]+x;int cy=dy[i]+y;str[cx][cy]^=1;}
}
int main(){cin>>n;while(n--){res=inf;//多组输入 for(int i=0;i<5;i++){cin>>light[i];	}
//不是暴力枚举每一行操作
//暴力枚举第一行操作		for(int op=0;op<(1<<5);op++){memcpy(str,light,sizeof(light));//头文件 string.h ，老写错成strcpy int cnt=0;//i=0 第1行 for(int j=0;j<5;j++){//第1行 if((op>>j)&1){flip(0,j);cnt++;} }//i=1~4  剩余行 for(int i=1;i<5;i++){for(int j=0;j<5;j++){if(str[i-1][j]=='0'){//千万不能写成 !str[i-1][j]  啊  flip(i,j);cnt++;}}}//check最后一行 bool bright=true;for(int j=0;j<5;j++){if(str[4][j]=='0'){bright=false;break;}} if(bright){res=min(res,cnt);}}if(res>6)cout<<"-1";else cout<