k5§1.1.1算法的概念(珠海市斗门和风中学邝国均).pdf

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