递推递归笔记

递归实现组合型枚举

从 1∼n
这 n
个整数中随机选出 m
个，输出所有可能的选择方案。

输入格式

两个整数 n,m
,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围
n>0
,
0≤m≤n
,
n+(n−m)≤25

#include<iostream>
using namespace std;

int n,m;
bool sta[25];
int p[25];

void dfs(int u){
	if(u==m+1){
		for(int i=1;i<=m;i++){
			cout<<p[i]<<" ";
			
		}
		cout<<endl;
		return;
	}
	
	for(int i=1;i<=n;i++){	
        //大于才往里放	
		if(i>p[u-1]){
		
			if(sta[i]!=true){
				sta[i]=true;
				p[u]=i;
				dfs(u+1);
				sta[i]=false;
			}
		}
	}
}

int main(){
	cin>>n>>m;
	dfs(1);
    return 0;
}

带分数

$100$ 可以表示为带分数的形式：$100 = 3 + \frac{69258}{714}$

$100$ 还可以表示为：$100 = 82 + \frac{3546}{197}$

注意特征：带分数中，数字 $1 \sim 9$ 分别出现且只出现一次（不包含 $0$）。

类似这样的带分数，$100$ 有 $11$ 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 $1 \sim 9$ 不重复不遗漏地组成带分数表示的全部种数。

数据范围

$1 \le N < 10^6$

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

#include<iostream>
#include<algorithm>
using namespace std;

int tar, num=0;
int a[10] = { 1,2,3,4,5,6,7,8,9 };
int b[10] = { 1,2,3,4,5,6,7,8,9 };



int main() {
	cin >> tar;
	while (1) {
		//first 找分割线
		int x = 0;
		for (int i = 0; i < 7; i++) {
			//second
			x = x * 10 + a[i];
			int y = 0;
			for (int j = i + 1; j < 8; j++) {
				y = y * 10 + a[j];
				int z = 0;
				for (int k = j + 1; k < 9; k++) z = z * 10 + a[k];
				if (x + (y / z) == tar && y % z == 0) num++;
				//cout << "x: " << x << "  y: " << y << "  z: " << z << endl;
			}

		}

		next_permutation(a, a + 9);//全排列数组的某一部分
		//cout << "new a:";
	/*	for (int i = 0; i < 9; i++) {
			cout << a[i];
		}
		cout << endl;*/

		bool flag = 0;
		for (int i = 0; i < 9;i++) {
			if (a[i] != b[i]) {
				flag = 1;
				break;
			}
		}

		if (!flag) break;
	}
	cout << num;
	return 0;
}