算法大视界-全套PPT课件.pptx

第一章绪论主要内容：1.1何为算法1.2算法之特性1.3“敲7”游戏1.4计算机求解问题的基本步骤1.5思考：寻找生活中的算法问题1.6总结与思考附录1.1何为算法我们首先来看看如何在手机上下载消消乐游戏？整个下载过程就是在系统提示下一步步完成的。一系列的下载步骤就构成了一个下载算法。再来看看手机解锁问题：首先我们会给手机设置一个密码，在打开手机的时候输入自己设定的密码，这时候手机里的程序会根据输入的数字进行逐一的检测，如果全部的密码都符合要求，则解锁成功。整个匹配的过程也是一个算法。在日常生活中我们经常会碰到类似的各种各样算法！我们可以这样理解：算法是完成一个任务所需要的一系列的步骤。算法定义：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。1.2算法之特性一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2.确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径，不允许有二义性。例如下面这句话：‘张三对李四讲，他的儿子考上了大学。’该句话的确切含义？3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5.有输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。1.3敲“7”游戏1.3.1游戏描述集体游戏，一群人围成一圈，从第一个人开始，从1开始报数，报到7的倍数的人敲桌子，报到数字中含7的人也敲桌子，其他人按数字顺序报数，应该敲桌子却报数的人要出局。要求输出每一轮每个人的报数或者敲桌子的情况。1.3.2计算机中如何表示一个“人”“敲7”游戏需要一群人围在一起来玩，那么在计算机中怎么表示这群人呢？我们知道，人的属性有很多。姓名、性别、身高、体重，...。在这个游戏中需要的人的属性有什么呢？...我们的问题是什么呢？是要输出每个人的报数或者敲桌子的行为，那么这些跟什么相关呢？当然是每个人所坐的位置有关。还有别的相关的属性吗？比如性别、身高体重？答案是没有关系。那么我们表示一个人的数据就只有一个：他坐的位置。一个位置在计算机中用什么来表示呢？答案是整数在“敲7”游戏中，参加游戏的每个人，我们用该人所在位置（整数）来表示。这个表示参与者的位置信息称为数据元素。何为数据元素：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。可由若干个数据项组成。1.3.3计算机如何表示数据元素之间的关系设想，在“敲7”游戏中，表示游戏参与者的这些数据之间的关系是什么？按照座位顺序递增数数，他们之间就是一个先后的顺序关系，中间不允许跳跃或者交叉，一旦在座位上坐好后，他们之间的顺序关系就不会发生改变，除非有人出错出局。若有人出局，则出局的人的前面的人和后面的人就新建立了一个顺序关系。因此，我们需要为所有参加敲7游戏的人按照座位号排一个顺序。最后一个人的后继设定为第一个人，就围成了一个圈。在这类参与者排队的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。线性结构除了线性结构之外，数据的逻辑结构还有以下几种:树形结构图状结构或网状结构集合…ana1a2…ai计算机如何表示这种关系（逻辑关系）呢？在计算机中通过两种不同的存储方式来表示这种关系：顺序存储结构：就是把这些参与者的数据顺序存储在计算机的存储设备上，存储位置的先后就是这些人的顺序，也就是用存储位置来表示这些参与者的顺序关系。顺序存储方式：顺序表链式存储结构：在表示数据元素的同时，再增加一个地址数据，用来存储下一个数据元素在计算机中的存储地址。链式存储方式：链表假设第一个元素的存储地址是31，我们用一个变量H（指针）表示,则该链式存储结构可形象表示为：存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU2531头指针HHQIANZHAOanai+1…a1a2…ai-1ai+2a1a2…ai-1aiai+1…an-1an在“敲7”游戏中，如果有人说错（假设此