递推递归笔记

递归实现组合型枚举

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

输入格式

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

输出格式

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}

递推递归笔记
http://example.com/2024/02/08/递推递归笔记/
作者
邓骏韬
发布于
2024年2月8日
许可协议