资源简介

(共21张PPT)
第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
谢谢聆听，
下节课再见！

展开更多......

收起↑