第一章复习课_252080.ppt

第一章 算法初步复习课 * 主备人：唐强 王廷伟 向妍艳　 审核人：牟必继 温故而知新 知识结构 算法 程序框图 算法语句 辗转相除法与更相减损术 秦九韶算法 进位制 知识梳理 1.算法的概念 在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法. 用程序框、流程线及文字说明来表示算法的图形称为程序框图. 2.程序框图的概念 3.程序框、流程线的名称与功能 图形符号 名 称 功 能 终端框 （起止框） 输入、输出框 处理框 （执行框） 判断框 流程线 表示一个算法的起始和结束 表示一个算法输入和输出的信息 赋值、计算 判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N” 连接程序框，表示算法步骤的执行顺序 4.算法的顺序结构 （1）概念： 由若干个依次执行的步骤组成的逻辑结构，称为顺序结构. （2）程序框图： 步骤n 步骤n+1 5.算法的条件结构 （1）概念： 由若干个在一定条件下才会被执行的步骤组成的逻辑结构，称为条件结构. （2）程序框图： 满足条件？ 步骤A 步骤B 是 否 满足条件？ 步骤A 是 否 6.算法的循环结构 （1）概念： 由按照一定的条件反复执行的某些步骤组成的逻辑结构，称为循环结构. （2）程序框图： 循环体 满足条件？ 是 否 循环体 满足条件？ 是 否 7.算法的输入语句 INPUT “提示内容”；变量 8.算法的输出语句 PRINT “提示内容”；表达式 9.算法的赋值语句 变量=表达式 10.算法的条件语句 IF 条件 THEN 语句体 END IF IF 条件 THEN 语句体1 ELSE 语句体2 END IF 满足条件？ 步骤1 步骤1 是 否 满足条件？ 步骤A 是 否 11.算法的循环语句 DO 循环体 LOOP UNTIL 条件 满足条件？ 是 循环体 否 WHILE 条件 循环体 WEND 循环体 满足条件？ 是 否 12.辗转相除法 第一步，给定两个正整数m，n(mn). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步. 求两个正整数的最大公约数 13.更相减损术 第一步，给定两个正整数m，n(mn). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表 示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步. 求两个正整数的最大公约数 14.秦九韶算法 第一步，输入多项式的次数n，最高次 项的系数an和x的值. 第二步，令v=an，i=n-1. 第三步，输入i次项的系数ai. 第四步，v=vx+ai，i=i-1. 第五步，判断i≥0是否成立.若是，则返回第 二步；否则，输出多项式的值v. 求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值 15. 十进制化k进制的算法 第四步，若q≠0，则a=q，返回第二步； 否则，输出全部余数r排列得到 的k进制数. 第一步，输入十进制数a和基数k的值. 第二步，求出a除以k所得的商q，余数r. 第三步，把所得的余数依次从右到左排 列. 除k取余法 例1、某工厂2005年的年生产总值为200万元，技术革新后预计以后每年的年生产总值都比上一年增长5%.设计一个程序，输出预计年生产总值超过300万元的最早年份. 第三步，判断所得的结果是否大于300. 若是，则输出该年的年份；否则， 返回第二步. 第一步，输入2005年的年生产总值. 第二步，计算下一年的年生产总值. 算法分析： 巩固练习 （3）控制条件：当“a300”时终止循环. （1）循环体：设a为某年的年生产总值，t为年生产总值的年增长量，n为年份，则t=0.05a，a=a+t，n=n+1. （2）初始值：n=2005，a=200. 循环结构： 开始 n=2005 a=200 t=0.05a a=a+t n=n+1 a300？ 结束 输出n 是 否 程序框图： 开始 n=2005 a=200 t=0.05a a=a+t n=n+1 a300？ 结束 输出n 是 否 程序： n=2005 a=200 DO t=0.05*a a=a+t n=n+1 LOOP UNTIL a300 PRINT n END 例2、一个球从100m高处自由落下,每次着地后又跳回到原高度的一半再落下.