04第四讲归纳与递归.ppt

ACM程序设计第四讲 归纳与递归 归纳法 1 引言 如果我们知道如何求解规模为n-1的问题，那么我们的任务就化为如何把解法扩展到规模为n的问题 2 选择排序 对数组a[1…n]按从小到大顺序排序 用归纳法：假设我们已经知道如何对n-1个数排序，则： 要对a[1…n]排序 （1）求a[1…n]的最小值a[j]; (2) a[1] a[j]; (3) 对a[2…n]排序 算法1 selectionSort (int a[ ],int n) {sort(a,1,n);//对a[1...n]排序} sort(int a[ ],int i,int n) {（1）j=min(a,i,n); //求a[i…n]中最小值的下标j; (2) a[i] a[j]; (3) if(i+1n)sort( a, i+1, n); } 以上函数中，数组a的首地址，和数组元素个数n，从何而来？ 方法一： 用参数传递，如算法5.1 Sort(int a[],int i,int n) 方法二： 把数组a和n定义为全局变量，则在函数Sort(int i)中可以使用。 方法三：定义类，把a和n作为类的成员变量，函数Sort(int i)做为类的成员函数。 3 插入排序 问题：如何在一个已有序的序列a[1...n]中插入一个新元素x，使其仍然有序？ 简单！ 首先检查是否有足够空间，然后，用一个for循环实现新元素的插入 ，....... 用归纳法思想：假设我们已经知道如何对n-1个元素排序，则 要对a[1…n]排序 （1）对a[1...n-1]排序； （2）将a[n]插入a[1...n-1]的适当位置上，使其仍然有序。 要对a[1…i]排序 （1）对a[1...i-1]排序； （2）将a[i]插入a[1...i-1]的适当位置上，使其仍然有序。 算法2 sort(int a[], int i) { //本函数对a[1...i]排序 if(i1) {sort(a, i-1); //对a[1...i-1]排序 insert(a, i-1, a[i]); );//将a[i]插入已排好序的a[1...i-1]中 } } 4 整数幂 设计一个求x的n次幂的算法 方法一：对x用迭代自乘n次 for(i=1,fact=1;i=n;i++) fact=fact*x; 其时间复杂度为Θ(n) 能否设计一个更高效的算法？ 用归纳法分析： 假设已经知道如何求xn/2 令 如果n 是偶数，那么xn=(xm)2; 否则 xn=(xm)2x 算法3 Exp(float x, int n) //求 xn {Power(x,n);} Power(float x,int m) { （1） 如果m==0 则返回y=1; 否则 （2）y=Power(x,m/2) (3) y=y*y; (4) 如果m为奇数，则y=xy; （5）返回y;} 算法3a power(float x,int m) {if(m==0) return 1; else {y=power(x,m/2) y=y*y; if(m%2!=0)y=xy; return y; }} 方法二：重复平方法 (1)令n的二进制数是dkdk-1...d0。 (2)y赋初值1， (3)从左到右扫描二进制数字: 如果当前的二进制数字为0，则y=y*y; 否则，y=y*y*x 13=(1 1 0 1) 2 d3= 1, d2=