(
课件网) 第8课 算法的多样性 主要内容： 1.同一问题存在多种算法。 2.同一问题的多种算法验证。 下图中，童童从学校到家有哪几条路线可以走？ 现实中，解决一个问题的算法往往具有多样性，即可用不同的算法解决同一个问题。 例如，解决猜数字游戏问题，除了前面学过的算法外，还可以采用顺序查找和二分查找算法。 猜数字游戏中，同学A输入数字的过程其实是一个“查找”问题，即在1-100范围内查找目标数da，可采用多种不同的策略来解决。 一 问题分析 策略一：按顺序依次查找。 依次将1，2，3，...，99,100（或100,99,98，...，2，1）与da比较，直到找到为止。 一 问题分析 策略二：取中间数查找。 1-100范围内的数是依次增加的，依据该有序性可依次取中间数来查找。先取1-100的中间数50与da比较，若da等于50，则查找成功；若da小于50，则取1-49的中间数25与da比较；若da大于50，则取51-100的中间数75与da比较...如此反复，直道找到为止。在1-100范围内查找目标数37的过程如下所示： 一 问题分析 一 问题分析 一 问题分析 二 解决问题的多种算法设计 根据解决问题采用的策略，将其设计成算法。例如，上述猜数字游戏就可“按顺序依次查找”设计成顺序查找算法，“取中间数查找”设计成二分查找算法。 二 解决问题的多种算法设计 算法一：顺序查找。假设目标数为37，并用变量da表示，取到的数用变量cai表示。对应的算法流程图如图： 二 解决问题的多种算法设计 算法二：二分查找。假设目标数为37，并用变量da表示，计算得到的中间值用变量cai表示，用变量cz和zz表示可取数的范围，初始查找范围为1-100，则cz的初值为1，zz的终值为100。对应的流程图如图： 三 解决问题的多种算法验证 上述两种算法可以通过编写程序或流程图的执行进行验证。 三 解决问题的多种算法验证 三 解决问题的多种算法验证 算法二的流程图验证： 根据上述算法二的流程图，可通过表格的形式列出变量cz、zz和cai的值来验证该算法。 通过3次循环，找到数37。 三 解决问题的多种算法验证 在上述算法一种，若变量cai的取值依次为100，99，...，2，1，则相应的算法和程序如何修改？ da=37 cai=100 while cai>0: if cai==da: print(“找到的数为：”,cai) break else: cai=cai-1 谢谢聆听， 下节课再见！
