第四章 循环算法总结.doc

第四章 循环
主要语法： while语句，for语句，do while语句，以及break与continue，具体语法看书或者课件
主要思想：能循环执行的东西一定是重复的东西，所以重要的是找出步骤当中重复的地方

例如 打印出一行 ***** ，则可以看成是重复打印*号五次，则重复的地方就在于打印*号，重复五次如何实现呢？基本思想是用一个变量控制，从一数到五则表示五次
i=1;
while(i<=5)
{ printf("*");
i++;
}
或者用
for(i=1;i<=5;i++)
printf("*");

注意的地方:while 以及for语句 执行循环体的时候默认只有一个语句，如果想让多句语句循环执行，则必须加｛｝变成复合语句
本章主要算法：
1.迭代算法
1. 累加题目：
u s=1+2+3+…..+100
可以看成是 +1
+2
+3
+……
+100
所以重复的地方在于每次加上一个数，那每次加的数不一样我们可以用一个变量来表示，比如说i，则每次的动作就可以总结为+i，但是每次加完要去改变i的值，即i要自加1，至于累加则用累加器：sum=sum+
则每次的动作可以总结为 sum=sum+i;一共累加100次
则程序可以表达为
sum=0;
for(i=1;i<=100;i++)
sum=sum+i;
所以循环注意的三个地方：
a) 循环体也就是重复的地方是什么
b) 重复的次数也就是循环终止的条件
c) 循环的初始值

u s=2+22+222+2222+….
这道题目是上道题目的延伸，也是每次加上一个数，每次加的数不一样我们也可以用一个变量例如t来表示，则每次的累加可以表示为 sum=sum+t; 如果要累加n项，那么就是循环n次， 那么如果t=2，那下次要想再用t的变量来表示加上22，则它们之间的关系应该是t=t*10+2;所以循环里面要做的重复的事情是 每次进行累加，即 sum=sum+t; 累加完还要为下一次累加做准备，即是 t=t*10+2
sum=0;t=2
for(i=1;i<=n;i++)
{ sum=sum+t;
t=t*10+2;
}
循环的初始值可以把第一次循环代进去得到，程序写完必须把第一次循环以及第二次循环跟最后一次循环执行一遍，看对不对。
u s=1+2!+3!+4!+….+n!
此道题目也是累加，则也是sum=sum+t，那么每次累加的值不一样，则可以用t=t*i来表示，累加n项则是循环n遍
Sum=0;t=1;
for(i=1;i<=n;i++)
{sum=sum+t;
t=t*(i+1);
}
这道题目要注意的地方，t跟i有关系，所以如果是先累加再计算下一项的话，应该是t=t*(i+1);因为比如i=1时，要算的下一项是1*2，所以应该是t*2，也就是t*（i+1）；所以当循环变量i与里面的累加项还有关系的时候要注意与i的关系，这个程序也可以改为
Sum=0;t=1;
for(i=1;i<=n;i++)
{ t=t*i；
sum=sum+t;}
自己考虑下两个程序的差别，语句的顺序不一样所带来的影响。

u s=1+x/1-x2/2!+x3/3!-…..xn/n!
前后两项之间的关系是 t=t*(-1)*x/i;
sum=1;t=-1;
for(i=1;i<=n;i++)
{ t=t*(-1)*x/i
sum=sum+t;
}
或者
sum=1;t=x；
for(i=1;i<=n;i++)
{ sum=sum+t;
t=t*(-1)*x/（i+1）
}
2. 猴子吃桃P129 6.10
猴子第一天摘下若干个桃子，当即吃了一半，又多吃了一个。以后每天早晨猴子都吃掉前一天剩下的一半多一个。到第10天，猴子再去吃桃子时发现只剩下1个桃子。问第一天猴子摘了多少个桃子？

分析题目可以发现如果后一天是n个，那么前一天将是（n+1）*2
所以已知第十天是1个，则可以根据规则算出第九天到第一天的数
n=1
for(i=9;i>=1;i++)
n=(n+1)*2;
3. 整数逆序输出 ：输入1234输出4321
要想逆序输出，则分析这道题目的算法，找出重复的地方：
1234%10 输出4
123%10 输出3
12%10 输出2
1%10 输出1
则重复的地方在于 %10，每次被除的数不一样，可以用变量例如x来代替，那么前后两项之间的关系则是 x=x/10;

while(x!=0)
{printf(“%d”,x%10);
x=x/10
}
当x是个位数的时候应该是最后一次输出，那么输出之后还要执行x=x/10,所以x将会变成0停止循环，则循环的条件应该是x！=0
4. 辗转相除法求最大公约数和最小公倍数
main()
{ int p,r,n,m,t;
scanf("%d,%d",&n,&m);
if(n<m)
{ t=n;n=m;m=t;} /*将n,m两个数中大的数放在n，小的数放在m*/
p=m*n; /*保留m*n的值*/
while(m!=0)
{ r=n%m; n=m; m=r;} /*求出最大公约数，放在变量n*/
printf("最大公约数:%d\n",n);
printf(“最小公倍数:%d\n”,p/n); /*最小公倍数＝两个数的积/最大公约数*/
}

2.求特殊数

Ø 水仙花数 P129 习题6.6
所有的三位数，则应该从100判断到999，每个数判断过去，每个数都是取出它的个、十、百位数，然后判断是否立方和等于本身
For(i=100;i<=999;i++)
{a=i/100; /*百位*/
b=i%100/10 /*十位*/
c=i%10 /*个位*/
if(a*a*a+b*b*b+c*c*c==i) printf(“%d”,i) /*说明是水仙花数，则输出*/
}
Ø 素数 P126 例题6.8
素数，指的是只能被1或者自身整除的数，判断是否素数，也就是如果在2到n-1之间找到一个数能被整除，那么这个数将不是素数，也就是从2一直判断到n-1，看能否被整除,如果中间有一个数能被整除，那么可以跳出循环，那么跳出来后我们判断i的值是多少，如果是i<=n-1,那么说明是从break那里强制跳出，说明有一个数满足m%i = =0，则说明不是素数
for(i=2;i<=n-1;i++)
{ if(m%i= =0) break;
}
if(i<=n-1) printf(“是素数”)
esle printf(“不是素数”)

Ø 完数 P129 习题6.7
1000以内的则应该从1判断到999,for(i=1;i<=999;i++),
For(i=1;i<=999;i++)
{
Sum=0;
For(j=1;j<i;j++)
If(i%j= =0) sum=sum+j; /* 对于每一个i判断只要能被i整除的都是它的因子，则把因子累加*/
If(sum= =i) printf(“%d”,i);/* 如果所有因子的累加和等于自身，则是说明是完数，则输出*/
}
3. 循环嵌套
首先理解下列程序

打印三行 *****
*****
*****
一共打印三行，每行都是打印出五个*号，然后再打印一个换行符
For(i=1;i<=3;i++)
{
printf(“*****”);
printf(“\n”);
}

其中打印五个*号也可以用循环来做，即重复打印五个*号，则程序可以改为

for(i=1;i<=3;i++) /*外层循环*/
{
for(j=1;j<=5;j++)/*内层循环*/
printf(“*”);
printf(“\n”);
}
则对于每一次i的外层循环来说，j都从1循环到5，也就是每一次外层循环，内层循环都循环五次，也就是说printf(“*”);这条语句一共执行了5*3 ，15次；

3. 如何打印
*
***
*****
*******

一共四行，则外层循环控制行数 for(i=1;i<=4;i++)｛｝花括号里面代表每一行怎么打的。
对于每一行都是怎么实现的呢?应该这样分析：每一行都是先打出空格，再打印*号，再打印换行符，那么空格的个数是随着行数的增加而减少的，则跟行数的i的关系应该是-i，而*号是随着行数的增加而增加的，而且行数增加1，*号的个数是增加2，所以与i的关系应该是+2*i,先把跟i的关系写出来，其中还有的常量将第一行代进去，即可以得到，例如，第一行时候i=1，那么空格数应该是三个，所以应该是j从1开始，到3结束，所以应该是4-1才是3，所以就是4-i，其他类推。

for(i=1;i<=4;i++)
｛
for(j=1;j<=4-i;j++)
printf(“ ”);
for(k=1;k<=2*i-1;k++)
printf(“*”);
printf(“\n”);
｝
4. 穷举法

例：百钱买百鸡.公鸡5元一只,母鸡3元一只,小鸡1元三只;一百元买一百只鸡,且公鸡,母鸡,小鸡都要有.有几种买法?将所有公鸡和母鸡还有小鸡的组合都尝试过去。

三重循环，对于每一次i的循环，j都从1循环到33，对于每一次i与j，k都从3循环到100，也就是把所有的公鸡。母鸡、小鸡的组合都组合过去了，最后判断如果同时满足鸡的数量是100只，钱的数量是100块，则说明这种组合是正确的。
main()
{ int i,j,k,n=0;
for(i=1;i<=19;i++)
for(j=1;j<=33;j++)
for(k=3;k<=100;k+=3)
{
if(i+j+k= =100&& i*5+j*3+k/3= =100)
{n++;
printf(“i=%d,j=%d,k=%d\n”,i,j,k);}
}
printf(“\n n=%d”,n);
}
二重循环：
main()
{ int i,j,k,n=0;
for(i=1;i<=19;i++)
for(j=1;j<=(100-5*i)/3;j++)
{ k=100-5*i-3*j;
if(i+j+3*k==100)
{n++;
printf(“i=%d,j=%d,k=%d\n”,i,j,3*k);}
}
printf(“\n n=%d”,n);
}
以上题目是典型代表，具体还是应该多看看第六章的课件，然后结合上机练习，所有的程序都应该先弄懂它的算法，然后把程序按照自己的思路上机实践一遍，如果只是看的话那么一切都是空的，重在实践，即程序把它弄懂之后应该独立的把程序自己写一遍，然后上机实现看看是否是对的，这样才能充分的理解！！

练习与答案
1. 用循环实现1+2+3+……+1000，要求用while，do while ，for语句分别实现

main()
{
long i,sum=0;
for(i=1;i<=1000;i++)
sum=sum+i;
printf("%ld",sum);

}

main()
{
long i=1,sum=0;
while(i<=1000)
{sum=sum+i;
i++;
}
printf("%ld",sum);

}

2. 思考如何实现1+3+5+……+999
main()
{
long i,sum=0;
for(i=1;i<=999;i=i+2)
sum=sum+i;
printf("%ld",sum);

}

3计算s=1+2!+3!+4!+……n! （测试数据，如果输入n=5，sum应该等于153）

main()
{
long n,i,sum=0,t=1;
scanf("%ld",&n);
for(i=1;i<=n;i++)
{ t=t*i;
sum=sum+t;
}
printf("%ld",sum);}
4.计算s=1+x/1!-x2/2!+x3/3!-x4/4!……xn/n! （测试数据，如果给x赋值5，n赋值5，则结果应该为14.33333）
main()
{
long n,i,x,sum=1,t=-1;
scanf("%ld%ld",&n,&x);
for(i=1;i<=n;i++)
{ t=t*(-1)*x/i;
sum=sum+t;
}
printf("%ld",sum);
}
5.甲每天买苹果，每个苹果五毛钱，第一天买2个苹果，第二天买了第一天的两倍少一个，以此类推，问第n天买了多少个苹果，要花多少钱
（测试数据：n=8，结果是129个苹果，花了64.5块钱）
main()
{
long t;int n,i;
scanf("%d",&n);
for(i=2;i<=n;i++)
t=t*2-1;
printf("%ld",t);
}

6.输入一个整数，要求逆序输出该数，并求出它们的和
（测试数据输入1234，能输出4321，并输出sum=10）
main()
{ int x;
scanf(“%d”,&x);
while(x!=0)
{printf(“%d”,x%10);
x=x/10;
}

7. 在屏幕上输出以下图形：

*
***
*****
*******
*****
***
*

main()
{ int i,j,k;
for(i=1;i<=4;i++)
｛
for(j=1;j<=4-i;j++)
printf(“ ”);
for(k=1;k<=2*i-1;k++)
printf(“*”);
printf(“\n”);
｝
for(i=1;i<=3;i++)
{
for(j=1;j<=i;j++)
printf(" ");
for(k=1;k<=7-2*i;k++)
printf("*");
printf("\n");
}
}

8：百钱买百鸡.公鸡5元一只,母鸡3元一只,小鸡1元三只;一百元买一百只鸡,且公鸡,母鸡,小鸡都要有.有几种买法?并输出对应的公鸡，母鸡和小鸡数
(正确答案：三种买法)
main()
{ int i,j,k,n=0;
for(i=1;i<=19;i++)
for(j=1;j<=(100-5*i)/3;j++)
{ k=100-5*i-3*j;
if(i+j+3*k==100)
{n++;
printf(“i=%d,j=%d,k=%d\n”,i,j,3*k);}
}
printf(“\n n=%d”,n);
}