程序设计基础

程序设计基础谌卫军清华大学软件学院2006年秋季第五章1第五章

循环控制2西绪福斯的故事西绪福斯是希腊神话中的人物，他因为触犯了宙斯，死后被打入地狱受惩罚。每天清晨，他都必须将一块沉重的巨石从平地搬到山顶上去。每当他自以为已经搬到山顶时，石头就突然顺着山坡滚下去，于是西绪福斯只好重新回头去搬石头，而石头再滚下山，……，如此循环往复，没有穷尽。3在程序设计中，当我们需要重复地去执行某一段代码时，可使用循环（loop）的方法。一个循环就是一组重复执行的语句。……x=x+1;

sum=sum+x;

scanf(…);……循环体4

for语句

while语句

do-while语句

break语句和continue语句程序举例本章的组织结构55.1for语句如图所示，显示前100个整数的平方和立方。问题描述：111248392741664525125………6问题分析： 笨方法：对这100个整数分别进行计算。printf(“%d%d%d\n”,1,1*1,1*1*1);printf(“%d%d%d\n”,2,2*2,2*2*2);printf(“%d%d%d\n”,3,3*3,3*3*3);printf(“%d%d%d\n”,4,4*4,4*4*4);……共需要100条语句。7问题分析： 需要对这个问题进行抽象，归纳为一种统一的形式，然后采用循环语句来重复地执行一定的次数。 对于1－100当中的每一个整数x，其平方为：x*x，其立方为：x*x*x，可以采用for语句来重复地执行100次，每一次处理一个整数。8

for(表达式1；表达式2；表达式3)

{

语句块；}一般形式：（1）先求解表达式1（循环变量赋初值）；

（2）求解表达式2（循环条件测试），若其值为非0（真），则

执行内嵌的语句块，然后转（3）；若其值为0（假），则

结束循环，执行for语句后面的一个语句；

（3）求解表达式3（循环变量增值）；

（4）转（2），继续执行；执行过程：真假结束循环各部分最少被执行几次？9

//显示前100个整数的平方和立方

#include<stdio.h>voidmain()

{

inti;for(i=1;i<=100;i++)

{printf(“%d%d%d\n”,i,i*i,i*i*i);}

}循环变量10111248392741664525125636216749343864512981729101001000111211331运行结果：11

//显示前100个整数的平方和立方

#include<stdio.h>voidmain()

{

inti;for(i=1;i<=100;i++)

{printf(“%3d%5d%7d\n”,i,i*i,i*i*i);}

}12

111248392741664525125636216749343864512981729101001000111211331新的结果：13（一）对于for语句的一般形式中的“表达式1”，(1) 它可以被省略，此时应在for语句之前给循环变量赋初值。当它被省略时，其后的分号不能省略；

例如：for(;i<=100;i++)sum=sum+i;(2) 它可以是设置循环变量初值的赋值表达式，也可以是与循环变量无关的其他表达式。

例如：for(sum=0;i<=100;i++)sum=sum+i;(3) 它可以是一个简单的表达式，也可以是逗号表达式，即包含多个简单表达式，中间用逗号隔开。

如：for(sum=0,i=1;i<=100;i++)sum=sum+i;几点说明14（二）对于for语句的一般形式中的“表达式2”，(1) 它可以被省略，即不判断循环条件，循环无终止地进行下去。也就是认为表达式2的值始终为真。此时程序设计者应另外设法保证循环能正常结束；

例如：for(i=1;;i++)sum=sum+i;(2) 它一般是关系表达式（如i<=100）或逻辑表达式（如(a<b)&&(x<y)），但也可以是数值表达式或字符表达式，只要其值为非零，就执行循环体。

例如：for(i=0;(c=getchar())!=‘\n’;i+=c);15（三）对于for语句的一般形式中的“表达式3”，(1) 它也可以被省略，即没有循环变量增值，此时程序设计者也应能保证循环能正常结束；

例如：for(i=1;i<=100;){sum=sum+i;i++;}(2) 与表达式1一样，它可以是一个简单的表达式，也可以是逗号表达式。

例如：for(i=0,j=100;i<=j;i++,j--)k=i+j;(3) 它一般是作为循环变量增值，但也可以是对循环变量进行减值，而且每一步不一定非要加1或减1，也可以是其他的常量。16高斯的难题德国数学家高斯，在上小学的时候，老师出了一道难题，计算1+2+3+……+100，高斯很快就在自己的小石板上写出了答案5050，老师非常惊讶，高斯怎么算得这么快呢？原来，高斯不是一个数一个数按部就班地加起出来的，而是发现这些数字有一个规律，一头一尾依次两个数相加，它们的和都是一样的：1+100=101，2+99=101，一直到50+51=101，一共是50个101，所以，他很快就把答案算出来了。17基本思路： 把问题抽象为一种统一的形式，然后采用循环语句来重复地计算。 用一个变量sum来保存总和，对于1、2、3、…、100中的每一个整数i，依次把它加入到sum当中，即sum=sum+i。18#include<stdio.h>

voidmain()

{

inti,sum;

sum=0;

for(i=1;i<=100;i++)

{

sum=sum+i;

}

printf(“sum=%d”,sum);

}sum0i=11i=235050i=100……19将原来的for(i=1;i<=100;i++)

修改为for(i=1;i<=100;i=i+2)

问：这是在计算哪些整数的和，答案是多少?

将原来的for(i=1;i<=100;i++)

修改为for(i=1;i<=100000;i++)

问：程序执行后能够得出正确结果吗？如果

不能，自己想办法解决。思考题：在程序中做如下的修改205.2while语句问题描述：显示前若干个整数的平方和立方，只要其立方值

小于10000。111248392741664525125………21问题分析： 与for语句的例子有些类似，但不完全相同。前者指定了需要处理的整数个数，而这里是要求最大的那个整数，其立方必须小于某个固定的值。 循环体内的语句无须变化，完成的是相同的功能。区别在于循环结束条件的判定。可以用while语句来完成。22

while(表达式){

语句块；}一般形式：先判断表达式，如果表达式的值为非0

（真），那么执行while语句中的内嵌语句

块，然后又回到表达式的判断；如果表达式

的值为0（假），那么结束循环。执行过程：假结束循环真各部分最少被执行几次？23

//显示前若干个整数的平方和立方，只要其立方值

//小于10000。

#include<stdio.h>voidmain()

{

inti;

while(i*i*i<10000)

{

printf(“%3d%5d%7d\n”,i,i*i,i*i*i);

}

}i=1;i++;24

//显示前若干个整数的平方和立方，只要其立方值

//小于10000。

#include<stdio.h>voidmain()

{

inti;for(i=1;i*i*i<10000;i++)

{

printf(“%3d%5d%7d\n”,i,i*i,i*i*i);

}

}25脆弱的输入方式charchoice;

printf("你是否想借书?(y/n)");scanf("%c",&choice);

……如果用户输入的是y/n以外的字符呢？26健壮的输入方式charchoice;printf("你是否想借书?(y/n)");

scanf("%c",&choice);

while(choice!='y'&&choice!='n')

{

printf("你是否想借书?(y/n)");

scanf("%c",&choice);

}

……275.3do-while语句do

{

语句块；}

while(表达式)一般形式：先执行一次循环体语句，然后判别表达式，如果

表达式的值为非0（真），那么返回去重新执行循环

体语句；如果表达式的值为0（假），那么结束循环。执行过程：真假结束循环28健壮的输入方式(do-while)charchoice;do

{printf("你是否想借书?(y/n)");

scanf("%c",&choice);}while(choice!='y'&&choice!='n');

……295.4break和continue语句break语句的功能：用来跳出switch结构；用来从循环体内跳出循环体，即提前结束循环，接着执行循环下面的语句。一般形式为：break;30健壮的输入方式(whileagain)charchoice;while(1)

{

printf("你是否想借书?(y/n)");

scanf("%c",&choice);

if(

choice=='y'||choice=='n')break;

}

……31输入一组整数，当输入–1时表示输入结束，

然后计算这组整数的平均值；问题描述：12425125–1计算输入数据的平均值讨论32voidmain()

{

intValue,TotalValue,Num;printf(“本程序用于计算一组整数的平均值\n”);

printf(“输入-1表示数据的结束。\n”);

TotalValue=0;

Num=0;

while(1)

{

scanf(“%d”,&Value);

if(Value==-1)break;

TotalValue+=Value;

Num++;

}

if(Num>0)

printf(“平均值是：%.1f”,(double)TotalValue/Num);

}累加模式33while(…)

{….while(…)

{……

break;}……

}

…...跳出最近的循环。34while(…)

{

….

while(…)

{

……

continue;

……

}

……

}结束本次循环，即跳过循环体中尚未执行的语句，直接

回到循环条件的判别。continue语句355.5程序举例5.5.1计算7！问题描述： 计算7！。在数学当中，N！的定义为：

N！＝N×(N–1)×(N–2)×…×2×1，因此，我们可以把7！展开为：

7！＝7×6×5×4×3×2×1，我们的目标即计算这7个整数之积。36思路分析：从程序的扩展性和通用性来看，不宜采用算术表达式的方法；本题涉及到多个连续的整数的相乘（具有明显的规律性和一致性），因此可以考虑采用循环语句的方法；循环语句的关键在于循环控制条件和循环体语句的设计；循环控制条件的设计：可令整型变量i去表示7、6、5、…、1，初始值为7或1，然后依次递减或递增，直到遍历所有整数；37思路分析（续）：循环体语句的设计：让整型变量sum来表示乘积，其初值为1。对于每一个当前的整数i,将其乘以sum，再将乘积保存在sum中，即

sum=sum*i

当循环结束后，sum中的值即为所求；在设计好循环控制条件和循环体语句之后，可以根据方便与否和个人的喜好，采用任意一种循环语句（for语句、while语句或do-while语句）来编程，因为它们在功能上是

等价的。38

初始时sum=1，i=1

…

7×6×5×4×3×2×1sum=1*1=1isum=sum*isum=1*2=2sum=2*3=6sum=720*7=504039//计算7！

#include<stdio.h>voidmain()

{

inti=1,sum=1;for(i=1;i<=7;i++)

{

sum=sum*i;

}

printf(“7!=%d”,sum);

}用for语句来实现//计算7！

#include<stdio.h>voidmain()

{

inti=1,sum=1;

while(i<=7)

{

sum=sum*i;

i++;

}

printf(“7!=%d”,sum);

}用while语句来实现累积405.5.2求π的近似值例.求π的近似值

用变量pi表示π的值。

令 表示括号中的每个项当最后一项的绝对值小于等于时，忽略掉以后的项思考2分钟41思路分析：显然不是一个简单的算术表达式，而必须采用循环语句的方法；循环控制条件的设计：题目已指明，当最后一项的绝对值小于等于10-6时，循环结束；循环体语句的设计：需要计算每一项的值，并把它们累加起来，难点在于如何来确定

a和b的值，其中a为1、3、5、7、…，它是一个公差为2的等差数列，即ak+1=ak+2，初始值为1；b为一个符号位，其值在+1和-1之间来回变化，即bk+1=–1*bk，初值为1。42voidmain()

{

intnum=0; //总项数

doublepi=0,a=1.0,b=1.0,c=1.0;//a为分母,b为分子

while(fabs(c)>1e-6)

{

pi=pi+c; //累加每一项

num=num+1; //总项数加1

a=a+2.0; //计算下一项的分母

b=-b; //分子变正负号

c=b/a; //计算下一项

}pi=4.0*pi;

printf("pi=%.6f\n",pi);

printf("num=%d\n",num);

}43运行结果：

pi=3.141591，num=500000循环控制条件不同，则得到的精度不同：将1e-6变为1e-7：pi=3.141592，num=5000000将1e-6变为1e-5：pi=3.141573，num=50000将1e-6变为1e-4：pi=3.141393，num=5000445.5.3求两个整数的最小公倍数问题分析：假设这两个整数为x,y，且x>y，令它们的最小公倍数为z。z一定会大于或等于x；z=kx,k=1,2,…；z一定会被y整除。45基本思路：令k=1,2,3,4,…，则kx＝x,2x,3x,4x,…，即以x为公差的等差数列，那么z即为该数列当中能被y整除的最小整数。因此，我们可以用循环语句来寻找该数。46第一步z=x=5 5%3!=0不能整除第二步z=2x=10 10%3!=0不能整除第三步z=3x=15 15%3==0 能整除找到了z，15就是5和3的最小公倍数举例来说：

x=5,y=3.47

intx,y,z,temp,k;printf("请输入两个整数，用空格隔开：");

scanf("%d%d",&x,&y);

if(x<y)

{

temp=x;x=y;y=temp;//x=y;y=x;?

}

for(k=1;;k++)

{

z=k*x;

if(z%y==0)break;

}

printf("最小公倍数为：%d\n",z);实现方法之一48

intx,y,z,temp;printf("请输入两个整数，用空格隔开：");

scanf("%d%d",&x,&y);

if(x<y) //让x表示两者中的大数

{

temp=x;x=y;y=temp;

}

z=x;

while(z%y!=0) //当z不能被y整除时，就让z累加x

{

z=z+x;

}

printf("最小公倍数为：%d\n",z);实现方法之二49思考题：在程序当中为什么先要把x设定为两者之中的大数，若不这么做，程序是否正确？如果不正确，为什么？如果正确，那么这两种做法有何区别？505.5.4显示二维图形问题描述： 在屏幕上显示下列二维图形。******************51******************问题分析：假设有m行n列，对于每一行来说，都需要连续画n个*，似乎用一重循环已经无法满足题目要求，需要在循环里面再嵌套一层循环，即多重循环。52重复m遍做以下的事情{

重复n遍做以下的事情

{

打印一个*号

}

换到下一行；}基本思路：53intm=3,n=6,i,j; for(i=1;i<=m;i++) //外循环，打印3行{for(j=1;j<=n;j++) //内循环，打印1行

{

printf(“*”);}printf(“\n”); //换行}嵌套的循环54问题描述： 在屏幕上显示下列二维图形。***************另一个二维图形有何规律？55introw=5,i,j; for(i=1;i<=row;i++) //外循环，打印5行{for(j=1;j<=i;j++) //内循环，每行i个*

{

printf(“*”);}printf(“\n”); //换行}56问题描述： 在屏幕上显示下列二维图形。***************再一个二维图形对于第i行，先打印(i–1)个空格；再打印(5–i+1)个星号。57introw=5,i,j; for(i=1;i<=row;i++) //外循环，打印5行{for(j=1;j<=i–1;j++)//打印i-1个空格

{

printf(“”);}

for(j=i;j<=row;j++)//打印row–i+1个*

{printf(“*”);}printf(“\n”); //换行}58for(j=1;j<=i–1;j++)printf(“”);//打印i-1个空格for(j=i;j<=row;j++)printf(“*”);//打印row–i+1个*i=1(第一行)：for(j=1;j<=0;j++)printf(“”);//0个空格for(j=1;j<=row;j++)printf(“*”);//5个星号i=2(第二行)：for(j=1;j<=1;j++)printf(“”);//1个空格for(j=2;j<=row;j++)printf(“*”);//4个星号i=5(第五行)：for(j=1;j<=4;j++)printf(“”);//4个空格for(j=5;j<=row;j++)printf(“*”);//1个星号……595.5.5谁做的好事？清华附中有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。

A说：不是我。

B说：是C。

C说：是D。

D说：他胡说。已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。问题描述：注：这个例子和本课程的其他一些例子，来自于吴文虎老师的讲义，在此表示感谢。60下面，我们把四个人说的四句话写成关系表达

式。在声明变量时，让thisman表示要找的人，

定义他为字符型变量。charthisman;让“==”的含义为“是”让“!=”的含义为“不是”61A说：不是我。写成关系表达式为（thisman!=‘A’）B说：是C。写成关系表达式为（thisman=

=‘C’）C说：是D。写成关系表达式为（thisman=

=‘D’）D说：他胡说。写成关系表达式为（thisman!=‘D’）相应字符的ASCII码值为：字符 ‘A’ ‘B’‘C’‘D’ASCII码值6566 676862显然，不是'A'做的好事（四个关系表达式值的和为1）思路分析(1)：如何找到该人，一定是“先假设某人是做好事者，

然后到每句话中去测试看有几句是真话”。“有三句

是真话就确定是该人，否则换下一人再试”。比如，

先假定是A同学，让thisman=‘A’，代入到四句话中：A说：thisman!='A'; 'A'!='A' 假，值为0。

B说：thisman=='C'; 'A'=='C' 假，值为0。

C说：thisman=='D'; 'A'=='D' 假，值为0。

D说：thisman!='D'; 'A'!='D' 真，值为1。63思路分析(2)：显然，不是‘B’所为（四个关系表达式值的和为2）再试B同学，让thisman=‘B’；代入到四句话中A说：thisman!=‘A’; ‘B’!=‘A’ 真，值为1。

B说：thisman==‘C’; ‘B’==‘C’ 假，值为0。

C说：thisman==‘D’; ‘B’==‘D’ 假，值为0。

D说：thisman!=‘D’;‘B’!=‘D’真，值为1。64再试C同学，让thisman=‘C’；代入到四句话中A说：thisman!=‘A’; ‘C’!=‘A’ 真，值为1。

B说：thisman==‘C’; ‘C’==‘C’ 真，值为1。

C说：thisman==‘D’; ‘C’==‘D’ 假，值为0。

D说：thisman!=‘D’;‘C’!=‘D’真，值为1。显然，就是‘C’做了好事（四个关系表达式值的和

为3），这时，我们可以理出头绪，要用所谓的枚

举法，一个人一个人地去试，四句话中有三句为

真，该人即为所求。思路分析(3)：65//thisman分别赋值为'A','B','C','D'for(thisman='A';thisman<='D';thisman++)

{

sum=(thisman!='A') //A的话是否为真

+(thisman=='C') //B的话是否为真

+(thisman=='D') //C的话是否为真

+(thisman!='D'); //D的话是否为真

if(sum==3)

{

printf(“Thismanis%c\n”,thisman);

break;

}

}从编写程序的角度看，实现枚举最好用循环结构。665.5.6案件分析问题描述：某地刑侦大队涉及六个嫌疑人的一桩疑案进行分析：

A、B至少有一人参与该案件；

A、D不可能是同案犯；

A、E、F三人中有两人参与该案件；

B、C或同时参与，或与本案无关；

C、D中有且仅有一人参与该案件；如果D没有参与该案件，则E也不可能参与。试编写一程序，将犯罪嫌疑人找出来。67思路分析(1)：显然这是或的关系，因此有

CC1=(A||B)将案情的每一条线索写成逻辑表达式，第一条用

CC1表示，第二条用CC2表示，……A B CC10 0 0

1 0 1

0 1 1

1 1 1CC1:

A、B至少有一人参与该案件令变量A表示A是否参与该案件，A＝{0,1}；

变量B表示B是否参与该案件，B＝{0,1}；68思路分析(2)：A D CC20 0 1

1 0 1

0 1 1

1 1 0CC2:

A、D不可能是同案犯

A是案犯，D不是案犯，写成A&&(!D)D是案犯，A不是案犯，写成D&&(!A)A、D都不是案犯，写成(!A)&&(!D)这三者是或的关系，因此有：

CC2＝(A&&(!D))||(D&&(!A))

||((!A)&&(!D))

等价于：CC2＝!(A&&D)＝(!A||!D)69思路分析(3)：CC3:

A、E、F三人中有两人参与该案件。分析有三

种可能：第一种，A和E参与，F不参与，写成A&&E&&(!F)

第二种，A和F参与，E不参与，写成A&&F&&(!E)

第三种，E和F参与，A不参与，写成E&&F&&(!A)这三者是或的关系，因此有：CC3＝(A&&E&&(!F))

||(A&&F&&(!E))

||(E&&F&&(!A))70AEFA&&E&&(!F)A&&F&&(!E)E&&F&&(!A)CC311100001101001101010101100110010000010000010000000000000CC3的真值表71思路分析(4)：CC4:

B、C或同时参与，或与本案无关，分析有两种

可能：第一种，同时参与，写成B&&C

第二种，都与本案无关，写成!B&&!C这两者是或的关系，因此有：

CC4＝(B&&C)||(!B&&!C)CC5:

C、D中有且仅有一人参与该案件，可分析为；CC5＝(C&&!D)||(D&&!C)72思路分析(5)：CC6:如果D没有参与该案件，则E也不可能参与。这是一种蕴涵关系，可写成：

!D!E蕴涵关系的规律是PQ等价于!P||Q，因此上式等价于：

CC6＝D||!E以上是案情分析，已经化成了计算机可解的逻辑

表达式。73枚举组合！6个人每个人都有作案或不作案两种可能，因此有26种组合，从这些组合中挑出符合6条分析的作案者。

定义6个整数变量，A，B，C，D，E，F，分别表示6个人。枚举每个人的可能性{0，1}

让0表示不是罪犯；让1表示就是罪犯。采取枚举方法，枚举什么呢？74for(A=0;A<=1;A++)

for(B=0;B<=1;B++)

for(C=0;C<=1;C++)

for(D=0;D<=1;D++)

for(E=0;E<=1;E++)

for(F=0;F<=1;F++)

{

CC1=A||B;

CC2=!A||!D;

CC3=(A&&E&&!F)||(A&&F&&!E)

||(E&&F&&!A);

CC4=(B&&C)||(!B&&!C);

CC5=(C&&!D)||(D&&!C);

CC6=D||!E;

if(CC1+CC2+CC3+CC4+CC5+CC6==6)

{

printf("犯罪嫌疑人是：%c%c%c%c%c%c\n",

A?'A':'',B?'B':'',C?'C':'',

D?'D':'',E?'E':'',F?'F':'');

}

}75犯罪嫌疑人是：ABCF

A、B至少有一人参与该案件；

A、D不可能是同案犯；

A、E、F三人中有两人参与该案件；

B、C或同时参与，或与本案无关；

C、D中有且仅有一人参与该案件；如果D没有参与该案件，则E也不可能参与。765.5.7求质数问题描述：求100以内的所有质数。问题分析：（1）对100以内的每一个整数，判断其是否为质数；（2）判断整数m是否为质数的方法：让m被2到除，如果m能被其中的任何一个整数整除，则说明它不是一个质数；否则的话，说明它是一个质数。77inti,j,sq,num;num=0;

for(i=2;i<=100;i++)

{

sq=(int)sqrt(i);

for(j=2;j<=sq;j++)

{

if(i%j==0)break;

}

if(j>sq)

{

printf("%2d",i);

num++;

if(num%10==0)printf("\n");

}

}78

2357111317192329313741434753596167717379838997795.5.8猜数游戏问题描述：猜数游戏。计算机随机地选择一个在0－999之间的整数，然后让人来猜。如果猜测的数字大于实际的数字，就提示说太大了；否则就提示说太小了。总共只给10次机会。80

随机数说明：1、要产生随机数需要在程序开头加入头文件

#include<s