循环嵌套与枚举算法
一、打印二维图形
打印二维图形是指输出多行有规律的内容，它包括行数与列数两个基本数据，通常借助循环嵌套结构来实现控制输出
1、每行内容长度相同
例题：【打印矩形】 输出n行m列的字符'@'二维图形。
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << '@';}cout << endl;
}
Copy
核心知识点：
1、实现过程：把每行的内容（m个）输出后换行，然后重复n行；故使用循环嵌套结构实现
2、易得外层for循环控制行数，内层for循环控制列数（即每行长度）
3、换行指令cout << endl;要放在内层for循环结束后
2、每行内容长度增加
例题：打印如下字符'@'三角形
@
@@
@@@
Copy
int n = 3;
for (int i = 0; i < n; i++) {for (int j = 0; j < i + 1; j++) {cout << '@';}cout << endl;
}
Copy
核心知识点：
1、外层控制行数，故外层循环条件为i < n
2、容易发现，每行内容的长度（列数）是逐层+1，故内层循环条件应该为j < ? + i * 1，代入i = 0 时,j = 1可得? = 1，故内层循环条件最终为j < i + 1
3、每行内容长度减少
例题：打印如下字符'@'三角形
@@@@@
@@@
@
Copy
int n = 3;
for (int i = 0; i < n; i++) {for (int j = 0; j < 2 * n - 1 - i * 2; j++) {cout << '@';}cout << endl;
}
Copy
核心知识点：
1、外层控制行数，故外层循环条件为i < n
2、容易发现，每行内容的长度（列数）是逐层-2，故内层循环条件应该为j < ? - i * 2，代入i = 0 时,j = 5可得? = 5； 但实际情况是第一行i = 0时，其长度不是固定为5的，可以发现它与n有关，思考可得是2 * n - 1，故内层循环条件最终为j < 2 * n - 1 - i * 2
4、每行有不同内容，长度规律不同
例题：打印如下字符'@'三角形
@ @@@
@@@@@
Copy
int n = 3;
for (int i = 0; i < n; i++) {for (int j = 0; j < n - 1 - i; j++) {cout << ' ';}for (int j = 0; j < 2 * i + 1; j++) {cout << '@';}cout << endl;
}
Copy
--@
-@@@
@@@@@
Copy
核心知识点：
1、首先转换为上图，易得实际输出内容包括空格（图中用-表示）和字符'@'两个内容
2、外层控制行数，故外层循环条件为i < n
3、对于空格内容，随着行数 i 的增加，数量逐行-1，其内层循环条件应该为j < ? - i * 1，代入i = 0 时,j = 2可得? = n - 1，故其内层循环条件最终为j < n - 1 - i
4、同理对于字符'@'内容，随着行数 i 的增加，数量逐行+2，故其每行的长度为? + 2 * i，代入i = 0 时，j = 1，可得? = 1，故其内层循环条件为j < 2 * i + 1
5、每行内容呈规律输出
例题：打印如下数字三角形
1
23
345
4567
56789
Copy
int n = 5;
for (int i = 0; i < n; i++) {for (int j = i + 1; j < 2 * (i + 1); j++) {cout << j;}cout << endl;
}
Copy
核心知识点：
1、外层控制行数，故外层循环条件为i < n
2、容易发现，每行内容是呈规律输出的，这里可以考虑借助循环索引j来控制输出； 易得每行起始元素与行数i有关，代入i = 0 时, j = 1可得内层循环索引初始化语句应该为int j = i + 1;；
3、与此同时，内层循环条件应该为j < i + 1 + ?，这里的?指的是每行内容的长度，可得? = i + 1，故内层循环条件最终为j < 2 * (i + 1)
二、枚举算法
也叫穷举法，即列举所有的可能方案，最后找出符合条件的答案
1、简单枚举
指枚举的是单一元素，通常借助单层for循环结构即可实现遍历查找
例题：输出1~100以内所有7的倍数
for (int i = 1; i <= 100; i++) {if (i % 7 == 0) {cout << i << ' ';}
}
Copy
输出：7 14 21 28 35 42 49 56 63 70 77 84 91 98
Copy
核心知识点：
1、列举所有可能的元素：
借助循环索引i，逐个遍历1~100，故循环结构为for (int i = 1; i <= 100; i++)
2、验证符合条件的元素：
根据题目要求输出7的倍数，对应的程序为i % 7 == 0，借助if语句判断，最后将其输出cout << i << ' ';
2、复杂枚举
指枚举的是元素组合，通常要借助for循环嵌套结构实现遍历查找
例题1：鸡兔同笼，已知鸡兔个头总数为a，鸡兔脚的总数为b，求鸡和兔各有多少只（保证有答案）
int a, b;
cin >> a >> b;
for (int i = 0; i <= a; i++) {for (int j = 0; j <= a; j++) {if (i + j == a && i * 2 + j * 4 == b) {cout << i << ' ' << j;}}
}
Copy
核心知识点：
1、列举所有可能的元素组合：
这里借助变量索引i , j 分别表示鸡、兔的数量，通过for循环从0遍历到a（易得鸡和兔的数量范围可能在0~a之间），故循环嵌套结构为
for (int i = 0; i <= a; i++) {for (int j = 0; j <= a; j++) {}
}
Copy
当鸡的数量i = 0时，尝试令兔的数量j = 0/1/2...a；
当鸡的数量i = 1时，尝试令兔的数量j = 0/1/2...a；
.
.
.
当鸡的数量i = a时，尝试令兔的数量j = 0/1/2...a
2、验证符合条件的元素组合：
根据题目要求需要同时满足总的头数为a，总的脚数为b，对应的程序为i + j == a && i * 2 + j * 4 == b，借助if语句判断，最后将其输出cout << i << ' ' << j;
例题2：百钱买百鸡，公鸡每只5钱，母鸡每只3钱，小鸡三只1钱，花100钱刚好买到100只鸡，请问有几种方案（按公鸡、母鸡、小鸡的数量依次输出各种方案）
for (int i = 0; i <= 100; i++) {for (int j = 0; j <= 100; j++) {for (int k = 0; k <= 100; k += 3) {if (i + j + k == 100 && i * 5 + j * 3 + k / 3 == 100) {cout << i << ' ' << j << ' ' << k << endl;}}}
}
Copy
核心知识点：
1、列举所有可能的元素组合：
这里借助变量索引i , j ，k分别表示公鸡、母鸡、小鸡的数量，通过for循环从0遍历到100（易得每种鸡的购买数量范围可能在0~a之间） 根据题目，小鸡的数量只能为3的倍数，否则最终的金额将会包含有小数，显然不符合题目要求，故k的变化规律为k += 3 最终环嵌套结构为
for (int i = 0; i <= 100; i++) {for (int j = 0; j <= 100; j++) {for (int k = 0; k <= 100; k += 3) {}}}
}
Copy
输出：
0 25 75
4 18 78
8 11 81
12 4 84
Copy
2、验证符合条件的元素组合：
根据题目要求需要同时满足鸡的数量等于100，所花费金额也等于100，对应的程序为i + j + k == 100 && i * 5 + j * 4 + k / 3 == 100，借助if语句判断，最后将其输出cout << i << ' ' << j << ' ' << k << endl;
3、同源枚举
指的是在同一个集合中寻找组合方案，需要注意以下两点：
1、同一个元素可否重复拿来组合，即(a, a)是否合法
2、组合方案有无顺序要求，即(a, b)与(b, a)是否重复
例题：给定10个数字0~9，找出任意两个数字，使其相加的和为奇数
程序1：
int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 0; i < 10; i++) {for (int j = 0; j < 10; j++) {if (i != j && (arr[i] + arr[j]) % 2 == 1) {cout << i << ' ' << j << endl;}}
}
Copy
容易发现： 当i = 0, j = 1时，组合(0, 1)满足条件； 当i = 1, j = 0时，组合(1, 0)也满足条件； 但实际情况是上述两个方案只视为一种，只是顺序不一样
为解决方案冲突问题，通常通过限制i, j的大小关系来防止此类情况，具体如下：
程序2：
int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 0; i < 10; i++) {for (int j = i + 1; j < 10; j++) {if ((arr[i] + arr[j]) % 2 == 1) {cout << i << ' ' << j << endl;}}
}
Copy
修改后，只有(0, 1)组合出现，不会有(1, 0)组合；其他组合也是同样情况 这是由int j = i + 1;来规定j必然是大于i的，从而保证了方案不会重复