素材：2012届高中数学2.1算法的基本思想素材北师大必修3.doc

第二章 算法初步第一节 算法的基本思想一 算法概念所谓算法可理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或看成按照要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题。 算法作为一个名词，我们虽没有深刻接触过这个概念，但算法在我们的学习和日常生活中却已经是无处不在了。如我们在小学学过的四则运算法则：先乘除后加减从里往外脱括弧以及乘法口诀，洗衣机的使用说明书，中国象棋的棋谱，国际象棋的棋谱等都是算法的具体体现。因此，处理任何问题都需要算法，从广义上说，算法就是做某一件事的步骤或程序。在数学上，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成.。算法一般是机械的，有时要进行大量重复的计算，只要按部就班的去做总能算出结果，通常把算法过程称为“数学机械化”。 二 算法的要求应当注意的是，我们现在所学习的算法是不同于求解一个具体问题的方法，它的要求是：写出的算法，必须能解决一类问题，并且能重复使用；算法过程能一步一步执行，每一步执行的操作，必须确切，不能含糊不清，而且在有限步后能得出结果。对于上述的算法要求，可细分如下：(1)、有穷性：一个算法的步骤序列是有限的，必须在有限操作之后停止，不能是无限的。这一点是十分重要的，是成功完成任务的必要条件，特别在算法的循环结构中，一定要考虑好何时终止，转入下一步操作。(2)、确定性：算法中的每一步应该是确定的并且能有效地执行，且能得到确定的结果，而不应是模棱两可。(3)、通用性：算法应该适用于求解一类问题，而不是只是用来解决一个具体的问题。这样在解决具体问题时，可以先针对具体问题涉及算法，在设计的过程中，或在设计完成后，考虑如何修改或推广该算法可以解决类似的问题，已达到通用性的要求。(4)、能行性：算法中每一部的运算和操作必须是相当基本的，也即它们原则上是能够精确地执行的。所谓基本和能实现是相对的，如：让计算机计算12345是可以做到的，但让计算机去执行“倒一杯水”“替我理发”等则是做不到的。(5) 有输入有输出 算法有零个或多个输入，还要有一个或多个输出。三 算法的表达描述表达描述算法可以有不同的方式，常用的有自然语言、程序框图、程序设计语言、为代码等。自然语言 它是指用汉语、英语或数学语言描述算法。优点是通徐易懂，党算法中的操作不重复且都是按顺序执行时，比较容易描述，如果算法中包含判断和转向，并且操作步骤较多时，此时描述起来就不那么直观清晰了。程序框图 就是用规定的图形符号来描述算法。用程序框图描述算法，它逆补了自然语言描述算法时有时显得庸长且易产生歧义的不足，它具有直观结构清晰、条理分明、便于检查修改与交流等优点。程序设计语言 算法最终要通过程序的形式编写出来，并在计算机上执行，程序设计语言分为低级语言和高级语言，低级语言包括机器语言和汇编语言，机器语言是计算机唯一能够识别的语言，汇编语言是一种符号语言。高级语言也叫算法语言，其表达方式接近于自然语言，容易被人们掌握和书写。四 概念应用灵活运用算法的概念和算法的基本思想和方法，可以写出一此简单问题的算法，我们常见的算法问题主要有两类：第一类 数值性计算问题如：解方程（或方程组），解不等式（或不等式组），套用公式判断性的问题，累加，累乘等一类问题的算法描述，对这类问题的解决我们可通过建立相应的数学模型，或通过固有的公式或计算方法来进行算法的设计与描述，同时要求所涉及的算法要步骤清晰和条理。例1、写出解方程x22x30的一个算法。解：算法1：第一步：移项，得x22x30； 第二步：式两边同加1并配方，得（x1）24； 第三步：式两边开方，得x12； 第四步：解得x3或x1。算法2：第一步：计算方程的判别式并判断其符号2243160；第二步：将a1，b2，c3代入求根公式x，得x13，x21点评：求解某个问题的算法不同于求解一个具体问题的方法，因此在设计算法时一定要做到以下几点：（1）写出的算法必须能解决一类问题，并且能够重复使用；（2）要使算法尽量简单、步骤尽量少；（3）要保证算法正确，且计算机能够执行。而在本题中出现了两种不同的算法，比较两种算法发现，算法2更简单，步骤少，所以利用公式解决问题是最理想、合算的算法，因此我们在今后设计算法的过程时，首先要考虑利用公式。第二类 非数值性计算问题解决对于象排序、查找、变量变换、文字处理等非数值性计算问题，要先建立过程模型，通过模型来进行算法的设计与描述。例2、有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题。分析：由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水瓶的办法进行交换。解：算法步骤如下：第一步：取一只空的墨水瓶，设其为白色；第二步：将黑墨水瓶中的蓝墨水装入白瓶中；第三步：将蓝墨水瓶中的黑墨水装入黑瓶中；第四步：将白瓶中的蓝墨水装入蓝瓶中；第五步：交换结束。点评：在本体中我们首先建立过程模型