循环设计补充

1常见算法：顺推法从应用题的已知条件出发，一步一步顺着推理，逐步推出问题的答案，这种解题方法称为顺推法，也叫综合法。顺推思路的思维过程是：从应用题的已知条件出发，先选出两个有直接联系的已知条件，组成一道简单应用题（即一步应用题）。求出答案后，未知条件成为已知条件，然后同另一个有联系的已知条件，组成一道新的简单应用题。这样不断推究下去，最后一道简单应用题的得数，就是原应用题的解。2常见算法：顺推法【累加型】类型诸如□+□+□+□+……+□+□

求其前n项之和的编程题。累加型算法

若设i为循环变量，s为前n项累加之和，则程序的基本结构为：

s=0;for(i=1;i<=n;i++)s=s+□;3例编程求1－1/2+1/3－1/4+1/5－…+1/99－1/100分母为奇数时，相加分母为偶数时，相减法1：从变化规律分析……程序：main(){inti;floats=0;for(i=1;i<=100;i++)if(i%2)s=s+1/i;elses=s-1/i;printf("Sum=%f\n",s);}运行结果：Sum=1.000000错在哪里？4

例：编程求1－1/2+1/3－1/4+1/5－…+1/99－1/100法2：这是个累加型算法的编程题……程序：#include<math.h>main();{inti;floats=0;for(i=1;i<=100;i++)s=s+pow(-1,i+1)/i;printf("Sum=%f\n",s);}

程序：#include<math.h>main(){inti,k=1;floats=0;for(i=1;i<=100;i++){s=s+

k/i;k=-k;}printf("Sum=%f\n",s);}累加型算法程序基本结构为：

s=0;for(i=1;i<=n;i++)s=s+□;错在哪里？(如何检查程序错误？)运行结果：Sum=0.688172运行结果：Sum=1.0000005常用算法：顺推法【阶乘型】类型诸如□×□×□×□×……×□×□

求其前n项之积的编程题。阶乘型算法若设i为循环变量，s为前n项相乘之积，则程序的基本结构为：

s=1;for(i=1;i<=n;i++)s=s*□;6

编程求∑i!=1!+2!+3!…+n!（n由键盘输入）外循环为累加型内循环为阶乘型法1：从变化规律分析……程序：main(){inti,j,n;floats,s1;

printf("请输入n=");scanf("%d",&n);

s=0;for(i=1;i<=n;i++){

s1=1;

for(j=1;j<=i;j++)s1=s1*j;s=s+s1;}

printf("Sum=%.0f\n",s);}运行结果：n=5Sum=1537

编程求∑n!=1!+2!+3!…+n!（n由键盘输入）在同一个循环中先阶乘，后累加法2：通过单循环实现……程序：main(){inti,n;floats,s1;

printf("请输入n=");scanf("%d",&n);s=0,s1=1;for(i=1;i<=n;i++){s1=s1*i;s=s+s1;}printf("Sum=%.0f\n",s);}运行结果：n=5Sum=1538顺推法的其它应用Fibonacci数列斐波纳契数列（FibonacciSequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34……这个数列从第三项开始，每一项都等于前两项之和。9倒推法倒推思路的思维过程是：从应用题的所求问题出发，找出解答这个问题的两个必要条件，哪个是已知的，哪个是未知的。对于未知条件，把它作为问题，再去找解决它的两个条件，这样不断推究下去，直到所需要的条件都是题目中已知条件为止，这时问题也就解决了。也称分析法。猴子吃桃问题（教材p77）10穷举法穷举法是一种重复型算法。其基本思想是，对问题的所有可能状态一一测试，直到找到解或将全部可能状态都测试过为止。在编程中，主要使用循环语句和选择语句。循环语句用于穷举出所有可能的情况，而选择语句则用来判断当前的条件是否为所求的解。基本格式：

for(n=1;n<=循环次数;n++){if(n满足指定的条件)

输出n；}11有4名专家对4件产品质量进行评估。A说：2号产品质量最好。B说：4号产品是最好的。C说：3号产品质量不是最好的。D说：B说错了。事实上，只有一件产品质量最好，且只有一位专家说对了，其他三人都说错了。请编程输出最好的产品号及说对的专家。（1）假定1号产品质量最好，即令k=1，将k=1代入4位专家的话中，则有：

（2）假定2号产品质量最好，即令k=2，将k=2代入4位专家的话中，则有：专家评估判断当前k值专家结论判断结论01==414B01==212A1!4D11!=31!3C11!=4专家评估判断当前k值专家结论判断结论02==424B12==222A2!4D12!=32!3C12!=4假定3号产品质量最好，即令k=3将，将k=3代入4位专家的话中，则有：

专家评估判断当前k值专家结论判断结论03==434B03==232A3!4D03!=33!3C13!=4main(){intk,man,sum=0,g=0;for(k=1;k<=4;k++){sum=0;if(k==2){sum=sum+1;man=1;}if(k==4){sum=sum+1;man=2;}if(k!=3){sum=sum+1;man=3;}if(k!=4){sum=sum+1;man=4;}if(sum==1){printf("Thebestproductis%d.\n",k);printf("%cisright.\n",64+man);g=1;break;}}if(g!=1)printf("Can'tfounttheanswer!\n");}15素数与因数素数：除1和它本身之外再无别的约数；算法：判断m%i==0成立否？

i取值:2～(m-1)或：2～16因数一整数被另一整数整除,后者即是前者的因数,如1,2,4都为8的因数如果一个正整数等于它的所有正真因数的和，我们称这个数为一个完数(perfect)。例如：6=1+2+3；28=1+2+4+7+14，所以6和28都是完数。不是完数的正整数分为亏数(deficient)和冗数(abundant)，依据这个数的所有真因数的和与其本身的大小来划分。因此，9是亏数因为9>1+3；而12是冗数因为12<1+2+3+4+6。17求两个整数的最大公约数和最小公倍数。

若已知整数x和y的最大公约数是k，则它们的最小公倍数是x*y/k。

下面介绍求两个整数最大公约数的两种方法：

①

辗转相除法

两个数相除，若余数为0，则除数就是这两个数的最大公约数。若余数不为0，则以除数作为新的被除数，以余数作为新的除数，继续相除，……，直到余数为0，除数即为两数的最大公约数。如：

a=32，b=12。求a和b的最大公约数。

32%12的值为8，不为0；

12%8的值为4，不为0；

8%4的值为0，所以a和b的最大公约数是4。18②

相减法

两个数中从大数中减去小数，所得的差若与小数相等，则该数为最大公约数。若不等，对所得的差和小数，继续从大数中减去小数，……，直到两个数相等为止。仍以a=32，b=12为例：

a

b

32

12

32-12=20（20>12）

20-12=8

(8<12)

12-8=4(4<8)

8-4=4

(4=4)

所以，32和12的最大公约数是4。19辗转相除法程序：

main

(

)

/*

辗转相除法求最大公约数和最小公倍数

*/

{

int

x,y,a,b,t;

scanf

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

a=x;

b=y;

/*

保存x,y以便求它们的最小公倍数

*/

t=a%b;

while

(

t!=0

)

/*

余数不为0，继续相除，直到余数为0

*/

{

a=b;

b=t;

t=a%b;

}

printf("x=%d,y=%d

→

%d,%d\n",

x,

y,

b,

x*y/b

);

}

20相减法程序：

main

(

)

/*

相减法求最大公约数和最小公倍数

*/

{

int

x,

y,

a,

b,

t;

scanf

("%d,%d",

&x,

&y);

a=x;

b=y;

/*

保存x,y以便求它们的最大公约数和最小公倍数

*/

while

(

a!=b)

/*

a,b不相等，大数减小数，直到相等为止。*/

if

(a>b)

a=a-b;

else

b=b-a;

printf

("x=%d,y=%d

→

%d,%d\n",

x,

y,

a,

x*y/a);

}

21⑶穷举法有两整数a和b：①i=1②若a，b能同时被i整除，则t＝i③i++④若i<=(a,b中小者)，则再回去执行②⑤若i>(a,b中小者)，则t即为两数的最大公约数22main()/*穷举法求最大公约数*/{intm,n,a,b,i,t;

prinf("Inputtwointegernumbers:\n");scanf("%d,%d",&a,&b);

m=a;n=b;for(i=1;i<=(a<b?a:b);i++)if(a%i==0&&b%i==0)t=i;

printf("Thelargestcommondivisor:%d\n",t);printf("Theleastcommonmultiple:%d\n",m*n/t);}

23求三个正整数的最大公约数和最小公倍数24输出图形25编程显示以下图形（共N

行，N

由键盘输入）。

*************************此类题目分析的要点是：通过分析，找出每行空格、*与行号i、列号j及总行数N的关系。其循环结构可用右图表示。分析：（设N=5）第1行4个空格=5-11个“*”=2*行号-1第2