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

1、第2章递归与分治策略,2,2.1递归的概念,例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下：intfibonacci(intn)if(nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1的划分组成。,(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。,2.1递归的概念,例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(

2、n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,6,2.1递归的概念,例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,7,整数划分问题,8,比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，

3、同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：,9,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。,1

4、0,二分搜索技术,数据读取方法：,11,循环赛日程表,N=2k个运动员进行网球循环赛。设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。,12,循环赛日程表,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,13,循环赛日程表,voidtable(intk,int*a)intn=1;for(inti=1;i=k;i+)n*=2;for(in

5、ti=1;i=n;i+)a1i=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+)aij+(t-1)*m*2=ai-mj+(t-1)*m*2-m;aij+(t-1)*m*2-m=ai-mj+(t-1)*m*2;m*=2;,14,输油管道问题,某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定

6、主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?编程任务：给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。,15,数据输入：第1行是油井数n，1=n=10000。接下来n行是油井的位置，每行2个整数x和y，-10000=x，y1)for(inti=1;i=n/2;i+)ans+=f(i);returnans;,28,半数集问题,29,半数集问题,30,半数单集问题,给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。(1)nset(n)；(2)在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3)按此规则进行处理，直到

7、不能再添加自然数为止。例如，set(6)=6,16,26,126,36,136。半数集set(6)中有6个元素。注意该半数集不是多重集。集合中已经有的元素不再添加到集合中。编程任务：对于给定的自然数n，编程计算半数集set(n)中的元素个数。,31,半数单集问题,数据输入：输入数据只有1行，给出整数n。(0n201)结果输出:输出只有1行，给出半数集set(n)中的元素个数。输入示例6输出示例6,32,半数单集问题,示例：99199,299,399,499,599,699,799,899,999,1099,1199,.,49999991999,2999,3999,4999注意条件0n201，即

8、0n/2100。在计算时可能产生重复的元素是2位数。,33,半数单集问题,注意条件0n201，即0n/2100。在计算时可能产生重复的元素是2位数。一个2位数x重复产生的条件是：在1位数y=x%10的半数集中已产生x,因此x/10y/2，即：2(x/10)x%10,x/10,X%10y,123456789101112,12,34,整数因子分解问题,大于1的正整数n可以分解为：n=x1*x2*xm。例如，当n=12时，共有8种不同的分解式：12=12；12=6*2；12=4*3；12=3*4；12=3*2*2；12=2*6；12=2*3*2；12=2*2*3。编程任务：对于给定的正整数n，编程计算n共有多少种不同的分解式。,35,整数因子分解问题,数据输入：第一行有1个正整数n(1n2000000000)。结果输出:计算出的不同的分解式数。输入示例12输出文件示例8,36,整数因子分解问题,对n的每个因子递归搜索：inttotal=0;/全局变量voidsolve(intn)if(n=1)total+;elsefor(inti=2;i=n;i+)if(n%i=0)solve(n/i);,12=12；12=6*2