累加算法2008

算法和程序设计循环结构及累加、累乘的算法设计•Fork=1To20Step2PrintkNext输出20以内的奇数k=1DoWhilek=20Printkk=k+2Loop并统计个数Sum=1+2+3+……+100循环次数sumi循环条件(i=100)结束开始sum=0i=1i=100sum=sum+ii=i+1输出sum是否初值条件循环体输出数据sum=1+2+3+4+……+100sum=0i=1Dowhilei=100sum=sum+ii=i+1loopPrintsum结束开始sum=0i=1i=100sum=sum+ii=i+1输出sum是否sum=0;（总和）i=1（循环变量）i=100sum=sum+i;表示sum原来的值加上变化后i的值之后再次赋给sumi=i+1;sumsum←0i←1Dowhile(i=100)i←i+1sum←sum+Iloop输出sum的值问：１如果循环体内的两个赋值语句交换位置，结果会怎样？２如果两个赋初值的语句交换位置呢？循环次数sumi循环条件(i=100)结论：循环体内语句不可随意调换位置sum←0i←1DoWhile(i=100)sum←sum+ii←i+1loop输出sum的值问：求解1+2+……+１００0的值应如何改？1+2+……+n的值呢？I=1000I=n改变循环变量练习求解：2+4+6+……+100I←2sum←0I=100sum←sum+ii←i+2输出sumsum←0i←2DoWhile(i=100)sum←sum+ii←i+2loop输出sum的值I←1s←1I=100s←s*ii←i+1输出s思考：下列程序的功能？并用伪代码来描述s←1i←1DoWhile(i=100)s←s*ii←i+1loop输出s的值结论：求解1*2*3*……*100的值（累乘算法）思考：累乘问题中的s的初值能否为0？如设为0会怎样？练习：写出求2*4*6*8*10的伪代码s←1i←2DoWhile(i=10)s←s*ii←i+2loop输出s的值练习：问：循环执行的次数？I←1DoWhile(I=4)I←I+1LoopPrintIi循环次数循环条件(I=4)4练习：S←0i←1DoWhile(I=3)s←s+Ii←I+1loop输出s的值结果：6c←1DoWhile(c=20)c←c+6loop输出c的值练习：c循环条件(c=20)25i是循环变量，初值为1累加器(accumulator)算法执行过程中，用来形成并存贮数据之和的变量。假定变量s作为累加器，变量d中存贮了符合要求的一个数据。累加器的典型用法：1.在求和开始前的准备阶段中，应预置初值0。s←02.算法执行过程中，每遇到一个符合要求的数据时，重复执行数据d累加到sum的动作：s←s+di1结束赋初值yn输出ss0{累加器例：求解1+2+3+……..+n的算法(n由用户键盘输入)虚线框部分生成1+2+…+n序列的和ss+i:i=i+1输入ni=n练习：s←0i←4DoWhile(I=1)s←s+Ii←I-1loop输出s的值sI←I-1循环次数循环条件10拓展：仿照上例求sum=1+2+……+100的值sum←0i←100DoWhile(I=1)s←s+Ii←I-1loop输出sum练习1:求1-1000内所有奇数之和的算法流程图开始S=0i=1S=S+ii=i+2结束输出Si≤1000YesNo当型循环开始S=0i=1S=S+ii=i+２结束输出SYesNoi≤1000直到型循环开始S=0i=1S=S+ii=i+1结束输出Si≤100YesNo开始S=0i=1S=S+1/ii=i+1结束输出Si≤100YesNo练习3：填空完成计算1+++……++的算法流程图。提示:参考练习1，考虑每个加数的分母变化规律。尤其注意观察练习1练习3中的对应加数项，两个对应加数存在什么数量关系。31219911001开始S=0i=1S=S+ii=i+1结束输出Si≤100YesNo直到型循环练习1:计算1+2+3+……+99+100S=S+1/i大家练：说明以下流程图所表示的意义（其中n为自然数）K=nss+1/k:k=k+1yn输入ns0:k1输出s输入ns0：k1Dowhile(K=n)ss+1/kk=k+1loop输出s请试用伪代码表示重复模式一般格式是：Dowhile(条件)循环体LOOP表示的意义为：1+1/2+1/3+…+1/n在数学中，N个自然数1，2，3，……，N的乘积称为N的“阶乘”，记作N！。即N！=1×2×3×……×（N-1）×N100！=1×2×3×……×99×10011!=1×2×3×……×10×114!=1×2×3×4说明：练习2:填空完成计算1×2×3×……×99×100的算法流程图（提示:参考练习1）开始S=0i=1S=S+ii=i+1结束输出Si≤100NoYes开始S=1i=1S=S×ii=i+1结束输出Si≤100NoYes开始S=0i=1S=S+ii=i+1结束输出Si≤100YesNo直到型循环练习1:计算1+2+3+……+99+100S=S×iS=1练习4:填空完成计算8！+9！的算法流程图。(提示：参考练习2，可先计算8！，N！=（N-1）！×N，如9！=8！×9，8！+9！=8！+8！×9）开始S=1X=2S=S×XX=X+1结束输出SX≤8NoYesS=S+S×9开始S=1X=2S=S×XX=X+1X≤100NoYes结束输出SX≤8S=S+S×9结束输出S课外思考思考题4：怎样用流程图描述计算1！+2！+3！+……+99！+100！的算法。(提示：N!=(N-1)!×N，4!=3!×4，考虑如何利用每次乘积的结果。)思考题5：怎样用流程图描述计算3！+4！+5！+……+9！+10！的算法。练习5：填空完成计算1-+-+-……+-的算法流程图。（提示：参考练习3，考虑每个加数的符号变化）514121319911001开始S=0X=1s=s+T/XX=X+1结束输出SX≤100NoYesT=1T=-t-T开始S=1X=2T=–TX=X+1结束输出SX≤100NoYesT=1S=S+/XT应用举例设计一个算法，计算一批数据的算术平均值。这批数据由使用者从键盘输入，使用者预先不指定数据的个数。并约定：输入0时表示本次计算所需的全部数据已输入完毕。-2开始c0输入dd0Sumsum+dcc+1输出sum/c结束ynSum0c0输入dDoWhile(d0)sumsum+dcc+1输入dloop输出sum/c的值Sum0输入d用流程图表示用伪代码表示注意其中的变量，区别累加器、计数器如果第一次就输入0，程序是否会出错？怎样处理?参考解答Sum0c0输入dDoWhile(d0)sumsum+dcc+1输入dloopif(c=0)then输出0else输出sum/c的值endif输出0C=0输出sum/c结束yn所谓“圆周率”是指一个圆的周长与其直径的比值。古今中外，许多人致力于圆周率的研究与计算。为了计算出圆周率越来越精确的近似值，一代代的数学家为了这个神秘的无限不循环小数贡献了自己毕生的心血。早在我国的魏晋时期，数学家刘徽就用“割圆术”求出了比较精确的圆周率。他发现：当圆内接正多边形的边数不断增加后，多边形的周长会越来越接近圆周长，而正多边形的面积也会越来越接近圆面积。于是，刘徽利用正多边形面积和圆面积之间的关系，从正六边形开始，逐步把边数加倍——正十二边形、正二十四边形、正四十八边形……一直到正三百七十二边形，算出圆周率等于3.1416，将圆周率的精确度提高到小数点后的4位。另一位对圆周率颇有研究的是我国南北朝时期的著名数学家、天文学家祖冲之（公元429年~500年）。他在刘徽研究的基础上，进一步的发展，经过漫长而又繁琐的计算，一直算到正24576边形，进而得到一个结论：圆周率的值介于3.1415926~3.1415927之间，成为世界上最早把圆周率推算到小数点后7位的科学家，直到1000年后才有西方的数学家达到或超过祖冲之的成就。现在人们计算圆周率，大多是为了验证计算机的计算能力。古人计算圆周率，一般使用“割圆术”，但是这种基于几何的算法计算量太大，速度慢，吃力不讨好。随着数学的发展，数学家们在进行数学研究时，有意无意的发现了许多计算圆周率的公式，下面两个是常用的计算圆周率的公式：圆周率π是一个非常重要的数学常量，这是一个无理数，即，一个无限不循环小数。自古至今，人们提出了很多方法来计算π的值。下面是约翰·沃利斯(1650)给出的计算公式：-2598787656543432122分析：偶数位分母加２，分子不变奇数位分子加２，分母不变n=InputBox(n=)i=1:s=1:x=2:y=1DoWhilei=ns=s*x/yi=i+1IfiMod20Thenx=x+2Elsey=y+2EndIfLoopPrint2*s如：已知π/4≈1-1/3+1/5-1/7+…求π的近似值(最后一项的绝对值小于10-6)-13用伪代码表示为：DimpiAsDoublepi=0:i=1:d=1DoWhilei=1000000pi=pi+d/id=-di=i+2LoopPrint4*pi开始i=1000000pi=pi+d/i结束ynpi=0:i=1:d=1用流程图表示为输出pi•i=i+2pi=pi*4d＝-d算法２算法３pi=0:i=1DoWhilei=1000000pi=pi+2/(i*(i+2))i=i+4LoopPrint4*pii=1DoWhilei=1000000a=a+1/(4*i+1)i=i+1Loopi=1DoWhilei=1000000b=b+1/(4*i-1)i=i+1Looppi=1+a-bPrint4*pi算法4算法5s=0:i=1DoWhilei=1000000s=s+1/ii=i+2s=s-1/ii=i+2LoopPrint4*s输入20个数，求其中最大值max和最小值min。用流程图表示为•Dimx%x=InputBox(“请输入x的值：”)max=xmin=xi=2DOWHILEi=20x=InputBox(“请输入x的值：”)IFxminTHENmin=xENDIFIFxmaxTHENmax=xENDIFi=i+1LOOPPrintmax,min输入n个学生成绩，输出平均值。用流程图表示为•Dimn%,d%n=InputBox(“请输入学生个数”)s=0i=1DOWHILEi=nd=InputBox(“请输入成绩”)s=s+di=i+1LOOPPrints/n上机作业•１、求圆周率２、输入n个学生成绩，输出平均值３、输出５个数中的最大数和最小数４、输出矩形图案一个有趣的古典数学问题：有一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月又生一对兔子。假设所有兔子都不死，依次输出前10个月的兔子总数。-14月小兔中兔老兔110020103101411152126323753511235813…这就是Fibonacci数列请观察它的规律是什么？这个数列的第一、二项是1、1，以后的每一项是前二项的和。请为Fibonacci数列设计一个算法总数……递推法用伪代码表示为：n=2a=1b=1Printa,bDoWhile(n10)n=n+1C=a+bprintCa=bb=cLoop用流程图表示为开始n10n=n+1结束yna=1:b=1C=a+b输出C输出a,bn=2a=bb=c输出：1,1,2,3,5,8,13,21,34,55*用辗转相除法两个自然数的最大公约数的算法-20如：求252和198的最大公约数被除数x除数y余数r2521985419854365436183618018018是252和198的最大公约数输入x和y的值If(xy)thentx:x