重复结构典型算法

重复结构典型算法

例6.5编写求1-2+3-4+5-...-100的和程序。

第一步：设定项号，定义变量，找前后项关系这是关键的一步。

设定项号n=1234...

sum=1-2+3-4+5-...–100

存和前后项关系为n=n+1，比较简单。生成的数n有正负号，且有规律：奇数为正，偶数为负,可用二选一if语句判别；这里定义一个变量s判别。第二步：构造重复结构求解这类题目，循环体总要执行多次。采用dowhile重复结构是很自然的。用其它重复结构，可行吗？第2页,共28页，2024年2月25日，星期天

do{n=n+1;s=-s;sum=sum+s*n;}while(n<100);第三步：设置变量初值设置变量初值是保证正确计算出第一项值。十分明显，各变量的初值为：

intn=0,sum=0,s=-1;

第四步：

静态检查

跟踪三步左右，如果结果是正确的，一般情况下，可断定算法是正确的。

第3页,共28页，2024年2月25日，星期天

语句第一次循环第二次循环第三次循环

n=n+1;123s=-s1-11sum=sum+s*n;1-12第五步：编程

通过上述分析，确定了数据结构，定义了有关变量和类型(因明显是整型，未作说明),完成了算法设计。接下来编程就是用C语言精确表述这一思维过程。/*求1-2+3-4+5-...-100的和chap6_5.c*/#include<stdio.h>voidmain(){intsum=0,n=0,s=-1;printf("***运行结果***\n");第4页,共28页，2024年2月25日，星期天

do { n++; s=-s;sum+=s*n; }while(n<100); printf("1-2+3-4+...-100=%d\n",sum);}***运行结果***

1-2+3-4+...-100=-50例6.6编写下述功能程序：求sinx=x-x3/3!+x5/5!-x7/7!+...的近似值，误差为1×10-8。

第5页,共28页，2024年2月25日，星期天

do { n++; s=-s;sum+=s*n; }while(n<100); printf("1-2+3-4+...-100=%d\n",sum);}***运行结果***

1-2+3-4+...-100=-50例6.6编写下述功能程序：求sinx=x-x3/3!+x5/5!-x7/7!+...的近似值，误差为1×10-8。

第6页,共28页，2024年2月25日，星期天

第一步：设定项号，定义变量，找前后项关系设定项号n=1234...sinx=x-x3/3!+x5/5!-x7/7!+...

存sin函数值存x的幂xn存阶乘fact前后项关系比较复杂。从整体找前后项关系比较困难，分别找前后项的分子和分母的关系比较简便。前后项关系： 分子xn=-xn*x*x

分母fact=fact*(2*n-2)*(2*n-1)第7页,共28页，2024年2月25日，星期天第二步：

构造重复结构求解这类题目，循环体总要执行多次(循环次数不确定)，一般采用dowhile重复结构。

do{n=n+1;xn=-xn*x*x;fact=fact*(2*n-2)*(2*n-1);sinx=sinx+xn/fact;}while(fabs(xn/fact)>1e-8);

第三步：设置变量初值

floatx;doublen=1,xn=x,fact=1,sinx=x;

为保证精度，xn,fact,sinx取double型。为防止溢出，n也取double。第8页,共28页，2024年2月25日，星期天第四步：

静态检查

跟踪三步左右，如果结果正确，一般情况下，算法是正确的。语句第一次循环第二次循环第三次循环

n=n+1;234xn=-xn*x*x;-x3x3-x7fact=fact*(2*n-2)*(2*n-1); 3！

5！

7!sinx=sinx+xn/fact;x-x3/3!x-x3/3!＋x5/5!x-x3/3!＋x5/5!-x7/7!第五步：编程/*求sinx=x-x3/3!+x5/5!-x7/7!+...的近似值chap6_7.c*/#include<stdio.h>#include<math.h>#defineEPS1e-8/*符号常量，误差*/第9页,共28页，2024年2月25日，星期天voidmain(){floatx;doublen=1,xn,fact=1,sinx;

printf("***运行结果***\n");printf("输入x:");scanf("%f",&x);sinx=x;xn=x;/*不在变量定义时置初值，为什么？*/

do{ n=n+1;xn=-xn*x*x;fact=fact*(2*n-2)*(2*n-1);sinx=sinx+xn/fact;}while(fabs(xn/fact)>EPS);

printf("递推法sin%0.4f=%0.8f\n",x,sinx);printf("调库函数sin%0.4f=%0.8f\n",x,sin(x));}

***运行结果***输入x:1递推法sin1.0000=0.84147098调库函数sin1.0000=0.84147098第10页,共28页，2024年2月25日，星期天

例如：求a1/2

的近似值迭代公式：xn+1=(xn+a/xn)/2误差公式：|xn+1-xn|<=EPSfloata;/*由用户输入*//*存当前近似值*//*暂存前一次的近似值*/数据:doublex0；doublex1；主要算法:x1

=a/2；do{x0=x1;//保存当前解

x1=(x0+a/x0)/2;//计算新解}while(fabs(x1-x0)>EPS)；2迭代法

问题具有的共同特点是：已知迭代公式和误差公式。可直接应用重复结构，按迭代公式计算一个新解，并与前一个解比较，直到满足误差要求为止。scanf(“%f”,&a)；第11页,共28页，2024年2月25日，星期天下面以例说明分析问题和算法设计的方法。例6.7 编写求a1/2的近似值程序。

迭代公式和误差公式是数学工作者研究的课题。编程是应用数学工作者研究的成果，快速求出满足精度要求的值。有了迭代公式和误差公式，求解这类问题十分简单。定义原根x0表示xn，新根x1表示xn+1，其类型取double。为什么不直接用xn和xn+1？先以求21/2根为实例，按迭代法重复计算三次，观察根值的变化趋势。a为2,定义一个新根x1=a/2，其初值为1.0,重复按迭代公式计算一个新根：语句 第一次循环 第二次循环第三次循环x0=x1;1.01.51.417x1=(x0+a/x0)/2;1.51.4171.414

从上面x1的各次计算值可以看出：x1值一步一步逼近21/2的根值。求解这类问题，一般都采用dowhile重复结构实现。

第12页,共28页，2024年2月25日，星期天

x1=a/2; /*选定初值*/ do {x0=x1; /*前一次根值

*/ x1=(x0+a/x0)/2; /*按迭代公式计算一个新根值*/ }while(fabs(x1-x0)>ESP);/*判别是否满足误差要求*/

选择x1初值为2是否可以？为什么不选x0初值为a/2?依据上面分析，编写求a1/2近似值的完善程序就不感到困难了。/*应用迭代法求a1/2的近似值chap6_8.c*/#include<stdio.h>#include<math.h>#include<stdlib.h>#defineEPS1e-8voidmain(){floata;doublex0,x1;第13页,共28页，2024年2月25日，星期天

printf("***运行结果***\n");printf("读入一个实数:");scanf("%f",&a);if(a<0) {printf("错误:输入的实数小于0\n"); exit(1); }

x1=a/2;/*选定初值*/ do {x0=x1;/*前一次根值*/x1=(x0+a/x0)/2;/*按迭代公式计算一个新根值*/ }while(fabs(x1-x0)>EPS);

printf("迭代法sqrt(%f)=%0.8f\n",a,x1);printf("调库函数sqrt(%f)=%0.8f\n",a,sqrt(a));}第14页,共28页，2024年2月25日，星期天***运行结果***读入一个实数:123.987迭代法sqrt(123.987000)=11.13494497调库函数sqrt(123.987000)=11.13494497第15页,共28页，2024年2月25日，星期天3枚举法问题具有的共同特点是：不能用方程求解，只能一一列举各种情况，选取满足要求的解。可应用for嵌套结构实现。例如：“百鸡问题”鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问鸡翁、鸡母、鸡雏各几何。inti;/*鸡翁*/intj;/*鸡母*/intk;/*鸡雏*/数据:主要算法:for(i=1;i<20;i++)for(j=1;j<33;j++){k=100-i-j;if(15*i+9*j+k==300)printf("%4d%7d%7d\n",i,j,k);}第16页,共28页，2024年2月25日，星期天【补P1296.7】编程序求2～10000以内的完全数。

完全数：一个数的因子（除了这个数本身）之和等于该数本身。思路：设定i从2变到10000，对每个i找到其因子和s；判定i==s？若相等，则i为完全数，否则不是。

例如：6的因子是1、2、3，因子和

1+2+3＝6因此6是完全数使用穷举算法用双层循环实现第17页,共28页，2024年2月25日，星期天算法和程序：voidmain(){inti,j,s;

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

{s=0;

for(j=1;j<i;j++)if(i%j==0)s+=j;if(i==s)printf("%6d\n",s);

}}

for(i=2;i<=10000;i++)s=0for(j=1;j<i;j++)i%j==0TFs=s+ji==sTFi是完全数第18页,共28页，2024年2月25日，星期天思路：素数是指只能被1和它本身整除的数，如5、7、11、17、…等。

分别用2、3、…，n-1尝试能否整除整数n。如果n能被某个数整除，则n就不是素数。这是一种穷举算法设除数为j，从2循环到n-1【例】判断输入的某个数n是否为素数。若是素数，输出“YES”，若不是，输出“NO”。第19页,共28页，2024年2月25日，星期天算法和程序：#include<stdio.h>voidmain(){intj,n;printf("Enteranintegernumber:");scanf("%d",&n);for(j=2;j<=n-1;j++)

if(n%j==0)break;if(j>=n)printf("YES\n");elseprintf("NO\n");}

输入一个数nfor(j=2;j<=n-1;j++)n%j==0TF

退出循环

j>=nTF输出"YES“输出"NO"第20页,共28页，2024年2月25日，星期天程序的优化对于穷举法来说，为了提高程序的效率，就要减少尝试次数。#include<math.h>main(){intj,m,k;printf("Enteranintegernumber:");scanf("%d",&n);

k=sqrt(n);for(j=2;j<=k;j++)

if(n%j==0)break;if(j>=k+1)printf("YES\n");elseprintf("NO\n");}思考：如何输出100～200中所有的素数

第21页,共28页，2024年2月25日，星期天例题：从红、黄、兰、白、黑五种颜色的球中取出三种颜色的球，问共有几种取法。分析：可以使用整型常量1,2,3,4,5分别表示红、黄、兰、白、黑五种颜色，就可以声明三个int型变量分别存放三次取球的颜色：intc1,c2,c3;//分别存放第1，2，3次取球的颜色，取值范围为:1~5intcount;//计数器算法：count=0;for(c1=1;c1<=5;c1++)

for(c2=1;c2<=5;c2++){

for(c3=1;c3<=5;c3++)if(c3!=c1&&c3!=c2){printf(“%d\t%d\t%d\n”,c1,c2,c3);count++;}

}printf(“共有%d种取法\n”,count);if(c2==c1)continue;&&c1!=c2第22页,共28页，2024年2月25日，星期天【补】编程序，输出以下图形。

****************一共有4行，每行由空格和星号组成：空格数按行增加，星号按行减少变量

i

控制输出行数，从1变化到4变量j控制输出每行的空格和星号：j从1变化到

i-1，每次输出一个空格j从1变化到8-(2*i-1)，每次输出一个星号使用双重循环实现思路：4其他第23页,共28页，2024年2月25日，星期天算法和程序：voidmain(){inti,j;

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

{

for(j=1;j<=i-1;j++)printf("");for(j=1;j<=8-(2*i-1);j++)printf("*");printf("\n");

}}for(i=1;i<=4;i++)for(j=1;j<=i;j++)

输出一个空格

for(j=1;j<=8-(2*i-1);j++)

输出一个星号换行思考：如何输出10行图形？输出图形向右平移20个字符位置，应如何修改程序？第24页,共28页，2024年2月25日，星期天思路：数制转换

将二进制数、八进制数和十六进制数转换为十进制数。【补】编写将十六进制数转换为十进制数程序。求解这一问题的关键是如何将字符转换为整数的数字？

（1）将数字字符’0’

～’9’转换为整型数的数字0～9，可用表达式ch-’0’描述。例如ch为’0’，则’0’-’0’=48-48，其值为0。

（2）将大写字母’A’

～’F’转换为整型数的数字10～15，可用表达式ch-55描述。例如ch为’A’，则’A’-55=65-55，其值为10。