算法初步单元小结课件.ppt

1、算法初步单元小结算法初步单元小结第一课时第一课时第一章第一章 单元复习单元复习知识结构知识结构t57301p2算法算法程序框图程序框图算法语句算法语句辗转相除法与辗转相除法与更相减损术更相减损术 秦九韶算法秦九韶算法 进位制进位制知识梳理知识梳理1.1.算法的概念算法的概念 在数学中，按照一定规则解决某一在数学中，按照一定规则解决某一类问题的明确和有限的步骤类问题的明确和有限的步骤称为算法称为算法.用程序框、流程线及文字说明来表用程序框、流程线及文字说明来表示算法的图形称为示算法的图形称为程序框图程序框图.2.2.程序框图的概念程序框图的概念3.3.程序框、流程线的名称与功能程序框、流程线的名

2、称与功能图形符号图形符号 名名 称称 功功 能能 终端框终端框 （起止框）（起止框）输入、输出输入、输出框框 处理框处理框（执行框）（执行框）判断框判断框 流程线流程线 表示一个算法的起始和结束表示一个算法的起始和结束 表示一个算法输入和输出的表示一个算法输入和输出的信息信息 赋值、计算赋值、计算 判断某一条件是否成立，成立时在判断某一条件是否成立，成立时在出口处标明出口处标明“是是”或或“Y”Y”；不成立；不成立时标明时标明“否否”或或“N”N”连接程序框，表示算法步骤的连接程序框，表示算法步骤的执行顺序执行顺序 4.4.算法的顺序结构算法的顺序结构（1 1）概念：）概念：由若干个依次执行的

3、步骤组成的逻由若干个依次执行的步骤组成的逻辑结构，称为辑结构，称为顺序结构顺序结构.（2 2）程序框图：）程序框图：步骤步骤n步骤步骤n+15.5.算法的条件结构算法的条件结构（1 1）概念：）概念：由若干个在一定条件下才会被执行由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为的步骤组成的逻辑结构，称为条件结构条件结构.（2 2）程序框图：）程序框图：满足条件？满足条件？步骤步骤A步骤步骤B是是否否满足条件？满足条件？步骤步骤A是是否否6.6.算法的循环结构算法的循环结构（1 1）概念：）概念：由按照一定的条件反复执行的某些由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为步骤组成

4、的逻辑结构，称为循环结构循环结构.（2 2）程序框图：）程序框图：循环体循环体满足条件？满足条件？是是否否循环体循环体满足条件？满足条件？是是否否7.7.算法的输入语句算法的输入语句INPUT “INPUT “提示内容提示内容”；变量；变量8.8.算法的输出语句算法的输出语句PRINT “PRINT “提示内容提示内容”；表达式；表达式9.9.算法的赋值语句算法的赋值语句变量变量=表达式表达式10.10.算法的条件语句算法的条件语句IF IF 条件条件 THENTHEN 语句体语句体END IFEND IFIF IF 条件条件 THENTHEN 语句体语句体1 1ELSEELSE 语句体语句体

5、2 2END IFEND IF满足条件？满足条件？步骤步骤1步骤步骤1是是否否满足条件？满足条件？步骤步骤A是是否否11.11.算法的循环语句算法的循环语句DODO 循环体循环体LOOP UNTIL LOOP UNTIL 条件条件满足条件？满足条件？是是循环体循环体否否WHILEWHILE 条件条件 循环体循环体WENDWEND 循环体循环体满足条件？满足条件？是是否否12.12.辗转相除法辗转相除法第一步，给定两个正整数第一步，给定两个正整数m m，n(mn(mn).n).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r.r.第三步，第三步，m=nm=n，n=r.n=r.第

6、四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等的最大公约数等 于于m m；否则，返回第二步；否则，返回第二步.求两个正整数的最大公约数求两个正整数的最大公约数13.13.更相减损术更相减损术第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m-nm-n所得的差所得的差k.k.第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示.第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步

7、.求两个正整数的最大公约数求两个正整数的最大公约数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=vx+av=vx+ai i，i=i-1.i=i-1.第五步，判断第五步，判断i0i0是否成立是否成立.若是，则返回第若是，则返回第 二步；否则，输出多项式的值二步；否则，输出多项式的值v.v.求多项式求多项式f(x)=af(x)=an nx xn n

8、+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值的值15.k15.k进制化十进制的算法进制化十进制的算法110()110110nnknnnna aa aakakakak-=+LL第四步，判断第四步，判断in in 是否成立是否成立.若是，则若是，则输出输出b b的值；否则，返回第三步的值；否则，返回第三步.第一步，输入第一步，输入a a，k k和和n n的值的值.第二步，令第二步，令b=0b=0，i=1.i=1.第三步，第三步，i=i+1.i=i+1.1iibbak-=+16.16.十进制化十进制化k k进制的算法进制的算法第四步，若第四步，若q0q0，则，则a=qa

9、=q，返回第二步；，返回第二步；否则，输出全部余数否则，输出全部余数r r排列得到排列得到 的的k k进制数进制数.第一步，输入十进制数第一步，输入十进制数a a和基数和基数k k的值的值.第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排第三步，把所得的余数依次从右到左排 列列.除除k k取余法取余法 例例 某工厂某工厂20052005年的年生产总值为年的年生产总值为200200万万元，技术革新后预计以后每年的年生产总值元，技术革新后预计以后每年的年生产总值都比上一年增长都比上一年增长5%.5%.设计一个程序，输出预计设计

10、一个程序，输出预计年生产总值超过年生产总值超过300300万元的最早年份万元的最早年份.第三步，判断所得的结果是否大于第三步，判断所得的结果是否大于300.300.若是，则输出该年的年份；否则，若是，则输出该年的年份；否则，返回第二步返回第二步.第一步，输入第一步，输入20052005年的年生产总值年的年生产总值.第二步，计算下一年的年生产总值第二步，计算下一年的年生产总值.算法分析算法分析：巩固练习巩固练习（3 3）控制条件：）控制条件：当当“a a300”300”时终止循时终止循环环.（1 1）循环体：）循环体：设设a a为某年的年生产总值，为某年的年生产总值，t t为年生产总值的年增长量

11、，为年生产总值的年增长量，n n为年份，为年份，则则t=0.05at=0.05a，a=a+ta=a+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.05t=0.05*a aa=a+ta=a+tn=n+1n=n+1LOOP UNTIL aLOOP UNTIL a300300INPUT nINPUT nENDEND作业：作业：P50P50复习参考题复习参考题A A组：组：1 1，3.3.