1.1算法案例分析

1、1 算法的基本思想,第二章 算法初步,蒲城县尧山中学 韩红美,1.了解算法的含义，形成算法的初步印象，体会算法是解决问题的“机械”程序，并能在有限步内解决问题； 2.能够用自然语言叙述算法； 3.掌握正确的算法应满足的条件；（重点） 4.会写出简单问题的算法.（难点）,例1 在电视台的某个娱乐节目中，要求参与者快速猜出物品价格.主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确.在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜.下面是主持人和参与者之间的一段对话：,参与者：800元！ 主持人：高了！ 参与者：400元！ 主持人：低了！ 参与者

2、：600元！ 主持人：低了! 如果你是参与者，你接下来会怎么猜？,实际上，可以把过程概括如下：,按照上述方法，继续判断，直到游戏结束.像这样的一系列步骤通常称为解决这个问题的一个算法.,例2 在给定素数表的条件下，设计算法，将936分解成素因数的乘积.(4 000以内的素数表见课本附录1),解:算法步骤如下： 1.判断936是否为素数：否. 2.确定936的最小素因数：2. 936=2468. 3.判断468是否为素数：否. 4.确定468的最小素因数：2. 936=22234. 5.判断234是否为素数：否. 6.确定234的最小素因数：2. 936=222117.,7.判断117是否为素数

3、：否. 8.确定117的最小素因数：3. 936=222339. 9.判断39是否为素数：否. 10.确定39的最小素因数：3. 936=2223313. 11.判断13是否为素数：13是素数，所以分解结束.,分解结果是： 936=2223313.,按照以上程序，完成了对936的素因数分解.实际上，在给定素数表的基础上，对任意自然数n，都可以按照上述办法进行分解.,以上步骤是解决素因数分解问题的一个过程，只要依照这一系列步骤，都能解决这个问题，我们把这一系列步骤称为解决这个问题的一个算法.,例3 设计一个算法，求840与1764的最大公因数.,1.先将840进行素因数分解： ；,2.然后将1

4、764进行素因数分解： ；,3.确定它们的公共素因数:2,3,7；,4.确定公共素因数的指数：公共素因数2,3,7的指数分别为2,1,1;,5.最大公因数为: .,解：算法步骤如下：,以上步骤就是求两个正整数的最大公因数的一个算法.这个算法的思想具有一般性，它可以帮助设计求三个或者三个以上正整数的最大公因数的算法. 通过以上的例子可以看出，算法是解决某类问题的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决，一般来说，“用算法解决问题”都是可以利用计算机帮助完成的.,例4 “韩信点兵”问题. 韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳.据说他在点兵的时

5、候，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵方法：先令士兵从13报数，结果最后一个士兵报2；再令士兵从15报数，结果最后一个士兵报3；又令士兵从17报数，结果最后一个士兵报4.这样，韩信很快就算出了自己部队士兵的总人数.请设计一个算法，求出士兵至少有多少人?,1.首先确定最小的满足除以3余2的正整数：2;,解：具体算法步骤如下：,5.在第4步得到的一列数中找出满足除以7余4的最小数53,这就是我们要求的数.,4.然后依次加上15，得到8，23，38，53 ，显然这些数既满足除以3余2，又满足除以5余3;,3.在上列数中确定最小的满足除以5余3的正整数：8;,2.依次加3就得到

6、所有除以3余2的正整数：2，5，8，11，14，17，20，23，26，29，32，35，38，41，44，47，50，53，56，,3.算法要简洁，要清晰可读，不能繁杂，易程序化.,算法不同于求解一个具体问题的方法，是这种方法的高度概括.一个好的算法有如下要求：,1.写出的算法，必须能解决一类问题（如一元二次方程求根公式），并且能重复使用.,2.算法过程要能一步一步执行，每步执行的操作，必须确切，不能含混不清，而且在有限步后能得出结果.,例5. 一位商人有9枚银元，其中有1枚略轻的是假银元.你能用天平（不用砝码）将假银元找出来吗？,解: 1.把银元分成3组，每组3枚.,2.先将两组分别放在天

7、平的两边.如果天平不平衡，那 么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的第3组里.,3.取出含假银元的那一组，从中任取两枚银元放在天平的两边.如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元.,算法是什么？,算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤，或看成按要求设计好的、有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题.,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤.,说明：,1.算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步

8、地去做，最终便能解决问题.,2.算法的基本思想就是我们分析问题时的想法.由于想法不同、思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分.,3.从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法.,在函数的应用部分，我们学习了用二分法求方程f(x)=0的近似解，二分法求方程近似解的基本思想是：将方程的有解区间平分为两个小区间，然后判断解在哪个小区间；继续把有解的区间一分为二进行判断，如此周而复始，直到求出满足精度要求的近似解.,其算法步骤如下：,5.判断新的有解区间的长度是否大于精度:,(1)如果新的有解区间长度大于精度,则在新的有解区间的基础上重复相应步骤;,

9、(2)如果新的有解区间长度小于或等于精度,则这个有解区间中的任意一个数均为方程的满足精度的近似解.,3.计算f(0.5)=-0.625;,例6,；,6.计算f(0.75)=-0.015 625;,9.计算f(0.875)=0.435 546 875;,10.由于f(0.75)f(0.875)0.1;,;,12.计算f(0.812 5)=0.196 533 203 125;,所以，区间0.75,0.812 5中的任一数值，都可以作为方程的近似解.,13.因f(0.75) f(0.812 5)0，得有解区间0.75,0.812 5，0.812 5-0.75=0.062 50.1.,1.令f(x)=

10、x3+x2-1,因为f(0)f(1)0,所以设x1=0,x2=1.,3.若f(x1)f(m)0,则令x1= m;否则,令x2= m.,简化写法:,4.判断|x1-x2|0.1是否成立，若是,则x1,x2之间的任意值为满足条件的近似解;若否,则返回2.,算法的特征:,有穷性：一个算法应当包含有限的操作步骤而不应当是无限的;,确定性：算法中每一个步骤应当是确定的，而不应当是含糊的、模棱两可的;,有效性：算法中的每一个步骤应当能有效地执行，并得到确定的结果.,输入:有零个或多个输入;,输出:有一个或多个输出;,1.下列语句中是算法的个数为（）从济南到巴黎：先从济南坐火车到北京，再坐飞机到巴黎；统筹法中“烧水泡茶”的故事；测量某棵树的高度，判断其是否是大树；已知三角形的一部分边长和角，借助正余弦定理求得剩余的边角，再利用三角形的面积公式求出该三角形的面积 A.1 B.2 C.3 D.4,C,2.设计一个算法求三角形的面积，把下列步骤补充完整： (1)求出三角形的底边长； (2)_； (3)根据三角形的面积公式求出三角形的面积. 【解析】由题意知,第（2）步应为求底边上的高.,求底边上的高,3.一个人带三只狼和三只羚羊过河，只有一条船，船可以容纳一个人和两只动物没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊请设计过河的算法,解：算法