第10课 for循环举例

---

前言

学习了for循环，本次课再通过一些编程实例，巩固学过的知识。

---

一、课堂实例

1.平均成绩问题

输入：共两行。第一行一个整数，表示学生人数。第二行有n个整数，表示每个学生本次数学考试的分数，取值范围[0, 100]。
输出：共1行，该行包含一个浮点数，为所求的全班学生的平均成绩。

2. 水仙花数字问题

水仙花数字的定义是： n 位数的每个数位的 n 次方之和等于数字本身，例如，三位数的3个数位上的数字的立方加起来等于该三位数，四位数的4个数位上的数字的4次方加起来等于该4位数，……这种数字有个有趣的英文名叫 narcissistic number，原意是"自恋数"。
英语narcissistic 这个词又是源自希腊神话中的自恋美少年 Narcissus ，后来他变成了水仙花， narcissus 就是"水仙花"的意思，于是有人放弃"自恋数"而取了这个比较好听的名字。
请编写一段程序输出100~999中的水仙花数。即：若三位数 ABC , ABC = A + B +C2，则称 ABC 为水仙花数。
例如153，$1^3+5^3+3^3=1+125+27=153$，则称153是水仙花数字。
【数学分析】
该题可以采用枚举所有可能的值（穷举法）的方法，循环从100到999。在循环体中将三位数拆分成个位、十位和百位，然后判断各个位的立方和是否等于自身，如果等于则输出，否则继续循环。

3. 用字符打印金字塔图形问题

用某个字符输出类似金字塔形状的等腰三角形图形。

4. 幂的末尾数字问题

幂$a^b$的末尾三位数是多少？
输入：一行，两个正整数 a 和 b 。1≤ a ≤100, 1≤ b ≤10000。
输出：一行，从高位到低位输出幂的末3位数字，中间无分隔符。若幂本身不足3位，在前面补零。
样例输入：
7 2011
样例输出：
743

【数学分析】

根据题意，直接计算$a^b$几乎是不可能的任务，因为数据太大，会溢出。我们可以循环 b 次，每次提取运算结果的末3位与 a 相乘，这样会大大减少运算量。
最后还要判断结果的位数：如果结果是三位数，那么直接输出结果，如果结果是两位数，那么输出一个零再输出结果；对于其他情况，输出两个零再输出结果。

参考代码如下：

#include<iostream>
using namespace std;

// 幂$a^b$的末尾三位数是多少？
int main() {
	int a, b, r;
	cout << "Input integer a and b:" << endl;
	cin >> a >> b;
	r = 1;
	for(int i=1; i<=b; i++) {
		r = (r*a) % 1000;
	}
	
	if(r>100) cout << r << endl;
	else if(r>10) cout << '0' << r << endl;
	else cout << "00" << r << endl;

	return 0;
}

5. 救援问题

救生船从大本营出发，营救若干屋顶上的人回到大本营，屋顶数目以及每个屋顶的坐标和人数都将由输入决定，求出所有人到达大本营并登陆所用的时间。
救援坐标如图10-4所示，在直角坐标系的原点是大本营，救生船每次从大本营出发，救了人之后将人送回大本营。坐标系中的点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。救生船每次从大本营出发，以速度50m/min 驶向下一个屋顶，到达一个屋顶后，救下其上的所有人，每人上船需用1min，船原路返回，达到大本营，每人下船需用0.5min。假设原点与任意一个屋顶的连线不穿过其他屋顶。

图10-4 例题示意图

输入： n +1行，第一行是一个整数，表示屋顶数 n 。接下来依次有 n 行输入，每一行上包含两个表示屋顶相对于大本营的平面坐标位置的实数（单位: m )、一个表示人数的整数。
输出：一行。救援需要的总时间，精确到分钟（向上取整）。
样例输入：
2
30 40 3
-30 -40 2
样例输出：
12
【数学分析】
设屋顶个数为n ，屋顶的坐标是x、y，大本营到屋顶的距离是d ，屋顶的人数是 m ，所有人到达大本营并登陆所用的时间 time ，则大本营到屋顶的距离d ，根据勾股定理： $d=\sqrt{x^2+y^2}$，然后根据d求出一次救援时间＝大本营到屋顶时间＋上人时间＋屋顶到大本营时间＋下人时间，即
$$time=\frac{d}{50}+m\times 1+\frac{d}{50}+m\times 0.5=2\times \frac{d}{50}+(m\times 1)+(m\times 0.5)$$

n 个屋顶且原点与任意一个屋顶的连线不穿过其他屋顶表明，循环 n 次，将 time 累加即可。

#include<iostream>
using namespace std;

int main() {
	int n;		// the count of roofs
	int x, y;	// coordinate point
	int m;		// the number of people in a roof
	double d, time = 0.0;
	cout << "Input the count of roofs: " << endl;
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> x >> y >> m;
		d = sqrt(x*x + y*y);
		time += 1*m + 2*(d/50) + 0.5*m;
	}
	cout << ceil(time) << endl;
	
	return 0;
}

---

二、课后练习

1. 求解算式问题

编写程序，计算1-3+5-7+…+97-99的结果。

#include<iostream>
using namespace std;

int main() {
	int sum1 = 0;
	int sum2 = 0;
	for(int i=1; i<=99; i+=4) {
		sum1 += i;
	}
	for(int i=3; i<=99; i+=4) {
		sum2 += i;
	}
	cout << (sum1-sum2) << endl;
	return 0;
}

运行程序，输出结果为
-50

2. 三位数奇数问题

编写程序，统计0到9这10个数字可以组成多少个没有重复数字的3位数奇数。

#include<iostream>
using namespace std;

int main() {
	int count=0;
	for(int c=1; c<=9; c+=2) {
		for(int b=0; b<=9; b++) {
			if(b==c) continue;
			for(int a=1; a<=9; a++) {
				if(a==b || a==c) continue;
				count++;
			}
		}
	}
	cout << count << endl;
	return 0;
}

运行程序，输出结果为
320

此题也可以用排列组合中的乘法原理来解答。
先从5个奇数数字中选一个填到个位上，共有$A_5^1$种填法；
首位数字不能为0，再从余下的8个数字中选一个填到个位上，共有$A_8^1$种填法；
最后填充十位数字，从余下的8个数字中选一个，共有$A_8^1$种填法；
故共可以组成没有重复数字的三位数奇数的个数有 588=320 个。即
$$A_5^1\times A_8^1\times A_8^1=5\times 8\times 8=320$$

乘法原理是排列组合中的另一种基本原理。
具体是指：做一件事，完成它需要分成 n 个步骤，做第一步有 $m_1$种不同的方法，做第二步有$m_2$种不同的方法……做第 n 步有 $m_n$种不同的方法，那么完成这件事共有 $N=m_1\times m_2\times m_3\times \dots \times m_n$ 种不同的方法。注意，每种方法不能独立完成这件事情。例如，利用数字1、2、3、4、5组成不重复的3位数，那么百位数有5种选择，十位数有4种选择，个位数有3种选择，所以共有$5\times 4\times 3=60$种不重复的3位数组合。
已知从北京到上海中间必须经过济南，从北京到济南城共有$k_1$ 条路线，从济南到上海共有$k_2$条路线，那么从北京经过济南到达上海共有$k\times k_2$条路线。

3. 整数的因数问题

输入一个整数，输出其全部因数。

#include<iostream>
#include<cmath>
using namespace std;

int main() {
	int n;
	cin >> n;
	for(int i=1; i<=n; i++) {
		if(n%i==0) cout << i << ' ';
	}
	cout << endl;
	
	int temp = sqrt(n);
	for(int a=1; a<=temp; a++) {
		if(n%a==0) cout << a << ' ' << (n/a) << ' ';
	}
	cout << endl;

	return 0;
}

代码中后面的循环语句显然循环的次数要明显少得多，因为循环变量a是从1到sqrt(n)，a每次增1。
因为对于n=a*b，如果a<b，则必然存在a<=sqrt(n)且b>=sqrt(n)，这样我们只需要判断a并计算出b=n/a即可。

4. 鸡兔同笼问题

《孙子算经》中的鸡兔同笼问题：今有雉（zhì）兔同笼，上有35头，下有94足，问雉兔各几何？
对该问题，人们想出了多种解法。

解法1——抬腿法：
（1）假设所有的动物都抬起两条腿
（2）此时鸡没有腿，兔子有两条腿，此时腿的数量除以2，即为兔子的数量：(94-35*2)/2=12
（3）头的数量减掉兔子的数量，即为鸡的数量：35-rabbits

解法2——砍足法：
（1）每只动物均砍掉一半的脚，那么还剩94/2=47只脚，这47只脚中，每只鸡1只脚，每只兔子2只脚，那么47-35=12即为rabbits的数量。即rabbits*2+chicken=47, rabbits+chicken=35
（3）头的数量减掉兔子的数量，即为鸡的数量：35-rabbits=35-12=23

解法2——假设法：
假设全是鸡，其脚数为：35*2=70（只脚）
此时，鸡的总脚数比实际总脚数少：94-70=24（只脚）
则
兔的数量：24/(4-2)=12(只兔)
鸡的数量：35-12=23（只鸡）

或者
假设全是兔子，总脚数为：35*4=140（只脚）
此时，总脚数比实际总脚数多：140-94=46（只脚）
多的这些脚是在每一只鸡上都添加了2只脚得到的，所以
鸡：46/(4-2)=23（只鸡）
兔：35-23=12(只兔)

以上侧重于运用数学思维来解决问题，下面采用计算思维来解决问题，具体而言，就是采用枚举法来解决问题。因为问题非常简单，这里不予分析，读者可以直接阅读代码来体会枚举法的基本思想。

#include<iostream>
using namespace std;

int main() {
	unsigned int chickens, rabbits;
	for(rabbits=1; rabbits<23; rabbits++) {
		chickens = 35 - rabbits;
		if(chickens*2 + rabbits*4 == 94) {
			cout << "rabbits: " << rabbits << "  ";
			cout << "chickens: " << chickens << endl;
		}
	}
	return 0;
}

运行代码，输出结果为：
rabbits: 12 chickens: 23

5. 完全数问题

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
如果一个数恰好等于它的真因子之和，则称该数为“完全数”。第一个完全数是6，第二个完全数是28，第三个完全数是496，后面的完全数还有8128、33550336等等。截至2018年，相关研究者已经找到51个完全数。
请编写一个程序，找出10000以内的所有完全数。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int i, j, sum, n; 
	cout << "请输入所选范围上限: ";
	cin >> n;
	for(i=1; i<=n; i++) {
		sum = 0; /*保证每次循环时s的初值为0*/
		for(j=1; j<i; j++) {
			if(i%j == 0) /*判断j是否为i的因子*/
			sum += j;
		}
		if(sum == i) /*判断因子这和是否和原数相等*/
			cout << setw(7) << i;
	}

    return 0;
}

下面是程序运行的一次输入输出

请输入所选范围上限: 10000
      6     28    496   8128

6. 花束问题

花店里新购入一批鲜花，五颜六色非常好看。路西妹妹准备从其中的4枝蓝花、5枝红花和6枝黄花中取出8枝花组成一束花，且她必定会选择红花。请编写一段程序，统计共有多少种选择方案。
输入：无。
输出：一个整数，即方案数。
样例输入：无
样例输出：
23

【提示】采用穷举法：

方案数初始为0
for(蓝花数=0~4)
    for(红花数=1~5){
        黄花数 = 8 - 蓝花数 - 红花数;
        如果黄花数>=0 && 黄花数<=6, 则方案数加1;
    }

#include<iostream>
using namespace std;

int main() {
	int count = 0;
	int blue, red, yellow;
	for(blue=0; blue<=4; blue++) {
		for(red=1; red<=5; red++){
	        yellow = 8-blue-red;
	        if(yellow>=0 && yellow<=6) {
	        	count++;
	        	cout << blue << ' ' << red << ' ' << yellow << endl;
			}
	    }
	}
	cout << count << endl;  // 23
	return 0;
}

---

总结

本课主要介绍了如下问题的解决方法。

1. 平均成绩问题
2. 水仙花数问题
3. 用字符打印等腰三角形图形问题
4. 幂的末尾三个数字问题
5. 救援问题