算法的内容定位及要求课件

算法的内容定位及要求算法的内容定位及要求辽宁省高中新课程省级培训数学科讲师团舒凤杰1 1算法的含义2 2国外算法课程及教学的研究3 3算法进入中学数学课程的意义4 4算法的基本结构5 5算法的基本特点6 6算法的描述7 7课程目标与内容安排8 8算法教学中要注意的几点问题算法的内容定位及要求算法的内容定位及要求1-8算法的含义 计算机出现之前;计算机出现之后;什么是算法.1-3计算机出现之前计算机出现之前n n此时的算法，是指为了解决一类实际或科学问题而概括出来的，带有一般性的计算方法。n n例如:四则运算中的先乘除、后加减；欧几里得的算法 秦九韶算法 1-n n这些算法具有以下特征：这些算法具有以下特征：（1 1）机械性：每个步骤都是机械的、固定的，）机械性：每个步骤都是机械的、固定的，不需要计算者费时动脑筋。不需要计算者费时动脑筋。（2 2）有效性：任何人应用这种方法都能得到预）有效性：任何人应用这种方法都能得到预定结果。定结果。（3 3）通用性：对这样一类问题都可以应用。）通用性：对这样一类问题都可以应用。n n这一阶段的算法，往往都以自然语言描述或数这一阶段的算法，往往都以自然语言描述或数学公式的形式出现。如九章算术中每一道学公式的形式出现。如九章算术中每一道完整的题目，都分为完整的题目，都分为“题题”、“答答”、“术术”三部分，其中三部分，其中“术术”就是以语言形式描述的算就是以语言形式描述的算法。我们可以把这种算法称之为法。我们可以把这种算法称之为“原算法原算法”。即原始、本质的算法。即原始、本质的算法。1-3-2.1计算机出现之后计算机出现之后n n 此时的算法就不止是解决问题的过程和方法了，此时的算法就不止是解决问题的过程和方法了，还需要用计算机能识别、执行的形式表述出来。还需要用计算机能识别、执行的形式表述出来。我们可以称其为我们可以称其为“计算机算法计算机算法”。n n算法除了具有算法除了具有“原算法原算法”的那几条特征外，还需的那几条特征外，还需要满足以下两条：要满足以下两条：（1 1）确定性）确定性（definiteness)definiteness)是指算法中每一个步骤都要有明确的定义，不允是指算法中每一个步骤都要有明确的定义，不允许有模棱两可的解释，不允许有多义性。许有模棱两可的解释，不允许有多义性。（2 2）有限性）有限性（finitenessfiniteness）是指算法必须在执行有限个步骤后结束，并给出是指算法必须在执行有限个步骤后结束，并给出计算结果。计算结果。1-2什么是算法什么是算法n n简单地说，算法是完简单地说，算法是完成某项工作的方法和成某项工作的方法和步骤。步骤。n n现代意义上的现代意义上的“算法算法”通常是指可以用计通常是指可以用计算机来解决的某一类算机来解决的某一类问题的程序或步骤。问题的程序或步骤。1-图国内外算法课程及教学的研究n中国n美国n日本日本n俄罗斯1-4中国中国算法课程及教学n n虽然在以前我国的基础教育各阶段的数学教学大纲中都没有明确提到算法，但是算法在小学与中学的数学课程中却随处可见。从小学的加减乘除的四则运算、乘法口诀、珠算口诀，到中学一元二次方程的求根公式、解分式方程、求面积和体积的公式等等，这些都属于算法内容的范畴之内 1-1美国算法课程及教学美国算法课程及教学n n在美国数学课程标准在美国数学课程标准Principle&Principle&Standards for SchoolStandards for School MathematicsMathematics中明中明确提到算法确提到算法（algorithmsalgorithms）是在是在6868年级年级的的“数与运算标准数与运算标准”的熟练计算和作合理的熟练计算和作合理估计一项中。估计一项中。n n标准中提到：提出和分析关于整数、分数、标准中提到：提出和分析关于整数、分数、小数计算的算法，并且在使用中提高运算小数计算的算法，并且在使用中提高运算熟练性。熟练性。1-2n n在9-12年级“数与运算”部分，提出“学生应把分析和比较算法作为研究数学的一部分。通过比较算法，使学生考虑哪些更容易解释，哪些更容易运算，哪些更有效。在实际教学中，鼓励学生自己创造算法，并讨论比较不同算法的优劣”。n n尽管对算法的处理没有把它作为独立的内容，但是注重对算法思想的适当渗透。1-2 2019年NCTM下属的数学学会基金组织的专家就“标准”修订时，对课程中表现在数学中的来龙去脉的算法的性质问题进行相关修改，提出算法教学的三条原则：n n儿童需要学习一定的算法n n他们需要这样做的理由有三条：效率、数学理解能力、算法本身的概念n n在计算器和教育普及的年代，算法的概念变得更重要1-3 在在19891989年由日本数学教育学会颁年由日本数学教育学会颁布的算数，数学（小学校、中学布的算数，数学（小学校、中学校、高等学校）学习指导要领中校、高等学校）学习指导要领中的高中数学选修的的高中数学选修的A A、B B、C C中，每一中，每一部分都有关于算法的内容。部分都有关于算法的内容。日本算法课程及教学1-1 选修A 的第四部分内容是计算与计算机，包括计算机的操作，框图与程序，使用计算机进行计算。并在内容的处理中提到要使学生能够构造、理解、编制程序。1-1选修B的第四部分是算法与计算机，包括计算机的机能，各种各样算法的程序。选修C可以看成是算法的应用，目标中就提出灵活使用计算机进行矩阵计算，描绘各种各样曲线，进行数值计算和统计处理，要加深理解，以掌握知识、技能为目的，同时发展用数学和计算机结合的观点考察事物的能力。1-1以文部省审定的启林馆编写的教材为例数学B第四章算法n n计算机机能n n计算机机能计算机机能n nBASICBASIC语言语言n n算法n n算法（包括算法定义，辗转相除）算法（包括算法定义，辗转相除）n n进位转换的算法进位转换的算法n n求平方根的算法求平方根的算法1-2数学C第三章数值计算第三章数值计算n n方程的近似解二分法二分法切线法切线法用计算机求方程的近似解用计算机求方程的近似解n n数值积分法定积分求面积法定积分求面积法定积分的台形公式定积分的台形公式用计算机求定积分的近似值用计算机求定积分的近似值1-2 日本的教科书在算法的处理上，对每一种算法，都是先给出具体的推导公式，然后用语言描述求解过程，最后给出程序。1-1 前苏联1978年公布修订的大纲草案，依据草案编写的教材，七年级学习比较完整的“近似计算”，八年级有“电子计算机的算法和框图”。俄罗斯俄罗斯算法课程及教学1-1 1980教育部推荐前苏联教育科学学院编制的79年级选修课程大纲，分为“数学选学专题”，“数学的应用”和“算法的程序设计”三个方面，除“数学选学专题”外，其它两个方面都有算法内容。“数学的应用”中的数学函数和图象部分有用切线法求方程的近似解；“算法的程序设计”中有算法概念，算法框图，算法计算过程。1-1 1993年颁布的普通学校学科教学标准规定基础教育数学 课程包括代数、几何、和数学分析原理、数学综合课程、统计学、概率、逻辑学及其它数学课程，算法在代数和信息学中都有所体现。1-11.1.算法对数学课程本身的意义算法对数学课程本身的意义n n算法进入中学课程是顺应时代的发展算法进入中学课程是顺应时代的发展,是数学课程是数学课程与信息技术整合必然产物，是数学课程发展的新趋与信息技术整合必然产物，是数学课程发展的新趋势。势。n n数学正是由于计算机的出现，与信息技术相结合，数学正是由于计算机的出现，与信息技术相结合，才迎来了发展史上的第四个高峰。才迎来了发展史上的第四个高峰。n n前苏联数学教育家斯托利亚尔曾经指出前苏联数学教育家斯托利亚尔曾经指出:“任何水平的数学教学都一定包括算法的教学任何水平的数学教学都一定包括算法的教学”n n算法应该算法应该“成为理解数学发展的重要线索成为理解数学发展的重要线索”,”,成为继成为继数系和函数之后的数学课程特别是代数课程的第三数系和函数之后的数学课程特别是代数课程的第三条重要线索。条重要线索。1-42.2.算法对总体课程目标的意义算法对总体课程目标的意义n n算法是计算机技术的核心，计算机的发展说明了算法的重要性。n n算法是中国古代数学的特色。n n算法有助于发展学生的逻辑思维能力。n n算法越来越成为现代社会人们应该具有的一种基本素质。1-4算法的基本逻辑结构n算法通常由两部分构成：(1)操作 (2)控制结构1-2算法的操作算法的操作 计算机算法由计算机实现，组成它的操作主要包括：算术运算（、），逻辑运算（与、或、非等），关系运算（、等），函数运算等等。1-1控制结构控制结构n n控制结构的作用是控制算法各操作的执行顺序。一个算法通常由三种基本结构组成，这三种基本结构是：1.1.顺序结构2.2.分支结构3.3.循环结构1-3顺序结构顺序结构n n顺序结构算法的操作顺序是按照书写顺序执行的。n n顺序结构的表示:赋值操作赋值操作输入输出输入输出顺序结构按书写顺序顺序结构按书写顺序依次执行依次执行1-2顺序结构的算法举例顺序结构的算法举例n n设计算法，确定给定线段AB的等分点解决这个问题的算法如下：1.1.从已知线段的左端点从已知线段的左端点A A出发，作一射线；出发，作一射线；2.2.在在射射线线上上任任取取一一点点，并并作作线线段段，那那么么线线段段；3.3.连接连接；4.4.过过作作B B的的平平行行线线，交交线线段段ABAB于于，这这样样点点就是线段就是线段ABAB的等分点的等分点5.5.像这样的算法就是一个顺序结构的算法，只像这样的算法就是一个顺序结构的算法，只要按照书写顺序完成以上四个步骤，就能得要按照书写顺序完成以上四个步骤，就能得到线段到线段ABAB的等分点。的等分点。1-5顺序结构的算法框图顺序结构的算法框图n n尺规作图，确定线段尺规作图，确定线段ABAB的一个的一个5 5等分点等分点n n顺序结构的特点：顺序结构的特点：算法按照书写顺序算法按照书写顺序执行执行 1-2Z1=Ax0+By0+C Z2=A2+B2输出输出d结束结束开始输入输入x0,y0 A,B,C21zdz=分支结构分支结构n n分支结构的算法是根据指定的条件进行判断，由判断的结果决定选取执行两条分支路径中的一条。n n分支结构的表示:1-2分支结构的算法举例分支结构的算法举例n n对任意给定的三个整数x,y,z,设计算法求出其最大值。这个算法是简单的，只要先比较出x和y，得到一个大的值，再用这个值与z比较，这两者中大的值即为所求的最大值。n n可以将这个算法描述为：1.1.输入变量：输入变量：x,y,zx,y,z；2.2.b b：=x=x；3.3.比较比较b b和和y y：如果如果b by y,则则：=y.y.4.4.比较比较与与z z：如果如果 z,z,则则：=z,z,5.5.输出输出.1-5分支结构的算法框图分支结构的算法框图n n求三个数中的最大数求三个数中的最大数选择结构的选择结构的 特点特点:算法中需要进行判算法中需要进行判断，断，判断的结果决定后面的步判断的结果决定后面的步骤。骤。1-4开开 始始输入输入 a,b,ca,b,c计算计算输出输出x1,x2结结 束束否否是否循环结构循环结构n n循循环环结结构构的的算算法法要要根根据据条条件件是是否否满满足足决决定定是是否否继继续执行循环体中的操作。续执行循环体中的操作。满足条件？否循环体是直到型循环结构直到型循环结构 满足条件？是否循环体当型循环结构当型循环结构 直到型循环直到型循环在每次执行了循环体之后对循环条件进行判断：当条件不满足是执行循环体，满足则停止”反复循环直到条件满足”当型循环当型循环在每次执行循环体前对循环条件进行判断：当条件满足时，反复执行循环体，条件不满足则停止“当条件满足时，反复执行循环体”循环结构的算法举例循环结构的算法举例n n前面求三个数中的最大数，我们进行了两次比较，假如我们要找出个数中的最大数，按照上述算法就需要比较次，算法步骤就是步既不便于书写，也不便于阅读解决这个问题，就需要利用循环结构了，对于求个数中的最大数的问题，相应的算法可以用下列流程图来表示：1-1找出个数中的最大数程序框图1-图二分法求根算法二分法求根算法n n第一步确定有解区间第一步确定有解区间a,ba,b。(f(a)(f(a)f(b)0)f(b)0)n n第二步取第二步取a,ba,b的中点的中点（a+ba+b）2 2n n第第三三步步，计计算算函函数数f(x)f(x)在在中中点点处处的的函函数数值值f f（a+ba+b2 2）n n第四步，判断函数值第四步，判断函数值f f（a+ba+b2 2）是否为是否为0 0，n n如如果果为为0 0，x xa+ba+b2 2就就是是方方程程的的解解，问问题题就就得得到到了解决了解决n n如如果果函函数数值值f f（a+ba+b2 2）不不为为0 0，则则分分下下列列两两种种情情形：形：n n若若f(a)ff(a)f（a+ba+b2 2）000，则则确确定定新新的的有有解解区区间为间为（a+ba+b2 2，b b）1-4n n第五步判断新的有解区间的长度是否小于精确度：n n如如果果新新的的有有解解区区间间长长度度大大于于精精确确度度，则则在在新新的的有解区间的基础上重复上述步骤；有解区间的基础上重复上述步骤；n n如如果果新新的的有有解解区区间间长长度度小小于于或或等等于于精精确确度度，则则取新的有解区间的中点为方程的近似解取新的有解区间的中点为方程的近似解 1-1二分法程序框图二分法程序框图1-图开始开始计算增量计算增量I=PR 用用P+I代替代替P输出输出P结束结束是否到时间T否否是是输入输入R,P,TP=人口总数人口总数R=年增长年增长率率T=预测年数预测年数n例如：人口预测.已经知道现有的人口总数是P，人口的年增长率R，预测T年后人口总数将是什么？1-1n n13世纪意大利数学家斐波那契（Fibonacci,1170-1250）借用兔子的理想化繁殖来定义了两条规则：n n一对仔兔b（baby）开始，n n假设从出生算起一月后仔兔变为成年兔，把成年兔记为a（adult），这时，从b变成a；n n一对成年兔a在每一月末，要生一对仔兔，并把它记在双亲之后，即a变成ab。n n由此，我们得到一个字符序列：1-21 b2 a3 a b4 a b a5 a b a a b6 a b a a b a b a112358代代兔子对数兔子对数变化趋势变化趋势a1=1a2=11-1循环结构的算法循环结构的算法n n输出输出10001000以内所有能以内所有能被被3 3和和5 5整除的正整数。整除的正整数。n n循环结构的三个要素循环结构的三个要素 1 1）循环变量）循环变量 2 2）循环体）循环体 3 3）循环终止条件）循环终止条件 1-图算法的特点算法的特点n n有穷性n n确定性n n可行性1-图算法的描述算法的描述n一般有下列三种描述方法1.自然语言2.流程图3.程序语言1-3几种基本语句几种基本语句n n输入输出语句n n赋值语句n n条件语句n n循环语句1-4基本基本基本基本算法语句算法语句算法语句算法语句程序模块的构成程序模块的构成输入输入输出输出处理处理输入语句输入语句输出语句输出语句赋值语句赋值语句条件语句条件语句循环语句循环语句顺序结构顺序结构条件分支结构条件分支结构循环结构循环结构1-1赋值、输入和输出语句赋值、输入和输出语句赋值语句赋值语句“=”就是赋值运算符，作用是将右边数据或表达式的值赋给左边的变量,不是算术中的相等。例如：例如：a=3;x=x+1;输入语句输入语句输出语句输出语句1-1形式一：if (表达式)语句序列；表达式成立吗？表达式成立吗？语句序列语句序列真真假假执行过程：执行过程：条件语句条件语句条件语句条件语句例如：例如：if x5 y=3*x+8;end1-2if 条件表达式条件表达式 语句序列语句序列1；else 语句序列语句序列2；end 形式二二：执行过程：执行过程：表达式成立吗？表达式成立吗？语句序列语句序列1真真假假语句序列语句序列2 if x/2=0 disp(“x is a even”);else disp(“x is a odd”);end例如：判断一个数是奇数还是偶数例如：判断一个数是奇数还是偶数1-end循环语句循环语句循环循环指的是反复地执行一个或多个步骤指的是反复地执行一个或多个步骤.类型类型固定固定(循环次数为已知的情形循环次数为已知的情形)可变可变(循环次数为未知的情形循环次数为未知的情形)1-2n n固定的n n进行固定次数的重复操作.n n循环内计算或处理的数值对循环操作的次数没有影响.n n可变的n n重复操作,直到一个指定的条件满足.n n循环次数可以变化.1-2例如：例如：for循环的格式为：循环的格式为：for 循环变量循环变量=初值：步长：终值初值：步长：终值 循环体循环体end 循环条件表达循环条件表达式成立吗？式成立吗？否否是是循环体语句循环体语句循环变量循环变量 赋初值赋初值修改循环变量的值修改循环变量的值计算计算 sum=1+2+3+1000For 型循环：型循环：While型循环：型循环：while 表达式表达式 语句序列（即循环体）语句序列（即循环体）endWhile 1+eps1.001 eps=eps/2;end例例例：写出解三元一次方程组的算法、框图和程序分析：例：写出解三元一次方程组的算法、框图和程序分析：对于一般的三元一次线性方程组，可以表示为对于一般的三元一次线性方程组，可以表示为(1)333323213123232221211313212111=+=+=+bxaxaxabxaxaxabxaxaxa我们先看一看下面的三元一次方程组：我们先看一看下面的三元一次方程组：下三角形方程组下三角形方程组(2)333323213122221211111=+=+=bxaxaxabxaxabxa上三角形方程组。上三角形方程组。(3)333323232221313212111=+=+bxabxaxabxaxaxa可以看出，三角形方程组很容易求解可以看出，三角形方程组很容易求解.对于一般的三元一次对于一般的三元一次方程组，我们可以通过一些等价变换，将它变为三角形方程组。方程组，我们可以通过一些等价变换，将它变为三角形方程组。对于方程组对于方程组（3），如果，如果 可以解出可以解出 033a3333abx=把把 x3 代入代入（3）的第二个方程，得到：的第二个方程，得到：2232322axabx-=把把 x2 和和x3代入第三个方程，得到：代入第三个方程，得到：1131321211axaxabx-=开始开始aij=aij+c.akj读入读入 参数参数 0 0Nk=1akk0k=2i=k+1i=3c=-aik/akkj=k+1j=3j=j+1bi=bi+c.bki=i+1k=k+1a33 0 X3=b3/a33l=2l=1s=0m=l+1m=3S=S+alm.xmm=m+1Xl=(bl-S)/alll=l-1 输出结果输出结果0 0结束结束 NNNNNN顺顺序序消消元元法法框框图图中国古代数学中的算法案例中国古代数学中的算法案例中国古代数学中的算法案例中国古代数学中的算法案例3.秦九韶算法秦九韶算法 计算机上使用的算法常采用递推化的形式，递推计算机上使用的算法常采用递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过程化的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节省计算量优点是简化结构和节省计算量。多项式求值：给定的多项式求值：给定的x 求下列求下列n 次多项式次多项式的值的值。nnxaxaxaaxP+=L2210)(解：解：1.用一般算法，即直接求和法用一般算法，即直接求和法:nnxaxaxaaxP+=L2210)(加法次数为：加法次数为：n乘法的次数为乘法的次数为:2)1(321+=+nnnL11-=kkxt2.逐项求和法逐项求和法:令令 则则 记记kkxt=kkkkkxaxaxaau+=-1110L1-=kkxtt可以看出前可以看出前K+1项部分和项部分和uk等于前等于前K 项部分和项部分和uk-1再加上再加上第第K+1项，因此有项，因此有k=1,2,n 初值应取为初值应取为 所用乘法的次数为所用乘法的次数为2n，加法次数为，加法次数为n。nnxaxaxaaxP+=L2210)(+=-kkkkkktauuxtt11=0001aut3.秦九韶方法秦九韶方法:将多项式改写为将多项式改写为 0111)(axaxaxaxPnnnn+=-L01211)(axaxaxannnn+=-L0123120)(axaxaxaxannn+=-L0121)(axaxaxaxannn+=-LLL令令knknknnnkaxaxaxaxav-+=)()1()2(1LL递推公式为：递推公式为：k=1,2,n 计算量为：乘法计算量为：乘法n次次，加法加法n次次。=+=-nknkkavaxvv011-1课程目标n n算法是高中数学课程中的新增内容，其思想是非常重要的在本章中，学生将学习算法的初步知识，并通过对具体算法案例的分析，体验算法在解决问题中的重要作用，培养算法基本思想，提高逻辑思维能力，发展有条理的思考与数学表达的能力1-1n n算法的涵义、程序框图1.1.通过对解决具体问题过程与步骤的分析，体会算法的思想，了解算法涵义2.2.通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程在具体问题的解决过程中（如三元一次方程组求解等问题），理解程序框图的三种基本逻辑结构：顺序、条件分支、循环1-2n n基本算法语句n n经历将具体问题的程序框图转化为程序语句的过程，理解几种基本算法语句输入语句、输出语句、赋值语句、条件语句、循环语句，进一步体会算法的基本思想n n通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献，增强民族自豪感 1-2算法算法与程序框图基本算法语句算法案例算法涵义程序框图输入与输出语句赋值语句条件语句辗转相除法秦九韶算法进位制循环语句顺序结构条件结构循环结构框图的画法1-12.知识结构课时分配n n1.1 1.1 算法与程序框图算法与程序框图 约约6 6课时课时n n1.2 1.2 基本算法语句基本算法语句 约约4 4课时课时n n1.3 1.3 算法案例算法案例 约约2 2课时课时n n小小 结与复习结与复习 约约1 1课时课时1-4算法教学中要注意的问题算法教学中要注意的问题1.1.注重算法的基本思想的理解 2.2.算法教学必须通过实例进行 3.3.算法教学要注意循序渐进，先具体再抽象，先了解算理，再描述算法 4.4.把握重点、区分算法教学和程序语言教学5.5.分散难点，逐层深入6.6.在整个高中数学课程中渗透算法思想1-6 谢谢谢谢!n葫芦岛市教师进修学院舒凤杰nE-mail:lhshufengjie163算法的研究和应用正是本课程的主题算法的研究和应用正是本课程的主题算法的研究和应用正是本课程的主题算法的研究和应用正是本课程的主题 ！现代科学研究的三大支柱理论研究科学实验科学计算科学计算解题过程