5.3 典型程序设计案例
5.3 典型程序设计案例
案例5.7 素数
【项目任务】
判断m是否为素数。
【设计思路】
素数是除1和它本身之外不能被其他任何整数整除的正整数。判断一个数m是否为素数的基本思想是：用2～m-1之间的数依次除m，只要有一个数能将m整除，m就不是素数。但实际上，只要在2～ 
（或2～m/2）之间的任何数不能将m整除即可完成判断，这样可以减少工作量。
【程序代码】
#include <stdio.h>
#include <math.h>
main()
{
int m,i,k;
printf("\nPlease input a integer:");
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0) break;
if(i>k) printf("%d is a prime number!\n",m);
/*该处的条件刚好和上面的for语句的循环条件相反*/
else printf("%d is not a prime number!\n",m);
}
【运行结果】
Please input a integer:18
18 is not a prime number!
【知识拓展】
根据以上程序代码，编写能够输出100～200之间的所有素数的程序代码。
案例5.8 最大公约数
【项目任务】
求两个正整数的最大公约数。
【设计思路】
用辗转相除法设计程序。要求出u，v两个正整数的最大公约数，只要求出r，v两个正整数的最大公约数即可，其中r是u除以v的的余数。依此类推，直至余数r为0，v即为u和v两个正整数的最大公约数。
【程序代码】
#include <stdio.h>
main()
{
int u,v,r;
printf("Please input two integers:");
scanf("%d,%d",&u,&v);
while(v!=0)
{
r=u%v;
u=v;
v=r;
}
printf("%d\n",u);
}
【运行结果】
Please input two integers:36,8
4
【知识拓展】
除了使用辗转相除法外，也可以采用其他方法，例如逆归法更相减损法等，有兴趣的读者可参考相关书箱。
比较下面的程序跟上面的程序的差异。
#include <stdio.h>
main()
{
int u,v,r;
printf("Please input two integers:");
scanf("%d,%d",&u,&v);
for(i=u<v?u:v;i>=2;i--)
if(u%i==0 && v%i==0) break;
printf("%d\n",i);
}
编写代码实现以下功能：
（1）两个正整数的最小公倍数。
（2）求三个正整数的最大公约数。
案例5.9 完全数
【项目任务】
如果一个数恰好等于它的因子之和，这个数就是完全数，简称完数。例如，28的因子为1、2、4、7、14，而1+2+4+7+14=28，所以28是一个完数。找出10000之内（不包括10000）的所有完数。
【设计思路】
对指定区间中的每一个整数m实施穷举判别。根据完数的定义，为了判断整数m是否为完数，可以用试商法找出m的所有小于m的因数i，显然1<=i<=m-1。注意：1是任何整数的因数。
【程序代码】
#include <stdio.h>
main()
{
int m,i,s;
for(m=1;m<10000;m++)
{
s=0;
for(i=1;i<m;i++)
if(m%i==0) s+=i;
if(m==s)
{
printf("%d=1",m,t);
for(i=2;i<m;i++)
if(m%i==0) printf("+%d",i);
printf("\n");
}
}
}
【运行结果】
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
8128=1+2+4+8+16+32+64+127+254+508+1016+2032+4064
【知识拓展】
程序中的第一个for循环语句用来对10000以内的整数进行逐个验证，内嵌的循环体的作用是找出某个整数的所有因子，并把这些因子相加，最后把相加和与该数本身进行比较。如果两者相等，输出这个完数；否则，继续验证下一个数，直到10000为止。思考：如果将内嵌的第一个for语句改写成如下形式，将对结果产生什么影响。
s=1;
for(i=2;i<m;i++)
if(m%i==0) s += i;
案例5.10 水仙花数
【项目任务】
打印所有水仙花数。所谓水仙花数是指一个三位数，其各位数字的立方和等于该数本身。
【设计思路】
首先将一个三位数分离成三个数字，然后将这三个数字的立方和与原三位数进行比较，如果符合水仙花数的特征，则对该数进行输出；否则，继续计算下一个数，直到999。
【程序代码】
#include <stdio.h>
main()
{
int i,j,k;
int num;
printf("'Water Flower' number is:\n");
for(num=100;num<1000;num++) /*循环语句，每次循环num都自加1*/
{
i=num/100%10; /*求出num这个3位数的百位*/
j=num/10%10; /*求出num这个3位数的十位*/
k=num/1%10; /*求出num这个3位数的个位*/
if(i*i*i+j*j*j+k*k*k==num) /*百位数，十位数，个位数的立方和*/
printf("%-5d",num); /*以十进制整数形式输出*/
}
printf("\n");
}
【运行结果】
'Water Flower' number is: 153 370 371 407
【知识拓展】
该程序的关键是将一个三位数的百、十、个位数字分解出来，然后求出其立方和。
也可以从另外一个角度入手，将三个数字根据百、十、个位组合成一个三位数，判断其是否为水仙花数。代码如下：
#include <stdio.h>
main()
{
int i,j,k;
int num;
printf("'Water Flower' number is:\n");
/*三层嵌套循环语句*/
for(i=1;i<=9;i++) /* i为百位，其范围是1～9*/
for(j=0;j<=9;j++) /*j为十位，其范围是0～9*/
for(k=0;k<=9;k++) /*k为个位，其范围是0～9*/
{
num=i*100+j*10+k; /*i,j,k组合成一个三位数*/
if(i*i*i+j*j*j+k*k*k==num)
printf("%-5d",num);
}
printf("\n");
}
案例5.11 猴子吃桃问题
【项目任务】
猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第2天早上又将剩下的桃子吃掉一半，并多吃一个。以后每天早上都吃了前一天剩下桃子的一半零一个。到第10天早上想再吃时，见只剩一个桃子了。求第1天共摘了多少桃子？
【设计思路】
第10天时，还有一个桃子，这是第9天剩下的，那么第9天呢（即第8天之后剩下多少）？
可以这样想：
第1天未吃之前有多少个桃子？暂记为tao(1)；
第2天未吃之前tao(2)有tao(1)/2-1个桃子，于是有：tao(1)=(tao(2)+1)*2；
第3天未吃之前tao(3)有tao(2)/2-1个桃子，于是有：tao(2)=(tao(3)+1)*2；
第4天未吃之前tao(4)有tao(3)/2-1个桃子，于是有：tao(3)=(tao(4)+1)*2；
第9天未吃之前tao(9)有tao(8)/2-1个桃子，于是有：tao(8)=(tao(9)+1)*2；
第10天tao(10)只有1个桃子，即天数为10，n=10时，返回1。
从以上分析可以得出：第i天的桃子数为tao(i)=(peachi+1+1)*2。于是，就建立起了递推式或迭代式。从初始值开始，迭代9次，就得到第1天的桃子数。
【程序代码】
#include <stdio.h>
main()
{
int prev; /* 前一天*/
int next=1; /*后一天, 初值为第10天桃子的个数*/
int i;
for(i=9;i>=1;i--)
{
prev=(next+1)*2;
next=prev;
}
printf("total=%d\n",prev);
}
【运行结果】
1534
【知识拓展】
在第7章中，还可以用递归方法完成这个项目的程序设计。
本 章 小 结
循环控制结构是C语言的三种控制结构之一，它由循环控制语句实现。常用的循环控制语句由while、do...while和for组成。if和goto语句结合起来也可以进行循环控制，但很少使用。while和do...while语句通常用于循环次数未知的循环控制。
如果一个循环语句的循环体中又出现了循环控制语句，则形成多重循环，称为循环嵌套。在循环嵌套时，要注意外循环和内循环在结构上不能交叉。