2020-2021学年第三章 算法基础3.1 体验计算机解决问题的过程本节综合与测试一等奖ppt课件

这是一份2020-2021学年第三章 算法基础3.1 体验计算机解决问题的过程本节综合与测试一等奖ppt课件，共15页。

在现实生活中，我们经常需要对数据进行统计、分析。当数据量不多时，我们可以采用人工方法来处理:然而，当数据量变多时，我们运用计算机来解决问题将是一种更高效、更便捷的方法。
3.1.1人工解决问题的过程
采样人工方法解决问题，首先需要明确所要解决的问题给出的条件，然后再根据已有的经验和知识确定解决问题的方法，从而解决问题。
探究活动思考如何设计从A市到B市耗时最少的旅行路线方案呢？假如我们从铁路公司、各航空公司和汽车客运公司网站得知，直达B市的交通工具只有火车和汽车两种，出发地有B1，B2，…，Bk市（没有A市），从A市出发到B1，B2，…，Bk市的交通工具有飞机、火车和汽车三种，这样从A市经B1，B2，…，Bk市到B市的交通情况如右图所示。由于从A市到B1，B2，…，Bk市有不同的交通工具，每一种交通工具又有不同的班次，因此从A市出发到中转城市B1，B2，…，Bk市就有M1、M2，…，Mk种班次。同样，从中转城市B1，B2，…，Bk市到B市也有不同的交通工具，每一种交通工具有不同的班次，因此从中转城市B1，B2，…，Bk市到B市就有N1，N2，…，Nk种班次。于是从A市经B1，B2，…，Bk市到B市的交通班车（班机）数共有：S=M1×N1+M2×N2+…+Mk×Nk寻找从A市到B市耗时最少的旅行路线问题就转化为在S种联运班次中找到一种耗时最少的联运班次。这样就需要遍历每一个班次进行比较。若用人工方式找出能够中转且等待时间和行驶时间最少的班次，工作量将极其浩大!
假设从A市到B市的中转城市只有B1、B2市，从A市经B1、B2市到B市的交通情况如表3-2和表3-3所示。
从以上两表可知，从A市经B,市到B市的联运班次有7×9=63(班），从A市经B,市到B市的联运班次有12×9=108（班)，合计为S=63+108=171(班）。然后在171班次中找到能够中转且等待时间加上行驶时间最少的联运班次，如图3-5所示。
分析根据表3-2和表3-3给出的已知条件，可以采用以下的思路求解耗时最少的联运班次问题:(1）)找出能够中转的从A市经B,市到达B市的联运班次，并计算所用的时间。(2）找到能够中转的从A市经B,市到达B市的联运班次中耗时最少的联运班次。(3）找出能够中转的从A市经B,市到达B市的联运班次，并计算所用的时间。(4）找到能够中转的从A市经B,市到达B市的联运班次中耗时最少的联运班次。(5)取两条线路中耗时最少的联运班次为最佳旅行路线。上述问题中，假如中转城市很多，交通班次也很多，找出耗时最少路线的工作量会非常大,若用人工穷举遍历,其效率就会很低。
3.1.2计算机解决问题的一般过程
当数据量很大，人工处理效率很低时，我们可以借助计算机，通过编写计算机程序解决问题。编写计算机程序解决问题要经过分析问题。设计算法，编写程序、调试运行程序等若干个步骤。
1.分析问题在利用计算机解决问题之前，我们首先要分析问题的需求情况、已知条件和需要解决的问题。例如，在从A市到B市耗时最少的旅行路线问题中，在不知道有多少个中转城市和每个城市有多少班车(或飞机)的情况下，我们可以利用大数据挖掘技术中的爬虫程序(参见配套学习资源包“第三章课本素林程序3-1”) 到铁路网站、各航空公司和汽车客运公司网站获取从A市经中转城市B1，B2，……，B3市到达B市的交通班次信息，再经过数据请洗后，形成结构化的数据存储为Excel文件(部分截图如图3.6所示，详细文件可参见配套学习资源包“第三章课本素彬Exel"文件夹)。
2.设计算法问题分析清楚后，需要给出解决问题的详细方法和步骤，这一过程称为设计算法。例如，对于从A市到B市耗时最少的旅行路线问题，根据获取的从A市到B市的中转城市B1，B2，……，Bk的班次，以及各城市各交通班次的发车时间和行驶时间等信息，采用以下的思路找出耗时最少的联运班次问题:(1)分别找出能够中转的从A市经B1，B2，……，Bk市到达B市的联运班次，并计算所用的时间。(2)分别找到能够中转的从A市经B1，B2，……，Bk到达B市的联运班次中耗时最少的联运班次，共k条线路。(3)取k条线路中耗时最少的联运班次为最佳旅行路线。
3.编写程序有了清晰可操作的算法描述，就可以选择t种计算机语言工具来编写程序，实现算法。一般来说，只要算法确定，对计算机程序设计语言的选择没有特别的限定，通常根据问题的特性和编程人员对语言的熟悉程度来选定编写程序。
例如，用Pyhn语言编写从A市到B市耗时最少的旅行路线问题的算法的程序可参见配套学习资源包“第三章课本素林程序3-1”。其中，找出能够从入市经B (i=1, 2,……，k)市到达B市的中转联运班次，并计算所用的时间以及找到耗时最少的联运路线的关键程序段如下。
4.调试运行程序程序编写完成以后，再通过键盘把程序输人计算机中运行，检查程序能否按预想的效果执行，这一过程称为程序的调试运行。计算机只能识别程序设计语言中所规定的语法规则，如果编写程序时与规则不一致，哪怕是一个标点符 号出错，也会因程序出错而中断运行。此时，我们可以根据计算机提示的出错信息修改程序，重新调试运行。由于Pythn是解释程序，因此它的调试是在运行过程中逐行进行的。当程序能够顺利运行以后，我们还需要对程序运行的结果进行检查。因为如果程序语句符合语法规则，而程序中却有逻辑或计算方法等错误，计算机是检查不出来的。因此，如果结果不合理，还要对程序甚至算法进行修改，直到程序的功能符合设计要求为止。
实践打开配套学习资源包“第三章课本素材\程序3-1”，调试并运行程序3-1，找出从A市到B市耗时最少的旅行路线问题的结果，如图3-7所示。