第一章复习课

主备人主备人：唐强：唐强 王廷伟王廷伟 向妍艳向妍艳 审审核人：牟必继核人：牟必继 温故而知新温故而知新 第一章第一章 算法初步复习课算法初步复习课知识结构知识结构算法算法程程序序框框图图算算法法语语句句辗转相除法与辗转相除法与更相减损术更相减损术 秦九韶算法秦九韶算法 进位制进位制知识梳理知识梳理1.1.算法的概念算法的概念 在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法类问题的明确和有限的步骤称为算法.用程序框、流程线及文字说明来表用程序框、流程线及文字说明来表示算法的图形称为示算法的图形称为程序框图程序框图.2.2.程序框图的概念程序框图的概念3.3.程序框、流程线的名称与功能程序框、流程线的名称与功能图形符号图形符号 名名 称称 功功 能能 终端框终端框 （起止框）（起止框）输入、输出输入、输出框框 处理框处理框（执行框）（执行框）判断框判断框 流程线流程线 表示一个算法的起始和结束表示一个算法的起始和结束 表示一个算法输入和输出的表示一个算法输入和输出的信息信息 赋值、计算赋值、计算 判断某一条件是否成立，成立时在判断某一条件是否成立，成立时在出口处标明出口处标明“是是”或或“Y Y”；不成立；不成立时标明时标明“否否”或或“N N”连接程序框，表示算法步骤的连接程序框，表示算法步骤的执行顺序执行顺序 4.4.算法的顺序结构算法的顺序结构（1 1）概念：）概念：由若干个依次执行的步骤组成的逻由若干个依次执行的步骤组成的逻辑结构，称为辑结构，称为顺序结构顺序结构.（2 2）程序框图：）程序框图：步骤步骤n步骤步骤n+15.5.算法的条件结构算法的条件结构（1 1）概念：）概念：由若干个在一定条件下才会被执行由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为的步骤组成的逻辑结构，称为条件结构条件结构.（2 2）程序框图：）程序框图：满足条件？满足条件？步骤步骤A步骤步骤B是是否否满足条件？满足条件？步骤步骤A是是否否6.6.算法的循环结构算法的循环结构（1 1）概念：）概念：由按照一定的条件反复执行的某些由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为步骤组成的逻辑结构，称为循环结构循环结构.（2 2）程序框图：）程序框图：循环体循环体满足条件？满足条件？是是否否循环体循环体满足条件？满足条件？是是否否7.7.算法的输入语句算法的输入语句INPUT INPUT “提示内容提示内容”；变量；变量8.8.算法的输出语句算法的输出语句PRINT PRINT “提示内容提示内容”；表达式；表达式9.9.算法的赋值语句算法的赋值语句变量变量=表达式表达式10.10.算法的条件语句算法的条件语句IF IF 条件条件 THENTHEN 语句体语句体END IFEND IFIF IF 条件条件 THENTHEN 语句体语句体1 1ELSEELSE 语句体语句体2 2END IFEND IF满足条件？满足条件？步骤步骤1步骤步骤1是是否否满足条件？满足条件？步骤步骤A是是否否11.11.算法的循环语句算法的循环语句DODO 循环体循环体LOOP UNTILLOOP UNTIL 条件条件满足条件？满足条件？是是循环体循环体否否WHILE WHILE 条件条件 循环体循环体WEND WEND 循环体循环体满足条件？满足条件？是是否否12.12.辗转相除法辗转相除法第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r.r.第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步.求两个正整数的最大公约数求两个正整数的最大公约数13.13.更相减损术更相减损术第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m-nm-n所得的差所得的差k.k.第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示.第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步.求两个正整数的最大公约数求两个正整数的最大公约数14.14.秦九韶算法秦九韶算法第一步，输入多项式的次数第一步，输入多项式的次数n n，最高次，最高次 项的系数项的系数a an n和和x x的值的值.第二步，令第二步，令v=av=an n，i=n-1.i=n-1.第三步，输入第三步，输入i i次项的系数次项的系数a ai i.第四步，第四步，v=v=vx+avx+ai i，i=i-1.i=i-1.第五步，判断第五步，判断i0i0是否成立是否成立.若是，则返回第若是，则返回第 二步；否则，输出多项式的值二步；否则，输出多项式的值v.v.求多项式求多项式f(xf(x)=a)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值15.15.十进制化十进制化k k进制的算法进制的算法第四步，若第四步，若q0q0，则，则a=qa=q，返回第二步；，返回第二步；否则，输出全部余数否则，输出全部余数r r排列得到排列得到 的的k k进制数进制数.第一步，输入十进制数第一步，输入十进制数a a和基数和基数k k的值的值.第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排第三步，把所得的余数依次从右到左排 列列.除除k k取余法取余法 例例1 1、某工厂、某工厂20052005年的年生产总值为年的年生产总值为200200万元，技术革新后预计以后每年的年生产总万元，技术革新后预计以后每年的年生产总值都比上一年增长值都比上一年增长5%.5%.设计一个程序，输出预设计一个程序，输出预计年生产总值超过计年生产总值超过300300万元的最早年份万元的最早年份.第三步，判断所得的结果是否大于第三步，判断所得的结果是否大于300.300.若是，则输出该年的年份；否则，若是，则输出该年的年份；否则，返回第二步返回第二步.第一步，输入第一步，输入20052005年的年生产总值年的年生产总值.第二步，计算下一年的年生产总值第二步，计算下一年的年生产总值.算法分析算法分析：巩固练习巩固练习（3 3）控制条件控制条件：当：当“a a300300”时终止循时终止循环环.（1 1）循环体循环体：设：设a a为某年的年生产总值，为某年的年生产总值，t t为年生产总值的年增长量，为年生产总值的年增长量，n n为年份，为年份，则则t=0.05at=0.05a，a=a=a+ta+t，n=n+1.n=n+1.（2 2）初始值初始值：n=2005n=2005，a=200.a=200.循环结构循环结构：开始开始n=2005a=200t=0.05aa=a+tn=n+1a300？结束结束输出输出n是是否否程序框图程序框图：开始开始n=2005a=200t=0.05aa=a+tn=n+1a300？结束结束输出输出n是是否否程序程序：n=2005n=2005a=200a=200DODOt=0.05*at=0.05*aa=a=a+ta+tn=n+1n=n+1LOOP UNTIL aLOOP UNTIL a300300PRINT nPRINT nENDEND 例例2 2、一个球从、一个球从100m100m高处自由落下高处自由落下,每次每次着地后又跳回到原高度的一半再落下着地后又跳回到原高度的一半再落下.编写编写程序程序,求当它第求当它第1010次着地时次着地时,(1)(1)第第1010次着地后反弹多高次着地后反弹多高?(2)(2)向下的运动共经过多少米向下的运动共经过多少米?(3)(3)全程共经过多少米全程共经过多少米?100100505025251 12 23 34 41010着地次数着地次数高度高度0 0(1)(1)第第1010次着地后反弹多高次着地后反弹多高?开始开始h=50h=50i10?i10?h=h/2h=h/2i=1i=1结束结束输出输出h h否否i=i+1i=i+1h=50h=50i=1i=1WHILE iWHILE i=10=10h=h/2h=h/2i=i+1i=i+1WENDWENDPRINT hPRINT hENDEND是是(2)(2)第第1010次着地时向下的运动共经次着地时向下的运动共经过多少米过多少米?开始开始h=100h=100s=100s=100h=h/2h=h/2s=s=s+hs+hi=1i=1结束结束输出输出s s否否i=i+1i=i+1是是h100h100s=100s=100i=1i=1WHILE iWHILE i=10=10h=h/2h=h/2s=s=s+hs+hi=i+1i=i+1WENDWENDPRINT sPRINT sENDENDi10?i10?(3)(3)全程共经过多少米全程共经过多少米?s=s=s+hs+h开始开始h=100h=100s=100s=100i10?i10?h=h/2h=h/2i=1i=1结束结束输出输出s s否否i=i+1i=i+1是是s=s+2hs=s+2hs=s=s+hs+hh=100h=100s=100s=100i=1i=1WHILE iWHILE i=10=10h=h/2h=h/2i=i+1i=i+1WENDWENDPRINT sPRINT sENDENDs=s+2*hs=s+2*h 例例3 3、阅读下列程序：若输入的两个、阅读下列程序：若输入的两个数数m=428m=428，n=284n=284，求计算机输出的数，求计算机输出的数.INPUT mINPUT m，n nDODOr=m r=m MODnMODnm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND 例例4 4、求、求324324，243243，270270三个数的最大三个数的最大公约数公约数.2727 例例5 5、已知、已知f(xf(x)=8x)=8x7 7+5x+5x6 6+3x+3x4 4+2x+1,+2x+1,用用秦九韶算法去秦九韶算法去f(2)f(2)的值的值.f(xf(x)=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1)=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1f(2)=1397f(2)=1397 例例6 6、用秦九韶算法求多项式、用秦九韶算法求多项式f(xf(x)=a)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值，令的值，令v0=an，v vk k=v=vk-1k-1x+ax+an-kn-k(k=1(k=1，2 2，n).n).若若f(xf(x)=3x)=3x5 5+4x+4x4 4+5x+5x3 3+2x+2x2 2+2x+1,+2x+1,当当x=3x=3时，求时，求v v4 4的值的值.V V4 4=270=270 例例8 8、把八、把八进制数进制数23762376（8 8）化为五进制化为五进制数数.23762376（8 8）=1278=20103=1278=20103（5 5）例例7 7、把、把十进制数十进制数104104化为三进制数化为三进制数.104=10212104=10212（3 3）