lecture042归纳与递归.ppt

ACM程序设计 第四讲 归纳与递归,归纳法,1 引言 如果我们知道如何求解规模为n-1的问题，那么我们的任务就化为如何把解法扩展到规模为n的问题,2 选择排序,对数组a1n按从小到大顺序排序 用归纳法：假设我们已经知道如何对n-1个数排序，则： 要对a1n排序 （1）求a1n的最小值aj; (2) a1 aj; (3) 对a2n排序,算法1 selectionSort (int a ,int n) sort(a,1,n);/对a1.n排序 sort(int a ,int i,int n) （1）j=min(a,i,n); /求ain中最小值的下标j; (2) ai aj; (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)做为类的成员函数。,问题：如何在一个已有序的序列a1.n中插入一个新元素x，使其仍然有序？ 简单！ 首先检查是否有足够空间，然后，用一个for循环实现新元素的插入 ，.,3 插入排序,2,4,8,10,X=6,6,用归纳法思想：假设我们已经知道如何对n-1个元素排序，则 要对a1n排序 （1）对a1.n-1排序； （2）将an插入a1.n-1的适当位置上，使其仍然有序。,要对a1i排序 （1）对a1.i-1排序； （2）将ai插入a1.i-1的适当位置上，使其仍然有序。,算法2 sort(int a, int i) /本函数对a1.i排序 if(i1) sort(a, i-1); /对a1.i-1排序 insert(a, i-1, ai); );/将ai插入已排好序的a1.i-1中 ,如果不要”if(i1)“这个递归进行的条件 这个程序运行时会出现什么症状？,4 整数幂,设计一个求x的n次幂的算法 方法一：对x用迭代自乘n次 for(i=1,fact=1;i=n;i+) fact=fact*x; 其时间复杂度为(n) 能否设计一个更高效的算法？,Hoj1060: 求N的N次方的最高位上的数字，N10亿,10的10亿次方多少位？ 10亿的10亿次方呢？100亿亿位！,双精度能表示到三百多位整数，有效数字只达到19位,用归纳法分析： 假设已经知道如何求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,请用213验证本算法！,13=(1 1 0 1) 2 d3= 1, d2= 1 , d1= 0 , d0= 1 13= 1 23+ 1 22+ 0 21 + 1 X13=x23 x22 x1 （需8次乘法） =(x)2 x)2 ) 2x （需5次乘法）,13=2*6+ 1 =2*(2*3+ 0)+ 1 = 2*(2*(2*1+ 1)+ 0)+ 1 =2*(2*(2*(2*0+ 1)+ 1)+ 0)+ 1,13=(1 1 0 1) 2 d3= 1, d2= 1 , d1= 0 , d0= 1 , 13= 1 23+ 1 22+ 0 21 + 1 20 X13=(x2 x)2 ) 2x （需5次乘法）,(2)y赋初值1， (3)从左到右扫描二进制数字: 如果当前的二进制数字为0，则y=y*y; 否则，y=y*y*x,d3= 1：y=1*1*x=x; d2= 1 ：y=x*x*x=x3; d1= 0 ：y=x3*x3=x6; d0= 1 ：y=x6*x6 *x =x13;,算法4 Exp(float x,int n) y=1; 将n 用二进制数dkdk-1.d0表示。 for( j=k ; j= 0;j-) y=y*y; if(dj=1) y=y*x; return y; ,6 生成排列,先讲一个故事，三个小孩玩“毛毛虫游戏”，为了公平，她们要不停的换次序，要尝试完所有的排列，有多少种排列，四个人呢？五个人呢？,方法一:指定排头法,问题：对于数1,2,.,n生成所有的排列 分析：可用数组存储这n个元素。 初始状态下,ai=i, i=1n 若n=3,则有 （1）1为排头的所有排列：1 2 3、1 3 2 （2）2为排头：2 1 3、2 3 1 （3）3为排头：2 1 3、2 3 1,对n个数的情况，归纳分析如下： 假定可以生成n-1个数的所有排列，那么就可以扩展生成n个数的排列。方法如下： （1）生成数2,3,.,n的所有排列，并在每个排列前加上数1； （2）生成数1,3,.,n的所有排列，并在每个排列前加上数2； （i）生成数2,.i-1, 1,i+1,n的所有排列，并在每个排列前加上数i； . （n）生成数2,.,n-1, 1的所有排列，并在每个排列前加上数n；,数组P的初始状态 :1,2,n （1）生成数2,3,.,n的所有排列，并在每个排列前加上数1； perm(2,n) （2）生成数1,3,.,n的所有排列，并在每个排列前加上数2； s1：将p1与p2交换；P: 2, 1,3,.,n s2： perm(2,n); s3： 将p1与p2再交换回来；P: 1, 2,3,.,n （i）生成数2,.i-1, 1,i+1,n的所有排列，并在每个排列前加上数i； s1： 将p1与pi交换；P: i, 2,.i-1, 1,i+1,n s2： perm(2,n); s3： 将p1与pi再交换回来；P: 1, 2,3,.,n,算法5 Permutation (int n) for(i=1;i=n;i+) Pi=i; Perm(1,n); /生成1到n的所有排列 ,Perm(int m,int n) /生成Pm到Pn的全排列 如果m=n，输出P1.n; /递归到叶子结点，得到一个排列，返回上一层 否则 for j=m to n 互换Pj和Pm；/让Pj当排头 /生成Pm+1.n的所有排列 Perml(m+1,n); 互换Pj和Pm； /让Pj回到原位 ,生成1,2,3,4的所有排列,P:,Perm(1,4) : for j=1 to 4 j=1: P1与P1互换 1 2 3 4 Perm(2,4) : for j=2 to 4 j=2: P2与P2互换 1 2 3 4 Perm(3,4)： for j=3 to 4 j=3： P3与P3互换 1 2 3 4 Perml(4,4)：输出1 2 3 4 P3与P3互换 j=4： P4与P3互换： 1 2 4 3 Perml(4,4)：输出1 2 4 3 P4与P3互换 ： 1 2 3 4 j=3: P3与P2互换 1 3 2 4 Perm(3,4)： for j=3 to 4 j=3： P3与P3互换 1 3 2 4 Perml(4,4)：输出1 3 2 4； P3回位； P3与P3互换： j=4： P4与P3互换 1 3 4 2 Perml(4,4)：输出1 3 4 2 ； P4回位； P4与P3互换： j=4:输出：1 4 3 2 、 1 4 2 3,请写出其前6个排列,方法二:填补空位法,问题：对于数1,2,.,n生成所有的排列 分析：可用数组a1n代表n个空位。 初始状态下,ai=0,i=1n 若n=3,则有 （1）3站在第一个空位的所有排列： 3 1 2、3 2 1 （2） 3站在第二个空位的所有排列： 1 3 2 、2 3 1 （3） 3站在第三个空位的所有排列： 1 2 3、2 1 3,算法6 Permutation 2(int n) for(i=1;i=n;i+) Pi=0; Perm2(n); /生成1到n的所有排列 ,Perm2(int m) /n、n-1m+1都已找好位置，用1m填补数组P的m个空位 如果m=0 ,则说明n、n-11都已找好位置，输出一个排列 否则 对当前每一个空位（共m个）： （1）指定m放入其中一个； （2）用1m-1填补数组P的剩余m-1个空位,Perm2(int m) /n、n-1m+1都已找好位置，用1m填补数组P的m个空位 if(m=0) 输出一个排列p1n / n、n-11都有位置了 else /否则，为m找位置 for(j=1;i=n;j+) /扫描所有位置 if(pj=0) /对当前每一个空位 pj=m; /指定m放入其中一个； perm2(m-1) /用1m-1填补数组P的剩余m-1个空位 pj=0;/m离开j位置，尝试别的位置，j位置置空 ,课下练习,组合：从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合，例如OR = 1,2,3,4, n = 4, r = 3，则组合为： 1,2,3; 1,2,4; 1,3,4; 2,3,4.,6 寻找多数元素,问题：有整型数组a1.n,如果整数x在数组a中出现的次数多于半数，则x称为多数元素。 方法一：计算每一个元素出现的次数 O(n2) 方法二：排序，然后求在中间位置的元素出现的次数 O(nlogn),归纳法分析此问题 观察结论5.1：在原序列中去除两个不同的元素后，那么在原序列中的多数元素在新序列中还是多数元素。 例1： 1，2，2，3，2，2，3 显然2是多数元素 去除1，2，在2，3，2，2，3中2仍是多数元素 去除1，3，在2，3，2，2，3中2更是多数元素,但是，在新序列中是多数元素的，在原序列中不一定是多数元素。 例2： 1，3，2，3，2，2，3 显然没有多数元素 去除1，3，在2，3，2，2，3中2成了多数 故在观察结论5.1的支持下，能得到多数元素的候选者,寻找多数元素候选者的过程： （1）计数器count置1，另c=A1; (2)从A2开始向后扫描，for j=2 to n 若aj与c相等，则count+; 若aj与c不等，则count 若count=0,则对Aj+1.n寻找多数元素候 选者（递归调用自身）。,寻找候选者算法(1) Candidate(int A,int m ,int n) /寻找Am.n中多数元素候 选者 c=Am; count=1; for(j=m+1; j0, j+) if(Aj=c)count+; else count-; if(jn)return c; else return canditate(A,j+1,n); /对则对Aj+1.n寻找多数元素候 选者。 ,寻找候选者算法(2) Candidate(int A,int m ,int n) /寻找Am.n中多数元素候 选者 c=Am;count=1; for(j=m+1;j=n; j+) if(Aj=c)count+; else count-; if(count=0) return canditate(A,j+1,n); /则对Aj+1.n寻找多数元素候 选者。 return c; ,寻找候选者算法(3) Candidate(int A,int m ,