第三章-算法基础.ppt

第三章算法基础引言数据在信息社会中具有重要价值，掌握数据处理的基本方法与技能具有重要意义。随着数据的快速增长，人工方式处理海量数据的效率正变得低下，因此掌握利用计算机和算法更高效地分析和解决问题的方法在计算机科学界的作用日益凸显。计算机解决问题的过程1、分析问题在利用计算机解决问题之间，我们首先要分析问题的需求情况、已知条件和需要解决的问题2、设计算法问题分析清楚后，需要给出解决问题的详细方法和步骤，这一过程称为设计算法。3、编写程序有了清晰可操作的算法描述，就可以选择一种计算机语言工具来编写程序，实现算法。一般来说，只要算法确定，对计算机程序设计语言的选择没有特别的限定，通常根据问题的特性和编程人员对语言的熟悉程度来选定编写程序。4、调试运行程序程序编写完成以后，再通过键盘把程序输入计算机中运行，检查程序能否按预想的效果执行，这一过程称为程序的调试运行。一、设计从A市到B市耗时最少的旅行路线方案当从A市到B市没有直达的交通工具时（不考虑水上交通工具），我们可以利用铁路公司、汽车客运公司和航空公司公布的信息，设计出最佳的旅行路线。我们从铁路公司、各航空公司和汽车客运公司网站得知，直达B市的交通工具只有火车和汽车两种，出发地有B1，B2，…，Bk市（没有A市），从A市出发到B1，B2，…，Bk市的交通工具有飞机、火车和汽车三种，这样从A市经B1，B2，…，Bk市到B市的交通情况如右图所示。二、设计从A市到B市耗时最少旅行路线的算法从A市到B市耗时最少的旅行路线问题，根据获取的从A市到B市的中转城市B1，B2，…，Bk的班次，以及各城市各交通班次的发车时间和行驶时间等信息，采用以下的思想找出耗时最少的联运班次问题，即算法如下：（1）分别找出能够中转的从A市经B1，B2，…，Bk市到达B市的联运班次，并计算所用的时间。（2）分别找到能够中转的从A市经B1，B2，…，Bk市到达B市的联运班次中耗时最少的联运班次，共k条线路。（3）取k条线路中耗时最少的联运班次为最佳旅行路线。三、编写求解从A市到B市耗时最少的旅行路线问题的程序Python语言编写从A市到B市耗时最少的旅行路线问题的算法的程序。其中，找出能够从A市经Bi（i=1，2，…，k）市到达B市的中转联运班次，并计算所用的时间以及找到耗时最少的联运路线的关键程序段如下。调试运行程序在从A市到B市耗时最少的旅行路线问题中，我们分析并设计了算法和编写了程序之后，可以快速地找出从A市到B市耗时最少的旅行路线问题的结果，如下图所示。算法及其描述1、算法算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。2、算法的特征算法作为能确实解决某个问题的策略，具有五个方面的重要特征。有穷性。一个算法在了有穷的运算之后就必须结束。例如，在上面的算法中，x的值从1开始穷举，重复执行语句，直到x8时终止执行。确定性。算法执行的每一个步骤必须有确切的定义，不能出现模棱两可的情况。例如，上面算法步骤5。数据输入。一个算法必须有零个或多个数据输入，这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）。数据输出。一个算法有一个或多个数据输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。例如，在上面的算法中，有两个输出，即步骤5的个数t和具体解（x、y、z的值）。可行性。算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。3、算法的描述3.3计算机程序与程序设计语言在完成问题分析和算法设计两个环节之后，接下来就要开始编写计算机程序对数据进行统计分析，进而形成解决问题的方案。计算机程序设计语言计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级语言的发展历程。1、机器语言目前，计算机采用的物理器件主要是电子元件，但由于电子元件的物理特性，计算机只能识别“0”和“1”组成的二进制数。因此，二进制是计算机语言的基础。因此，早期的程序设计语言是由“0”和“1”所表示的二进制代码指令组表示的。这样的语言是计算机能直接接收和执行的，通常被称为“机器语言”。机器语言是第一代计算机语言。3、高级语言**由于从A市到B1，B2，…，Bk市有不同的交通工具，每一种交通工具又有不同的班次，因此从A市出发到中转城市B1，B2，…，Bk市就有M1、M2，…