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