1.1.1算法的概念(上课).ppt

1、普通高中课程标准试验教科书 人教A版数学必修3 第一章 算法初步,长汀一中 数学组 赖茂生 2008.2.17,1.1.1算法的概念 1.1.2程序框图与算法的基本逻辑结构,假设家中生火泡茶有以下几个步骤： a.洗刷茶壶 b.烧水 c.洗刷茶具 d.沏茶 请设计一个最优算法。,算法1：S1：洗刷茶壶 S2：烧水 S3：洗刷茶具 S4：沏茶,算法2： S1：洗刷茶壶 S2：烧水，同时洗刷茶具 S3：沏茶,思考？,第二步：解，得,第一步： - ，得 ,第三步：将 代入，得,1、算法的概念,“算法”通常是指按照一定规则解决的某一类问题的明确的和有效的步骤，而且能够在有限步之内完成。算法通常可以编成计

2、算机程序，让计算机执行并解决问题。,一般来说，“用算法解决问题” 可以利用 计算机帮助完成。,2、算法的特点,（1）有限性,即一个算法的步骤序列是有限的；,（2）确定性,即算法中的每一步应该是确定的并且能有效地执行且得到确定的结果；,（4）逻辑性,即算法从初始步骤开始，分为若干明确的步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，而且每一步都是正确无误的，从而组成了一个有着很强逻辑性的步骤序列；,（5）不唯一性,即求解一个问题的算法不一定是唯一的；,（6）普遍性,即很多具体的问题，都可以设计合理的算法去解决。,（3）有效性 算法中的每一个步骤都是可以在有限的时 间内完成的基本操作，

3、并能得到确定的结果 。,练习,1、判断下列关于算法的说法是否确：,1、求解某一类问题的算法是唯一的；,2、算法必须在有限步操作之后停止：,3、算法的每一步必须是明确的，不能有歧义或模糊：,4、算法执行后一定产生确定的结果：,一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,例,写出一个求有限整数序列中的最大值的算法。,解：算法如下： S1 先假定序列中的第一个整数为“最大值”。,S2 将序列中的下一个整数值与“最大值”比较，如果它大于此“最大值”，这时你就假定“最大值”是这个整数。,S3 如果序列中还有其他整数，重复S2。,S4 在序列中一直到没有可比的数

4、为止，这时假定的“最大值”就是这个序列中的最大值。,例1,任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数作出判定。,解：算法如下： S1 输入n。,S2 判断n是否等于2。若n2，则n是质数；若n2，则执行 S3。,S3 依次从2（n1）检验是不是n的因数，即整除n的数。若有这样的数，则n不是质数；若没有这样的数，则n是质数。,例2,写出一个求有限整数序列中的最大值的算法。,解：算法如下： S1 先假定序列中的第一个整数为“最大值”。,S2 将序列中的下一个整数值与“最大值”比较，如果它大于此“最大值”，这时你就假定“最大值”是这个整数。,S3 如果序列中还有其他整数，重复S2

5、。,S4 在序列中一直到没有可比的数为止，这时假定的“最大值”就是这个序列中的最大值。,例3,写出求 的值的算法。,解法1：算法如下： S1 先求 ，得到结果2； S2 将第一步所得结果2再乘以3，得到结果6。 S3 将6再乘以4，得到24； S4 将24再乘以5，得到120； S9 将362880再乘以10，得到3628800，即是最后的结果。,例,用二分法设计一个求方程 的近似正根的算法，精确度0.05。,解,练习 任意给定一个正实数a，试设计一个算法求 以a为直径的圆的面积。,第一步：输入a的值.,第二步：_. 第三步：_. 第四步：输出圆的面积的值.,解,例,任意给定一个大于1的整数n

6、，试设计 一个程序或步骤对n是否为质数作出判断。,第一步：判断n是否等于2。若n2，则n是质数； 若n2，则执行第二步；,第二步：依次从2到（n-1）检验是不是n的因数， 即是否能整除n的数。若有这样的数，则n不是 质数；否则，n是质数。,解：,练习 任意给定3个正实数，试设计一个算法，判断 分别以这三个数为三边边长的三角形是否存在。,第一步: 输入三个正实数a , b , c.,解,第二步：？,小结：,算法的特征是什么？,算法的概念：算法通常指可以用来解决的某 一类问题的步骤或程序，这些步骤或程序必须是明 确的和有效的，而且能够在有限步之内完成的。,2、算法的特点,（1）有限性,即一个算法的

7、步骤序列是有限的；,（2）确定性,即算法中的每一步应该是确定的并且能有效地执行且得到确定的结果；,（4）逻辑性,即算法从初始步骤开始，分为若干明确的步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，而且每一步都是正确无误的，从而组成了一个有着很强逻辑性的步骤序列；,（5）不唯一性,即求解一个问题的算法不一定是唯一的；,（6）普遍性,即很多具体的问题，都可以设计合理的算法去解决。,（3）有效性 算法中的每一个步骤都是可以在有限的时 间内完成的基本操作，并能得到确定的结果 。,二、 算法的表示,1. 用自然语言表示,2. 用程序框图表示,终端框（起止框）,处理框,输入输出框,判断框,流程

8、线,常用流程图符号（程序框）,表示一个算法的起始和结束,表示一个算法输入和输出的信息,判断某一条件是否成立，成立时在 出口处标明“是”或“Y”；不成立时 标明“否”或“N”.,赋值、计算,表示流程的路径和方向,二、 算法的表示,1. 用自然语言表示,2. 用程序框图表示,第一步：判断n是否等于2. 若n=2,则n是质数;若n2, 则执行第二步. 第二步:依次从2到(n-1)检验是不是n的因数, 即整数n 的数, 若有这样的数, 则n 不是质数; 若没有这样的 数, 则n 是质数.,例1 任意给定一个大于1的整数n ，试设计一个程序 或步骤对n是否为质数做出判定。,二、 算法的表示,1. 用自然

9、语言表示 优点是使用日常用语, 通俗易懂 缺点是文字冗长, 容易出现歧义,2. 用程序框图表示: 用图框表示各种操作 优点是直观形象, 易于理解,比较自然语言与程序框图表示方法的各自特点,顺序结构,条件结构,循环结构,P,A,三种基本结构（表示一个良好算法的基本单元）,顺序结构,条件结构（选择结构）,循环结构,While（当型）循环,Until（直到型）循环,成立,不成立,顺序结构,由若干个依次执行的处理步骤组成的。,例1 已知一个三角形的三边边长分别为2、3、4，利用 海伦-秦九韶公式设计一个算法，求出它的面积，画出 它的程序框图.,条件结构（选择结构）,算法的流程根据条件是否成立有不同的流

10、向,例2 任意给定3个正实数，设计一个算法， 判断分别以这3个数为三边边长的三角形是 否存在.画出这个算法的程序框图.,例3 设计房租收费的算法,其要求是:住房面积80平方米以内,每平方米收费3元,住房面积超过80平方米时,超过部分,每平方米收费5元.输入住房面积数,输出应付的房租.,算法分析：,第一步：输入住房面积S,第二步：根据面积选择计费方式：如果S小于或等于80，则租金为M=s3，否则为M=240+(S-80)5,第三步：输出房租M的值。,小结：,算法的特征是什么？,算法的概念：算法通常指可以用来解决的某 一类问题的步骤或程序，这些步骤或程序必须是明 确的和有效的，而且能够在有限步之内完成的。,2、算法的特点,（1）有限性,即一个算法的步骤序列是有限的；,（2）确定性,即算法中的每一步应该是确定的并且能有效地执行且得到确定的结果；,（4）逻辑性,即算法从初始步骤开始，分为若干明确的步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，而且每一步都是正确无误的，从而组成了一个有着很强逻辑性的步骤序列；,（5）不唯一性,即求解一个问题的算法不一定是唯一的；,（6）普遍性,即很多具体的问题，都可以设计合理的算法去