第3讲归纳法解答.ppt

归纳法 基于递归的技术 在最简单的形式中，递归是这样一种过程：先把问题分成一个或多个子问题，这些子问题在结构上和原来的问题一模一样，然后解这些子问题，把这些子问题的解组合起来，从而得到原问题的解。 归纳法，或称为尾递归； 无重叠子问题； 有重叠子问题。 归纳法 考虑一个带有参数n的问题，n通常表示问题实例中事务的数目 在进行问题求解时，从求解一个带有小一点参数的相同问题开始，然后再把解推广到包含所有n个对象 该方法基于数学归纳法证明技术，所设计的算法的正确性已自然地嵌入到算法的描述中了。 Algorithm 5.1 SELECTIONSORTREC Input: An array A[1…n] of n elements. Output: A[1…n] sorted in nondecreasing order. 1. sort(1) Procedure sort(i) {Sort A[i…n]} 1. if in then 2. k?i 3. for j?i+1 to n 4. if A[j]A[k] then k?j 5. end for 6. if k ?i then interchange A[i] and A[k] 7. sort(i+1) 8. end if 选择排序算法分析 对于n个输入元素，令C(n)表示元素的比较次数，则C(1)=0; 过程sort(1)被调用时，数组中有n个元素，元素比较的总次数包括： n-1次元素比较次数 对A[2..n]中的元素进行排序的比较次数，即C(n-1) 递推式的解为： ?(n2) Algorithm 5.2 INSERTIONSORTREC Input: An array A[1…n] of n elements. Output: A[1…n] sorted in nondecreasing order. 1. sort(n) Procedure sort(i) {sort A[1…i]} 1. if i1 then 2. x?A[i] 3. sort(i-1) 4. j?i-1 5. while j0 and A[j]x 6. A[j+1]?A[j] 7. j ? j-1 8. end while 9. A[j+1]?x 10. end if 插入排序算法分析 令C(n)表示元素的比较次数，显然C(1)=0 Sort第一次被调用时，有n个元素。假设我们知道如何对前n-1个元素排序，则A[1..n-1]排序后，只需将A[n]元素插入到其合适的位置 最好情况下插入合适位置只需比较1次，而最坏情况下要比较n-1次 最好情况： 最坏情况： 基数排序 多关键字排序 基于高位优先的方法 基于低位优先的方法 —— 基数排序 对k个关键字位施行归纳法导出基数排序算法 假设对低位的k-1位关键字(dk-1,dk-2,…d1)已经按字典顺序排序，则在按第k位关键字排序后，就完成了全部的排序 基数排序例 给定输入数据A={7467, 1247, 3275, 6792, 9187, 9134, 4675, 1239} 7467 1247 3275 6792 9187 9134 4675 1239 7467 1247 3275 6792 9187 9134 4675 1239 6792 9134 3275 4675 7467 1247 9187 1239 6792 9134 3275 4675 7467 1247 9187 1239 9134 1239 1247 7467 3275 4675 9187 6792 9134 1239 1247 7467 3275 4675 9187 6792 9134 9187 1239 1247 3275 7467 4675 6792 1239 1247 3275 4675 6792 7467 9134 9187 Algorithm 5.3 RADIXSORT Input: A linked list of numbers L={a1…an} and k, the number of digits. Output: L sorted in nondecreasing order 1. for j?1 to k 2. Prepare 1