体会递归感
题目描述
当 n为 1 时，图形如下图：
X
当 n 为 2时，图形如下图：
X X
X
X X
当 n≥2 时，图形规律如下：
图形n-1 图形n-1
图形n-1
图形n-1 图形n-1
给定 n组数据，输出每组数据对应的图形。
输入
输入共 n+1 行，前 n行每行一个数，表示要输出的图形的大小，最后一行输入 ?1代表程序结束。（1≤n≤7）
输出
每输入一个数输出一组图形，并在图形后的下一行输出一个 ??。
注意，图形后应补齐空格。
思考过程：要求第n组图形，那么可以求第n - 1组图形，求n - 2组图形，以此类推，直到第一组图形，第一组图形就只有一个 ‘X’。所以可以从第n组开始递推到第1组得到每个位置的第一组的位置，再从各个第一组位置递归到第n组，在递归过程保存保存各个位置的第一组的‘X’。而且可以发现第n组图形的边长是第n - 1组图形的3倍。也就是Len[7] = {1， 3， 9，27，81，243，729}，且确认位置**左上角图形的左上角位置为(x,y),右上角图形的左上角位置为(x+Len[n]/3*2, y)，中间图形的左上角位置为(x+Len[n]/3,y+Len[n]/3)，左下角图形的左上角位置为(x,y+Len[n]/3 *2)，右下角位置为(x+Len[n]/3 2, y+Len[n]/3 2)
举例一个n=3的，左上角图形的左上角位置为(1, 1),右上角图形的左上角位置为(1+9/3*2, 1)，中间图形的左上角位置为(1+9/3,1+9/3)，左下角图形的左上角位置为(1,1+9/3 *2)，右下角位置为(1+9/3 *2,1+9/3 *2)
(1,1)
X X X X
X X
X X X X (1, 1) (1+9/3*2, 1) (1+9/3,1+9/3) (1,1+9/3*2) (1+9/3*2,1+9/3*2)
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
解题过程：
题目给的数据范围是7，那么就把第7组图形画出来（也就是保存到数组中）再根据输入的第几组去输出。递归函数确认为递归每组图形的左上角位置和第几组func(x, y, n)。
代码演示：
#include<iostream>
using namespace std;
char ans[1005][1005];
int nums[8] = {0, 1, 3, 9, 27, 81, 243, 729};
void func(int x, int y, int n) {
if (n == 1) {
ans[x][y] = 'X';
return ;
}
func(x, y, n - 1);
func(x, y + nums[n] * 2 / 3, n - 1);
func(x + nums[n] / 3, y + nums[n] / 3, n - 1);
func(x + nums[n] * 2 / 3, y, n - 1);
func(x + nums[n] * 2 / 3, y + nums[n] * 2 / 3, n - 1);
}
int main() {
func(1, 1, 7);
int n;
while (1) {
cin >> n;
if (n == -1) break;
for (int i = 1; i <= nums[n]; i++) {
for (int j = 1; j <= nums[n]; j++) {
if (ans[i][j] == 'X') {
cout << 'X';
} else {
cout << ' ';
}
}
cout << endl;
}
cout << '_' << endl;
cout << endl;
}
return 0;
}
递归实现指数型枚举
题目描述
从 1?n这 n 个整数中随机选取任意多个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。
输入
输入一个整数 n。（1≤n≤10）
输出
每行一组方案，每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
4
样例输出
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到4的数，第二列会出现2到4的数，第三列会出现3到4的数，第四列会出现4到4的数，也就说遍历到每一列可以得到这列的列序数到n的数，再遍历去改变第一列的数。因为在列数遍历到n的时候要回到遍历n - 1列，所以 用到递推和递归，递推到第n列，再递归回到第一行。
比如
//递推到第n列
1
1 2
1 2 3
1 2 3 4
//递归回到第n - 1列且改变成第n - 1列的下一个值，比如前一个是3，现在就是4。因为4即是n，所以循环结束
1 2 4
//递归回到第n - 2列且改变成第n - 2列的下一个值，比如前一个是2，现在就是3，因为3<n,所以要遍历到4
1 3
1 3 4
//递归回到第n - 3列且改变成第n - 3列的下一个值，比如前一个是1，现在就是2，因为n<2,所以要遍历到4，遍历的过程递归
2
2
2 3
2 3 4
2 4
3
3 4
4
解题过程：设置一个数组，记录每一次遍历到的列位置并且输出整个数组。递归函数func(strat, idx)，其中strat为第一列的值，idx为数组的下标，idx也就是遍历到的列数
#include<iostream>
using namespace std;
int ans[15];
int n;
void print(int idx) {
for(int i = 0; i <= idx; i++) {
i && cout << ' ';
cout << ans[i];
}
cout << endl;
}
void func(int strat, int idx) {
for (int i = strat; i <= n; i++) {
ans[idx] = i;
print(idx);
func(i + 1, idx + 1);
}
}
int main() {
cin >> n;
func(1, 0);
return 0;
}
增加递归回溯感：
#include<iostream>
using namespace std;
int n, ans[15], cnt;
void print() {
for (int i = 0; i <= cnt; i++) {
i && cout << ' ';
cout << ans[i];
}
cout << endl;
}
void func(int strat) {
for (int i = strat; i <= n; i++) {
ans[cnt] = i;
print();
//递推过程增加数组下标，形成下推感
cnt++;
func(i + 1);
cnt--;//回溯感，在递归过程回溯数组下标
}
}
int main() {
cin >> n;
func(1);
return 0;
}
递归实现组合型枚举
C n m C^m_n Cnm?
** 题目描述**
从 1?n这 n个整数中随机选取 m个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。
输入
输入两个整数 n,m。（1≤m≤n≤10）
输出
每行一组方案，每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
5 3
样例输出
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
思考过程：这道题就是在n个数中随意挑m个数出来进行。观察上面样例，会发现一个呈周期的现象：现在把这些数放倒
[1 1 1 1 1 1] [2 2 2][3]
[[2 2 2][3 3][4]] [[3 3 4][4]]
[[3 4 5][4 5][5]] [[4 5 5][5]]
会发现在第一列为1的一段数组中，第二列出现了从1+1到1+m的数，也就是2、3、4，在第二为2的一段数组中，第三列出现了2+1到2+m的数。而第一列出现从1到n - m + 1的数。说明现在我只需要控制第一列出现的数和后面会出现几列数就可以，因为第二列到第m列会中的每一列会被上一列控制，比如第二列会被第一列控制（第一列出现的是1，那么第二列只能是1+1到1+m）。
解题过程：
因为第一列的个数就是一个内循环用到递归。首先定义一个递归函数func(start, left)，start为第一列的数的值，根据上面分析，第一列会出现1到n-m+1的数，所以要循环递归。left为已到m - left列，只要left为0就截止列数。
代码演示：
int n, m, cnt;
int nums[15];
void print() {
for (int i = 0; i < m; i++) {
i && cout << " ";
cout << nums[i];
}
cout << endl;
}
void func(int start, int left) {
if (left == 0) {
print();
return 0;
}
for (int i = start; i <= n; i++) {
nums[cnt] = i;
cnt++;
func(i+1, left-1);//更换第一列出现的值且检查到第几行，当到m行就就截至列数，列数截止时就输出这m列的所有值
cnt--;
}
}
int main() {
cin >> n >> m;
func(1, m);
return 0;
}
递归实现排列型枚举
A n n A^n_n Ann?
题目描述
从 1?n 这 n个整数排成一排并打乱次序，按字典序输出所有可能的选择方案。
输入
输入一个整数 n。（1≤n≤8）
输出
每行一组方案，每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
3
样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思考过程：组合问题和排列问题的区别就是，全排列问题的每一列都会出现1到n的数，所以就只要每一列都遍历一下1-n就可以，因为每一列都是一个内循环，所以用到递归。
解题过程：
定义一个递归函数func()，递归的意义就是递推时使列数增加，递归时使更改列数的值，因为n列中每一列的值不一样，所以用一个标记数组mark来记录n列中已出现过的数
代码演示：
int n, cnt;
int nums[15], mark[15];
void print() {
for (int i = 0; i < n; i++) {
i && cout << " ";
cout << nums[i];
}
cout << endl;
}
void func() {
if (cnt == n) {
print();
return ;
}
for (int i = 1; i <= n; i++) {
if (mark[i] == 0) {
nums[i] = i;
mark[i] = 1;
cnt++;
func();
cnt--;
mark[i] = 0;
}
}
}
int main() {
cin >> n;
fun();
return 0;
}
排列组合应用
上面三道排列组合问题输出的都是一堆数字，这些数字有什么用呢？其实这些数字就是下标，只要把这些数字套到每一个不是数字的数组里面就可以得到其他的排列。
比如组合问题：在五个人 A、B、C、D、E中选三个人
int cnt;
string people[5] = {'A','B','C','D','E'};
int nums[5];
void func(int start, int left) {
if (left == 0) {
for (int i = 0; i < n; i++) {
i && cout << " ";
cout << people[nums[i]];
}
cout << endl;
return 0;
}
for (int i = start; i < n; i++) {
nums[cnt] = i;
cnt++;
func(i + 1, left - 1);
cnt--;
}
}
int main() {
func(0, 3);
}
总结：组合排列问题都会用到循环递归（递归套一个循环），三种枚举的不同是：指数型在枚举过程输出，组合是限制输出列数且在截断时输出，全排列是每一列都可能出现每一个值且无限制列数直到所有数都出现过就输出。
