第二章 循环结构程序设计

第二章 循环结构程序设计

目录

2.1 for循环

②7744问题

2.2 while循环和do-while循环

3n+1问题

近似计算

2.3 循环的代价

阶乘之和

2.4 算法竞赛中的输入输出框架

②输入输出重定向，

④多组数据

2.5 注解与习题

①水仙花数

②韩信点兵

③倒三角形

正三角形

④子序列的和

---

2.1 for循环

①格式：for(初始化；条件；调整)

②7744问题

floor（x）返回不大于x的最大整数；

floor（x+0.5）四舍五入

#include
#include
int main(){
for(int a=1;a<=9;a++)
for(int b=0;b<=9;b++)
{
int n=a*1100+b*11;
int m=floor(sqrt(n)+0.5);
if(m*m==n)
printf("%d",n);
}

#include
int main() {
	for (int x = 1; ; x++) {
		int n = x * x;
		if (n < 1000) continue;//continue是跳回for循环的开始，直接进行下一次循环
		if (n > 9999) break;//break是直接跳出循环
		int hi = n / 100;//前两位
		int lo = n % 100;//后两位
		if (hi / 10 == hi % 10 && lo / 10 == lo % 10)//abcd   a=b c=d
			printf("%dn", n);
	}
return 0;
}

2.2 while循环和do-while循环

格式：while（条件）循环体；

3n+1问题

对于任意大于1的自然数n，若n为奇数，则将n变为3n+1，否则变为n的一半。经过若干次这样的变换，一定会使n变为1。输入n，输出变换的次数。n<=10^9。

#include
int main() {
	int n2, count = 0;
	scanf("%d", &n2);
	long long n = n2;//避免对long long的输入输出
	while (n > 1)
	{
		if (n % 2 == 1)
			n = n * 3 + 1;
		else
			n /= 2;
		count++;
	}
	printf("%d", count);
	return 0;
}

近似计算

π/4=1-1/3+1/5-1/7+······，直到最后一项小于1e-6

1e-6表示的是浮点数。也就是1*10的-6次方。

#include
int main() {
	double sum = 0;
	for (int i = 0; ; i++)
	{
		double term = 1.0 / (i * 2 + 1);
		if (i % 2 == 0)sum += term;
		else sum -= term;
		if (term < 1e-6) break;
	}
	printf("%.6fn", sum);
	return 0;
}

2.3 循环的代价 阶乘之和

输入n，计算s=1！+2！+3！+……+n！的末六位（不含前导0）。n<=1e+6,n!表示前n个正整数之积；

只要末六位，输出时对1e+6取模即可。

#include
int main() {
	const int MOD = 1000000;
	int n, s=0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
			int sum = 1;
			for (int j = 1; j <= i; j++) {
				sum =(sum* j%MOD);
			}
			s =(s+ sum)%MOD;
		}
		printf("%dn", s);
	
	return 0;
}

问题：乘法溢出。

循环结构程序设计最常见的两个问题：算术运算溢出和程序效率低下。

解决方案：数学知识

返回到原题，n！，若n！末尾有6个0，则不影响和的末六位。

而当n等于25时，25！末尾有6个0，从这一项往后所有的项都不会影响和的末6位，

所以应在程序前面写if(n>25) n=25;

#include
int main() {
	const int MOD = 1000000;
	int n, s=0;
	scanf("%d", &n);
	if (n > 25)
		n = 25;
	for (int i = 1; i <= n; i++) {
			int sum = 1;
			for (int j = 1; j <= i; j++) {
				sum =(sum* j%MOD);
			}
			s =(s+ sum)%MOD;
		}
		printf("%dn", s);
	return 0;
}

#include

printf("Time used=%.2fn",(double)clock()/CLOCK_PER_SEC);
//获得整个程序的运行时间

2.4 算法竞赛中的输入输出框架

①在Windows下，输入完毕后先按Enter键，再按Ctrl+Z键，最后再按Enter，即可结束输入。

    在Linux下，输入完毕后按Ctrl+D键即可结束输入。

②输入输出重定向，

在main函数的入口处加一下两条语句。文件输入输出

freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

注意：竞赛之前先了解文件读写的规定，是标准输入输出，还是文件输入输出，如果是文件输入输出，是否禁止用重定向方式访问文件。

③

//若比赛要求用文件输入输出，但禁止用重定向的方式，用fopen
FILE *fin,*fout;
fin=fopen("data.in","rb");
fout=fopen("data.out","wb");

fscanf(fin,"%d",&x);

fprintf(fout,"%d",x);

fclose(fin);
fclose(fout);//关闭文件夹
//若想改为标准输入输出，只需赋值"fin=stdin;fout=stdout;"即可

④多组数据

输入一些数据，求出最小值、最大值、平均值（保留三位小数）。输入保证这些数都是不超过1000的整数。

输入包含多组数据，每组数据第一行是整数个数n，第二行是n个整数，n=0为输入结束标记，程序应当忽略这组数据。相邻两组数据之间应该输出一个空行。

#include
#define INF 1000000000 
int main() {
	int x, n = 0, kase = 0;
	while (scanf("%d", &n) == 1 && n)//n=0为输入结束标志，&&n
	{
		int s = 0;
		int min = INF, max = -INF;
		for (int i = 0; i < n; i++) {
			scanf("%d", &x);
			s += x;
			if (x < min) min = x;
			if (x > max) max = x;
		}
		if (kase) printf("n");
		printf("Case %d:%d %d %.3fn", ++kase, min, max, (double)s / n);
	}
	return 0;
}

2.5 注解与习题 ①水仙花数

100~999中的所有水仙花数。

#include
#include
int main() {
    int a,b,c = 0;
    int count = 0;
    for (int i = 100; i < 1000; i++) {
        a = i / 100;//百位
        b = (i / 10) % 10;//十位
        c = i% 10;//个位
        if (i == pow(a, 3) + pow(b, 3) + pow(c, 3)) {
            count++;
            if (count != 0&&count!=1) {
                printf(" ");
            }//空格分开每组数据
            printf("%d", i);
        }
    }
    return 0;
}

②韩信点兵

相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。
输入3个非负整数a,b,c ，表示每种队形排尾的人数（a<3,b<5,c<7），
输出总人数的最小值（或报告无解）。已知总人数不小于10，不超过100 。
 

③倒三角形

#include
int main() {
	int n = 0;
	scanf("%d",& n);
	for (int i = n; i>0; i--)
	{
		for (int k =n-i; k >0; k--) 
		{
			printf(" ");
		}
		for (int j=2*i-1 ; j >0; j--)
		{
				printf("#");
		}
		printf("n");
	}
	return 0;
}

正三角形

#include 
using namespace std;
int main()
{
	int n;
	cin >> n;
		for (int i = 0; i <= n; i++) 
		{
			for (int k = 0; k < n - i; k++) 
			{
				cout << " ";
			}
			for (int j = 0; j < 2 * i - 1; j++)
			{
				cout << "#";
			}
			cout << endl;
		}
}

④子序列的和

输出两个正整数n

#include
int main() {
	int n, m = 1,kase=0,s=0;
	while (scanf("%d %d", &n, &m) && (n != 0) && (m != 0))
	{
		double sum = 0;
		for (int i = n; i <= m; i++)
		{
			sum += 1.0 / i/i;
		}
		++kase;
		printf("Case %d :%.5lf",kase ,sum);
	}
	return 0;
}