C语言-嵌套循环与循环结构的程序设计

1、嵌套循环

循环里面还包含有循环称之为嵌套循环，也叫多重循环。

下面看一个嵌套循环计算阶乘和的例子：

例1：求阶乘和

#include 	 

int main(void)
{
	int i, j, n;
	double item;
	double sum;

	printf("Enter n:");	
	scanf("%d", &n);
	sum = 0;
	for (i=1; i<=n; i++){	/*外层循环执行n此，求累加和*/
		item = 1;			/*置item的初值为1，以保证求阶乘都从1开始连乘*/
		for (j=1; j<=i; j++){	/*内层循环重复i次，算出item=i!*/
			item *= j;
		}
		sum += item;		/*累加i!*/
	}
	printf("1!+2!+...+%d!=%.0f\n", n, sum);
	
	return 0;
}

Enter n:15
1!+2!+…+15!=1401602636313

该程序就使用了嵌套循环，外层循环重复了n次，每次累加1项item(即i!)，而每次的累加对象i!由内层循环计算得到，内层循环重复i次，每次连乘1项。

嵌套循环一定要注意内外层循环的初始化，假如本例将嵌套循环改成如下：

	item = 1;		/*循环初始化*/
	for (i=1; i<=n; i++){
		for (j=1; j<=i; j++){
			item = item*j;
		}
		sum += item;
	}

此时就会出现错误，因为此时item的初始化放在了外循环，那么内循环时就仅在计算1!时初始化了1次。

计算3!会得到结果为12(1!*2!*3!)，这里就出现了错误。

所以正确的做法应该在外循环初始化sum=0;内循环初始化item=1。

注： 内外层循环的变量不能相同。

2、循环结构程序设计

对于需要用到循环结构的程序设计，首先要是要明确循环程序的要点：
（1）归纳出哪些 *** 作需要反复执行——循环体。

（2）这些 *** 作在什么情况下重复执行——循环控制条件。

确定了循环体和循环条件，循环结构就可以确定了，然后需要选择三种循环语句（for，whlie和do-while）中的一种来实现循环。

一般来说，如果事先知道了循环次数，首选for语句，因为它看起来最清晰，循环的4个组成部分一目了然；如果循环次数不明确，需要通过其他条件控制循环的话，通常选用while语句或者do-while语句；若是必须先进入循环，经循环体运算得到循环控制条件后，再判断是否进行下一次循环，使用do-while语句。

例2：最值问题

输入一批学生的成绩，找出最高分。

这种没有指定输入数据的个数，需要自己增加循环条件，一般有两种方法：
1、先输入一个正整数n，代表数据的个数，然后再输入n个数据，循环重复n次，这种属于指定次数的循环，选for语句。

2、设定一个特殊的数据（伪数据）作为循环的结束标志，由于成绩都是非负数，选用一个负数作为输入的结束标志。

由于循环次数未知，可以选用while语句。

程序1：

/*从输入的n个成绩中选出最高分，用for语句实现*/
#include 

int main(void)
{
	int i, mark, max, n;			/*max中放最高分*/
	
	printf("Enter n:");				
	scanf("%d", &n);		
	printf("Enter %d marks:", n);
	scanf("%d", &mark);				/*读入第一个成绩*/
	max = mark;						/*假设第一个成绩是最高分*/
	for (i=1; i<n; i++){			/*由于已经读了一个数，循环执行n-1次*/
		scanf("%d", &mark);			/*读入下一个成绩*/
		if (max < mark){			/*如果该成绩比最高分高*/
			max = mark;				/*再假设该成绩为最高分*/
		}
	}
	printf("Max = %d\n", max);
	
	return 0;
}

Enter n:6
Enter 6 marks:87 34 90 10 88 99
Max = 99

程序2：

/******从输入的一批以负数结束的成绩中选出最高分，用while语句实现*******/
#include 

int main(void)
{
	int mark, max;					/*max中放最高分*/ 
	
	printf("Enter marks:");			
	scanf("%d", &mark);				/*读入第一个成绩*/
	max = mark;						/*假设第一个成绩是最高分*/
	/*当输入的成绩mark大于等于0时，执行循环*/
	while (mark > 0){
		if (max < mark){			/*如果读入的成绩比最高分高*/
			max = mark;				/*再假设该成绩为最高分*/
		}
		scanf("%d", &mark);			/*读入下一个成绩*/
	}
	printf("Max = %d\n", max);
	
	return 0;
}

Enter marks:98 78 98 49 90 99 45 0 88 -2
Max = 99

例3：斐波那契数列

输入正整数 n n n( 1 ≤ n ≤ 46 1\leq n \leq 46 1≤n≤46)，输出斐波那契(Fibonacci)数列的前n项：1，1，3，5，8，13， … … …，每行输出5个。

Fibonacci数列就是满足任一项数字是前两项的和（最开始的两项均定义为1）的数列。

/*输出斐波那契数列的前n项*/
#include  

int main(void)
{
	int i, n, x1, x2, x;			/*x1和x2依次代表前两项，x表示最后一项*/
	
	printf("Enter n:");	
	scanf("%d", &n);
	if (n<1 || n>46){
		printf("Invalid.\n");
	} else if (n == 1){
		printf("%10d", 1);			/*输出第1项*/
	} else {
		x1 = 1;						/*头两项都是1*/
		x2 = 1;
		printf("%10d%10d", x1, x2);	/*先输出头两项*/
		for (i=3; i<=n; i++){		/*循环输出后n-2项*/
			x = x1+x2;				/*计算新项*/
			printf("%10d", x);
			if (i%5 == 0){			/*如果i是5的倍数，换行*/
				printf("\n");
			}
			x1 = x2;				/*更新x1和x2，为下一次计算新项x做准备*/
			x2 = x; 
		}
	}

	return 0;
}

Enter n : 14
         1         1         2         3         5
         8        13        21        34        55
        89       144       233       377

计算斐波那契数列时，从第三项开始，每一项的值就是前2项的和。

用两个变量存储最近产生的两个序列值，计算出新一项数据后，需要更新这两个变量的值。

假定最开始两项分别用x1=1和x2=1表示，则新项x=x1+x2，然后更新x1和x2：x1=x2及x2=x，为计算下一个新项x作准备。

本例要求输出n项，循环次数是确定的，选择for循环。

这里计算斐波那契数列采用的是迭代法，还可以使用数组计算和递归的方法来实现。

迭代法也称辗转法，是一个不断从变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。

迭代法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性 *** 作的特点，让计算机对一组指令（或一定步骤）进行重复执行，再每次执行这组指令（或这些步骤）时，都从变量的原值推出新值。

例4：素数问题

输入2个正整数m和n( 1 ≤ m ≤ n ≤ 500 1\leq m\leq n \leq 500 1≤m≤n≤500)，输出m到n之间的全部素数，每行输出10个。

素数就是只能被1和自身整除的正整数，1不是素数，2是素数。

/*使用嵌套循环求m导n之间的全部素数*/
#include 
#include 		/*调用求平方根函数，需要包含数学库*/

int main(void)
{
	int count, i, k, flag, limit, m, n;	/*flag表示是否为素数*/
	
	printf("Enter m n:");	
	scanf("%d%d", &m, &n);				
	count = 0;							/*count记录素数的个数，用于控制输出格式*/
	if (m < 1 || n > 500 || m > n){		
		printf("Invalid.\n");
	} else {
		for (k=m; k<=n; k++){
			if (k <= 1){					/*小于等于1的数不是素数*/
				flag = 0;
			} else if (k == 2){				/*2是素数*/
				flag = 1; 
			} else {						/*其他情况：大于2的正整数*/
				flag = 1;					/*先假设k是素数*/
				limit = sqrt(k)+1;
				for (i=2; i<=limit; i++){
					if (k%i == 0){			/*若k能被某个i整除，则k不是素数*/
						flag = 0;			/*置flag为0*/
						break;				/*提前结束循环*/ 
					}
				}
			}
			if (flag == 1){					/*如果k是素数*/
				printf("%6d", k);			/*输出k*/
				count++;					/*累加已经输出的素数个数*/
				if (count%10 == 0){			/*如果count是10的倍数，换行*/
					printf("\n");
				}
			}
		}
	}
	
	return 0;
}

Enter m n:2 45
     2     3     5     7    11    13    17    19    23    29
    31    37    41    43

本例使用的是二重嵌套循环，外层循环遍历m~n之间的所有数，内层循环对其中的每一个数判断是否为素数。

判断素数可以判断该数m是否能被 [ 0 , m ] [0, \sqrt{m}] [0,m ​]之间的数整除就可以了。

本例使用了标志位的小技巧，即引入了变量flag，flag的值为1则表示素数，为0不是素数。

这里先假设其为素数，若不是素数，则将flag置0，否则不变。

判断真假状态经常使用标志位的技巧来进行判断。

例5：搬砖问题

某工地需要搬运砖块，已知男人一人搬3块，女人一人搬2块，小孩两人搬1块。

如果想用n人正好搬n块砖，问有哪些搬法？

/*n人正好搬n块砖*/
#include 

int main(void) 
{
	int children, cnt, men, n, women;
	
	printf("Enter n:");	
	scanf("%d", &n);
	cnt = 0;
	for (men=0; men<=n; men++){
		for (women=0; women<=n; women++){
			for (children=0; children<=n; children++){
				if ((men+women+children==n)&&(men*3+women*2+children*0.5==n)){
					printf("men = %d, women = %d, children = %d\n", men, women, children);
					cnt++;
				}
			}
		}
	}
	if (cnt == 0){
		printf("None\n");
	}
	
	return 0;
}

Enter n:53
men = 1, women = 16, children = 36
men = 4, women = 11, children = 38
men = 7, women = 6, children = 40
men = 10, women = 1, children = 42

这里采用了枚举的方法，枚举了男人、女人和小孩的人数，最后已人数等于要搬的砖数作为判断条件。

采用了三重循环嵌套，找出所有可能的情况。

三重循环计算量较大，本例可以改进一下。

若只枚举男人和女人，则小孩的人数就可以通过约束条件算出来，即chilren = n-men-women。

并且砖的数量为n块，男人的数量无法超过n/3，女人的数量不会超过n/2，这样就缩小了枚举的范围，提升了程序的运行效率。

下面为改进后的程序：

/*改进后的程序：仅枚举men、women，并且加上限制条件*/		
#include 

int main(void) 
{
	int children, cnt, men, n, women;
	int limit_m, limit_w;
	
	printf("Enter n:");
	scanf("%d", &n);
	limit_m = n / 3;
	limit_w = n / 2;
	cnt = 0;
	for (men=0; men<=limit_m; men++){
		for (women=0; women<=limit_w; women++){
			children = n-men-women;
			if (men*3+women*2+children*0.5 == n){
				printf("men = %d, women = %d, children = %d\n", men, women, children);
				cnt++;
			}
		}
	}
	if (cnt == 0){
		printf("None\n");
	}
	
	return 0;
}

两组程序效果完全一样，未改进前，if语句执行了 ( n + 1 ) 3 (n+1)^3 (n+1)3次，而改进后，if语句只执行了 ( 1 + n / 3 ) ∗ ( 1 + n / 2 ) (1+n/3)*(1+n/2) (1+n/3)∗(1+n/2)次。

例如当n=53时，未改进前执行了157464次，而改进后执行了486次，可以看到执行效率的差别很大。

因此可以看到，虽说都能实现统一功能，但不同的程序执行效率差别很大。

因此设计程序时要考虑程序的执行效率，选择更优秀的算法。

例6：找零问题

有足够数量的5分、2分和1分的硬币，现在要用这些硬币来支付一笔小于1元的零钱，问至少要用多少个硬币？输入零钱，输出硬币的总数量和相应面额的硬币数量。

#include 

int main(void)
{
	int flag, money, n1, n2, n5;	/*n1, n2, n5分别表示1分、2分和5分硬币的数量*/
	
	flag = 1;						/*flag表示是否找到满足条件的解并中止嵌套条件*/
	printf("Enter money:");	
	scanf("%d", &money);
	for (n5=money/5; (n5>=0)&&(flag==1); n5--){
		for (n2=(money-n5*5)/2; (n2>=0)&&(flag==1); n2--){
			for(n1=money-n5*5-n2*2; (n1>=0)&&(flag==1); n1--){
				if ((n5*5+n2*2+n1) == money){	/*找到满足条件的解*/
					printf("fen5:%d, fen2:%d, fen1:%d, total:%d\n", n5, n2, n1, n1+n2+n5);
					flag = 0;		/*置flag为0，则三重循环的条件都不满足，中止嵌套循环*/
				}
			}
		}
	}
	
	return 0;
}

Enter money:29
fen5:5, fen2:2, fen1:0, total:7

本例要求硬币的总数最小，那么优先考虑使用面值打的硬币，即按照5分、2分和1分的顺序，分别从取值范围的上限到下限，采用三重循环嵌套，找到满足条件的解。

当找到满足条件的解时，第一个即为硬币总数最少的那个解，那么循环不需要继续。

本例使用了flag标志找到解，在三个循环上都添加了这个条件的判断，一旦flag变为0，则直接退出所有循环。

这里采用的是贪心算法。

贪心法接近人们日常思维习惯，在对问题求解时，通常只考虑当前局部最优的策略，能否最终得到全局的最优解是贪心法的关键。

本例中，局部策略是每次按可换面值最大的硬币找零钱，这样的局部策略正好可以得到最终全局最优解，即最后换取的硬币总数最少。

参考 C语言程序设计(第4版)/何钦铭，颜晖
例题及课后习题参考程序https://gitee.com/sgxgitee/mooc-c