递归与排列组合问题

1.OnlineJ240：图形打印

Tags：递归

当 n 为 1 时，图形如下图：

1
X

当 n 为 2 时，图形如下图：

1
2
3
X X
 X 
X X

当 n ≥ 2 时，图形规律如下：

1
2
3
图形n-1    图形n-1
    图形n-1
图形n-1    图形n-1

给定 n 组数据，输出每组数据对应的图形。

输入：

输入共 n+1 行，前 n 行每行一个数，表示要输出的图形的大小，最后一行输入 −1 代表程序结束。（1 ≤ n ≤ 7）

输出：

每输入一个数输出一组图形，并在图形后的下一行输出一个 −。

注意，图形后应补齐空格。

1
2
3
4
5
1
2
3
4
-1
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
X
-
X X
 X 
X X
-
X X   X X
 X     X 
X X   X X
   X X   
    X    
   X X   
X X   X X
 X     X 
X X   X X
-
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
   X X               X X   
    X                 X    
   X X               X X   
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
         X X   X X         
          X     X          
         X X   X X         
            X X            
             X             
            X X            
         X X   X X         
          X     X          
         X X   X X         
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
   X X               X X   
    X                 X    
   X X               X X   
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
-

参考代码

==思路==：递归函数的定义以 (x, y) 点为左上角画n大小的图形

  1. n = 1时，num[1] = 1
  2. n = 2时，num[2] = 3
  3. n = 3时，num[3] = 9…
  4. n = n时，num[3] = (n - 1) * 3

假设画最大的图形：func(1, 1, 7)可以递归为画以下图形：

  • 左上角func(1, 1, 6)
  • 右上角func(x, y + num[n]/3*2, 6)
  • 左下角func(x + num[n]/3*2, y, 6)
  • 右下角func(x + num[n]/3*2, y + num[n]/3*2, 6)
  • 中间部分func(x + num[n]/3*1, y + num[n]/3*1, 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
#include<iostream>
using namespace std;

char ans[1005][1005];//存储答案
int num[10] = {0, 1, 3, 9, 27, 81, 243, 729};//工具数组:用于纪录n对应的图形长度

void func(int x, int y, int n) {
    if (n == 1) {
        ans[x][y] = 'X';
        return;
    }
    func(x, y, n - 1);//左上角
    func(x, y + num[n] / 3 * 2, n - 1);//右上角
    func(x + num[n] / 3 * 2, y, n - 1);//左下角
    func(x + num[n] / 3, y + num[n] / 3, n - 1);//中间部分
    func(x + num[n] / 3 * 2, y + num[n] / 3 * 2, n - 1);//左下角
}

int main() {
    func(1, 1, 7);//预先将最大图形绘制完成
    int t;
    while (cin >> t) {
        if (t == -1) break;
        for (int i = 1; i <= num[t]; ++i) {//根据预先绘制图形 绘制实际图形
            for (int j = 1; j <= num[t]; ++j) {
                if (ans[i][j] == 'X') cout << 'X';
                else cout << ' ';
            }
            cout << endl;
        }
        cout << '-' << endl;
    }
    return 0;
}

2.OnlineJ235：指数型枚举

从 1 − n 这 n 个整数中随机选取任意多个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。

输入：

输入一个整数 n。（1 ≤ n ≤ 10）

输出：

每行一组方案，每组方案中两个数之间用空格分隔。

注意每行最后一个数后没有空格。

1
3
1
2
3
4
5
6
7
1
1 2
1 2 3
1 3
2
2 3
3
1
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

参考代码

==思路==：

  1. 第一层可选：1 ~ n
  2. 第二层可选：2 ~ n || 3 ~ n || 4 ~ n || … || n-1 ~ n
  3. 上一层选的几，这一层就需要从几开始，这样才能避免重复、并保证后面选出的数字肯定要比之前选的更大

image-20230306214034503

image-20230306214057986

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
#include<iostream>
using namespace std;

int n, num[15];

void print(int deep) {
    for (int i = 1; i <= deep; ++i) {
        if (i != 1) cout << " ";
        cout << num[i];
    }
    cout << endl;
}

void func(int x, int deep) {
    for (int i = x; i <= n; ++i) {
        num[deep] = i;
        print(deep);
        func(i + 1, deep + 1);//递归选取
    }
}

int main(){
    cin >> n;
    func(1, 1);//func(从几开始选, 当前的层数)
    return 0;
}

3.OnlineJ236：组合型枚举

从 1 − n 这 n 个整数中随机选取 m 个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。

输入：

输入两个整数 n,m。（1 ≤ m ≤ n ≤ 10）

输出：

每行一组方案，每组方案中两个数之间用空格分隔。

注意每行最后一个数后没有空格。

1
3 2
1
2
3
1 2
1 3
2 3
1
5 3
1
2
3
4
5
6
7
8
9
10
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

参考代码

1

4.OnlineJ237：排列型枚举

从 1 − n 这 n 个整数排成一排并打乱次序，按字典序输出所有可能的选择方案。

输入：

输入一个整数 n。（1 ≤ n ≤ 8）

输出：

每行一组方案，每组方案中两个数之间用空格分隔。

注意每行最后一个数后没有空格。

1
3
1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

参考代码

1

5.排列组合问题总结：

6.搜索讲解：

7.搜索走地图问题：