算法初步B2.ppt

1、2010年暑假新课程培训,北京市高中数学课改培训指导组,人民教育出版社数学B版,算 法 初 步,一、算法的含义,1.什么是算法？ 算法就是能够在有限步产生问题结果的一系列的数 学步骤（大不列颠百科全书）。 现代意义上的“算法”通常是指可以用计算机来解决 的某一类问题的程序或步骤。,2.算法语句的特点,有穷性：一个算法必须要保证在执行有限步骤后能够得出结果.,确定性：算法的每一个步骤必须有确切的定义，不能含糊不清。,可行性：设计出的算法能够精确地运行，算法 中的每一个步骤都是可以执行的。,逻辑性：一个算法从它的初始步骤开始，前一步是后一步的前提，只有执行完前一步才能进行下一步，从而组成了一个有着

2、很强逻辑性的序列。 概括性：写出的算法必须能够解决某一类问题，并且能够重复使用。,二、算法的地位和作用,1有利于培养学生的思维能力 算法一方面具有具体化、程序化、机械化的特点， 同时又有 高度抽象性、概括性和精确性 对于一个具体算法而言，从算法分析到算法语言的实现，任 何一个疏漏或错误都将导致算法的失败 算法是思维的条理化、逻辑化！算法所体现出来的逻辑化 特点被有些学者看成是逻辑学继形式逻辑和数理逻辑之后逻辑 学发展的第三个阶段因此， 培养逻辑思维能力， 不仅可以 通过平面几何的论证， 代数运算的严密演绎等手段进行培 养， 还可以通过算法设计的学习来达到,2有利于培养学生理性精神和实践能力 由

3、于算法的具体实现可以和信息技术相联 系， 因而，算法有利于培养学生理性精神和 实践能力，也是实施探究性学习的良好素材,3.有利于学生数学应用意识的培养 算法教学注重“模仿、操作、探索”的操作过程；在 教学成果与评价中注重锻炼学生的实际应用能力，提升 学生的理性思维能力与模型化思想，让学生能够切身感 受数学的实用价值，从而有利于学生数学应用意识的培养。,4.有利于激发学生的人文价值观念与爱国 情操 算法内容中为学生提供了丰富的中国古代算法案例的阅读内容，这些案例蕴涵了丰富的算法思想，通过阅读中国古代算法案例，体会中国数学对世界数学发展的杰出贡献，有利于激发学生的人文价值观念与爱国情操。,三、学

4、习 目 标,通过对解决具体问题过程与步骤的分析，体会算法的思想，了解算法的含义。,通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程。理解程序框图的三种基本逻辑结构：顺序、条件分支、循环。,经历将具体问题的程序框图转化为程序语句的过程，理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句，进一步体会算法的基本思想。 通过学习中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。,重 点 和 难 点,重点：是理解算法的概念掌握算法的三种 基本结构，运用基本算法语句编写程序 解决实际问题。,难点：循环语句,运用基本算法语句编写 程序解决实际问题。,2010年考试

5、说明,四、教学建议,1.重视算法思想的培养，经历运用自然语言、程序框图和基本算法语句解决具体问题的过程，树立算法化的思维模式 。 注意不要把算法上成算法语言课或程序设计课。,四、 教学建议,2.加强典型数学实例教学、注重“模仿、操作、探索”的过程 (1)要注重典型实例说明； (2)体验从数学语言、程序框图到程序语句的逐步精确的过程； (3)采用螺旋上升、渐次递进的方式展开教学。,四、教学建议,. 突出重点、解决难点、抓住关键 (1) 多举一些数学实例，体现数学与算法的有机结合； (2) 例习题的配备要广一些，难度要小一些； (3) 注意激发兴趣。,四、教学建议,4.如果条件允许，可以让学生上机

6、实现，或模拟上机实现，这是检验学生学习算法的一种方式，也是学生比较感兴趣的部分。 5. 适当与其它知识融合，借助算法复习已学知识，也可以尝试数学史与算法教学的整合。,第1课时：算法的概念 课时: 2节。,教学要求： 通过对解决具体问题过程与步骤的分析（如二元一次方程组求解等问题），体会算法的思想，了解算法的含义。 能用自然语言描述具体问题的算法。,具体建议,以二元一次方程组的求解为例：,第一步,第二步,第三步,数学中的算法数学中引例：二元一次方程组实际问题的求解 列出二元一次方程组，解具体的二元一次方程组,用自然语言概括解法,例：二元一次方程组的求解,第一步,第二步,第三步,第四步,第五步,将

7、该解法推广到一般的二元一次方程组（含字母系数）,完善细节 整理解题步骤，用自然语言表述,在这节课的教学中 （1）通过分析探究求解二元一次方程组的算法活动体会 概念与思想； （2）讲清算法与解法的关系： 算法由解法提炼而得，但不等于解法； 算法与解法既有联系，又有区别，它们之间是一般 和特殊的关系，也是抽象与具体的关系。算法的获得 要借助一般意义上具体问题的求解方法，而任何一个 具体问题都可以利用这类问题的一般算法来解决。,第1课时：算法的概念,1.1.2程序框图：课时：1节.,重点：框图的概念以及画框图的规则； 难点：理解框图符号的意义。 建议：最好通过前面讲过的实例介绍每个框图 符号所表达的

8、意义.,程序框图,1.1.3算法的三种基本逻辑结构和框图表示,课时: 3节。 重点：对算法三种逻辑结构的理解； 难点：算法的框图表示。 注意: 1. 由数学语言向框图的过渡； 2. 通过实例熟悉三种逻辑结构和框图，并巩固上一节的画框图规则。,算法的三种基本逻辑结构, 顺序结构,顺序结构描述的是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行。,算法的三种基本逻辑结构,条件分支结构,在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向.由这种根据作出判断，再决定执行哪一种操作的结构为条件分支结构.,算法的三种基本逻辑结构,循环结构,根据指定的条件是否重

9、复执行一条或多条指令的控制结构称为循环结构.即从某处开始，按照一定的条件反复执行某一处理步骤.,例题 写出能找出任意3个整数a、b、c中最大值 的算法.,解：,S1 max=a.,S2 如果bmax,则 max=b.,S3 如果Cmax,则 max=C.,S4 max就是a、b、c中最大值,例题解析,数学语言,解：,在a、b、c中找出最大的数的算法是：,S1 输入a、b、c.,S2 如果ab且ac，则输出a.,否则，执行S3.,S3 如果bc，则输出b.,否则，执行S4.,S4 输出c.,程序框图为：,例 写出求1+2+3+100的值 的一个算法,数学语言： S1 sum=0. S2 i=1.

10、 S3 sum = sum + i. S4 i=i+1. S5 若i100，则返回执行S3，S4，S5； 若i100，则结束. S6 输出sum.,S1 sum=0 S2 i=1 S3 sum=sum+i S4 i=i+1 S5 若i100，则返回执S3，S4，S5； 若i100，则算法结束。 S6 输出sum,否,1.赋值语句,（1）在表述一个算法时，经常要引入变量，并赋给 该变量一个值。用来表明赋给某一个变量一个具体 的确定的值的语句叫做赋值语句。,（2）赋值语句中的一般格式是： 变量名 = 表达式,其中：赋值语句中的“ = ”号，称为赋值号。,1.2基本算法语句 课时：4节,（3）赋值语

11、句的作用：先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值。,例如：,a = 3; b = 4; c = 5;,P = ( a + b + c )/2 ;,S = sqrt( p( p a )( p b)( p c ) );, 实质是海仑公式,（4）注意的问题：,“ = ”赋值号左边只能是变量，不能是表达式。,“ = ”赋值号左右不能对换。,赋值号“ = ”与数学中的等号“ = ”的意义不同。,一个赋值语句只能给一个变量赋值，不能给两 个或多个变量赋值。,不能用赋值语句进行代数式的运算。,例 说出下列赋值语句的意义，并指出 其条件下a、b、c的值。,a

12、 = 8; b = 6 ; c = -1; a = b ; b = a + b + c ; c = b a + c ;,a b c,6 6 -1,6 11 -1,6 11 4,其结果是：6， 11， 4,2.输入语句,（1）在某些算法中，变量的初值要根据情况经常地改变。一般我们把程序和初始数据分开，每次算题时，不改变程序部分，只输入相应的初始数据即可。这个过程的程序语句用“输入语句”控制。,（2）在Scilab4.0中输入语句之一是“input” 输入语句的一般格式是： 变量名 = input ( “提示信息” ）,（3）输入语句的意义：在于把程序和初始数据分开， 达到用程序解决一类问题的目的

13、。,例 任给三个变量a、b、c赋值，计算三个数的算术平均数。,解： a = input ( “ a = ” ）; b = input ( “ b = ” ）; c = input ( “ c = ” ）; aver = ( a + b + c )/3 ; print(% io(2),aver),3.输出语句,（1）任何求解问题的算法，都要把求解的结果“输出”。所以在任何程序语言中也必须有“输出语句” 来控制输出。,（2）在Scilab4.0中主要介绍的输出语句是“print”,输出语句“print”的一般格式是： print(%io(2),表达式),（3）在输出语句 “print(%io(2)

14、,表达式)”中应 注意的问题, print(%io(2),表达式)中的“表达式”是指输出的数据（变量、常量、表达式等）, print(%io(2),a,b,c)在屏幕上输出的结果的顺序是c、b、a., print(%io(2),表达式)中的io表示 input-output(输入-输出），%io(2)表示在屏幕上输出。,例 写出下列运算输出的结果,（1）a=5; b=3; c=(a+b)/2; d=c*c; print(%io(2),d),（2）a=1; b=2; c=a+b; b=a+c-b; print(%io(2),a,b,c),d=16,a=1, b=2 ,c=3,4.条件语句,（1）

15、条件语句：处理条件分支结构的算法语句。,在 Scilab语言中的条件语句为 if 语句 和select case 语句.在教材中只研究 if 语句的应用。,如：写出求一元二次方程ax2+bx+c=0根的算法程序,a=input(“a=”); b=input(“b=”); C=input(“c=”); d=bb-4ac; if d0; disp(“no solution”) else t=sqrt (d); X1=(-b+t)/(2a) X2=(-b-t)/(2a) end,解：程序语言如下,(2)条件语句的一般格式：,if 表达式 语句序列1： else 语句序列2： end,if 表达式 语

16、句序列1 end,5.循环语句,（1）有规律的重复计算或者在程序中需要对某些语句进行重复的执行，这样就需要用循环语句进行控制。,（2）循环语句的格式, for循环语句的格式是：,for 循环变量=初值：步长：终值 循环体 end, while循环语句的格式是：,while 表达式 循环体 end,注意的问题,（1）“ for循环语句”是在循环次数已知时 使用的循环，在循环的次数未知时不能 使用。,（2）“while循环语句”是在未知循环次数 的条件下进行的循环，也可以在循环 次数已知的循环中使用。,例如：计算 1+2+3+-+100,for语句,S=0; for i=1:1:100 s=s+i

17、; end Print(%io(2),s),While语句,S=0; i=1; while i=100 s=s+i; i=i+1; end s,例 设计计算：246100的程序,for语句,S=0; for i=2:2:100; s=s*i; end s,While语句,S=1; i=2; while i=100 S=s*i; i=i+2; end,1.3中国古代数学中的算法案例,课时：2节。 建议：1、更相减损之术，执行程序，体会算法 2、割圆术：了解即可。 3、秦九昭算法：一方面：这个算法目前仍在广泛使用（也可叫霍纳法）；另一方面，教材中也给出了比较算法优劣的方法之一。,本节主要介绍的内容

18、：,一、更相减损之术（又称“等值算法”） -研究如何求二个正整数的最大公约数.,二、割圆术 -解决圆周率的近似值问题.,三、秦九韶算法 -解决求多项式函数值问题.,1.更相减损术（等值算法）：,例题 求78和36的最大公约数.,解：,（78，36）,（6，36）,（42，36）,（6，30）,（6，18）,（6，12）,（6，24）,（6，6）,所以，78和36的最大公约数为 6.,此种算法称为等值算法,另，辗转相除法：,（78，36）,（6，36）,所以，78和36的最大公约数为 6.,此种算法又欧几里得算法.,等值算法程序框图：,2.(刘徽）割圆术,1,hn,xn,设圆o的面积为S，其内接

19、正n边形的面积为Sn.,由于,所以正2n边形的面积等于：,S2n=Sn+nxn(1-hn)/2.,从而有,S2nSS2n+(S2n-Sn).,计算圆周率的不足近似值,计算圆周率的过剩近似值,3.秦九韶算法,研究已知一个一元n次多项式函数,P(x) = anxn + an-1xn-1 +- +a1x + a0,当x = x0 时，求P(x0)问题,我们以5次多项式为例，研究其算法.,f(x) = a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0,设,=（a5x4 + a4x3 + a3x2 + a2x +a1)x + a0,= (a5x3 + a4x2 + a3x + a2)x + a1)x + a0,= (a5x2 + a4x + a3)x + a2)x + a1)x + a0,= (a5x +a4)x + a3)x + a2)x+a1)x + a0,以上运算：加法进行了5次、乘法进行了5次，共进行了 5+5 =10次.,P(x) = a