2.循环结构程序设计

内容

for 循环

1. 输出1，2，3，...，n的值

   #include<stdio.h>
   
   int main()
   {
       int n;
       scanf("%d", &n);
       for(int i=1; i<=n; i++){
           printf("%d\n", i);
       }
       return 0;   
   } 
   

   1. for循环的格式: for(初始化; 条件; 调整) 循环体;
   2. 注意理解for循环的执行过程
   3. 在循环内定义变量的i，循环体外不可见。尽量缩小变量定义的范围。
2. 输出所有形如aabb的4位完全平方数。

   #include<stdio.h>
   #include<math.h>
   
   int main()
   {
       // 两层循环嵌套 
       for(int i=1; i<10; i++){
           for(int j=0; j<10; j++){
               // 得到 aabb 这种数 
               int n = i*1100+j*11;
               // 开方，四舍五入 
               int m = floor(sqrt(n) + 0.5);
               if(m*m == n){
               printf("%d\n", n);
               } 
           }
       }
       return 0;   
   }
   

   1. 伪代码，实际应用中，不需要太拘泥于伪代码的格式，主要目标是描述算法梗概，避开细节，启发思路。
   2. 浮点运算可能存在误差。在进行浮点数比较时，应考虑到浮点误差。

   // 解答二 枚举法
   #include<stdio.h>
   #include<math.h>
   
   int main()
   {
       for(int i=1; ; i++){
           int x = i*i;
           if(x < 1000){
               continue;
           }
           if(x > 9999){
               break;
           }
           int hi = x/100;
           int low = x%100;
           if(hi/10 == hi%10  && low/10 == low%10){
               printf("%d\n", x);
           }
       } 
       return 0;   
   }
   

   注：把所有平方数都列举出来，选出满足条件的，四位数，aabb型。

while循环和do-while循环

1. 3n+1问题
   对于任意大于1的自然数n，若n为奇数，则将n变为3n+1，否则变为n的一半。经过若干次这样的变换，一定会使n变为1。求变换次数。

   #include<stdio.h>
   
   int main()
   {
       int n, times;
       scanf("%d", &n);
       times = 0;
       while(n != 1){
           if(n%2 == 0){
               n = n/2;
           }else{
               n = 3*n+1;
           }
           times++;
       }
       printf("%d", times);
       return 0;   
   }
   

   1. while循环的格式为：while(条件) 循环体;
   2. 当需要统计某种事物个数时，可以用一个变量来充当计数器。
   3. 不要忘记测试，一个看上去正确的程序可能隐含错误。
   4. 在观察无法找出错误时，可以用“输出中间结果”的方法查错。
   5. 在32位的系统中，运算器一次最多可以处理32位的数据，寄存器的最大宽度也是32位的。然后， C语言中对数据宽度的规定是指针变量、long型变量的宽度推荐是处理器一次能够处理的最大宽度，所以就是32位，也就是4个字节。同理，在64位系统中，运算器、寄存器等一次处理的宽度是64位，也就是8个字节，所以指针变量、long型变量等也就都是8个字节了。
2. 近似计算
   计算Π/4=1-1/3+1/5-1/7+...，直到最后一项小于10的负6次方。

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

   do-while语句不常使用。

循环的代价

1. 阶乘之和
   输入n，计算S=1！+2！+3！+...+n！的末6位（不含前导0）。n<=10的6次方。

   #include<stdio.h>
   
   int main()
   {
       int n;
       scanf("%d", &n);
       int six = 0;
       for(int i = 1; i<=n; i++){
           int s = 1;
           for(int j =1; j<=i; j++){
               s = s*j;
           }
           six += s;
       }
       printf("%d", six%1000000);
       return 0;   
   } 
   

   用上面的程序会发现两个问题:
   - 输入100时，会出现负数，乘法溢出了。
   - 输入10的6次方，也会溢出，同时发现太慢了。

   从题目可以知道，他只要最后面的六位，可以在中间结果上每次都取模。

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

   测试几组数据，发现从40开始，答案始终不变，原因是25！的末尾有6个0，所以从第25项开始，后面所有项都不会影响末尾的6位数字，所以可以放弃使用每次都%一下的方法，只需if(n>25 n=25;)

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

1. 数据统计
   输入一些整数，求出它们的最小值、最大值和平均值(保留3位小数)。输入保证这些数都是不超过1000的整数。

   #include<stdio.h>
   
   int main()
   {
       int x, n=0, min, max, s = 0;
       while(scanf("%d", &x) == 1){
           s += x;
           if(x < min){
               min = x;
           } 
           if(x > max){
               max = x;
           }
           n++;
       }
       printf("%d %d %.3f\n", min, max, (double)x/n);
       return 0;   
   }
   

   上面的程序，如何停止输入呢？
   • windows中，输入完毕后按Enter键，再按ctrl+z键，最后再按Enter
   • Linux中，输入完毕后按Ctrl+D键即可结束输入

   #include<stdio.h>
   #define INF 1000000000
   
   int main()
   {
       int x, n=0, s = 0, kase=0;
       while(scanf("%d", &n) == 1 && n){
           int s = 0, 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 %.3f\n", ++kase, min, max, (double)s/n);
       } 
       return 0;   
   }
   

练习

1. 水仙花数
   输出100-999中的所有水仙花数。若3位数ABC满足ABC= A³ + B³ + C³，则称其为水仙花数。例如153=1³+5³+3³，所以153是水仙花数。

   #include<stdio.h>
   #include<math.h>
   
   int main()
   {
       int daffodil;
       for(int i=100; i<=999; i++){
           int unit = i%10;
           int tens = i/10%10;
           int hundreds = i/100;
           bool j = (i == (int)(pow(unit, 3)+pow(tens, 3)+pow(hundreds, 3)));
           if(j){
               printf("%d = %d^3 + %d^3 + %d^3\n", i, hundreds, tens, unit);
           }
       }
   
       return 0;   
   }
   

   这道题没有难度，主要就是熟悉熟悉循环的运用。
2. 韩信点兵

   #include<stdio.h>
   
   int main()
   {
   
       while(true){
           int a, b, c;
           scanf("%d%d%d", &a, &b, &c);
           bool isExist = false;
           int i=0;
           for(i = 10; i<=100; i++){
               if(i%3 == a && i%5 == b && i%7 == c){
                   isExist = true;
                   break;
               }
           }
           if(isExist){
               printf("case: %d\n", i);
           }else{
               printf("case: No answer\n");
           }
       }
   
       return 0;
   }
   

   这道题目说“每次只看排尾”，意思也就是只看余数，这样遍历，一次一次试就可以了，虽然效率不高。
3. 倒三角形

   #include<stdio.h>
   
   int main()
   {
       int n;
       scanf("%d", &n);
       for(int i=1; i<=n; i++){
           // 输出前面的空格 
           for(int j=1; j<i; j++){
               printf(" ");
           }
           // 输出中间的* 
           for(int k=1; k<=1+2*(n-i); k++){
               printf("*");
           }
           // 输出后面的空格 
           for(int j=1; j<i; j++){
               printf(" ");
           }
           printf("\n");
       }
       return 0;
   }
   

4. 子序列的和

   #include<stdio.h>
   #include<math.h>
   
   int main()
   {
       int n, m;
       int sign =0;
       while(scanf("%d%d", &n, &m) == 2){
           if(n == 0 && m == 0){
               break;
           }
           double result;
           result = 0;
           for(double i=n; i<=m; i++){
               result += 1.0/pow(i,2);
           }
           sign++;
           printf("Case %d: %.5f\n", sign, result);
       }
   
       return 0;
   }
   

   scanf 的返回值为输入值的个数。
5. 分数化小数

   #include<stdio.h>
   
   int main()
   {
       int sign = 0;
       int a, b, c;
       while(scanf("%d%d%d", &a, &b, &c) != EOF){
           if(a==0 && b==0 && c==0){
               break;
           }
           double d = 1.0*a/b;
           sign++;
           printf("Case %d: %.*f", sign, c, d);
       
       }   
   
       return 0;
       
   }
   

   注意：%.*f
6. 排列

   #include<stdio.h>
   
   int main()
   {
       for(int i=1; i<=9; i++){
           for(int j=1; j<=9; j++){
               for(int k=1; k<=9; k++){
                   if(i==j || i==k || j==k){
                       continue;
                   }
                   int a = i*100+j*10+k*1;
                   int b = i*200+j*20+k*2;
                   int c = i*300+j*30+k*3;
                   if(a<999 && b<999 && c<999){
                       printf("%d %d %d\n", a, b, c);
                   }
               }
           }
       }
       return 0;
   }  
   

7. 猜猜下面程序的输出内容，一定要运行一遍。

   #include<stdio.h>
   
   int main()
   {
       float i;
       for(i=0; i != 10; i += 0.1){
           printf("%.1f\n", i);
       }
       return 0;
   }
   

   double和float都不能用==来比较。根据浮点数的存储参考IEEE 754浮点数标准
   0.4 ≈ 二进制0.011 001100110011...
   0.3 ≈ 二进制0.0100110011001100...
   0.7 ≈ 二进制0.1011001100110011...
   但是，float只存前几位，两个float想加只有前几位参与操作，损失后面的精度，如果前面的不一样样比较就出现不想等，如果都一样这里就相等，但你换别的数字试试可能也不相等，原因就是精度损失。
   可以把要比较的两个数相减的绝对值与一个较小的数比，例如，fabs(f1-f2)<1e-6