循环嵌套的应用03-减少重复计算¶
能从前一次结果接着算，就不要每次从头算。
能由其他变量算出来，就少枚举一个变量。
下面保留不同写法，重点比较哪些计算重复了，哪些循环可以省掉。
求出 e 的值¶
计算 1 + 1/1! + 1/2! + ... + 1/n!。下面的代码先处理 0 <= n <= 20，n 已经读入。
两层循环，每次重新计算阶乘：
double ret = 1;
for (int i = 1; i <= n; i++) {
long long t = 1;
for (int j = 1; j <= i; j++) {
t *= j;
}
ret += 1.0 / t;
}
printf("%.10lf", ret);
一层循环，在前一个阶乘的基础上继续乘：
long long t = 1;
double ret = 1;
for (int i = 1; i <= n; i++) {
t *= i;
ret += 1.0 / t;
}
printf("%.10lf", ret);
ret 从 1 开始，对应式子最前面的 1。除法写 1.0 / t，不要写成整数除法。
第一种写法，乘法次数是 1 + 2 + ... + n；第二种只有 n 次，对应 O(n²) 和 O(n)。
使用 printf，需要头文件 <cstdio>。
百钱买百鸡¶
公鸡每只 5 元，母鸡每只 3 元，小鸡 3 只 1 元。100 元买 100 只鸡，求所有方案。
i、j、k 分别表示公鸡、母鸡、小鸡的数量。
三层循环，分别枚举：
for (int i = 0; i <= 100 / 5; i++) {
for (int j = 0; j <= 100 / 3; j++) {
for (int k = 0; k <= 100; k += 3) {
if (i * 5 + j * 3 + k / 3 == 100 && i + j + k == 100) {
cout << i << ' ' << j << ' ' << k << '\n';
}
}
}
}
两层循环，由总只数算出小鸡数量：
for (int i = 0; i <= 100 / 5; i++) {
for (int j = 0; j <= 100 / 3; j++) {
int k = 100 - i - j;
if (k >= 0 && k % 3 == 0 && i * 5 + j * 3 + k / 3 == 100) {
cout << i << ' ' << j << ' ' << k << '\n';
}
}
}
注意 k % 3 == 0，小鸡数量要是 3 的倍数，不能只靠整数除法判断钱数。
鸡兔同笼¶
已知共有 x 个头、y 条腿，求鸡和兔各有多少只。下面按非负整数输入来讨论。
两层循环，分别枚举鸡和兔：
for (int i = 0; i <= x; i++) {
for (int j = 0; j <= min(x, y / 4); j++) {
if (i + j == x && 2 * i + 4 * j == y) {
cout << i << ' ' << j << '\n';
}
}
}
使用 min，需要头文件 <algorithm>。
一层循环，用总头数减去鸡的数量，算出兔的数量：
for (int i = 0; i <= x; i++) {
int j = x - i;
if (2 * i + 4 * j == y) {
cout << i << ' ' << j << '\n';
}
}
还可以列方程，直接计算：
// x、y使用long long，下面的运算不超出类型范围
if (y % 2 == 0 && y >= 2 * x && y <= 4 * x) {
long long tuzi = (y - 2 * x) / 2;
long long ji = x - tuzi;
cout << ji << ' ' << tuzi;
}
先判断有没有合法解，再做整数除法。 腿数要是偶数，还要在全部是鸡、全部是兔这两种情况之间。
不满足条件时怎么输出，按题目要求来。