递推与递归方法.

Presentation on theme: "递推与递归方法."— Presentation transcript:

1 递推与递归方法

2 用递归的思想思考问题 1.递推算法 2.递归

3 1.递推算法 有一类问题，每相邻两项之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式： Fn=g(Fn-1)
这就在数的序列中，建立起后项和前项之间的关系，然后从初始条件(或最终结果)入手，一步步地按递推关系递推，直至求出最终结果(或初始值)。很多程序就是按这样的方法逐步求解的。如果对一个问题，我们要是能找到后一项与前一项的关系并清楚其起始条件(最终结果)，问题就好解决。

4 递推算法解决问题时，可能会遇到两种情况： 1.问题可以表示成数学上明确的递推公式的形式，例如：
(1).n个自然数求和：sn=1+2+…+n，可写成递推公式： (2).n个数的阶乘：n!=1*2*3*…*n，可写成递推公式：

5 有一些问题，其求解过程无法写出显式的递推公式，但就其本质而言，仍然是递推求解，对于这类问题，有一个跟一般的叫法，称为迭代法。
2.无法直接写递推公式的形式 有一些问题，其求解过程无法写出显式的递推公式，但就其本质而言，仍然是递推求解，对于这类问题，有一个跟一般的叫法，称为迭代法。 这类问题可用下面的一般形式描述： x0=<初值> x1=x0 <op> <项1> x2=x1 <op> <项2> ……… xn=xn-1 <op> <项n>　 … x=<初值> while(…) { 　……… x=x <op> <项n> 　 }　

6 【例】设计一个程序，输入一个n位数（n>=3）,将各数字分开，并按其反序输出。
分析: 问题的关键是如何将一个数字的各位分开？如1234，将其分解成1,2,3,4。令：x0=1234,xi表示xi-1/10的商，ri表示xi-1%10的余数，即　r=x%10 初值： x0=1234 step1: r1=x0%10 = 4 x1=x0/10 = 123 step2: r2=x1%10 = 3 x2=x1/10 = 12 step3: r3=x2%10 = 2 x3=x2/10 = 1 step2: r4=x3%10 = 1 x4=x3/10 = 0 根据上述运算过程，可以总结出下列递推公式： 这是一个双递推公式，当时，递推结束。

7 【例】(非线性方程求根)编一程序利用牛顿法求解方程ex+3x-2=0的根，要求两相邻近似根之差的绝对值不大于0.001。

8 由于用线性函数近似原函数f(x)太粗糙，因此x作为方程的根误差很大。解决的办法是多次用线性函数逼近原函数，即任给初值x0，第一次逼近求得的根用x1表示，第二次用x2表示，…，第i次用xi表示，即可得到下面的迭代序列： 这样非线性方程 求根的叠代计算公式可写成下面的通式：

9 double Newton(double x0)
{ double x1,x2,y1,y2,eps=0.001; x2=x0; //给x2赋初值为x0 do { x1=x2; y1=fun(x1); //y1=f(x1) y2=dfun(x1); //y2=f'(x1) x2=x1-y1/y2; }while(fabs(x2-x1)>eps); return x2; }

10 【例】(求平方根)编程求任意正实数a的平方根。

11 【例】 （贮油点问题）一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500升。显然卡车一次是过不了沙漠的。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿越沙漠，试问司机如何建立这些储油点？每一储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。 No Distance(k.m.) oil(litre) X X X X X X X X X X X X

12

13

14

15 void main() { int k; /*贮油点位置序号*/ float d,d1; /*d:累计终点至当前贮油点的距离,d1:i=n至始点的距离*/ float oil[10],dis[10]; int i; printf("编号 距离(k.m.) 油量(l.)\n"); dis[0]=1000; oil[0]=0; for(k=1; ; k++) dis[k]=dis[k-1]-500.0/(2*k-1); oil[k]=oil[k-1]+500; if(dis[k]<0) break; } dis[k]=0; //端点处理 oil[k]=oil[k-1]+dis[k-1]*(2*(k-1)+1); for(i=k;i>=0;i--) //输出结果 printf("%-2d %5.0f %5.0f\n",k-i,dis[i],oil[i]);

16 运行结果 编号 距离(k.m.) 油量(l.)

17 首先写出递推关系，然后利用穷举的办法求解
例：运动会连续开了n天，一共发了m枚奖牌。第一天发1枚及剩下（m-1）枚的1/7，第二天发2枚及剩下的1/7，以后每天按此规律发奖牌，在最后一天即第n天发了剩下的n枚奖牌。问运动会开了多少天？一共发了多少枚奖牌？ 分析：本题涉及到两个方面的算法策略： 其一是递推 其二是穷举 首先写出递推关系，然后利用穷举的办法求解

18 寻找递推关系 用fi表示每一天发放将牌数，xi表示每剩余奖牌数 初始：f0=0, x0=m
第一天：f1=1+(x0-1)/7; x1=x0-f1 第二天：f2=2+(x1-2)/7; x2=x1-f2 第三天：f3=3+(x2-3)/7; x3=x2-f3 … 第i天： fi=i+(xi-1-i)/7; xi=xi-1-fi 第n天： fn=n+(xn-1-n)/7; xn=0

19 穷举 题目要求两个未知数，一个是奖牌数m，一个运动会天数n。因此对这两个变量都要进行穷举，具体实现时，对此两个数进行循环，即使用双重循环。涉及到退出循环的条件？ (1)、m和n都必须是自然数； (2)、m-1应该是7的倍数，即m=7*k+1 (3)、最后一天发放n枚奖牌，根据递推公式 fn=n+(xn-1-n)/7 得 　 fn=n,xn-1=n 有了这些基本的分析后，现在请自己动手写出程序

20 void main() { int m,n,k,t; int flag=1; int f,x; k=1; do { m=7*k+1; x=m; n=1; while(n<m && flag>0){ if(x==n){ flag=0; break; } t=x-n; if(t%7==0){ f=n+t/7; x=x-f; n++; else break; k++; }while(flag>0); cout<<"n="<<n<<"\t"<<"m="<<m<<endl;

21 编程实验 1. A、B、C、D、E五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在河边睡着了。早晨，A第一个醒来，他将鱼平分5分，把多余的一份扔进湖中，拿自已的一份回家去了，B第二个醒来，也将鱼平分为5分，把多余的一份扔进湖中，只拿走自己的一份。接着CDE依次醒来，也都按同样的办法分鱼。问5人合伙捕到多少条？每人醒来后看到的鱼是多少？

22 2.（约瑟夫环问题）据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。但是约瑟夫与他的朋友并不想死，请你帮他编个程序，找出约瑟夫与他的朋友应该排在什么位置才可能免于一死？

23 排列顺序 自杀顺序

24 3. 某日，王母娘娘送唐僧一批仙桃，唐僧命八戒去挑。八戒从娘娘宫挑上仙桃出发，边走边望着眼前罗筐中的仙桃咽口水，走到128里时，倍觉心烦腹饥口干不能再忍，于是找了个背静处开始吃起前头箩筐中的仙桃来，越吃越有兴头，不觉竟将一筐仙桃吃尽，才猛然觉得大事不好。正在无奈之时，发现身后还有一筐，便转悲为喜，将身后的一筐仙桃一分为二，重新上路。走着走着，又馋病复发，才走了64里路，便故伎重演，又在吃光一筐仙桃后，把另一筐一分为二，才肯上路。以后，每走前一段路的一半，便吃光一头箩筐中的仙桃，才上路。如此这般，最后走了一里走完，正好遇上师傅。师傅一看，两个箩筐中个只有一只仙桃，于是大怒，要八戒交代一路偷吃了多少仙桃。八戒掰着指头，好几个时辰也回答不出。 请设计一个C语言程序，为八戒计算一下，一路偷吃了多少仙桃。

25 2.递归思想 递归思想的本质： 数学归纳法 递归是递推的更一般的形式，或“递推是递归的特例”

26 数学归纳法 第一数学归纳法 第二数学归纳法 𝑃 𝑛 0 =𝑡𝑟𝑢𝑒 𝑃 𝑛−1 =𝑡𝑟𝑢𝑒→𝑃 𝑛 =𝑡𝑟𝑢𝑒
𝑃 𝑛 0 =𝑡𝑟𝑢𝑒 𝑃 𝑛−1 =𝑡𝑟𝑢𝑒→𝑃 𝑛 =𝑡𝑟𝑢𝑒 第二数学归纳法 𝑃 𝑛 0 =𝑡𝑟𝑢𝑒 ∀𝑘,𝑃 𝑘 =𝑡𝑟𝑢𝑒→𝑃 𝑛 =𝑡𝑟𝑢𝑒 ,𝑘<𝑛

27 数学归纳法思想用于算法设计 第一数学归纳法 第而数学归纳法 𝑃( 𝑛 0 )可解 假设𝑃 𝑛−1 可解，求解𝑃(𝑛)
𝑃( 𝑛 0 )可解 ∀𝑘,𝑘<𝑛,𝑃 𝑘 可解，求解𝑃(𝑛)

28 例1：(顺序查找)在数组A[0:n-1]中查找是否存在关键字key. 归纳假设：假设在A[0:k-1]中查找关键字可解；
(1) 当k=1时，数组只有一个元素A[0:0]，显然可解。 (2)现在要从A[0:k-1]可解到处，到处A[0:k]可解，算法很简单 //顺序查找，递归算法 booolean searchRecui(A[],int key, int k){ if(k<0) return false; if(A[k]==key) return true; else return searchRecui(A,key,k-1); }

29 归纳假设：假设可以解决前面k个人的约瑟夫问
例2：(约瑟夫环) n个人（编号0到n-1）围成一圈，从第一个人开始报数，报数到m就出列，然后从下一个人开始报数，报道m出列，……，一直进行下去，最后一个人是胜利者。利用递归的方法求胜利者（编号）。 归纳假设：假设可以解决前面k个人的约瑟夫问 (1) k=1时，答案是明显的，胜利者就是第一个人。 (2) 现在要求在前k个人可解的情况下，如何求解k+1个人的约瑟夫问题。 (3) 实例分析,k=11,m=3 A=(0,1,2,3,4,5,6,7,8,9,10),第一个出列的人是2，变换 B=(8,9,2,0,1,2,3,4,5,6,7)，规模为n-1的问题

30 启发：规模为n的约瑟夫问题通过变换，可以变换为规模为n-1的问题 ==》 已知如何求解规模为n-1的问题后就可求解规模问n的问题。
如何P(n)==>P(n-1) ? 如何 P(n-1)==>P(n) ? 观察,A是P(n),B是P(n-1) B=(A-m)%n ， A=(B+m)%n f(n)=(f(n-1)+m)%n

31 public class Joseph { public static void main(String[] args) { int n, m, s=0; n=11; m=3; s=0; for (int i=2; i<=n; i++) s=(s+m)%i; System.out.printf ("n=%d s= %d\n",n, s+1); }

32 归纳假设：知道用插入排序求解规模为k的数组A[0:k-1]的排序问题。
例3：插入排序，递归实现 归纳假设：知道用插入排序求解规模为k的数组A[0:k-1]的排序问题。 (1) k=1时，数组只有一个元素，是有序的 (2) A[0:k-1]以排好序，如何解决A[0:k]的排序问题？==》 将A[k]按有序方式插入A[0:k-1]中即可

33 归纳假设：知道用选择排序求解规模为k的数组A[0:k-1]的排序问题。
例4：选择排序，递归实现 归纳假设：知道用选择排序求解规模为k的数组A[0:k-1]的排序问题。 (1) k=1时，数组只有一个元素，是有序的 (2) A[0:k-1]以排好序，如何解决A[0:k]的排序问题？==》 将A[k]按有序方式插入A[0:k-1]中即可

34 //插入排序--递归实现 static void insertSortRecrui(int[] A,int k){ if(k<1) return; insertSortRecrui(A,i-1); int j, x=A[k];; for(j=k-1;j>=0 && A[j]>x;j--) A[j+1]=A[j]; A[j+1]=x; }

35 【例】 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

36 public static void recruiPerm(int s[],int k,int m)
{ if(k==m){ printp(s,m); } else{ for(int i=k;i<=m;i++){ MyMath.swap(s, k, i); recruiPerm(s,k+1,m);

37 【例】整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。
同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1， ； 2+2+2， ， ； 。

38 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 (2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。

39 因此 f(n, m) = f(n-m, m)+f(n,m-1);
(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。   (4) m<n时，根据划分中是否包含最大值m，可以分为两种情况：          (a). 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);          (b). 划分中包含m的情况，即{m, {x1,x2,...xi}}, 其中{x1,x2,... xi} 的和为n-m，因此这种情况下为f(n-m,m)              因此 f(n, m) = f(n-m, m)+f(n,m-1);

40 正整数n的划分数p(n)=q(n,n)。 private static int q(int n,int m){ if(n==1 || m==1) return 1; if(m>n) return q(n,n); if(m==n) return 1+q(n,n-1); return q(n,m-1)+q(n-m,m); } public static int divideCount(int n){ return q(n,n);

41 【例】Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

42 在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。
当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。

43 void hanoi(int n, int a, int b, int c)
{ if (n > 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } 思考题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。

44 青蛙过河问题 一条小溪，青蛙可以从左岸跳到右岸，在左岸有一石柱L,面积只容得下一只青蛙落脚，有一队青蛙在尺寸上一个比一个大，将青蛙从小到大用(1，2，3，…，n)一个一个编号，规定初始时这队青蛙只能爬在左岸的石头L上，按编号顺序，小的爬在大的上面，不允许大的爬在小的上面。在小溪中有S个石柱，有y片荷叶，规定小溪中柱子上可以允许多只青蛙落脚，但同样要求按编号大的在下，小在上重迭起来，而且编号必须相邻。对于荷叶只允许一只青蛙落脚，不允许多只青蛙在其上。对于右岸的石柱R，与左岸的石柱L一样，只容得下一只青蛙落脚，多个青蛙必须按与左岸相同的规律重迭起来。当青蛙从左岸的L上跳走后就不允许再跳回来，问，在已知小溪中有S根石柱和y根茶叶的情况下，最多能跳过多少只青蛙？

45 解：如下图所示 假设y片荷叶，s-1个石柱能够跳过的青蛙数为 f(s-1,y),现在要求增加一个石柱情况下，共s个石柱的时候，能够跳过的青蛙数目？ 借鉴汉诺塔问题的思路，将问题分生两个子问题： ① 根据假设，将小溪里新增加的石柱作为中介，首先借助于s-1个石柱和y片荷叶，可以将f(s-1,y)只青蛙跳到第S个石柱上。 ② 第①步完成后，仍然空闲y片荷叶和s-1各石柱可用，可以跳过f(s-1,y)只青蛙到何的右岸石柱R上。 ③ 第s个石柱上的f(s-1,y)只青蛙借助于y片荷叶和s-1各石柱跳到右边的石柱R上。 综上所述，s个石柱，y片荷叶可跳过的青蛙数是：    f(s,y)=2*f(s-1,y) 公式只对s是递归的，y只是起初始条件的作用    f(0,y)=y+1