第2章 归纳技术.ppt

1、第2章 归纳技术,内容提要,一、引言二、常规排序及基数排序(Radix Sort)三、求整数次幂四、多项式求值五、产生排列,知识要点,归纳与递归算法之间的关系 数学归纳法的基本模式（用于证明问题） 递归算法的基本模式（用于求解问题） 递归算法的特点 应用举例 设计求解典型问题的递归算法 设计产生排列、组合的递归算法,学习要求,理解归纳与递归之间的关系 熟悉算法复杂度分析的基本方法,2.1引言,一、数学归纳法的基本模式(用于证明问题) 1、n=1, f(1)成立； 2、假设kn结论成立，即f(k)成立。于是，利用f(1)、f(n-1)得f(n)也成立； 3、综上所述，对于所有的n1，都有f(n)

2、成 立。 注：保证其正确性的原理称为归纳原理。,2.1引言,二、递归算法的基本模式(用于求解问题) 1.n=1, f(1) (直接求解)； 2.若f(k)（kn）可求，则利用f(1)、f(n-1)得f(n)。 注： 一般来说，求f(k)（kn）比求f(n)容易。关键是 要有办法由f(1)、f(n-1)得到f(n)。由归纳原理保证 其正确性。,2.1引言,三、递归算法的框架 f(n) n=1, f(1) (直接求解)； n1, 利用f(1)、f(n-1)求得f(n)； ,2.1引言,递归算法的优点 读写简明； 算法的正确性易于用数学归纳法来证； 算法的复杂性往往可利用递归关系来分析 递归算法的缺

3、点 算法的执行流程不易理解； 递归调用往往需要额外的时空开销。,2.1引言,2.算法 Algorithm SELECTIONSORTREC Input:An array A1.n of n elements. Output: A1.n sorted in nondecreasing order. Procedure sort(i) Sort A1.i 1.if in then 2. ki 3. for ji+1 to n 4. if AjAk then kj 5. end for 6. if k != i then 互换 Ai和Ak7. sort(i+1) 8.end if,2.1引言,3.复

4、杂度分析 算法计算时间C(n)满足的递归方程为： C(n)=C(n-1)+(n-1),n=2;C(1)=n=1. 其解为：C(n)=,2.1引言,例2插入算法思想 A1i排序 若 i1,A1i-1排序 ; 将Ai插入到A1i-1中的适当位置处 ； ,2. 算法 Algorithm INSERTIONSORTREC Input:An array A1.n of n elements. Output: A1.n sorted in nondecreasing order. 1.sort(1) Procedure sort(i) Sort A1.i 1.if i1 then 2. xAi 3. so

5、rt(i-1) 4. ji-1 5. while j0 and Ajx 6. Aj+1Aj 7. jj-1 8. end while 9. Aj+1x 10.end if 3.复杂度分析 算法计算时间C(n)满足的递归方程为： C(n)=C(n-1)+(n-1),n=2;C(1)=n=1.解为：C(n)=,2.1引言,2.2 基数排序（Radix Sort）,一、问题 要求对n个数的序列L=a1, a2 , ,an进行排序，其中每个数恰好由k位数字组成，每位数字均取自0,1,9。 二、算法思想 根据对k使用归纳法来设计递归算法。,2.2 基数排序（Radix Sort）,三、实例 下面给出了一

6、个基数排序的示例。左边第一列表示输入数据，随后的各列分别表示按照第一位、第二位、第三位、第四位数字的排序结果。7467 6792 9134 9134 12391247 9134 1239 9187 12473275 3275 1247 1239 32756792 4675 7467 1247 46759187 7467 3275 3275 67929187 7467 3275 3275 67929134 1247 4675 7467 7467 4675 9187 9187 4675 9134 1239 1239 6792 6792 9187,2.2 基数排序（Radix Sort）,四、算法

7、Algorithm RADIXSORTInput: 一张有n个数的表L=a1, a2 , ,an 和k位数字 Output: 按非降序排列的表L 1.for j1 to k2. Prepare 10 empty lists L0,L1,.L93. While L is not empty 4. anext element in L.Delete a from L.5. i jth digit in a.Append a to list Li.6. end while7. LL08. for i1 to 99. LL,Li append list Li to L 10. end for 11.

8、end for12. return L,public class RadixSort public static void sort(int number, int d) int k = 0; int n = 1; int temp = new intnumber.lengthnumber.length; int order = new intnumber.length; while(n = d) for(int i = 0; i number.length; i+) int lsd = (numberi / n) % 10); templsdorderlsd = numberi; order

9、lsd+; ,for(int i = 0; i number.length; i+) if(orderi != 0) for(int j = 0; j orderi; j+) numberk = tempij; k+; orderi = 0; n *= 10; k = 0; ,public static void main(String args) int data = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100; RadixSort.sort(data, 100); for(int i = 0; i data.length; i+) Sys

10、tem.out.print(datai + ); ,2.2 基数排序（Radix Sort）,2.3. 求整数次幂,一、问题,二、算法思想,2.3. 求整数次幂,2.3. 求整数次幂,三、算法,2.3. 求整数次幂,2.4.多项式求值,一、问题 求下列实系数多项式的值： 二、算法思想 (Horners rule）,2.4.多项式求值,三、算法,四、算法复杂度 算法时间复杂度为：(n),2.5. 产生排列(Generating Permutations),一、问题 要求产生1,2,n的所有排列。 二、算法思想 12,3,n 的排列 ， 21,3,n 的排列 ， ， n 1,2,n-1的排列 。,2.5. 产生排列(Generating Permutations),2.算法 Algorithm PERMUTATIONS1Input:A positive integer n.Output: All permutations of the numbers 1,2,.,n1. for j1 to n2. Pjj3. end for4. perm1(1),Procedure perm1(m)1. if m=n then output P1.n2. else3. for jm to n4. interchange Pj and Pm5. perm(m+1)6. inte