循环结构(四)——循环嵌套

有不懂的地方可以si我，和我一起学习C++吧。

fzy20110826

1685人浏览 · 2024-08-15 10:22:48

fzy20110826 · 2024-08-15 10:22:48 发布

🚀欢迎互三👉：程序猿方梓燚 💎💎
🚀所属专栏：C++教程💎

🚀关注博主，后期持续更新系列文章

🚀如果有错误感谢请大家批评指出，及时修改

🚀感谢大家点赞👍收藏⭐评论✍

🍁引言

在编程的世界里，循环结构是实现重复操作的强大工具。而当循环与循环相互嵌套时，就如同打开了一扇通往更复杂、更强大逻辑的大门。循环嵌套就像是一个精心编排的舞蹈，外层循环掌控着整体的节奏，内层循环则在其中演绎着细腻的动作。

想象一下，要绘制一个复杂的图案，外层循环决定了图案的行数，内层循环则雕琢着每行中的细节。又或者在处理大量数据时，外层循环遍历不同的数据集，内层循环则对每个数据集中的元素进行精确操作。

例如，在生成乘法表的程序中，外层循环控制行数，内层循环控制列数，两者相互配合，才能准确无误地展示出乘法运算的结果。再比如，要找出一个二维数组中的最大值，就需要通过循环嵌套来遍历数组的每一个元素。

循环嵌套让我们能够解决那些看似棘手、实则充满规律的问题，它是编程中的艺术，也是提升程序效率和灵活性的关键。接下来，让我们深入探索循环嵌套的奥秘，开启编程的新篇章。

🍁例题

🚀例1

求 S=1!+2!+3!+....+10!

分析：这个问题是求10以内自然数的阶乘之和，可以用for循环来实现。程序结构如下：
for(i=1;i<=10;++i) {   
    (1)i阶乘的值存到t；    //t=i!
    (2)累加t到s中；       //s+=t
}
显然根据以上结构，通过10次的循环可以求出1！，2！，…10!,并不断累加起来，求出s。而求t=i!,又可以用一个for循环来实现：
t=1;
for (j=1;j<=i;++j)
    t*=j;
因此整个程序为：
#include <iostream>
using namespace std;
int main (){
    int t,s;
    s=0;
    for(int i=1;i<=10;++i) {
        t=1;
        for (int j=1;j<=i;++j)            //求i!
            t*=j;
            s+=t;                           //累加i!
    }
    return 0;
}
以上程序是一个for循环的嵌套。这种方法是比较容易想到的，但实际上对于求i！，我们可以根据求出的（i-1）！乘上i即可得到，而无需重新从1再累乘到i。

🚀例2

对于给定的自然数n(n<20)，在屏幕上输出仅由“*”构成的n行的直角三角形。例如：当n=5时，输出：

【分析】打印图形总是逐行进行的，本题要重复n行操作，对于每一行，又重复若干次输出“*”操作。于是，构成了一个两层循环：外层循环是1至n行的处理，而内层循环，则是输出同一行上的每一列。分析样例，不难发现，每一行上“*”的个数恰好是行数。因此对于第i行，内层循环可以设置重复i次。

程序如下：
#include <iostream>
using namespace std;
int main () {
	int i, j, n;
	cin >> n;
	for (i = 1; i <= n; ++i) { //外层循环，控制行数
		for (j = 1; j <= i; ++j) //内层循环，输出一行中的*数
			cout << "*";
		cout << endl;        //每行最后要换行
	}
	return 0;

}
🚀例3

百钱买百鸡问题。鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

💎【方法1】

在数学中解决这个问题，我们通常会列出一个方程组，设鸡翁x，鸡母y，鸡雏z，则： x+y+z=100

5*x+3*y+z/3=100

同时满足上述两个方程的x、y、z值就是所求。

根据这个思路，问题就转化为求解方程组，我们列举x、y、z的所有可能解，然后判断这些可能解是否能使方程组成立。能使方程组成立的，就是真正的解。

再进一步分析，x的取值范围是1～100/5，y的取值范围是1～100/3，z的取值范围是1～3*100。

程序如下：
#include <iostream>
using namespace std;
int main() {
	int x, y, z;
	for (x = 0; x <= 100 / 5; x++) //列举鸡翁数的所有可能
		for (y = 0; y <= 100 / 3; y++) //列举鸡母数的所有可能
			for (z = 0; z <= 3 * 100; z++) //列举鸡雏数的所有可能
				if (5 * x + 3 * y + z / 3 == 100 && x + y + z == 100 && z % 3 == 0) //满足两个方程组
					cout << x << " " << y << " " << z << endl; //输出x、y、z值
	return 0;
}
运行结果：

【说明】这里用了一个三层循环的程序解决问题。当x取得一个数值时，for的y循环体都要执行遍y的所有取值；当y取得一个数值时，for的z循环体都要执行遍z的所有取值；对于z的每一个取值，if语句都要执行一次。不难算法，在程序的执行过程中，作为最内层循环体的if语句，将被执行：(1+100/5)*(1+100/3)*(1+3*100)=214914次。而观察程序的运行结果，问题的解远远小于这个数字，只有4组解。如何减少循环次数呢？

💎【方法2】

由于题目的特殊性，鸡翁、鸡母、鸡雏共100只，一旦确定鸡翁x和鸡母y的数量，鸡雏便只能购买100-x-y只。这样，我们可以尝试写出一个两层循环的程序，解决这个问题。程序如下：
#include <iostream>
using namespace std;
int main() {
	int x, y, z;
	for (x = 0; x <= 100 / 5; x++) //列举鸡翁数的所有可能
		for (y = 0; y <= 100 / 3; y++) { //列举鸡母数的所有可能
			z = 100 - x - y;           //根据x，y计算鸡雏的数量
			if (5 * x + 3 * y + z / 3 == 100 && z % 3 == 0) //判断总钱数是否符合条件
				cout << x << " " << y << " " << z << endl; //输出x、y、z值
		}
	return 0;
}
【说明】对于与本题类似的求解不定方程问题，都可以用循环来求解。为提高效率，可以在程序中进行适当优化，减少循环体的执行次数。

🚀例4

求100－999中的水仙花数。若三位数ABC，ABC=A3+B3+C3，则称ABC为水仙花数。例如153，13+53+33=1+125+27=153，则153是水仙花数。

【分析】根据题意，采用三重循环来求解。由于循环次数一定，用for循环最为简单。

程序如下：
#include<iostream>
#include<iomanip>                            //调用setw函数需注明使用该库
using namespace std;
int main() {
	for (int a = 1; a <= 9; ++a)
		for (int b = 0; b <= 9; ++b)
			for (int c = 0; c <= 9; ++c) {
				if (a * a * a + b * b * b + c * c * c == a * 100 + b * 10 + c)
					cout << setw(6) << a * 100 + b * 10 + c; //setw函数控制输出场宽
			}
	return 0;
}
运行结果：

同时也可以采用一个for循环来求解，表面上看好像优于三重循环，实际上却比上面的程序效率低，请同学们自己分析。

程序如下：
#include<iostream>
#include<iomanip>
using namespace std;
int main() {
	int a, b, c;
	for (int m = 100; m <= 999; ++m) {
		a = m / 100; 		      //m的百位
		b = (m % 100) / 10; 		 //m的十位
		c = m % 10;                   //m的个位
		if (a * a * a + b * b * b + c * c * c == m)
			cout << setw(6) << m;
	}
	return 0;
}
🚀例5

输出100—200中所有的素数。

分析：我们可对100-200之间的每一个整数进行判断，若它是为素数，则输出。而对于任意整数i，根据素数定义，我们从2开始，到sqrt（i），找i的第一个约数，若找到第一个约数，则i必然不是素数。

程序如下：
#include <iostream>  
#include<cmath>                            //在Dev C++中可调用数学函数库cmath
using namespace std;
int main ()
{
  int x;
  for (int i=100;i<=200;++i)
  {
     x=2;
     while(x<=floor(sqrt(i))&&(i%x!=0))    //floor为取整函数，需调用math.h库
     x=x+1;                       //在枚举的范围内并且没有出现约数则继续枚举
     if ( x>floor(sqrt(i)))
       cout<<i<<"\t";
  }
  return 0;
}
🚀例6

【分析】分支和循环结合在一起时威力特别强大：我们枚举所有可能的aabb，然后判断它们是否为完全平方数。注意，a的范围是1～9，b可以是0。主程序如下：
for (a=1; a<=9; a++)
      for (b=0; b<=9; b++)
        if (aabb是完全平方数) printf("%d\n",aabb);
另一个思路是枚举平方根x，参考程序如下：
#include<cstdio>
int main()
{
	int n=0,hi,lo;
	for (int x=1 ;  ; ++x)                //可以直接从x=32开始枚举
	{
		n=x*x;
	 	if (n<1000) continue;
	 	if (n>9999) break;
	 	hi = n/100;
		lo = n%100;
		if (hi/10 == hi%10 && lo/10 == lo%10) printf("%d\n",n);
	}
	return 0;
}
此程序中的新东西是continue和break语句。continue是指跳回for循环的开始，执行调整语句并判断循环条件，就是“直接进行下一次循环”，而break是指直接跳出循环。另外，注意到这里的for语句是“残缺”的：没有指定循环条件。事实上，3个部分都是可以省略的。没错，for(;;)就是一个死循环—如果不采取措施(如break)，它就永远不会结束。

🚀例7

把一个合数分解成若干个质因数乘积的形式(即求质因数的过程)叫做分解质因数。分解质因数(也称分解素因数)只针对合数。输入一个正整数n，将n分解成质因数乘积的形式。

输入样例： 36

输出样例： 36=2×2×3×3

【分析】

将任意的n分解为质因数的乘积，要从最小的质数开始，那么，我们就不妨从2开始试除，能整除就输出2，再对商继续试除,直到不再含有因子2；然后用下一个质数反复试除，……，再用下一个质数试除，……，一直到商为1，停止操作。

这里，质因数的递增，是一层循环，每一个质因数的反复试除，又是一层循环。因此，本题使用两层循环来解决。

程序如下：
#include <iostream>
using namespace std;
int main() {
	int n, i = 2;
	cin >> n;
	cout << n << "=";
	do  {
		while (n % i == 0) { //n能被i整除，就重复做除法操作
			cout << i;
			n /= i;
			if (n != 1)
				cout << "×";
		}
		i++;
	} while (n != 1);        //n没有除尽，就重复操作
	return 0;
}
🚀例8

阶乘之和输入n，计算S=1! + 2! + 3! + … + n!的末6位(不含前导0)。n<=106， n!表示前n个正整数之积。

样例输入：10

样例输出：37913

【分析】这个任务并不难，引入累加变量S之后，核心算法只有一句话：
for (i=1;i<=n;i++)
        S+=i!
不过C++语言并没有阶乘运算符，所以这句话只是伪代码，而不是真正的代码。事实上，我们还需要一次循环来计算i!：
for (j=1;j<=i;++j) 
    factorial*=j;
代码如下：
#include<cstdio>
int main()
{
	int n,s=0;
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	{
		int factorial=1;
		for (int j=1;j<=i;++j)
		  factorial*=j;
		s+=factorial;		
	}
	printf("%d\n",s%1000000);
	return 0;
}
注意累乘器factorial(英文“阶乘”的意思)定义在循环里面。换句话说，每执行一次循环体，都要重新声明一次factorial，并初始化为1(想一想，为什么不是0)。因为只要末6位，所以输出时对10^6取模。

当n=100时，输出-961703，直觉告诉我们：乘法溢出了。这个直觉很容易通过“输出中间变量”法得到验证，但若要解决这个问题，还需要一点数学知识。试一下n=106时输出什么？更会溢出，但是重点不在这里。事实上，它的速度太慢！让我们把程序改成“每步取模”的形式，然后加一个“计时器”，看看它到底有多慢。
#include<cstdio>
#include<ctime>
const int MOD = 1000000;
int main() {
	int n, s = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		int factorial = 1;
		for (int j = 1; j <= i; ++j)
			factorial = (factorial * j % MOD);
		s = (s + factorial) % MOD;
	}
	printf("%d\n", s);
	printf("Time used= %.2lf\n", (double)clock() / CLOCKS_PER_SEC);
	return 0;       //输出时间包含键盘输入的时间，建议用文件输入输出，后面章节介绍文件
}
这个程序真正的特别之处在于计时函数clock()的使用。该函数返回程序目前为止运行的时间。这样，在程序结束之前调用它，便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。

输入100000，按Enter键，系统迟迟不输出答案，原因在于程序中重复进行了多次阶乘运算，浪费了大量时间，具体优化方法请参考例1 。

也可以用数组来解决此类问题，代码如下:
#include <cstdio>
#include <ctime>
const int MOD = 1000000;
int factorials[100001];  // 存储已经计算过的阶乘
int main() {
	int n, s = 0;
	scanf("%d", &n);
	factorials[0] = 1;
	for (int i = 1; i <= n; ++i) {
		factorials[i] = (factorials[i - 1] * i) % MOD;  // 利用上一次的阶乘结果
		s = (s + factorials[i]) % MOD;
	}
	printf("%d\n", s);
	printf("Time used= %.2lf\n", (double)clock() / CLOCKS_PER_SEC);
	return 0;
}
优化后的代码主要有以下不同：

新增了一个数组 factorials 来存储已经计算过的阶乘值。

原始代码每次计算一个新的 i 的阶乘时，都要重新从 1 乘到 i ，而优化后的代码可以直接利用前一个 i - 1 的阶乘值乘以 i 得到当前 i 的阶乘值，避免了重复计算，大大提高了计算效率。

计算阶乘的方式改变。

原始代码通过嵌套的循环来计算阶乘，而优化代码通过数组存储和递推的方式计算阶乘。

总的来说，优化后的代码通过利用已计算的结果和避免重复计算，显著提高了程序在处理较大输入值时的性能。