计算机导论PPT第十章_算法课件.ppt

《计算机导论PPT第十章_算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章算法1概念非正式定义算法:逐步解决问题或完成任务的方法.i图1.1计算机中算法的非正式定义示例设计一个算法能够从一组正整数(如5,1000,10,000,1,000,000)中找到最大整数，要求具有通用性并与整数的个数无关。解决这个问题的一种直接的方法就是先用一组少量的整数，然后将这种解决方法扩展到任意多的整数。图1.2在五个整数中寻找最大值将算法命名为FindLargest.不同于其它算法的名字接受5个整数作为输入，然后输出其中的最大值图1.2并没有给出每一步究竟做了工作。图1.3更加详细的对这个过程进行了描述图1.3定义寻找最大值算法的动作细化为了使算法能够被应用，还需要进行细化，以

2、解决如下两个问题步骤2到步骤5的功能相同，但描述语言却不同通过将步骤2到步骤5的描述改为“IfthecurrentintegerisgreaterthanLargest,setLargesttothecurrentinteger.”第一步的动作与其它步骤中的不一样最大值没有被初始化。如果将其赋值为-，那么第一步就可以和其他步骤的描述一样图1.4细化的FindLargest泛化假设要从n个自然数中找到最大值，n的值可能是100、或1000.可以按照图1.4重复每一步让计算机重复这个步骤n次图1.5泛化的FindLargest2三种结构结构化程序设计或算法中存在顺序、选择和循环三种结构，程序必定

3、是由这三种结构组成。已经证实其他结构都是不必要的。图2.1三种结构3算法的表示到目前为止，我们已经使用图来表示算法的基本概念。算法的表示存在多种方式，这里我们将介绍UML和pseudocode这两种工具。图3.1三种结构的UML表示UMLUML是算法的图形表示法，采用“大图”的方式隐藏算法的所有细节，显示算法从开始到结束的整个流程。附录中有UML的具体说明。这里我们只介绍三种结构的UML表示。Pseudocode伪代码是一种类似英文的算法表示法。目前还没有一个公认的标准。有些人使用得过于详细，有些人则使用的过粗；有些采用一种很像英文的代码，有些人则使用类似Pascal编程语言的语法。图3.2三

4、种结构的Pseudocode表示例3.1使用伪代码写一个求两个整数之和的算法算法3.1计算两个整数之和例3.2用伪代码写出判断一个数值成绩是否及格的算法算法3.2判断成绩是否及格例3.3将整数型成绩转化为字母等级成绩的算法算法3.3赋予字母等级例3.4从一组数量未知的整数中找出最大值的算法算法3.4从一组整数中找出最大值例3.5从1000个整数中找出最大值的算法算法3.5从1000个整数中找出最大值4算法的更正式的定义前面讨论了算法的概念并给出了它的表示，下面给出算法更为正式的定义Algorithm:Anorderedsetofunambiguousstepsthatproducesaresu

5、ltandterminatesinafinitetime.i5基本算法有些算法在计算机的应用中非常普遍，我们称之为基本算法。这里将讨论一些常用的算法。讨论只是通用性的，具体的实现则取决于采用何种语言。求和可以很容易的实现两个或三个数的相加，但怎样才能实现一系列数相加呢？答案很简单，在循环中使用加法操作（图5.1）可分为三个逻辑部分:1.将和(sum)初始化2.循环，在每次迭代中将一个新数加到和(sum)上3.退出循环，返回结果图5.1求和算法乘积如何求出一系列数的乘积？方法很简单，在循环中使用乘法操作（图5.2）可分为三个逻辑部分:1.初始化乘积product.2.循环，在每次迭代中将一个新数

6、与乘积相乘.3.退出循环，返回结果.图5.2乘积算法最大最小前面我们讨论了在一组数中寻找最大值的算法。思想是通过判断结构找到两个数中的较大值。如果把这个结构放在循环中，就可以得到一组数中的最大值。求解一组数中的最小值和上面的方法相似，只有两个小小的不同。用判断结构找出两个数中的较小值。在初始化时使用一个很大的而不是非常小的数。计算机科学中一个最普遍的应用就是排序，即根据数据的值对它们进行排列。最基本的排序算法主要有选择排序、冒泡排序和插入排序，其他更高效的算法都是建立在这几个算法的基础之上的。本节我们主要介绍选择排序和冒泡排序算法。排序图5.3选择排序选择排序在选择排序中，数字列表也被分为已排

7、序的和未排序的两个表。找到未排序列表中的最小元素并将其移动到已排序的子列表中。这样已排序的元素个数增加1个，而未排序的元素的个数减少1个。每次元素从未排序列表移动到已排序列表，便完成一次扫描。因此，含有n个元素的列表需要n-1次扫描来完成数据排序。图5.4选择排序示例图5.5选择排序算法冒泡排序在冒泡排序方法中，数字列表被分为两个表：已排序的和未排序的。在未排序的字列表中，最小的元素通过冒泡的方法