§ 算法的概念

1 / 10 算法的概念 莲山课 件 k 算法的概念 【教学目标】： （ 1）了解算法的含义，体会算法的思想。 （ 2）能够用自然语言叙述算法。 （ 3）掌握正确的算法应满足的要求。 （ 4）会写出解线性方程（组）的算法。 （ 5）会写出一个求有限整数序列中的最大值的算法。 【教学重点】算法的含义、解二元一次方程组和判断一个数为质数的算法设计。 . 【教学难点】把自然语言转化为算法语言。 . 【学法与教学用具】： 学法： 1、写出的算法，必须能解决一类问题 (如：判断一个整数n(n1)是否为质数；求任意一个方程的近似解； ) ，并且能够重复使用。 2、要使算法尽量简单、步骤尽量少。 3、要保证算法正确，且计算机能够执行，如：让计算机计算 12345 是可以做到的，但让计算机去执行 “ 倒一杯水 ”“ 替我理发 ” 等则是做不到的。 2 / 10 教学用具 :计算机， TI-voyage200 图形计算器 【教学过程】 一、本章章头图说明 章头图体现了中国古代数学与现代计算机 科学的联系，它们的基础都是 “ 算法 ” 。 算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念。但是我们却从小学就开始接触算法，熟悉许多问题的算法。如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现。广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。 古代的计算工具：算筹与算盘 . 20 世纪最伟大的发明：计算机，计算机是强大的实现各种算法的工具。 例 1：解二元一次方程组： 分析：解二元一次方程组的主要思想是消元的思想，有代入消元和加减消元两种消元的方法，下面用加减消元法写出它的求解过程 . 解：第一步： -2 ，得： =3； 3 / 10 第二步：解 得； 第三步：将代入 ，得 . 学生探究：对于一般的二元一次方程组来说，上述步骤应该怎样进一步完善？ 老师评析：本题的算法是由加减消元法求解的， 这个算法也适合一般的二元一次方程组的解法。下面写出求方程组的解的算法： 例 2：写出求方程组的解的算法 . 解：第一步： a1 -a2 ，得： 第二步：解 得； 第三步：将代入 ，得 利用 TI-voyage200 图形计算器演示：（吸引学生的注意力） 运行结果： （其中输入 a1=1,b1=-2,m1=-1,a2=2 b2=1,m2=1，当然可输入其它数值 ) 算法概念： 在数学上，现代意义 上的 “ 算法 ” 通常是指可以用计算机来解决的某一类问题是程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成 . 说明： 4 / 10 1.“ 算法 ” 没有一个精确化的定义，教科书只对它作了描述性的说明 . 2.算法的特点 : (1)有限性： 一个算法的步骤序列是有限的，必须在有限操作之后停止，不能是无限的 . (2)确定性： 算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可 . (3)顺序性与正确性： 算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能完成问题 . (4)不唯一性： 求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法 . (5)普遍性： 很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限、事先设计好的步骤加以解决 . 例题讲评： 例 3、任意给定一个大于 1 的整数 n，试设计一个程序或步5 / 10 骤对 n 是否为 质数做出判断 . 分析：（ 1）质数是只能被 1 和自身整除的大于 1 的整数 . （ 2）要判断一个大于 1 的整数 n 是否为质数，只要根据质数的定义，用比这个整数小的数去除 n，如果它只能被 1 和本身整除，而不能被其它整数整除，则这个数便是质数 . 解：算法： 第一步：判断 n 是否等于 2.若 n=2，则 n 是质数；若 n 2，则执行第二步 . 第二步：依次从 2（ n-1）检验是不是 n 的因数，即整除 n的数 .若有这样的数，则 n 不是质数；若没有这样的数，则 n是质数 . 说明：本算法是用自然 语言的形式描述的 .设计算法一定要做到以下要求： （ 1）写出的算法必须能解决一类问题，并且能够重复使用 . （ 2）要使算法尽量简单、步骤尽量少 . （ 3）要保证算法正确，且计算机能够执行 . 利用 TI-voyage200 图形计算器演示： (学生已经被吸引住了 ) 运行 例 4、 .用二分法设计一个求方程的近似根的算法 . 分析：该算法实质是求的近似值的一个最基本的方法 . 解：设所求近似根与精确解的差的绝对值不超过，算法： 第一步：令 .因为，所以设 x1=1， x2=2. 6 / 10 第二步：令，判断 f（ m）是否为 0.若是，则 m 为所求；若否，则继续判断大于 0 还是小于 0. 第三步：若，则 x1=m；否则，令 x2=m. 第四步：判断是否成立？若是，则 x1、 x2 之间的任意值均为满足条件的近似根；若否，则返回第二步 . 说明：按以上步骤，我们将依次得到课本第 4 页的表 1-1 和图于是，开区间（，）中的实数都满足假设条件的原方程是近似根 .运行结果： 练习 1： 写出解方程 x2 2x 3 0 的一个算法。 解：算法 1： 第一步：移项，得 x2 2x 3 0； 第二步： 式两边同加 1 并配方，得（ x 1） 2 4； 第三步： 式两边开方，得 x 1 2 ； 第四步：解 得 x 3 或 x 1。 算法 2： 第一步：计算方程的判别式判断其符号 22 43 16 0； 第二步：将 a 1， b 2， c 3 代入求根公式 x， 得 x1 3， x2 1 评析：比较两种算法，算法 2 更简单，步骤少，所以利用公7 / 10 式解决问题是最理想、合 算的算法。因此在寻求算法的过程中，首先是利用公式。 下面设计一个求一般的一元二次方程 ax2 bx c 0 的根的算法如下： 第一步：计算 b2 4ac； 第二步：若 0； 第三步：输出方程无实根； 第四步：若 0 ； 第五步：计算并输出方程根 x1,2。 练习 2、求 1357911 的值，写出其算法。 第一步，先求 13 ，得到结果 3； 第二步，将第一步所得结果 3 再乘以 5，得到结果 15； 第三步，再将 15乘以 7，得到结果 105； 第四步，再将 105 乘以 9，得到 945； 第五步，再将 945 乘以 11，得到 10395，即是最后结果。 评析：求解某个问题的算法不同于求解一个具体问题的方法，算法必须能够解决一类问题，并且能够重复使用；算法过程要能一步一步地执行，每一步操作必须确切，能在有限步后得出结果。 练习 3、有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题。 8 / 10 分析：由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水 瓶的办法进行交换。 解：算法步骤如下： 第一步：取一只空的墨水瓶，设其为白色； 第二步：将黑墨水瓶中的蓝墨水装入白瓶中； 第三步：将蓝墨水瓶中的黑墨水装入黑瓶中； 第四步：将白瓶中的蓝墨水装入蓝瓶中； 第五步：交换结束。 评析：对于这种非数值性问题的算法设计问题，应当首先建立过程模型，根据过程设计步骤，完成算法。 小结 1、算法概念和算法的基本思想 （ 1）算法与一般意义上具体问题的解法的联系与区别； （ 2）算法的五个特征。 2、利用算法的思想和方法解决实际问题，能写出一此简单问题的算法 3、两类算法问题 （ 1）数值性计算问题，如：解方程（或方程组），解不等式（或不等式组），套用公式判断性的问题，累加，累乘等一类问题的算法描述，可通过相应的数学模型借助一般数学计算方法，分解成清晰的步骤，使之条理化即可。 （ 2）非数值性计算问题，如：排序、查找、变量变换、文9 / 10 字处理等需先建立过程模型，通过模型进行算法设计与描述。 4、利用 TI-voyage200 图形计算器演 示时，开始学生看，想，探究，然后模范、创新。图形计算器为学生创建一个自我发挥的平台。 作业：（课本第 4 页练习） 1、任意给定一个正实数，设计一个算法求以这个数为半径的圆的面积 . 解：算法步骤： 第一步：输入任意一个正实数 r； 第二步：计算以 r 为半径的圆的面积：； 第三步：输出圆的面积 S. 2、任意给定