递归和递推(一)

在递归中可以画出一个递归树,再由递归树找出退出条件和每次递归的做法

递归实现指数型枚举

例:枚举1~n的任取m个数的各种排列,0 =< m =< n,1 =< n <= 15.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 16;
int n;
int ways[N];	//0表示未使用,1表示有这个数字, 2表示没有这个数字

void dfs(int u){
	if(u > n){
		for(int i = 1; i <= n; i++){
			if(ways[i] == 1)
				printf("%d ", i);
		}
		puts("");
		return;
	}
	ways[u] = 1;
	dfs(u+1);
	ways[u] = 0;
	
	ways[u] = 2;
	dfs(u+1);
	ways[u] = 0;

}
int main()
{
	scanf("%d", &n);
	dfs(1);
	return 0;
}

递归的排列型枚举

例:将1~n进行全排列,1 =< n <= 9.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 10;
int n;
int ways[N];
bool used[N]; //需要判断是否用过某个数
void dfs(int u){
	if(u > n){
		for(int i = 1; i <= n; i++){
			printf("%d ", ways[i]);
		}
		puts("");
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!used[i] == true){
			used[i] = true;
			ways[u] = i;
			dfs(u+1);
			used[i] = false;
		}
	}
}

int main(){
	scanf("%d", &n);
	dfs(1);
	return 0;
}

上一篇:[NOIP2012] 同余方程(第三次考试大整理)


下一篇:引用的使用方法,引用传递