《第8课 算法的多样性》参考课件1

第二单元算法的效率目

录第9课

算法的评价方法第8课

算法的多样性第11课“韩信点兵”筛选法的实现第10课“韩信点兵”枚举法的实现第12课“韩信点兵”同余法的实现学习目标能依照算法的描述和问题实例评估算法的效率。知道算法具有多样性。能根据简单问题求解的需求设计出合适的算法。前

言

解决同一个问题可能会有多种算法不同算法的效率也有可能是不一样的在利用算法解决问题时，要根据问题求解的需求设计出合适的算法。思

考

猜数字游戏，你能用多种算法来解决吗?

你觉得怎样的算法才是“好”的算法?第8课算法的多样性学习内容同一问题的多种算法验证同一问题存在多种算法讨

论

下图中，童童从学校到家有哪几条路线可走?建

构

日常生活中，算法具有多样性，即可用多种不同的算法来解决同一个问题。

例如，解决猜数字游戏问题，除了前面学过的算法外，还可以采用顺序查找和二分查找算法。一、问题分析

猜数字游戏中，同学A输入数字的过程其实是一个“查找”问题，即在1-100范围内查找目标数da，可采用多种不同的策略来解决。

例如:

方法一:按顺序依次查找

依次将1，2，3，•••，98,，99，100(或100，99，•••，3，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，初始范围为1-100

第一次比较:37<50，范围调整为1-49

第二次比较:37>25，范围调整为26-49

第三次比较:37=37，查找成功。小知识

计算机中的“查找”指根据既定条件找出满足条件的对象，也就是说在存储的大量数据内找出一个特定的数据，或者判定在一批数据内是否存在特定的数据。试一试

采用“按顺序依次查找”的方法，在1-100范围内查找数37，则需比较的次数是多少?二、解决问题的多种算法设计

根据解决问题采用的策略，将其设计成算法。例如，上述猜数字游戏就可将“按顺序依次查找”设计成顺序查找算法，“取中间数查找”设计成二分查找算法。

算法一:顺序查找。假设目标数为37，并用变量da表示，取到的数用变量cai表示。对应的算法流程图如下:二、解决问题的多种算法设计二、解决问题的多种算法设计

算法二:二分查找。

假设目标数为37，并用变量da表示，计算得到的中间值用变量cai表示，用变量cz和zz表示可取数的范围，初始查找范围为1-100，则cz的初值为1，zz的终值为100。对应的算法流程图如下:二、解决问题的多种算法设计三、解决问题的多种算法验证

上述顺序查找算法和二分查找算法可以通过编写并运行程序或流程图来进行验证。

程序验证算法一:想一想

算法一的程序，若变量da的值为137，那么运行结果会是什么?如果想要显示相应的提示，那么应该如何修改程序?三、解决问题的多种算法验证

用流程图验证算法二:

根据刚才讲到的算法二的流程图，通过下方表格的形式列出变量cz、变量zz和变量cai的值来进行验证。

找到数37，共进行了3次循环。试一试

请同学们试一试，当变量da的值为137时，怎样用表格列出变量cz、变量zz和变量cai的值。练