第12课 循环综合举例

---

前言

本课使用循环结构，介绍了以下问题的解决方法。

1. 质数判断问题
2. 百人百砖问题
3. 猴子吃桃问题
4. 质因数分解问题
5. 数字统计问题

---

一、循环综合举例

1. 质数判断问题

编程输出100至200之间的所有质数。

#include <iostream>
#include <cmath>
using namespace std;int main() {bool flag;for(int i=100; i<=200; i++) {flag=true;for(int j=2; j<=sqrt(i); j++) {if(i%j==0) {flag=false;break;}}if(flag) cout << i << '\t';}cout << endl;return 0;
}

2. 百人百砖问题

100块砖，100个人搬。男人每次搬砖4块，女人每次搬砖3块，2个小寒搬砖1块.若要一次性搬完，问男人、女人、小孩各要安排多少人？

#include <iostream>
using namespace std;int main() {int men, women, children, flag;for(int men=0; men<=25; men++) {for(int women=0; women<=33; women++) {children=100-men-women;if(children%2==0 && 4*men+3*women+children/2 == 100)cout << men << '\t' << women << '\t' << children << endl;}}return 0;
}

运行程序，输出

0       20      80
5       13      82
10      6       84

可以与下面的程序比较以下，看孰的运行效率更高。

#include <iostream>
using namespace std;int main() {int men, women, children, flag;for(int men=0; men<=25; men++) {for(int women=0; women<=33; women++) {for(int children=0; children<=100; children++) {if(children%2==0 && men+women+children==100 && 4*men+3*women+children/2 == 100)cout << men << '\t' << women << '\t' << children << endl;}}}return 0;
}

运行程序，t同样输出如下

0       20      80
5       13      82
10      6       84

3. 猴子吃桃问题

猴子摘了一堆桃，当天吃掉一半，觉得不过瘾，又多吃了一个；单二天，它吃了剩下的桃子的一半又多一个，以后每天都这样吃下去，直到第10天要吃时，它发现只剩下一个桃子了。问猴子第一天共摘下了多少个桃子？

#include<iostream>
using namespace std;
int main() {int rest = 1;//第10天只剩一个桃子for(int day = 9; day > 0; day--) {rest = (rest + 1) * 2;//每天的桃子总数是后一天剩余桃子加1乘2}cout << "The number of peaches on the first day is: " << rest << endl;return 0;
}

运行程序，输出结果为
1534

用while循环实现，应该代码更好理解一些些。

#include<iostream>
using namespace std;
int main() {int rest = 1;//第10天只剩一个桃子int day = 9;while(day--) {rest = (rest + 1) * 2;//每天的桃子总数是后一天剩余桃子加1乘2}cout << "The number of peaches on the first day is: " << rest << endl;  //1534return 0;
}

当然，最好写成下面这样子，代码更便于阅读理解。

#include<iostream>
using namespace std;
int main() {int rest = 1;//第10天只剩一个桃子int day = 9;while(day) {rest = (rest + 1) * 2;//每天的桃子总数是后一天剩余桃子加1乘2day--;}cout << "The number of peaches on the first day is: " << rest << endl;  //1534return 0;

如果改成“直到第8天要吃时，它发现只剩下一个桃子了”，则

#include<iostream>
using namespace std;
int main() {int rest = 1;//第8天只剩一个桃子cout << 8 << "\t" << 1 << endl;int day = 7;while(day) {rest = (rest + 1) * 2;//每天的桃子总数是后一天剩余桃子加1乘2cout << day << "\t" << rest << endl;day--;}cout << "The number of peaches on the first day is: " << rest << endl;return 0;
}

运行代码，输出如下

8       1
7       4
6       10
5       22
4       46
3       94
2       190
1       382
The number of peaches on the first day is: 382

前面我们做过一个类似的练习如下。
水果店新进了一批桃子，共计1020个。第一天卖了一半多两个，以后每天卖了剩下的一半多两个，问几天以后能卖完这些桃子？

#include<iostream>
using namespace std;int main() {int peaches=1020;int days=0;while(peaches!=0) {peaches = peaches/2 - 2;days++;cout << days << ": " << peaches << endl;}cout << "Total days: " << days << endl;return 0;
}

4. 质因数分解问题

已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。
【数学分析】
这个题具有很大的欺骗性，由于题目名为质因数分解，可能会让你马上想到判断质数。但在问题描述中已经确定" n 是两个不同质数的乘积"，实际上不需要判断质数。按顺序求两个乘数，则后一个乘数一定大于或等于前一个乘数。因此这个题目就变成一个整数可以拆成两个数相乘，输出第二个乘数。

#include <iostream>
using namespace std;int main() {int n;cin >> n;for(int i=2; i<=n/2; i++) {if(n%i==0) {cout << n/i << endl;break;}}return 0;
}

本题，依照上述代码，实际上应该写成“已知正整数n是两个不同的因数的乘积，试求出较大的那个因数。”
本题很容易让人联想到关于偶数的哥德巴赫猜想，即任一大于2的偶数都可写成两个素数之和。读者可以尝试编程验证之。

5. 数字统计问题。

请统计某个给定范围［l, r］的所有整数中，数字2出现的次数。比如，给定范围［2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。

输入：一行，为两个正整数 l 和 r ,(0≤l<r≤1000)，两个整数之间用一个空格隔开。输出：一行，表示数字2出现的次数。
样例输入：
2 22
样例输出：
6

#include <iostream>
using namespace std;int main() {int left, right, temp, count=0;cin >> left >> right;for(int i=left; i<=right; i++) {temp = i;while(temp) {if(temp%10==2) {count++;}temp /= 10;}}cout << count << endl;return 0;
}

二、课后练习

2. 末尾3位数问题

编写程序，计算$99^{99}$结果的末尾3位数字。
【分析】本题可以参见第10课中介绍的“幂运算的尾数问题”实例——即幂运算$a^b$的末尾3位数字是多少。

#include <iostream>
using namespace std;int main() {int a=99, b=99;int tail=1;for(int i=1; i<=b; i++) {tail = (tail*a)%1000;}if(tail>100) cout << tail << endl;else if(tail>10) cout << "0" << tail << endl;else cout << "00" << tail << endl;return 0;
}

运行程序，输出
899

3. 求自然常数e

已知自然常数e，计算公式如下
$e=1+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+...$
编程计算e的近似值，精度要求为$10^{-6}$。

Python实现代码如下。

# e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n!
import mathe = 1.0
eps = 0.1e-7
termN = 1
factorial = 1while math.fabs(1/factorial) >= eps:e += 1/factorialprint("termN = {}\t  e = {:.10f}".format(termN, e))termN += 1factorial *= termNprint("Approximate of e is %.8f" % e)

C++实现代码如下。

#include <iostream>
#include <iomanip>
using namespace std;//# e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n!
int main() {double e = 1.0;double eps = 0.1e-7;int termN = 1;long long factorial = 1;while(1.0/factorial>=eps)  {e += 1.0/factorial;cout << termN << '\t' << fixed << setprecision(8) << e << endl;termN += 1;factorial *= termN;}cout << "Approximate of e is " << e << endl;return 0;
}

运行程序，输入如下：

1       2.00000000
2       2.50000000
3       2.66666667
4       2.70833333
5       2.71666667
6       2.71805556
7       2.71825397
8       2.71827877
9       2.71828153
10      2.71828180
11      2.71828183
Approximate of e is 2.71828183

注意，代码中的表达式1.0/factorial不能写成1/factorial。

4. 数据统计问题

输入一些正整数，保证这些数都是不超过1000的整数（输入大于等于1000的时，结束程序)，求出它们的最小值、最大值和平均值。
输入：若干个正整数，空格分隔，以1000为结束。
输出：三部分内容，即最小值、最大值和平均值。
样例输入：
2 8 3 5 1 7 3 6 1000
样例输出：
min =1, max =8, average =4.375

#include <iostream>
using namespace std;//输入一些正整数，保证这些数都是不超过1000的整数
//（输入大于等于1000的时，结束程序)，求出它们的最小值、最大值和平均值。
int main() {int n, min=1000, max=0, count=0, sum=0;while(cin>>n) {if(n>=1000) break;if(n<min) min=n;if(n>max) max=n;sum += n;count++;}cout << "min=" << min;cout << ", max=" << max;cout << ", average=" << (sum*1.0/count);return 0;
}

运行程序，某次输入输出如下：

2 8 3 5 1 7 3 6 1000
min=1, max=8, average=4.375

5. 买苹果问题。

最近水果店新购入一批苹果，每个苹果0.8元。卡路第一天买2个苹果，从第二天开始，每天买前一天的2倍，直到当天购买的苹果个数达到且不超过50个，请级写程序，求每天平均花多少钱买苹果？

#include <iostream>
using namespace std;//最近水果店新购入一批苹果，每个苹果0.8元。卡路第一天买2个苹果，
//从第二天开始，每天买前一天的2倍，直到当天购买的苹果个数达到且不超过50个，
//请级写程序，求每天平均花多少钱买苹果？
int main() {int n=2, days=0;	//第一天买2个苹果float unit_price = 0.8;float total_consume = 0.0;while(n<=50) {days++;total_consume += unit_price*n;n *= 2;}cout << (total_consume/days) << endl;return 0;
}

运行程序，输出
9.92

6. 找5的倍数问题。

从键盘输入 n 个整数（ n ≤10)，找到第一个能被5整除的数。如果找到了，则输出此数，结束输入；如果没找到，则输出"未找到"。
输入： n 个整数，即待判断数据，最多10个。
输出：1个整数或"未找到"，1个整数为输入中第一个能被5整除的数。

#include <iostream>
using namespace std;//从键盘输入n个整数（n<=10)，找到第一个能被5整除的数。
//如果找到了，则输出此数，结束输入；如果没找到，则输出"未找到"。
int main() {int n, c=0;	//第一天买2个苹果while(cin>>n && c<=10) {c++;if(5==n) {cout << n << endl;break;}}return 0;
}

---

总结

借助于在循环体中适当地使用break语句和continue语句，for循环、while循环和do-while循环其实是可以相互替换的。