浅谈高中数学中的算法.doc

浅谈高中数学中的算法【摘要】算法具有悠久的历史背景，在现代生活中有着广泛的应用，是重要的数学研究对象，它在科学技术和社会发展中起着越来越重要的作用算法的思想和初步知识，也正在成为普通公民的常识因此，作为信息化社会未来的主人，中学生尤其是高中学生掌握一些基本的算法知识、进而养成用算法的思想意识看待世界及解决问题很有好处这是中国数学课程内容的新特色.在高中数学中学习算法有助于培养学生是逻辑思维、理性精神,增强民族自豪感，感受数学的应用价值.【关键词】算法 教学 新课程 计算机目录中文摘要1引言21 对算法的认识311 算法具有悠久的历史背景312 算法在现代生活中有着广泛的应用413 算法是重要的数学研究对象414 算法是中国数学课程内容的新特色42 算法的教育价值521 有助于培养学生的逻辑思维能力522 有助于培养学生的理性精神523 有助于增强学生的民族自豪感524 有助于学生感受数学的应用价值63 算法的新课标解读631 算法的分析与计算机实现632 算法与函数结合733 算法在实际生活中的应用834 经典数学中的算法84 算法与数学课程相关部分的交汇85 算法的解题方法解读951 程序框图1052 基本算法语句106 新课标中算法内容的重难点1161 算法设计1162 逻辑结构的理解1163 算法表示的转化167 新课标中算法内容突破重难点的策略和主要途径1671 目标和要求适当1672 教材编写要贴近学生实际1773 教学中学生自主探究，教师适度帮助178 算法的高考解读17参考文献 19英文摘要 19引言为解决一个问题而采取的方法和步骤，称为算法.算法是数学的重要组成部分，是计算机理论和技术的基础.随着现代信息技术的飞速发展，算法思想已经成为现代人应具备的一种数学素养.新课标中将算法列为必修内容，正是为了使学生形成符合时代要求的新的“数学基础”. 算法是高中数学课程中的新内容，其思想是非常重要的，但并不神秘陌生，它与传统的数学内容有密切的联系，虽然，在传统的数学内容中没有出现过这个名称，但是，它的思想反复体现在传统的数学内容中，可以说渗透到大部分内容之中.例如，求解一元一次方程，一元二次方程，二元一次方程组，求解不等式，求最大公因数，求解线性规划问题，几何作图，几何证明，等等，都可以说是算法问题.了解了算法的基本知识，会对这些问题又一个新的认识.1对算法的认识新教材中之所以设置算法的内容，是基于以下几方面的认识.11算法具有悠久的历史背景人类最早关于算法的记录存在于在两河流域发现的公元前两三千年的泥板书上，其中的一个典型例子就是计算利息何时能够等于本金.算法早期发展中值得一提的另一个成果应归功于古希腊的欧几里得，他提出的计算最大公约数的欧几里得算法（又称辗转相除法）至今仍在使用.而算法也是中国古代数学的一大特色.从中国古代的筹算、珠算、九章算术到吴文俊院士的机械化证明，都表明我国对算法的研究和运用有着悠久的历史、优良的传统和丰硕的成果.周髀算经、九章算术、算学启蒙、四元玉鉴等著作奠定了在14世纪以前中国一直是世界上数学最为发达的国家.中国古代数学以计算为中心、具有程序性和机械性的算法化数学模式与古希腊的以几何定理的演绎推理为特征的公理化数学模式相辉映，交替影响世界数学的发展.中国古代算法案例：更相减损之术、辗转相除法：求两个正数的最大公因数的方法辗转相除法算法步骤：第一步：用两数中较大数除以较小数，求商和余数第二步：用除数除以余数第三步：重复第二步，直到余数为0第四步，得出两数的最大公约数，即余数0之前的余数更相减损术算法步骤：第一步：用较大数减去较小数，得到差第二步：比较减数与差的大小，再用较大数减去较小数第三步：重复第二步，直到差与减数相等为止第四步：相等数即为最大公约数割圆术：用正多边形的面积逐渐逼近圆面积的算法求圆周率p秦九韶算法：求一元多项式的值的一种方法，递推关系为.12算法在现代生活中有着广泛的应用古代的计算工具有算筹与算盘，而20世纪最伟大的发明是计算机，计算机是实现各种算法的强大工具.算法是数学的重要组成部分，是计算机理论和技术的基础.随着计算机在科学研究、经济建设和社会管理等方面扮演的角色越来越重要，算法思想和算法技术有了更广阔的应用领域和更精练的表述形式，使之成为人们操控计算机的基本技术，也成为现代公民必备的一种数学素养.例如计算机算法分为数值运算算法和非数值运算算法.数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，此类算法与数学联系比较紧密.而非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等.一个程序应包括：（1）. 对数据的描述.在程序中要指定数据的类型和数据的组织形式，即数据结构（data structure）.（2）.对操作的描述.即操作步骤，也就是算法（algorithm）.可以说，程序就是遵循一定规则的、为完成指定工作而编写的代码.有一个经典的等式阐明了什么叫程序：程序 = 算法 + 数据结构 + 程序设计方法 + 语言工具和环境因此，算法是程序的灵魂！13算法是重要的数学研究对象算法作为一个名词，在初中教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念.但是我们却从小学就开始接触算法，熟悉许多问题的算法.如：做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现.在中学我们学习解一元二次方程，解一元一次不等式、一元二次不等式，解线性方程组等，这些都体现了算法思想.随着计算机技术的迅猛发展，诸如排序算法、图论中的算法、无限的迭代算法等等，已为当代数学教育所密切关注.所以算法也是现代数学发展的一个重要方向.14算法是中国数学课程内容的新特色中国古代数学以算法为主要特征，取得了举世公认的伟大成就.现代信息技术的发展使算法焕发了前所未有的生机和活力，算法进入中学数学课程，既反映了时代的要求，也是中国古代数学思想在一个新的层次上的复兴.毫无疑问，也就成为中国数学课程的一个新的特色.我国数学家吴文俊在继承中国传统数学的算法特征的基础上，创造性地发展了机器证明，用中国传统方法解决西方人擅长的几何论证问题.这也是我国传统特色与信息技术创造性结合的典范.他于2000年获得首届国家最高科学技术奖.2 算法的教育价值21有助于培养学生的逻辑思维能力算法具有数值化、程序化、机械化的特点，同时又有抽象性、概括性和精确性.对于一个具体算法而言，从算法分析到算法语言的实现，任何一个疏漏或错误都将导致算法的失败.算法是思维的条理化、逻辑化.算法所体现出来的逻辑化特点被有些学者看成是逻辑学继形式逻辑和数理逻辑之后发展的第三个阶段.因此，培养逻辑思维能力，不仅可以通过几何论证、代数运算等手段来进行，还可以通过算法设计的学习来达到.22有助于培养学生的理性精神算法既重视“算则”，更重视“算理”.对于算法而言，一步一步的程序化步骤，即“算则”固然重要，但这些步骤的依据，即“算理”有着更基本的作用.“算理”是“算则”的基础，“算则”是“算理”的表现.算法思想可以贯穿于整个中学数学内容之中，有很丰富的层次递进的素材，而在算法的具体实现上又可以和信息技术相联系.因而，算法有利于培养学生理性精神，是实施探究性学习的良好素材.23有助于增强学生的民族自豪感中国古代数学注重实际问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富的算法思想.比较经典的算法有：辗转相除法与更相减损术、秦九韶算法、冒泡排序法、割圆术等.用我国传统的开方术求高次方程的近似根，就是算法上的一大成就.通过这些经典算法的介绍，使学生对古代数学家钦佩的同时，增强了民族自豪感，从而达到民族精神教育的目的，肩负起振兴祖国的重任.24有助于学生感受数学的应用价值随着计算机在社会各方面的普及，软件的地位日渐突出.软件通常所指的就是计算机可以执行命令的集合，即程序.算法初步就是针对编写计算机程序而设计的一章教学内容.因此，算法的学习，有助于学生认识数学与实际生活以及计算机等学科的紧密联系，体会算法在刻画和解决实际问题中的作用，从中感受数学的应用价值.与现实生活联系比较紧密，有利于提高学生的学习兴趣，帮助学生在解决问题时养成从战略的高度审视全局的良好思维习惯.让数学在计算机学科中发挥出它的作用和地位，也让计算机很好的解决数学中复杂的计算问题和人所不能解决的问题，二者合一才能发挥出无穷的力量.算法是高中数学新增内容，算法思想是非常重要的.科学计算是当今三大科学研究方法之一，而算法又是科学计算的重要基础.计算机能有如此广泛而神奇的应用，除了芯片之外，主要靠软件，算法正是软件的核心，因此，计算机科学中的知识创新，主要就是算法的创新.而高中数学课程标准也强调计算机算法在整个数学发展中的独特作用，力求把计算机算法融入到数学课程的各个部分.可见，算法思想已逐渐成为每个现代社会公民应具有的数学素养.3 算法的新课标解读 要求学生在感受算法思想的基础上，结合对具体数学实例的分析，体验程序框图在解决问题中的作用；通过模仿、操作、探索，学习设计程序框图表达解决问题的过程；体会算法的基本思想以及算法的重要性和有效性，发展有条理的思考与表达能力，提高逻辑思维能力.31算法的分析与计算机实现例如, 在新教材中的一个循环结构形式的算法渗透了高中数学知识.例: 设计一个计算1+2+100 的值的算法及其程序.1.算法分析: 第一步, 令.第二步, 若 成立,则执行第三步; 否则, 输出S, 结束算法.第三步, .第四步,返回第二步. 2.程序:变式1:设计一个计算12+22+32+1002 的值的算法算法分析: 循环体关键部分语句为“”.变式2:设计一个计算2+4+6+100 的值的算法分析: 循环体关键部分语句为“”.变式3:设计一个计算1+2+4+7+46 的值的算法分析: 循环体关键部分语句为“”.以上例子和3 个变式充分地运用算法中的条件结构和循环结构, 在循环结构中一定有条件结构, 通过循环变量的“”, 在循环体“”与“”中的变化体现算法的多样性、计算机和数学的紧密联系.学生通过模仿、操作、探索, 学习程序设计框图表达解决问题的过程, 体会算法的思想和含义, 理解算法的基本结构和基本算法语句.32算法与函数结合例: 已知函数； 设计一个算法, 求函数的任意一个函数值.分析: 算法步骤如下: 第一步, 输入第二步, 若则执行第三步， 若 则执行第四步.第三步, 输出第四步,输出以上是分段函数的一个算法, 算法的思想使我们平时的函数解题更加程序化, 条理更清晰.类似的去模拟计算机如何运行, 使我们对有关函数题目有更深刻的理解.解题方法的程序化, 需要算法在问题中展现过程.33算法在实际生活中的应用例: 到银行办理个人异地汇款( 不超过100 万) 时, 银行要收取一定的手续费汇款不超过100 元, 收一元手续费; 超过100元但不超过5000 元, 按汇款额的1%收取; 超过5000 元, 一律收取50 元手续费.试用算法描述汇款额为x 元时, 银行收取手续费为y 元的过程.在我们的实际生活中, 如汇款、交电费、寄包裹等经常运用到算法.可见算法与我们的生活息息相关.该题实际上是一个常见的分段函数问题, 而分段函数问题是典型的条件语句问题, 所以很容易得到算法, 要注意条件语句的运用.实际生活中的许多问题, 通过设计算法, 会由计算机得以解决.34经典数学中的算法九章算术是中国古代的数学专著, 其中的“更相减损术”也是用来求两个数的最大公约数, 即“可半者半之, 不可半者, 副置分母、子之数, 以少减多, 更相减损, 求其等也, 以等数约之”.后人称为更相减损法.以上算法能让学生体会算法优势, 体现古代人的聪明才智.4 算法与数学课程相关部分的交汇随着“算法”进入新课标，课堂上、考场上使用计数器必然给我们课堂学习和考试带来观念上的革命，必然引起解题方法的革命，尽管现阶段计数器还不能进入高考考场，但随着我们对“算法”的学习与认识不断深入，相信不久的将来，高考会接纳计数器， 算法必将溶入高中数学大家庭，融入到数学课程的各个相关部分.近几年数学高考试题（特别是上海卷、北京卷）在这方面做了许多成功的探索，各地的高考模拟试题也把计算机科学与数学问题相结合，设计出许多创新试题，成为高考命题的新亮点.目的就是渗透信息技术和算法思想，在计算机科学背景下（新的情景中），考查考生的一般数学能力：包括学习数学新知识的能力、探究数学问题的能力、应用数学知识解决实际问题的能力及数学创新能力.算法应用广泛：（1）.运用r进制解题，即利用r进制数“逢r进一”及 (a1a2a3a4a5)r= a1r2 + a2r1 + a3r0 + a4r-1 + a5r-2，其中ai0,1,2, ,r-1rN这两个性质解题.（2）.利用计算器可对各种具体角的三角函数值求值，容许计算器进入考场必然产生新的解题方法，因此，一些传统的应用三角公式进行三角变换的问题有待改进.（3）.“算法”就是有步骤地解决某一类问题的过程.现代科学技术和生产实践对算法提出了新的要求，因此，新的课程理念十分重视算法的学习.每年高考数学解析几何试题中，都有许多这种模式化的算法问题.（4）.“算法”在数列、反三角函数、指对数函数、排列、组合、概率、统计等中也有广泛的应用.注意计算器上的统计功能键能够帮助我们有效地整理、分析数据，结合数字模型还可以进一步作出判断和预测.我们还可以建立线性回归、二次回归、对数回归、指数回归和乘方回归等模型，比较方便地处理数据以及进行相关的运算和分析.等等.更多的还在于我们自己去探索、去发现，只要我们理解和掌握了问题的算法，解题过程不也就是一个程序化的操作吗？在高中数学中，我们知道，函数思想、代数运算思想、算法思想、空间观念(几何直观、空间想象、数形结合)、数据处理与随机思想，它们都是贯穿了高中数学课程始终的核心思想，不仅在必修课程中，而且在选修课程中，也包括在选3、选4的课程中，它们像“无形的网络”把整个高中数学的内容有机地联系起来.作为高中数学主线之一的算法部分，我们很多老师感到恐怖，总觉得自己不会.通过研修学习，我对算法这一新内容有了了解，由害怕到期待着该内容的教学了，并切深感新教材内容的设计理念越来越能体现数学的实用的价值，不再枯燥乏味.5算法的解题方法解读随着现代信息技术的飞速发展，算法在科学技术、社会发展中发挥着越来越大的作用，并日益融入社会生活的各个方面.算法重在用一个统一的方法有步骤地解决一类问题，但它不是唯一的，一个好的算法应该用较少的便于实现的步骤去有效的解决问题.严格说来，一个算法必须满足以下几个特征：（1）有限性：算法包含有限操作步骤；（2）确定性：算法中每一个步骤都应当是确定的，不能是模棱两可的；（3）可行性：算法的每一步都能精确的执行，有确定的结果；（4）输入可以是零个或多个；（5）有一个或多个输出:算法的结果就是输出，没有输出的算法是没有意义的.计算机科学家尼克劳斯-沃思曾著过一本著名的书数据结构十算法=程序，可见算法在计算机科学界与计算机应用界的地位.51程序框图（1）.设计问题算法时，要根据题目进行选择，以简单、程序短、易于计算机上执行为原则.（2）.在画程序框图时，首先要选择结构，套用格式：若求只含有一个关系式的函数值时，只用顺序结构就能解决；若是分段函数或执行时需要先判断才能执行后继步骤的，必须引入条件结构；若问题涉及的运算进行了许多重复的步骤，而且数之间有相同的规律，则可引入变量，应用循环结构，但应用循环结构一定要用到顺序结构和条件结构，象1+2+3+100，12399 ，等等，都应用循环结构设计算法，绘制算法程序框图.52基本算法语句（1）.利用输入、输出、赋值三种语句写程序时应做到：需输入信息时用INPUT语句，需输出信息时用PRINT语句，当变量需要的数据较少或给变量赋值算式时，用赋值语句，当变量需要输入多组数据且程序重复使用时，应用输入语句.（2）.条件语句与条件结构相对应，循环语句与循环结构相对应，如果语句形式比较复杂，可借助框图写出程序.在用数学方法求解问题的过程中，提出问题、构造算法和使用计算工具这三项工作始终紧密相联.6新课标中算法内容的重难点61算法设计算法与平时解题的区别，在于平时解题不一定有严格的程序，而要让计算机执行，必须严格按步骤进行.因此在算法设计中，应将平时解题中没有想清楚的每一步都想清楚，这对学生的逻辑思维能力是极大的考验.另外，算法的多样性和方法的优化也会使学生很不适应.62逻辑结构理解对于某个具体的数学问题，理解设计程序框图时逻辑结构的选择和应用是难点，因为综合运用知识解决具体问题的能力是学生的薄弱环节，就好比认识字不一定能写出好的文章一样.一般算法有顺序结构、条件分支结构、循环结构三种基本逻辑结构.1. 顺序结构.顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的.它是由若干个依次执行的处理步骤组成的，它也是任何一个算法都离不开的一种算法结构，如图，其中A和B两个框是依次执行的，只有在执行完A框所指定的操作后，才能接着执行B框所指定的操作.顺序结构的一个简单的例子是交换变量a和b的值.算法如下：S1：m=a; S2：a=b;S3：b=m;程序框图如图：2.条件分支结构.在一个算法中，经常会遇到一些条件的判断、算法的流程根据条件是否成立有不同的流向，这种先根据条件作出判断，再决定执行哪一种操作的结构称为条件分支结构，如右图所示的一个条件分支结构，此结构中包含一个判断框，根据给定的条件P是否成立而选择执行A框或B框，请注意，无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，也不可能A框和B框都不执行.无论走哪一条路径，在执行完A框或B框之后，脱离本条件分支结构.A框或B框两个框中，可以有一个是空的，即不执行任何操作.举一个简单的例子：写出求方程（其中为常数）根一个算法，并画出程序框图.分析：此方程的根与p和q取值有关.算法如下：S1：输入；S2：如果则使并执行S3；否则，执行S4；S3：输出；S4：如果则输出“方程无实数根”，否则，输出“方程的解是全体实数”.该算法对应的程序框如下图：编写电信部门收取话费的程序，出租车司机收取客人行车费的程序等都需要用到条件分支结构.3.循环结构.需要重复执行同一操作的结构称为循环结构，即从某处开始，按照一定条件反复执行某一处理步骤，反复执行的处理步骤称为循环体.循环结构中通常都有一个起循环计数作用的变量，这个变量的取值一般都包含在执行或终止循环的条件中.循环结构有while型循环（也称当型循环）和until型循环（也称直到型循环）两种，要注意这两种循环的联系和区别.例如：作出计算1+3+5+n的程序框图：这三种基本结构的共同特点是：（1）.只有一个入口和出口.（2）.结构内的每一部分都有机会被执行到，也就是说对每一个框来说都应当有一条从入口到出口的路径通过它，如图中的A，没有一条从入口到出口的路径通过它，就是不符合要求的算法结构. 例如：编写用“二分法”求方程的近似解算法的程序.用Qbasic编写的程序：INPUT “a,b,d=”;a,b,dDOm=(a+b)/2g=a2-2f=m2-2IF g*f0 THENb=mELSEa=mEND IFLOOP UNTIL ABS(a-b)d OR f=0PRINT mEND 用VB语言编写的程序：Private Sub Form_Activate()a = InputBox()b = InputBox()d = InputBox()Do m = (a + b) / 2 g = a 2 2 f = m 2 2 If g * f 0 Then b = m Else a = m End IfLoop Until Abs(a - b) d Or f = 0Print mEnd Sub 用java语言编写的程序：import java.util.*; public class erfenfa public static void main(String args) Scanner sc=new Scanner(System.in); double a=sc.nextInt(); double b=sc.nextInt(); double d=sc.nextInt(); do double m=(a+b)/2; double g=a*a-2; double f=m*m-2; if(g*f0) b=m; else a=m;while (Math.abs(a-b)d | f=0);System.out.println(m=+m);用Qbasic实现时，使用了最基本的5个语句，它们是键盘输入语句（INPUT）、赋值语句（LET）、条件语句（IF.THEN）、循环语句（DO.LOOP UNTIL）、输出语句（PRINT）.如果使用目前流行的VB或java算法语言来实现算法，也可以使用相应语言的五个类似的语句即可实现（如以上程序）.63算法表示的转化课标要求通过模仿、操作、探索，经历设计程序框图、并将程序框图转化成程序语句的过程.这里面要经历两个转化，一是将自然语言转化为程序框图，二是将程序框图转化为程序语句.尽管课标中好象只要求“模仿”、“理解”，但模仿不等于重复，不会简单的应用绝不可能是真正意义上的理解，因此要求学生对算法表示进行准确地转化也是教学中的难点.从课标制定的目标和要求看，算法内容属于“程序性知识”或叫“默会知识”.这类知识是从活动过程和活动方式中表现出来的，主要通过在实践中通过观察、模仿、和自主活动而获得.因此只有在目标定位、教材编写、教学方式等方面均能对知识特点和学生的学习特点充分考虑，才能真正使课程的设置意图得到体现，难点得到突破.7新课标中算法内容突破难点的策略和主要途径71目标和要求适当 张奠宙先生指出：“算法应该从小学开始教”，“算法贯穿整个中学数学”.的确，算法的思想和知识、技能，是学生的终身发展所必需的.但是要求学生通过12课时就能一步到位，系统地掌握程序的设计和编写，显然是不现实的.算法内容重要的是让学生体会算法的思想，理解算法的重要性与有效性，加强逻辑思维，在经历过程中理解逻辑结构和语句.可以要求学生在观察、模仿的基础上，在教师的指导下尝试解决一些简单的问题，不应过分注重技术操作，将算法内容单纯地变成程序语言的学习和程序设计.72教材编写要贴近学生实际 在教材的编写中内容的呈现与设计，素材的选取都应贴近学生的实际，有助于激发学习兴趣，让学生乐于、易于接受，能较好地促进学生的自主探索.其中实例的开发尤为重要.另外教材编写中要把算法内容作为主线渗透到其他数学内容中去，以及与高中信息技术教材相呼应.73教学中学生自主探究，教师适度帮助 由于算法内容属于“默会知识”，学之道在于“悟”.教学中应当充分重视学生亲身感受、实践操作、合作交流，给学生提供探索与交流的空间，使数学学习过程真正成为学生在已有经验基础上的主动建构过程，在知识的形成与应用过程中认识和掌握双基，在经历过程中感悟算法的思想和方法.在强调学生自主探究的同时，教师也应适度地给予引导、帮助，如教学情境的设计、适时的点拨、情感激励等.8算法的高考解读算法初步是新课程试验教材的新增内容，算法思想是新课程强调的一种数学思想，算法的基本知识、方法和思想已渗透到人们的日常生活的方方面面，成为现代人应具备的一种数学素养.因此，算法备受高考命题者青睐，2007、2008年首批课改试验省份（山东、广东、海南和宁夏）高考数学试卷中都命制了算法程序框图选择题或填空题，注重考查考生的基础知识、基本技能和数学思想方