算法案例分析
自主学习
1.算法(algorithm)一词源于算术(algorism)，即算术方法，是指一个由已知推求未知的运算过程。后来，人们把它推广到一般，把进行某一工作的方法和步骤称为算法。 广义地说，算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的算法，等等。 2. 2．算法的重要特征：
（1）有限性：一个算法在执行有限步后必须结束； （2）确定性：算法的每一个步骤和次序必须是确定的；
（3）输入：一个算法有0个或多个输入，以刻划运算对象的初始条件．所谓0个输入是指
算法本身定出了初始条件．
（4）输出：一个算法有1个或多个输出，以反映对输入数据加工后的结果．没有输出的
算法是毫无意义的．
师生互动
例1
解：算法如下：
第一步：判断n是否等于2，若n=2，则n是质数；若n>2，则执行第二步。
第二步：依次从2至（n-1）检验是不是n的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数。
这是判断一个大于1的整数n是否为质数的最基本算法。
点评：通过例1明确算法具有两个主要特点：有限性和确定性。
练1
解：第一步：把水注入电锅； 第二步：打开电源把水烧开； 第三步：把烧开的水注入热水瓶.
点评：在日常生活中做任何一件事情，者是按照一定规则，一步一步进行，比如在工厂中生产一部机器，先把零件一道道工序进行加工，多面手一，又把各种零件按一定法则组装成一产，了完整机器，它们的工艺流程就是算法；在农村，种庄稼有耕地、播种、育苗、施肥、中耕、收割等各个环节，这些栽培技术也是算法。总之，在任何这些数值计算或非数值计算的过程中所采取的方法和步骤，都称之为算法。
例2。解：8251＝6105×1＋2146
显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0
则37为8251与6105的最大公约数。
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公
第- 1 -页 共17页
元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；
第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn＝0，此时所得到的rn-1即为所求的最大公约数。 练2. 53 巩固练习
1.D2.C3. 答案：第二个算法更高效.因为节约时间4. 答案：解析：算法1： S 1.再找一个大小与A相同的空杯子C； S 2.将A中的水倒入C中； S 3.将B中的酒倒入A中；
S 4.将C中的水倒入B中，结束. 算法2：
S1.再找两个空杯子C和D；
S2.将A中的水倒入C中，将B中的酒倒入D中；
S3.将C中的水倒入B中，将D中的酒倒入A中，结束.
课后巩固练习
1. 答案：解析：算法1：
S 1.再找一个大小与A相同的空杯子C； S 2.将A中的水倒入C中； S 3.将B中的酒倒入A中； S 4.将C中的水倒入B中，结束. 算法2：
S1.再找两个空杯子C和D；
S2.将A中的水倒入C中，将B中的酒倒入D中；
S3.将C中的水倒入B中，将D中的酒倒入A中，结束.
2.解：算法或步骤如下： S1 人带两只狼过河； S2 人自己返回；
S3 人带一只羚羊过河； S4 人带两只狼返回； S5 人带两只羚羊过河； S6 人自己返回； S7 人带两只狼过河； S8 人自己返回； S9 人带一只狼过河． 算法案例分析（2） 自主学习 1.略
第- 2 -页 共17页
2. 步骤或程序 计算机. 3. 多 师生互动 例1
解：用消元法解这个方程组，步骤是：
第一步：方程①不动，将方程②中x的系数除以方程①中x的系数，得到乘数m?第二步：方程②减去m乘以方程①，消去方程②中的x项，得到
4?2； 2?2x?y?7； ??3y??3第三步：将上面的方程组自下而上回代求解，得到y??1，x?4．
?x?4所以原方程组的解为?．
y??1?点评：通过例1再次明确算法特点：有限性和确定性
例2.则不难设计出以下步骤：
2
第一步：令f(x)=x–2。因为f(1)<0，f(2)>0，所以设x1=1，x2=2。 第二步：令m=(x1+x2)/2，判断f(m)是否为0，若则，则m为所长；若否，则继续判断f(x1)·f(m)大于0还是小于0。
第三步：若f(x1)·f(m)>0，则令x1=m；否则，令x2=m。
第四步：判断|x1–x2|<0.005是否成立？若是，则x1、x2之间的任意取值均为满足条件的近似根；若否，则返回第二
点评：渗透循环的思想，为后面教学做铺垫。巩固练习 例3解： 算法1 按照逐一相加的程序进行． 第一步：计算1+2，得到3；
第二步：将第一步中的运算结果3与3相加，得到6； 第三步：将第二步中的运算结果6与4相加，得到10； 第四步：将第三步中的运算结果10与5相加，得到15． 算法2 运用公式1?2?3? 第一步：取n=5；
第二步：计算
?n?n(n?1)直接计算． 2n(n?1)； 2 第三步：输出运算结果．
算法3 用循环方法求和． 第一步：使S?1，； 第二步：使I?2； 第三步：使S?S?I；
第四步：使I?I?1；
第五步：如果I?5，则返回第三步，否则输出S． 点评：一个问题的算法可能不唯一． 巩固练习
1.解：第一步：②×a1 - ①×a2，得：
?a1b2?a2b1?y?a1c2?a2c1 ③
第二步：解③得
y?a1c2?a2c1a1b2?a2b1；
第- 3 -页 共17页
第三步：将
y?a1c2?a2c1a1b2?a2b1代入①，得x?c1?b1y a1点评：可推广到解一般的二元一次方程组，说明算法的普遍性：很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限、事先设计好的步骤加以解决.
解2.
1．确定区间[a,b]，验证
f(a)f(b)?0，给定精度ε；
2. 求区间(a,b)的中点x1； 3. 计算
f(x1)： 若f(x1)?0，则x1就是函数的零点； 若f(a)f(x1)?0，则令b?x1（此时零
f(x1)f(b)?0，则令a?x1（此时零点x0?(x1,b)）；
点x0?(a,x1)）； 若
4. 判断是否达到精度ε；即若|a?b|??，则得到零点零点值a（或b）；否则重复步骤2~4．
3.解：因为一次只能渡过一个大人，而船还要回来渡其他人，所以只能让两个小孩先过河。
渡河的方法与步骤为：
第一步 两个小孩同船渡过河去； 第二步 一个小孩划船回来；
第三步 一个大人独自划船渡过河去； 第四步 对岸的小孩划船回来； 第五步 两个小孩再同船渡过河去； 第六步 一个小孩划船回来；
第七步 余下的一个大人独自划船渡过河去； 第八步 对岸的小孩划船回来； 第九步 两个小孩再同船渡过河去. 课后巩固练习
1.解：第一步：使S?1，；
第二步：使I?2；
1； I第四步：使S?S?n； 第五步：使I?I?1；
第六步：如果I?100，则返回第三步，否则输出S自主学习
第三步：使n?2解：算法如下：
第一步 输入总头数H，总脚数F；
第二步 计算鸡的个数x＝（4?H－F）/2； 第三步 计算兔的个数y＝（F－2?H）/2； 第四步 输出x，y. 排序方法多样性 师生互动
例1.首先中间的数（即第8个数）23比较，由于27>23，故27在23的右边；在于23右边的7个数中的中间的数39比较，由于27<39,故27在39的左边；再与23右边39左边的3个数中间数37比较，由于27<37，故27在37的左边；最后27与24比较，由于27>24，故27在2,4的右边，所以27应排在24与37之间，因此共进行4次比较即可完成。 例2
第- 4 -页 共17页
38，49，65，97，76，13，27，49 38，49，65，97，76，13，27，49 38，49，65，97，76，13，27，49 38，49，65，76，97，13，27，49 38，49，65，76，13，97，27，49 38，49，65，76，13，27，97，49 38，49，65，76，13，27，49，97 巩固练习1 、B 2 {7,5} 3、B 课后巩固练习 自主学习
1.①自然语言 ②程序框图 ③程序语言
2. 程序框图也叫流程图，是人们将思考的过程和工作的顺序进行分析、整理，用规定的文字、符号、图
形的组合加以直观描述的方法
3.
起止框
输入输出框 处理框 判断框
连接点
用带有箭头的流程线连接图形符号
4. _顺序结构、选择结构_、循环结构 师生互动
【解】其算法设计如下：
例1. 输入a，b，h； 2. 计算Ｓ＝1（ａ＋ｂ）ｈ； 3．输出Ｓ．
2流程图：
例2解：算法设计如下：
A B C 第- 5 -页 共17页