必修算法教材分析.ppt

普通高中课程标准实验教科书（人教-A版）数 学-3（必修）教学参考意见,海淀区高中新课程数学研修组,算法的历史,周髀算经和九章算术中均有记载“算法”原为“algorism”，意思是阿拉伯数字的运算法则，在18世纪演变为“algorithm”。欧几里得算法被人们认为是数学史上第一个算法。第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用的。,算法是计算机理论和实践的核心。例如，美国著名网络公司Googl的“网页排名”的算法中超越了很多搜索引擎公司，而且在学术界,这个算法被公认为是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程（Information Retrieval）的教程。,文章算法的力量-李开复,算法并不局限于计算机和网络例如：在高能物理研究方面，很多实验每秒钟都能有几个TB的数据量。但因为处理能力和存储能力的不足，科学家不得不把绝大部分未经处理的数据丢弃掉。可是新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类基因的研究，就可能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可能避免下一个911的发生。在气象方面，算法可以更好地预测未来天灾的发生，以拯救生命。所以，当今信息数据飞速增长的大环境下，算法的重要性不是在日益减小，而是在日益加强。,数学课程标准 必修3,算法初步单元教学设计,一、课标要求,（1）算法的含义、程序框图通过对解决具体问题过程与步骤的分析（如，二元一次方程组求解等问题），体会算法的思想，了解算法的含义.通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程.在具体问题的解决过程中，理解程序框图的三种基本逻辑结构：顺序、条件分支、循环.,（2）基本算法语句经历将具体问题的程序框图转化为程序语句的过程，理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句，进一步体会算法的基本思想.（3）通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献.,数学课程标准 必修3算法初步,算法初步单元教学设计,一.算法初步单元内容与结构,二.算法初步单元教学课时安排,三.算法初步单元教学目标分析,四.算法初步单元教学重点与难点分析,五.算法初步单元展开方式和特点,六.算法初步单元内容教学设计,七.算法初步单元教学的几点建议,一.算法初步单元内容与结构,1.内容,算法的基本结构,算法的基本思想,顺序结构,选择结构,循环结构,算法的基本语句,输入、输出语句,赋值语句,条件语句,循环语句,算法,一.算法初步单元内容与结构,2.结构,二.算法初步单元教学课时安排,1.1算法与程序框图 约4课时,1.2 基本算法语句 约4课时,1.3算法案例 约 2课时,复习与小结 约 2课时,单元小测 约 2课时,三.算法初步单元教学目标分析,1通过对解决具体问题过程与步骤的分析，体会算法的思想，了解算法的含义。,2通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程。在具体问题的解决过程中，理解程序框图的三种基本逻辑结构：顺序结构、选择结构、循环结构。,4通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。,3经历将具体问题的程序框图转化为程序语句的过程，理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句，进一步体会算法的基本思想。,四.算法初步单元教学重点与难点分析,1重点（1）理解算法的含义；（2）掌握算法的基本结构；（3）会用算法语句解决简单的实际问题。,2难点（1）程序框图；（2）变量与赋值；（3）循环结构；（4）算法设计。,五.算法初步单元展开方式与特点,1展开方式,自然语言,自然语言,自然语言,程序框图,程序框图,算法语句,五.算法初步单元展开方式与特点,2特点,螺旋上升、分层递进 整合渗透、前呼后应 三线合一、横向贯通 弹性处理、多样选择,六.算法初步单元教学内容分析,标准中对算法学习的设计主要分两方面：,一.是在必修3中集中学习算法的基础知识，此时应强调算法的基本思想、基本结构、基本语句；,二.是算法的思想贯穿于整个高中数学课程的始终，是高中数学课程的一条主线。在适当的内容中，不断地让学生用算法解决相关问题。,这个单元里，通过案例教学，使得学生在由简单应用到解决复杂问题的过程里循序渐进接受算法的基本思想，从而掌握所学知识及相应的思维方法。在整个单元教学过程中，应遵守以下几个原则：,采用案例教学方式；从学生的“最近发展区”创设问题情境；注重算理分析。,六.算法初步单元内容教学设计,1.算法的概念（描述性定义）（人教社B版）算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题。（人教社A版）在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。（北师大版）在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，通常把这些步骤称为解决这些问题的算法。这个描述反映了算法的基本思想。,算法的概念教学设计,（苏教版）对一类问题的机械的、统一的求解方法称为算法各种版本的共同的特点由实际问题或者一个数学问题解决的过程抽象出算法的概念.,（1）寓教于乐，体会算法思想,在算法的学习中，首先从学过的典型实例中，分析其中蕴含的算法思想，体会算法“通用化”、“机械化”、“程序化”的特点以及对算法步骤“明确”、“有效”、“有限”的要求。,（分步，分类）,第一步：把冰箱门打开第二步：把大象放进去第三步：把冰箱门带上,设置情境，提高学生学习兴趣，通过问题解决体会算法的概念,情境1：把大象放冰箱，统共分几步?,体会分步，逻辑，有限算法思想特征,设置情境，提高学生学习兴趣，通过问题解决体会算法的概念,情境2：跳青蛙,设置情境，提高学生学习兴趣，通过问题解决体会算法的概念,情境3：一个人带着三只狼和三只羊过河，只有一条船，同船可容纳一个人和两只动物，没有人在的时候，如果狼的数量不少于羊的数量就会吃羊。该人如何将动物转移过河？请设计步骤？（此例在中国科技馆有互动展示）,算法自然语言描述：第一步：人带两只狼过河，并自己返回；第二步：人带一只狼过河，自己返回；第三步：人带两只羊过河，并带两只狼返回；第四步：人带一只羊过河，自己返回；第五步：人带两只狼过河,通过具体实例，体会算法的基本特征（分步，逻辑性，有限性）比较一下自然语言和图形语言的区别，自然引出下节内容，程序框图,现在学习的算法不同于求解一个具体问题的方法,它有如下的要求:,(1)写出的算法,必须能解决一类问题,并能重复使用;,(2)算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且经过有限步后能得结果.,算法的含义广义：算法通常是指按照一定规则解决某一类问题的明确和有限的步骤.现代：指可以用计算机来解决的某一类问题的程序或步骤.,（2）通过简单算法案例的分析，体会算法的基本特征,给出一个算法案例，让学生对这个算法进行分析，体会算法的基本特征，获得算法的结果，进一步感受算法的基本思想。例如：,（3）通过案例进一步培养提炼算法基本思想与合理表述算法的能力,例如通过对“电视购物”、“二分法求方程的根”等案例教学，分析、抽象、程序化解决问题的过程，体会算法的思想，发展学生合理表述算法的能力，发展对具体问题的过程与步骤的分析能力，发展从具体问题中提炼算法思想的能力，发展有条理地、清晰地思维的能力。,2程序框图和基本结构的教学设计,（1）创设问题情境，引入“变量”与“赋值”,例.设计算法求一个学生数学、语文、英语、化学、物理五门课的平均成绩。,用a、b、c、d、e来表示数学、语文、英语、化学、物理的成绩，用S表示“和”,（2）理解“变量”与“赋值”,在算法过程中，其值不能被改变的量称为常量，其值可以被改变的量称为变量.,赋值：赋给某一个变量一个具体的确定值。赋值语句的一般格式：变量名=表达式“=”叫做赋值号赋值语句的作用：先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值。,（2）理解“变量”与“赋值”,在算法过程中，其值不能被改变的量称为常量，其值可以被改变的量称为变量.,赋值：赋给某一个变量一个具体的确定值。赋值语句的一般格式：变量名=表达式“=”叫做赋值号赋值语句的作用：先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值。,问题：x=1,y=5,现在要交换x,y的值,如何实现,注：赋值号左边只能是变量名字，而不能是表达式或数；赋值号左右不能对换；不能利用赋值语句进行代数式(或符号)的演算；赋值符号不能等同于数学中的等号.,如：2y=x、11=x是错误的；,如“x=A”、“A=x”的含义运行结果是不同的；,如y=y+1,与数学中的方程是有区别的.在计算机中表示将变量y的值取出,进行加1运算,重新存入变量y.,如y=x2-1=（x+1)(x-1)是不能实现的.,(注：苏教版中，赋值语句的一般格式为“变量名表达式”，),i=i+1,（3）通过解决算法案例，加强对“变量”与“赋值”的理解,（4）创设问题情境，初步感受程序框图的特点,开始,输入五科成绩：,计算,输出五科平均成绩,结束,程序框图又称流程图：是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。,用程序框图来表达算法，算法的基本逻辑结构展现的非常清楚,画程序框图的规则：（1）使用标准的框图的符号；（2）框图一般按从上到下、从左到右的方向画；（3）除判断框外，其他框图符号只有一个进入点和一个退出点.判断框是具有超过一个退出点的唯一符号；（4）一种判断框是二择一形式的判断，有且仅有两个可能的结果；另一种是多分支判断，可能有几种不同的结果；（5）在图形符号内描述的语言要非常简练清楚.,（5）通过上述案例，掌握顺序结构的特点,开始,输入五课成绩：,计算,输出五课平均成绩,结束,顺序结构：是由若干个依次执行的处理步骤组成的。,顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤。它的一般形式如右图所示，A框和B框是依次执行的，只有在执行完A框指定的操作后，才能接着执行B框所指定的操作。,A,B,（6）通过案例，了解条件分支结构的特点,条件分支结构主要用在一些需要依据条件进行判断的算法中，如分段函数的求值，数据的大小关系等问题中。,开始,输入x,x0？,是,y=x+2,y=x-2,结束,否,输出y,选择结构是指在算法中通过对条件的判断，根据条件是否成立而选择不同流向的算法结构。它的一般形式如右图所示，此结构中包含一个判断框，根据给定的条件P是否成立而选择执行A框或B框。无论P条件是否成立，只能执行A框或B框之一，不可能同时执行A框和B框，也不可能A框、B框都不执行。一个判断结构可以有多个判断框。,（7）通过模仿、操作、探索，设计程序框图表达解决问题的过程，掌握条件分支结构,开始,输入正数,a+bc,a+cb,b+ca,否,否,否,是,输出“能画三角形”,计算,计算,输出S,输出“不能画三角形”,结束,是,是,（8）创设问题情境，初步了解循环结构的特点,例.设计一个计算1+2+100的值的算法.,按照逐一相加的程序进行第一步:计算1+2，得到3；第二步:将第一步中的运算结果3与3相加，得到6；第三步:将第二步中的运算结果6与4相加，得到10；第九十九步：将第九十八步中的运算结果4950与100相加，得到5050.,简化描述：第一步：sum=0；第二步：sum=sum+1；第三步：sum=sum+2；第四步：sum=sum+3；第一百步：sum=sum+99；第一百零一步：sum=sum+100第一百零二步：输出sum.,开始,i=1,S=0,i=i+1,S=S+i,i100？,是,否,输出S,结束,判断框,i 叫做计数变量,(用于记录循环次数),S叫做累加变量,(用于记录累加结果),循环体,循环变量,循环结构：在一些算法中，也经常会出现从某处开始，按照一定条件，反复执行某一步骤的情况，这种结构称为循环结构.,循环体：反复执行的步骤称为循环体.,计数变量：在循环结构中，通常都有一个起到循环计数作用的变量，这个变量的取值一般都含在执行或终止循环体的条件中.,（1）直到型循环结构 如下右图所示，它的特征是在执行了一次循环后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止.,满足条件？,否,循环体,是,循环结构可细分为两类：,（2）当型循环结构 如图所示，它的特征是在每次执行循环体前，对条件进行判断，当条件满足时，执行循环体，否则终止循环。,满足条件？,否,循环体,是,第一，我们要确定算法中将要反复执行的部分，即循环体；,一般来说，在画出算法流程图之前，我们首先要确定三件事：,第二，确定循环变量，它的初始值和终值；,第三，确定循环的终止条件。,开始,i=1,S=0,i=i+1,S=S+i,i100？,是,否,输出S,结束,i 叫做计数变量,(用于记录循环次数),S叫做累加变量,(用于记录累加结果),循环体,循环变量,i=i+2,（9）通过案例分析，理解循环结构,例.下面是一个计算2+4+6+100的算法，请补充完整。,开始,i=2,S=0,S=S+,i,是,否,输出S,结束,i,100？,开始,i=2,S=0,S=S+i,i,是,否,输出S,结束,100？,i=i+2,直到型循环结构表示,i=i+2,开始,i=2,S=0,S=S+,i,是,否,输出S,结束,100？,i,i=i+2,开始,i=2,S=0,S=S+,i,是,否,输出S,结束,i,100？,i=i+1,开始,i=1,S=0,S=S+,i,是,否,输出S,结束,i,100？,它们的不同点在何处？,（10）通过模仿、操作、探索，设计程序框图表达解决问题的过程，掌握循环结构,例画出流程图求使得1+4+7+(3n-2)3000成立的最小自然数n.,循 环 体：S=S+_，i=i+_,循环变量：i计数变量，S累加变量,循环的终止条件：S3000,开始,i=0,S=0,i=i+1,S=S+(3i-2),S3000？,是,否,输出i,结束,直到型循环结构表示,当型循环结构表示,开始,i=1,S=0,i=i+3,S=S+i,S3000？,是,否,输出i,结束,重视基础知识的理解和掌握,学习算法首先要掌握算法概念和算法的基本思想，其次，理解程序框图的三种基本逻辑结构：顺序结构、条件分支结构、循环结构；理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句的含义。另外，在算法复习时要注意介绍一些经典的算法案例，以教材为主，也要关注将算法思想渗透到后续的高中数学课程的学习中去，尽可能地运用算法解决相关问题。,总之：,算法教学过程中应尽量使用信息技术,算法教学中，应当鼓励学生尽可能上机尝试。上机能极大地提高学生学习算法的兴趣：不但可以检验算法的正确性以及算法的好坏，而且还可以通过改进算法而引起学生对算法的更深入思考。有助于提高学生的信息素养。,数学上学习算法的主要作用是使学生形成“算法思维”。,帮助学生清晰的思考问题、提高逻辑思维能力；将解决具体问题的思路整理成算法的过程是一个思维的整理过程，是一个条理化，精确化和逻辑化的过程。希望学生能把这种思维习惯迁移到日常生活中。如立体几何证明的表述讲究严谨的逻辑关系。,关于算法在高考题中的特点及变化,（08海南文）右面的程序框图，如果输入三个实数a、b、c，要求输出这三个数中最大的数，那么在空白的判断框中，应该填入下面四个选项中的（）c xB.x cC.c bD.b c,答案:A,（07海南文、理5）如果执行下面的程序框图，那么输出的（）2450.25002550.2652,答案:C,（07广东文7、艺术理6）下面左图是某县参加2007年高考的学生身高条形统计图，从左到右的各条形表示的学生人数依次记为A1、A2、A10（如A2表示身高（单位：cm）（150，155）内的学生人数）.右图是统计左图中身高在一定范围内学生人数的一个算法流程图.现要统计身高在160180cm(含160cm,不含180cm)的学生人数，那么在流程图中的判断框内应填写的条件是（）A.i6 B.i7 C.i8 D.i9,答案:C,开始,输入n,结束,输出,否,（07山东文、理10）阅读右边的程序框图，若输入的n是100，则输出的变量S和T的值依次是（）A2550，2500B2550，2550C2500，2500D2500，2550,答案:A,是,（07海南文、理5）如果执行下面的程序框图，那么输出的（）2450.25002550.2652,答案:C,如何对高考题进行变式教学呢？,变式1,开始,k=1,？,是,否,结束,输出,是,否,k=1,结束,开始,程序框图如右图所示,若判断框内分别填写“k50”与“k50”，则执行程序后输出结果的差为（）100.10298.2,答案:A,变式2,A图,下面两个流程图，若使程序执行完后输出的结果相同，则图A和图B中的初始值k的赋值符合条件的为（）k=1，k=1.k=1，k=0 k=0，k=1.k=2，k=1,答案:B,（2009福建卷理）阅读右图所示的程序框图，运行相应的程序，输出的结果是（）A2 B.4 C.8 D.16,答案:C,3算法基本语句的教学设计,算法的基本结构是算法的核心，我们已经在前面做了重点分析。而程序框图和算法语句只是算法的两种表述方式，所以在这里对算法的基本语句不做重点阐述。但是要注意的是：每个版本的教材使用的计算语言不一致，在后继的信息技术学习中学生会重点学习计算机语言，所以不要过多关注各个算法语句的使用细枝末节，重点还是注重算理分析。,学生编写程序1：个人所得税计算,此单元教学可以发挥学生的主体性,此单元教学可以发挥学生的主体性,学生编写程序2：四舍五入,1.赋值语句,在表述一个算法时，经常要引入变量，并赋给该变量一个值。用来表明赋给某一个变量一个具体的确定的值的语句叫做赋值语句。赋值语句中的格式是：变量名=表达式 其中，赋值语句中的“=”号，称为赋值号。,赋值语句的作用的方式是先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值。运算方向为右左示例：a=3；b=4；c=5；s=(a+b+c)/2；,1.赋值语句,a+b=2,a=2,2=a,b=a,a=b,a,b=2,=,1.赋值语句,需要注意的问题赋值号左边只能是变量，不能是表达式。,赋值号左右不能对换。,不能用赋值语句进行代数式的运算。一个赋值语句只能给一个变量赋值，不能给两个或多个变量赋值。,赋值号与数学中的等号的意义不同。,a b c8 6-1,6,11,4,1.赋值语句,例 12 说出下列赋值语句的结果。a=8;b=6;c=-1;a=b;b=a+b+c;c=b a+c;,2.输入语句,在某些算法中，变量的初值要根据情况经常地改变。一般我们把程序和初始数据分开，每次算题时，不改变程序部分，只输入相应的初始数据即可。这个过程的程序语句用“输入语句”控制。格式：变量名=input(输入提示语),2.输入语句,意义：在于把程序和初始数据分开，达到用程序解决问题的通用性。例 c=input(“chinese”)；m=input(math)；e=input(english);aver=(c+m+e)/3;,3.输出语句,任何求解问题的算法，都要把求解的结果“输出”。所以在任何程序语言中也必须有“输出语句”来控制输出。格式：print(%io(2),输出内容)注意：（1）多个变量值倒序输出（2）disp语句也表示输出,print(%io(2),a,b,c);c=3b=2a=1,a=1;b=2;c=a+b,3.输出语句,4.条件语句,处理条件分支结构的算法语句。格式：if 表达式 语句序列1；else 语句序列2；end,4.条件语句,格式：if 表达式1 语句序列1；elseif 表达式2 语句序列2；else 语句序列3；end,10,x10,x=1,4.条件语句,例 13 任给一实数x，求函数f(x)的值 f(x)=解 x=input(x);if x1 f=10；else f=0；end,10,x10,-1=x=1-10,x-1,4.条件语句,解 if x1 f(x)=f=10；else if x=-1 f=0；else f=-10；end,4.条件语句,例 14 写出求一元二次方程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,5.循环语句,有规律的重复计算或者在程序中需要对某些语句进行重复的执行，这样就需要用循环语句进行控制。,5.循环语句,格式：for 循环变量=初值:步长:终值 循环体；end例 S=0;for i=1:100 S=S+i；end,5.循环语句,格式：while 表达式 循环体；end例 i=1;S=0;while i=100 S=S+i;i=i+1；end,计算：2+4+6+8+100,scilab程序实现 k=1;S=0;while k=50 S=S+2*k;k=k+1;end print(%io(2),S);,scilab语言运行结果,编写Scilab程序,计算1!+2!+3!+4!+100!,【法一】用 for 语句实现 S=0;an=1;for i=1:100 an=an*i;S=S+an;end;disp(S,1!+2!+3!+.+100!=);,【法二】用while语句实现S=0;an=1;i=1while i=100 an=an*i;S=S+an;i=i+1;end;disp(S,1!+2!+3!+.+100!=);,4算法案例的教学设计,通过阅读中国古代数学中的算法案例，即了解先贤们的优秀成果，体会中国古代数学对世界数学发展的贡献，增强民族自豪感。有让学生借助问题情境的设置，亲身经历知识发生、发展的过程，构建学生的自身知识体系。,在案例教学的过程中，注意案例的选择应从算法的典型性、与以往知识的连续性和可接受性的角度出发，重在对案例算法的分析，使得学生能够通过案例的学习进一步理解算法的本质。,1、求两个正整数的最大公约数,（1）求25和35的最大公约数（2）求49和63的最大公约数,2、求8251和6105的最大公约数,所以，25和35的最大公约数为5,所以，49和63的最大公约数为7,辗转相除法（欧几里得算法）,观察用辗转相除法求8251和6105的最大公约数的过程,第一步 用两数中较大的数除以较小的数，求得商和余数 8251=61051+2146,结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。,第二步 对6105和2146重复第一步的做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。,为什么呢？,思考：从上述的过程你体会到了什么？,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例2 用辗转相除法求225和135的最大公约数,225=1351+90,135=901+45,90=452,显然37是148和37的最大公约数，也就是8251和6105的最大公约数,显然45是90和45的最大公约数，也就是225和135的最大公约数,S1：给定两个正整数m,n,S2：用大数除以小数，计算m除以n所得的余数；,S3：除数变成被除数，余数变成除数，即 m=n,n=r,S4：重复S2,直到余数为0，即 若r=0，则m,n 的最大公约数为m，否则返回S2,思考1：从上面的两个例子可以看出计算的规律是什么？,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。,m=n q r,用程序框图表示出右边的过程,r=m MOD n,m=n,n=r,r=0?,是,否,思考2：辗转相除法中的关键步骤是哪种逻辑结构？,(53),练习1：利用辗转相除法求两数4081与20723的最大公约数.,20723=40815+318;4081=31812+265;318=2651+53;265=535+0.,思考:你能用当型循环结构构造算法，求两个正整数的最大公约数吗？写出算法步骤、程序框图和程序。,九章算术更相减损术,算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,例3 用更相减损术求98与63的最大公约数,解：由于63不是偶数，把98和63以大数减小数，并辗转相减,9863356335283528728721217141477,所以，98和63的最大公约数等于7,练习3：分别用辗转相除法和更相减损术求204与85的最大公约数。,解：,思考：把更相减损术与辗转相除法相比较，你有什么发现？你能根据更相减损术设计程序，求两个正整数的最大公约数吗？S1:给定两个正整数 m,n不妨设mn;S2：若m,n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m,n;S3：d=m-n;S4:判断“dn”是否成立。若是，则将n,d中的较大者记为m，较小者记为n，返回s3;否则，2kd(k时约简整数的2的个数)为所求的最大公约数。,否,N=d,是,是,否,否,是,INPUT“m,n=“;m,nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1WEND d=m-n,While dn IF dn then m=d ELSE m=n n=d End if d=m-nWend d=2k*dPRINT dEnd,秦九韶算法,设计求多项式f(x)=2x55x44x3+3x26x+7当x=5时的值的算法，并写出程序。,一般的解决方案,x=5;f=2*x5 5*x4 4*x3+3*x2 6*x+7;,上述算法一共做了解15次乘法运算，5次加法运算.优点是简单，易懂;缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高。,有没有更高效的算法？,用提取公因式的方法多项式变形为,f(x)=2x55x44x3+3x26x+7=x4(2x5)4x3+3x26x+7=x3(2x5)4)+3x26x+7=(2x5)x4)x+3)x6)x+7,这样共作了5次加法，5次乘法.,从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？,秦九韶算法适用一般的多项式P(x)=anxn+an1xn1+a1x+a0的求值问题,P(x)=anxn+an1xn1+a1x+a0=(anxn1+an1xn2+a1)x+a0=(anxn2+an1xn3+a2)x+a1)x+a0=(anx+an1)x+an2)x+a1)x+a0,令vk=(anx+an1)x+an(k1)x+ank,由此我们得到v1=v0 x+an1；v2=v1x+an2；v3=v2x+an3；.vn=vn1x+a0.,这种计算方法，称之为秦九韶方法。直到今天，这种算法仍是世界上多项式求值的最先进的算法。,这种方法的计算量仅为：乘法n次，加法n次.,直接求和法：直接计算P(x)=anxn+an1xn1+a1x+a0 的值需要进行n次加法，而乘法需要1+2+3+n=n(n+1)/2次。,逐项求和法,一次项中令c=x；二次项计算a2xc,再令c=xc；三次项计算a3xc；一般地，k次项计算akxc项，并令c=xc；如此继续下去，最后计算anxc，然后求总和.,从低次项往高次项看，第一项没做乘法，第二项做了1次乘法，以后每项均做了2次乘法，一共做了2n-1次乘法；最后将每一项计算的结果求和，共做了n次加法,逐项求和法所用的乘法的次数是2n1,加法是n次。当n3时，,通过比较，我们知道秦九韶的算法比其它的算法要优越得多。,观察秦九韶算法的数学模型，计算vk时要用到vk1的值，若令v0=an，我们可以得到下面的递推公式：v0=anvk=vk1x+ank(k=1,2,n),这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。,=,x+,怎样用程序框图表示秦九韶算法？,Scilab语言：,x=input(x=);n=input(n=);result=input(The first xishu);for i=1:1:n a=input(xishu:);result=result*x+a;end disp(result,The result is:);,n=input(n=);/输入多项式次数a=zeros(1,n+1);/定义带下标的变量for i=1:1:n+1a(i)=input(a(i)=);/顺次输入系数a0,a1,.,anendx=input(x=);/输入自变量的值y=a(n+1);for i=1:1:n y=y*x+a(n+1i);endy,例1.用秦九韶方法求多项式f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在x=0.2时的值。,解：在Scilab中运行上面的语句得到,v0=a5,v1=v0 x+a4,v2=v1x+a3,v3=v2x+a2,v4=v3x+a1,v5=v4x+a0,谢谢！,