C语言-递推递归

2020/2/21第二讲基础算法计算机科学与技术陈叶芳2020/2/22目录•递推•递归•排序与检索2020/2/23递推•指一个序列u1,u2,u3,…,un-1,un，后面的每一项都能按公式由前面的一项或连续的几项推算出来，或者前面的每一项都能按公式由后面的一项或连续的几项推算出来。前者叫“顺推”，后者叫“逆推”。•递推关系可用它前面1项表示的叫一阶递推数列，可用它前面2项表示的叫二阶递推数列。2020/2/24•有5人坐在一起，当问第5个人多少岁,他说比第4个人大2岁，问第4个人多少岁,他说比第3个人大2岁，依此下去，问第一个人多少岁，他说他10岁，最后求第5个人多少岁？•如果所坐的不是5人而是n人，写出第n个人的年龄表达式。递推xx+210…….2020/2/25显然可以得到如下公式:化简后的公式:F(n)=10+(n-1)*22020/2/26斐波那契级数-递推的经典问题•一对新生小兔，一个月后长成中兔，从第三个月开始长成大兔并每个月生一对小兔。按此规律，一年后共有多少对兔子。第n个月大兔对数中兔对数小兔对数总对数100112010131012411135212563238753513…2020/2/27Fibnacci数列即：1、1、2、3、5、8、13、21、34…32111f21nnffnnnn关键：确定问题的递归特性关键：分析出递归公式关键：分析出初始条件2020/2/28例-巧妙推算走楼梯•楼梯有n级台阶，如果一步走1级或2级，试问：共有多少种不同的走法？123n走上第1级台阶，只有“一步1级”1种走法，u1=1；走上第2级台阶，从平地起步，有“一步1级”走2步和“一步2级”走1步这两种走法，u2=2；走上第3级台阶，或者从台阶2“一步1级”走1步上来，或者从台阶1“一步2级”走1步上来，u3=u2+u1=2+1=3；走上第n级台阶，只能从第n-1级“一步1级”走1步上来，或者从第n-2级台阶“一步2级”走1步上来，un=un-1+un-2(n2)；2020/2/29例-巧妙推算走楼梯123n初始条件：u1=1；u2=2;1、2、3、5、8、13、21、34、55斐波那契序列2020/2/210总结：递推求解的基本方法：•首先，确认：能否容易的得到简单情况的解？•然后，假设：规模为N-1的情况已经得到解决。•最后，重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。2020/2/211在2×n的长方形方格中,用n个1×2的骨牌铺满方格,例如n=3时,为2×3方格，骨牌的铺放方案有三种(如图),输入n,输出铺放方案的总数思考题（NBUOJ1196）：2020/2/212骨牌铺放1、如果用一个骨牌直接覆盖最左边一列，则剩下的2(n-1)个方格有f(n-1)种铺法；2、如果用两个骨牌横向覆盖，则剩下的2(n-2)个方格有f(n-2)种铺法；2(n-1)2(n-2)3、第1列没有其他铺法，因此，f(n)=f(n-1)+f(n-2)；2020/2/213某人给不同地址不同姓名的n位朋友写信，信笺、信封都分别写好了。请问：所有信笺、信封全都装错的情况有多少种？伯努利装错信封问题信封：ABCDEF…信笺：abcdef…伯努利问题：求n个元素的排列，要求在排列中没有一个元素处于它应当占有的位置。2020/2/214伯努利装错信封问题信封：ABCDEF…信笺：abcdef…错误1：信封：ABCDEF…信笺：ba(后n-2封也都装错)错误2：信封：ABCDEF…信笺：b非a(后n-2封也都装错)装错情况种数Sn-2装错情况种数Sn-1Sn=（n-1)(Sn-1+Sn-2)2020/2/215分析思路：S1=0,只1封信，不会装错S4=3(S3+S2)=9S3=2(S2+S1)=2,3封信，a-B,b-C,c-A或a-C,c-B,b-AS2=1,2封信，互相装错2020/2/216得到如下递推公式：基本形式：d[1]=0;d[2]=1递归式：d[n]=(n-1)*(d[n-1]+d[n-2])这就是著名的错排公式2020/2/217递归1)!1(01!nnnnnintfact(intn)/*递归函数*/{intr;if(n==0)r=1;elser=n*fact(n-1);/*递归*/returnr;}printf(%d!=%d\n,5,fact(5));2020/2/218递归fact(5)=5*fact(4)院长fact(4)=4*fact(3)主任fact(3)=3*fact(2)教师fact(2)=2*fact(1)班长fact(1)=1*fact(0)班委fact(0)=1同学1)!1(01!nnnnn设计递归程序的重点是给下级安排工作2020/2/219递归intSearchBin(int*r,intk,intlow,inthigh)//递归{if(rowhigh)return0;//failedmid=(low+high)/2;if(k==r[mid])returnmid;//successelseif(kr[mid])returnSearchBin(*r,k,mid+1,high);elsereturnSearchBin(*r,k,low,mid-1);}}2020/2/220递归3)1()2()(21)2(11)1()(nnfnfnfnfnfnfintfunc(intn)/*求斐波那契数列的第n个数*/{intresult;if(n==1)result=1;elseif(n==2)result=1;elseresult=func(n-1)+func(n-2);/*递归*/returnresult;}2020/2/221递归•Hanoi（汉诺塔）问题：三根柱子A、B、C，其中A柱上有64个大小不等的圆盘，并且大的在下，小的在上。要求把这64个圆盘从A柱移动到C柱上，每次只能移动一个圆盘，移动时可以借助B来进行，但在任何时候，任何柱上的圆盘都必须保持大盘在下，小盘在上。求移动的过程。ABC2020/2/222递归•(1)假如只有一个盘子的话，可以直接将盘子从A柱移动到C柱，即AC。ABC2020/2/223递归•(2)假如有两个盘子，则：•AB•AC•BCABC2020/2/224递归•(3)假如有三个盘子，则情况开始复杂，移动顺序为：•AC•AB•CB•AC•BA•BC•ACABC2020/2/225递归•当有n个盘子需要移动时，通常的方法如下：（1）把A柱上n-1个盘子借助C柱移动到B柱上。只有这样，C柱才能为空，则A柱上的第n个盘子（最大的那个）才能直接移动到C柱上。（2）将A柱上的剩下的第n个盘子移动到C柱上。这个盘子已最后到位，不需要再移动了。（3）再将B柱上的n-1个盘子借助A柱移动到C柱。ABC2020/2/226递归voidhanoi(intn,charA,charB,charC)/*借助B，把n个盘子从A移动到C*/{if(n==1)move(A,C);else{hanoi(n-1,A,C,B);/*借助C，把n-1个盘子从A移动到B*/move(A,C);/*把第n个盘子从A移动到C*/hanoi(n-1,B,A,C);/*借助A，再把n-1个盘子从B移动到C*/}}ABCscanf(%d,&n);/*盘子个数*/hanoi(n,'A','B','C');2020/2/227排序与检索•查找表:用于查找的数据集合,由同一类型数据元素构成.2020/2/228排序与查找ABC…ZbananaBasketball…………列表：同一类型的数据元素（或记录）构成的集合。可利用任何数据结构实现。关键字：数据元素的某个数据项的值。查找：根据给定的关键字，在特定列表中确定与与之相同的数据元素，并返回该数据元素在列表中的位置。2020/2/229顺序查找法intseqList[n+1];//n号单元用作监视哨intOrder_Search(intarray[],intn,intkey){inti;array[n]=key;//设置监视哨，不用判断越界for(i=0;array[i]!=key;i++);return(in?i:-1);//找不到为-1,找到则为0~n-1的数值}1.每一步骤中省去了对是否越界的判断，如in2.当n1000时,可以节省一半以上的查找时间.特点：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败为止。特点：从前到后，或从后到前。for(i=0;in;i++)if(array[i]==key)returni;return-1;2020/2/230顺序查找法intseqList[n+1];//0号单元用作监视哨intOrder_Search(int*array,intn,intkey){r[0]=key;//设置监视哨，不用判断越界for(i=n;array[i]!=key;i--);returni;//找不到为0,找到则为1~n的数值}2020/2/231折半查找法(二分查找）•A在心里想一个不超过1000的正整数,由B来猜,请问可以在多少次以内猜到该数?特点：利用元素间的次序关系（要求数据集合有序）。采用了分治策略。2020/2/232折半查找法31015192528405583lowhighmid要求:查找关键字为55的数据元素(1)mid=(low+high)/2(2)55r[mid],则查找[mid+1,high]区间,既low=mid+1,mid=(low+high)/231015192528405583lowhighmid二分查找(BinarySearch)要求：要查找的列表是按关键字大小有序排列的。2020/2/233折半查找法31015192528405583lowhighmid要求:查找关键字为18的数据元素(1)mid=(low+high)/2(2)18r[mid],则查找[low,mid-1]区间,既high=mid-1,mid=(low+high)/231015192528405583lowhighmid若出现lowhigh情况,则查找失败2020/2/234折半查找法intSearchBin(int*r,intk){low=1;high=n;while(low=high){mid=(low+high)/2;if(k==r[mid])returnmid;//successelseif(kr[mid])low=mid+1;elsehigh=mid-1;}return0;//failed}2020/2/235折半查找法intSearchBin(int*r,intk,intlow,inthigh)//递归{if(rowhigh)return0;//failedmid=(low+high)/2;if(k==r[mid])returnmid;//successelseif(kr[mid])returnSearchBin(*r,k,mid+1,high);elsereturnSearchBin(*r,k,low,mid-1);}}2020/2/236插入排序在一个已经排好序的记录子集的基础上,每一步将下一个待排序的记录有序地插入到排好序的记录子集中.（扑克牌的抓牌操作）◆直接插入排序◆折半插入排序◆希尔排序2020/2/237直接插入排序初始序列：[51]33629687172851区别相同关键字，[]内为有序序列i=2(33)[3351]629687172851i=3(62)[335162]9687172851i=4(96)[33516296]87172851i=5(87)[3351628796]172851i=6(17)[173351628796]2851i=7(28)[17283351628796]51i=8(51)[172833515162879