第2章递归与分治策略习题与实验课件.ppt

《第2章递归与分治策略习题与实验课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章递归与分治策略12.1递归的概念例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：intfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}22.1递归的概念例5整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种

2、表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。3(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即2.1递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解

3、。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。4(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。2.1递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数

4、直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。52.1递归的概念例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。6整数划分问

5、题7比较x和a的中间元素a[mid]，若x=a[mid]，则x在L中的位置就是mid；如果xa[i]，同理我们只要在a[mid]的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。分析：8二

6、分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。9二分搜索技术数据读取方法：10循环赛日程表N=2k个运动员进行网球循环赛。设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-

7、1天。111234567821436587341278564321876556781234658721437856341287654321循环赛日程表按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。12循环赛日程表voidtable(intk,int**a){intn=1;for(inti=1;i<=k;i++)n*=2;for(inti=1;i<=n;

8、i++)a[1][i]=i;intm=1;for(ints=1;s<=k;s++){n/=2;for(intt=1;t<=n;t++)for(inti=m+1;i<=2*m;i++)for(intj=m+1;j<=2*m;j++){a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];a[i][j+(t-