第1章算法初步素材(苏教版必修3)

算法初步复习总结算法不仅是数学及其应用的重要组成部分．也是计算机科学的重要基础．在现代社会单,在现代社会里,计算机已经成为人们日常生活和工作不可缺少的工具．听音乐、看电巨、玩游戏、打字、画卡通画、处理数据,计算机几乎渗透到了人们生活的所有领域.那么计算机是怎样工作的呢?要想弄清楚这个问题,算法的学习是一个开始．从数学发E的历史来看，算法并不是一个全新的概念.比如,在西方数学中很早就有了欧几里得算法,而中国古代数学中蕴涵着更为丰富的算法内容和思想,割圆术、秦九韶算法等等都是很经典的算法.在算法初步这一章里，要学习的是算法的概念和程序框图,理解算法的基本结构、基本算法语句,了解一些很有意思的重要算法,体会算法的基本思想,发展有条理的思考与表达的能力,提高逻辑思维能力．一、基础知识要点总结算法一章的主要内容是算法的概念及含义,算法思想、程序框图及其规则,算法的三种基本结构.用数学语言写出算法并实现与程序框图的转换;赋值语句、输入语句和输出语句,用条件语句描述条件分支结构的算法,用循环语句描述循环结构的算法;用辗转楣除法与更相减损术求最大公约数,用秦九韶算法计算一元多次函数值,及割圆术的算法案例.二、专题总结．算法一章分三大节,第一节是算法与程序框图,主要介绍了算法、程序框图、顺序结构、条件结构、循环结构的概念,要求我们写出的算法必须能解决一类问题,并且能重复使用,算法的过程要能一步步执行,每步执行的操作必须确切,不能含混不清,而且经过有限步运算后能得出结果.要能够正确的画出框图.第二节是基本算法语句.主要介绍了赋值语句及格式,键盘输入语句、输出语句、条件语句夕环语句的概念.要知道这些语句的一般格式,以及它们的作用,能够将很多抽象算法及理论在计算机上操作、执行,从而能更好地解决问题．第三节是算法案例.主要介绍了辗转相除法、更相减损术、秦九韶算法等概念，能够利用对比方法，如辗转相除法与更相减损术对比等．三、学习目标1.通过对解决具体问题过程与步骤的分析(如二元一次方程组求解问题)，体会算法的思想,了解算法的含义.2.通过模仿、操作、探索,经历通过设计程序框图表达解决问题的过程.在具体问题的解决过程中(如三元一次方程组求解等问题),理解程序框图的三种基本逻辑结构:顺序、条件分支、循环.3.经历将具体问题的程序框图转化为程序语句的过程,理解几种基本算法语句:输入语句、输出语句、赋值语句、条件语句、循环语句,进一步体会算法的基本思想.4.通过阅读中国古代数学的算法案例,体会中国古代数学对世界数学发展的贡献.四、课程标准知识和能力总结1.能用数学语言写出算法,并实现与程序框图的转换,体会对同一个问题而言,算法的多样性、优劣性,以及学习算法的必要性,注重观摩实例,操作简例,探索应用科学学习方法.2.在由自然语言，数学语言、程序框图向形式语言甚至简单的程序语言过渡的过程中进一步培养自己的抽象概括能力、语言表达能力和逻辑思维能力以及构造性解决问题的创新能力.注意循序渐进、由易到难、由简到繁的学习程序,重在原理及基本结构的掌握.注重由算法思想、算理算法过渡到算法语言及简单的程序语言.学习中多观察、模仿、理解、记忆,然后再实践操作．3.体会辗转相除法与更相减损术在求最大公约数时,更相减损术的优越性.深刻体会数学与实际的紧密联系,以较高的志趣与热情投入到数学学习中．五、学习警示算法的学习应当通过实例进行,在解决具体问题的过程中学习一些基本逻辑结构和语句,体会算法的思想,提高逻辑思维能力.为了有条理地、清析地表达算法应将解决问题的过程整理成程序框图,进一步将程序框图翻译成计算机语言.但不应将此部分内容简单处理成程序语言的学习和程序设计.在高中数学课程其他有关内容中应渗透算法思想方法,尽可能地运用算法解决相关问题和上机尝试.六、高考导航高考中应重点考查对变量赋值的理解掌握,对循环结构的灵活运用,阅读程序框图说明算理与算法(包括输出结果)，根据要求画出程序框图等.如2001年上海高考题第22题,便考查了程序框图、循环结构、算法思想，并结合函数与数列,考查较强的逻辑思维能力,这说明,算法知识与其他知识的结合将是高考的重点,也恰恰体现了算法的普遍性、工具性,当然难度不会太大,重在算理、算法及其思想．算法中的函数与方程一、算法与函数函数中的许多问题，例如：分段函数求值，高次函数求值，求函数的最值等，利用算法思想，通过算法中的选择结构和循环结构等可以简单的求解．例1已知函数22yxx，[1010]x，，且xZ．求该函数的最大值．画出流程图，并写出伪代码．分析：所给函数是二次函数，但定义域是|1010xxxZ，≤≤，即函数自变量只能取10到10之间的整数，因此要求出其最大值，可以将函数自变量对应的每一个函数值都求出，从中找出最大值即可．解：流程图如图1所示：伪代码如下：点评：本题中由于所给函数的自变量的取值是10到10之间的整数，只有有限个，且他们之间都相差1，这一特点正好适合用算法中循环语句进行算法描述，只需将所有函数值一一求出，从中找到最大值即可．例2在音乐唱片超市里，每张唱片售价25元．顾客如果购买5张以上（含5张）唱片，则按照九折收费；如果顾客购买10张以上（含10张）唱片，则按照八五折收费．请设计一个完成计费工作的算法，并画出流程图．分析：假设用变量a表示顾客购买的唱片数，用Ｃ表示顾客要缴纳的金额，依题意应有25522.551021.2510aaCaaaa，，，，，．≤≥解：算法步骤如下：第一步：输入a；第二步：若a5，则25Ca；否则，执行第三步；第三步：若a10，则22.5Ca；否则21.25Ca；第四步：输出Ｃ；流程图如图2．二、算法与方程中外历史上曾经有无数多位数学家作了大量的工作，探求得到了各种方程的求根公式，这些公式实际上就是一种算法，对于某些没有求根公式的方程，也借助现代计算技术的发展得到了一些典型的算法，如：二分法、牛顿法等等．例3写出用二分法求方程530xx的近似解（误差不超过0.01）的流程图．分析：这是一个五次方程，对于这类高次方程，我们没有求根公式，要求其近似解，可以利用二分法．令5()3fxxx，由于(1)10f，(2)310f，所以取初始区间[]ab，为[12]，，然后根据二分法的步骤进行算法设计．解：流程图如下：点评：由于用二分法求方程的近似解是用越来越小的区间逐次逼近，因此可以利用循环结构控制这一过程，在逼近过程中每次都要对是否满足精确度进行判断，所以可以利用选择结构实现．《算法初步》复习指导大的比例．随着现代信息技术的飞速发展，算法在科学技术、社会发展中发挥着越来越大的作用，并日益融入社会生活的许多方面，算法思想已经成为现代人应具备的一种数学素养，下面我们从以下几方面对算法知识进行复习．一、重点、难点分析一般地讲，算法是人们解决问题的固定步骤和方法．在本模块中，我们应重点掌握的是在数值计算方面的算法．2007年高考新课程标准数学考试大纲对《算法初步》的要求是：（1）算法的含义、流程图：①了解算法的含义，了解算法的思想；②理解流程图的三种基本逻辑结构：顺序结构、选择结构、循环结构．（2）基本算法语句：理解几种基本算法语句——输入语句、输出语句、赋值语句、选择语句、循环语句的含义．注意的是，考纲对算法的含义和算法的思想的要求是“了解”，而对流程图和基本算法语句的要求是“理解”．由此可见，复习中应把重点放在流程图和基本算法语句上，要对这两方面的内容重点掌握、多加练习．表达算法的方法有自然语言、流程图和基本算法语句三种．自然语言描述算法只是学习算法的一个过渡，流程图和基本算法语句才是学习的重点，同时也是难点，尤其是选择结构和循环结构，在复习中是重中之重．1．理解基本逻辑结构顺序结构、选择结构和循环结构是算法的三种基本逻辑结构．在画流程图时，首先要进行逻辑结构的选择，若求只含有一个关系式的解析式的函数的函数值时，只用顺序结构就能解决，顺序结构是任何一个算法中必不可少的结构．选择结构主要用在一些需要依据选择进行判断的算法中，如分段函数的求值、数据的大小关系比较等问题．循环结构主要用在一些有规律的重复计算的算法中，如累加求和、累乘求积等问题．用循环结构表达算法，关键要做好以下三点：①确定循环变量和初始值；②确定算法中反复执行的部分，即循环体；③确定循环的终止选择．循环结构又分为当型（Ｗhile型）和直到型（Until型）两种．当型循环在每次执行循环体前对控制循环的选择进行判断，当选择满足时执行循环体，不满足则停止；直到型循环在执行了一次循环体之后，对控制循环的选择进行判断，当选择不满足时执行循环体，满足则停止．两种循环只是实现循环的不同方法，它们是可以互相转换的．对同一个问题如果分别用当型循环和直到型循环来处理的话，那么两者判断的条件恰好相反．2．理解基本算法语句伪代码是表达算法的简单而实用的好方法，要注意各语句的作用，准确理解赋值语句，灵活表达选择语句，注意While语句和For语句的区别．（1）输入、输出语句和赋值语句基本对应于算法中的顺序结构，这是任何一个伪代码都用到的语句，利用输入、输出语句和赋值语句设计伪代码时应明确：需输入信息时用Read语句，需输出信息时用Print语句．当变量需要的数据较少或给变量赋予表达式时，用赋值语句即可，当变量需要输入多组数据且程序重复使用时，使用输入语句较好．当然，赋值语句还具有将一个变量的值赋给另一个变量，前一个变量的值保持不变的功能．（2）选择语句是表达算法中的选择结构，因为算法的流程根据选择是否成立有不同的流向，就需要对选择作出判断，所以伪代码中要用到选择语句．在某些较复杂的算法中，有时需要对按选择要求执行的某一语句（特别是Else后的语句）继续按照另一选择进行判断，这时可以再利用一选择语句完成这一要求，这就需要选择语句的嵌套．（3）循环语句是用来实现循环结构的，在本章我们主要需要掌握For语句与While语句．两种循环语句的区别：“For循环”一般用于循环次数已知时；“While循环”是“前测试”的当型循环，即先判断，后执行，若初始条件不成立，则一次也不执行循环体中的内容，任何一种需要重复处理的问题都可以用这种循环来实现．注：①循环有时还可通过Goto语句实现，但Goto语句破坏了语句顺序执行的正常状况，因此，一般不提倡使用；②注意计数变量的取值范围，以免出现多一次或少一次循环的错误．3．掌握一些常见的算法类型对一些常见的算法，尤其是算法中特有的方法要熟练掌握，通过重点理解分析，做到举一反三．其中最常见的算法有：①累加（乘）算法；②二分法；③分段函数求值算法；④递推算法；⑤求两数最大公约数的算法（辗转相除法与更相减损术）；⑥秦九韶算法等，这些算法的每一类都有其规律，可通过重点分析典型例题的方法，进行模仿、类比，从而掌握其一般规律．4．掌握运算符号含义在算法中，有一些运算符号具有确定的含义，如赋值时常用1nnSSn，等，这些式子在伪代码中非常重要，应切实理解；又如，我们经常用mod（a，b）表示a除以b所得的余数，用int()x表示不超过x的最大整数．注：伪代码没有统一的格式，只要书写简便、容易理解、表达清楚即可，但在学习本章时，建议使用符号相对统一，以免引起混淆．如用赋值语句“5x”表示给变量x赋值5，就不要再用“5x”或“5x”等其他形式来表示了．