离散数学-newchap04(精品·公开课件).ppt

离散数学 第4章 算法 第4章 算法 algorithm一词源自公元9世纪的波斯数学家Al-Khowarizmi。 算法就是按步就班解决问题的方法。 要让计算机解决一个问题，问题的解决方法就必须描述成一组步骤精确的序列。 算法引论 一种创造性方法 [美] UDI MANBER著 电子工业出版社,2005 本章内容 算法简介 算法例子 算法分析 递归算法 4.1 引言 算法 一组有限的指令集合, 具有以下性质： ● 输入： 算法接受输入。 ● 输出：算法产生输出。 ● 精确性：步骤被精确描述。 ● 确定性：每步执行的结果是惟一的，且只依赖于输入和前面步骤执行的结果。 ● 有限性 ：算法可以终止，也就是在执行有限多条指令后停止。 ● 正确性：算法生成的输出结果是正确的，也就是算法可以正确地求解问题。 ● 一般性： 算法适应于一组输入。 算法例 1. large = a. 2. If b large, then large = b. 3. If c large , then large = c. 这个算法的思想是对这些数一个一个地检查，将所见的最大数赋值给变量large。在算法停止时，large 就等于这三个数中最大的了 跟踪 a=1, b=5, c=3 a=1, b=5, c=9 1. large = a. 2. If b large, then large = b. 3. If c large , then large = c. 伪代码 虽然普通的语言有时候足以描述一个算法，但是很多数学家和计算机科学家更喜欢伪代码（pseudocode），因为它具有精确性、结构化和普遍性的特点。 伪代码被如此命名是因为它类似于程序语言如C++ 和Java 的真正代码。现在已经有很多版本的伪代码。与真正计算机语言不同，伪代码摆脱了分号、大小写字母、关键字等烦恼，任意版本的伪代码都是可以接受的，只要它的指令是明确的。 算法4.1.1 找出三个数中的最大值 输入：三个数a、b 和c 输出：large（a、b 和c 中的最大值） 1. max3(a, b, c){ 2. large = a 3. if (b large) // 如果b 比large 大，更新large 4. large = b 5. if (c large) // 如果c 比large 大，更新large 6. large = c 7. return large 8. } 算法4.1.2 在数列中查找最大值 这个算法是在数列s1,..., sn 中找出最大的一个。 输入：s, n 输出：large（序列s 中的最大值） max (s, n){ large = s1 for i = 2 to n if (si large) large = si return large } 通过证明 large 是子序列s1,..., si 中的最大值是一个循环不变量，可施归纳于i，从而验证算法4.1.2 是正确的。 循环不变量 在基本步中（i = 1），注意到在循环开始前，s1 被赋值给large；因此，large 当然是子序列s1 中的最大值。 假设large是子序列s1,..., si 中的最大值。 假如i n 成立（因此又一次执行for循环），i 变成i + 1。 首先假设si+1 large，立刻可得si+1 是子序列s1,..., si, si+1 中的最大值。在这种情况下，算法赋值si+1给large，现在large 是子序列s1,..., si, si+1 中的最大值。 下面假设si+1 ≤ large，立刻可得large 是子序列s1,..., si, si+1 中的最大值。在这种情况下，算法不改变large 的值。现在证明了归纳步。 因此，large 是子序列s1,..., si 中的最大值是一个循环不变量。 for 循环在i = n 时结束。因为large 是子序列s1,..., si 中的最大值是一个循环不变量，此时，large 就是序列s1,..., sn 中的最大值。因此，算法4.1.2 是正确的。 问题求解要点 为了构造一个算法，假设问题的一部分已经解决通常是很有帮助的。 例如，在查找序列s1,..., sn 中的最大元素时（算法4.1.2），假设已经找到了子序列s1,..., si中的最大值是有帮助的。接下来，所有必须要做的就是比较下一个元素si+1，如果si+1 比large 大，只需要简单更新large。如果si+1不比large大，不需要修正large，重复这个过程就得到了算法。这些分析同样可以得出结论large的子序列s1, ..., si 中的最大值是一个循环