数学：第一章《算法初步》课件(新人教A版必修3)96808PPT课件

1、知识结构t57301p2算法程序框图算法语句辗转相除法与更相减损术 秦九韶算法 进位制第1页/共20页知识梳理1.1.算法的概念 在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法. . 用程序框、流程线及文字说明来表示算法的图形称为程序框图. .2.2.程序框图的概念3.3.程序框、流程线的名称与功能第2页/共20页图形符号 名 称 功 能 终端框 （起止框） 输入、输出框 处理框 （执行框） 判断框 流程线 表示一个算法的起始和结束 表示一个算法输入和输出的信息 赋值、计算 判断某一条件是否成立，成立时在出口处标明“是”或“Y”Y”；不成立时标明“否”或“N” N” 连接程序框

2、，表示算法步骤的执行顺序 第3页/共20页4.4.算法的顺序结构（1 1）概念： 由若干个依次执行的步骤组成的逻辑结构，称为顺序结构. .（2 2）程序框图：步骤n步骤n+1第4页/共20页5.5.算法的条件结构（1 1）概念： 由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为条件结构. .（2 2）程序框图：满足条件？步骤A步骤B是否满足条件？步骤A是否第5页/共20页6.6.算法的循环结构（1 1）概念： 由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为循环结构. .（2 2）程序框图：循环体满足条件？是否循环体满足条件？是否第6页/共20页7.7.算法的输入语句INPUT

3、“INPUT “提示内容”；变量8.8.算法的输出语句PRINT “PRINT “提示内容”；表达式9.9.算法的赋值语句变量= =表达式第7页/共20页10.10.算法的条件语句IF IF 条件 THENTHEN 语句体END IFEND IFIF IF 条件 THENTHEN 语句体1 1ELSEELSE 语句体2 2END IFEND IF满足条件？步骤1步骤1是否满足条件？步骤A是否第8页/共20页11.11.算法的循环语句DODO 循环体LOOP UNTIL LOOP UNTIL 条件满足条件？是循环体否WHILEWHILE 条件 循环体WENDWEND 循环体满足条件？是否第9页/

4、共20页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；否则，返回第二步；否则，返回第二步. . 求两个正整数的最大公约数第10页/共20页13.13.更相减损术第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn). 第二步，计算第二步，计算m-nm-n所得的差所得的差k. k. 第三步，比较第三步，比较n

5、n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m m；否则，返回第二步；否则，返回第二步. . 求两个正整数的最大公约数第11页/共20页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=v

6、x+ai i，i=i-1.i=i-1.第五步，判断第五步，判断i0i0是否成立是否成立. .若是，则返回第若是，则返回第 二步；否则，输出多项式的值二步；否则，输出多项式的值v. v. 求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0的值第12页/共20页15.k15.k进制化十进制的算法110( )110110nnknnnna aa aakakakak-=?+?LL第四步，判断第四步，判断in in 是否成立是否成立. .若是，则若是，则输出输出b b的值；否则，返回第三步的值；否则，返回第三步. .第一步，输入第一步，

7、输入a a，k k和和n n的值的值. .第二步，令第二步，令b=0b=0，i=1.i=1.第三步，第三步， ，i=i+1.i=i+1.1iibbak-=+?第13页/共20页16. 16. 十进制化k k进制的算法第四步，若第四步，若q0q0，则，则a=qa=q，返回第二步；，返回第二步； 否则，输出全部余数否则，输出全部余数r r排列得到排列得到 的的k k进制数进制数. .第一步，输入十进制数第一步，输入十进制数a a和基数和基数k k的值的值. .第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排第三步，把所得的余数

8、依次从右到左排 列列. .除k k取余法第14页/共20页 例 某工厂20052005年的年生产总值为200200万元，技术革新后预计以后每年的年生产总值都比上一年增长5%.5%.设计一个程序，输出预计年生产总值超过300300万元的最早年份. .第三步，判断所得的结果是否大于300.300. 若是，则输出该年的年份；否则， 返回第二步. .第一步，输入20052005年的年生产总值. .第二步，计算下一年的年生产总值. .算法分析：巩固练习第15页/共20页（3 3）控制条件：当“a a300”300”时终止循环. .（1 1）循环体：设a a为某年的年生产总值，t t为年生产总值的年增长量，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.循环结构：第16页/共20页开始n=2005a=200t=0.05aa=a+tn=n+1a300？结束输出n是否程序框图：第17页/共20页程序：开始n=2005a=200t=0.05aa=a+tn=n+1a300？结束输出n是否n=2005n=2005a=200a=200DODOt=0.05t=0.05* *a aa