《第2章-递归与分治策略-习题与实验》由会员分享，可在线阅读，更多相关《第2章-递归与分治策略-习题与实验（37页珍藏版）》请在金锄头文库上搜索。
1、第2章 递归与分治策略2.1 递归的概念例例2 Fibonacci2 Fibonacci数列数列无穷数列无穷数列1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，称为，称为FibonacciFibonacci数列。它可以递归地定义为：数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第第n个个Fibonacci数可递归地计算如下：数可递归地计算如下：int fibonacci(int n) if (n m1nm1; ;正整数正整数n n的最大加数的最大加数n n1 1不大于不大于m m的划分由的划分由n n1 1=m=m的划分和的划分和n n1 1
2、m-1 m-1 的划分组成。的划分组成。(3) (3) q(n,nq(n,n)=1+q(n,n-1);)=1+q(n,n-1);正整数正整数n n的划分由的划分由n n1 1=n=n的划分和的划分和n n1 1n-1n-1的划分组成。的划分组成。2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。而容易用递归函数直接求解。在本例中，如果设在本例中，如果设p(np(n) )为正整数为正整数n n的划分数，则难以找到递归关的划分数，则难以找到递归关系，因此考虑增加
3、一个自变量：将最大加数系，因此考虑增加一个自变量：将最大加数n n1 1不大于不大于m m的划分个的划分个数记作数记作q(n,mq(n,m) )。可以建立。可以建立q(n,mq(n,m) )的如下递归关系。的如下递归关系。52.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。而容易用递归函数直接求解。在本例中，如果设在本例中，如果设p(np(n) )为正整数为正整数n n的划分数，则难以找到递归关的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数
4、系，因此考虑增加一个自变量：将最大加数n n1 1不大于不大于m m的划分个的划分个数记作数记作q(n,mq(n,m) )。可以建立。可以建立q(n,mq(n,m) )的如下递归关系。的如下递归关系。正整数正整数n n的划分数的划分数p(np(n)=)=q(n,nq(n,n) )。 6整数划分问题整数划分问题7比较比较x和和a的中间元素的中间元素amid，若，若x=amid，则，则x在在L中的位置中的位置 就是就是mid；如果如果xai，同理我们只要在同理我们只要在amid的后面查找的后面查找x即可。即可。无论是在前面还是后面查找无论是在前面还是后面查找x，其方法都和在其方法都和在a中查找中查
5、找x一样，一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。第二个和第三个适用条件。二分搜索技术二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：8二分搜索技术二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。算法复杂度分析：算法复杂度分析：每执行一次算法的每执行一次算法的while循环，循环， 待搜索数
6、组的大小减待搜索数组的大小减少一半。因此，在最坏情况下，少一半。因此，在最坏情况下，while循环被执行了循环被执行了O(logn) 次。循环体内运算需要次。循环体内运算需要O(1) 时间，因此整个时间，因此整个算法在最坏情况下的计算时间复杂性为算法在最坏情况下的计算时间复杂性为O(logn) 。9二分搜索技术二分搜索技术n数据读取方法：数据读取方法：10循环赛日程表N=2k个运动员进行网球循环赛。个运动员进行网球循环赛。设计一个满足以下要求的比赛日程表：设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。
7、111234567821436587341278564321876556781234658721437856341287654321循环赛日程表按分治策略，将所有的选手分为两半，按分治策略，将所有的选手分为两半，n个选手的比赛日个选手的比赛日程表就可以通过为程表就可以通过为n/2个选手设计的比赛日程表来决定。个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下递归地用对选手进行分割，直到只剩下2个选手时，比赛个选手时，比赛日程表的制定就变得很简单。这时只要让这日程表的制定就变得很简单。这时只要让这2个选手进行个选手进行比赛就可以了。比赛就可以了。12循环赛日程表void table
8、(int k, int *a) int n=1; for(int i=1;i=k;i+) n*=2; for(int i=1;i=n;i+) a1i=i; int m=1; for(int s=1;s=k;s+) n/=2; for(int t=1;t=n;t+) for(int i=m+1;i=2*m;i+) for(int j=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; 13输油管道问题输油管道问题 n某石油公司计划建造一条由东向西的主输油管道。某石油公司计划
9、建造一条由东向西的主输油管道。该管道要穿过一个有该管道要穿过一个有n 口油井的油田。从每口油口油井的油田。从每口油井都要有一条输油管道沿最短路经井都要有一条输油管道沿最短路经(或南或北或南或北)与与主管道相连。如果给定主管道相连。如果给定n 口油井的位置口油井的位置,即它们的即它们的x 坐标（东西向）和坐标（东西向）和y 坐标（南北向）坐标（南北向）,应如何确应如何确定主管道的最优位置定主管道的最优位置, 即使各油井到主管道之间即使各油井到主管道之间的输油管道长度总和最小的位置的输油管道长度总和最小的位置?n编程任务：编程任务：n给定给定n 口油井的位置口油井的位置,编程计算各油井到主管道之编
10、程计算各油井到主管道之间的输油管道最小长度总和。间的输油管道最小长度总和。14n数据输入：数据输入：第第1 行是油井数行是油井数n，1=n=10000。接下来。接下来n 行是油井的行是油井的位置，每行位置，每行2 个整数个整数x 和和y，-10000=x，y=10000 。n结果输出结果输出: 输出的第输出的第1 行中的数是油井到主管道之间的输油管道最小行中的数是油井到主管道之间的输油管道最小长度总和。长度总和。n输入示例输入示例5 1 2 2 2 1 3 3 -2 3 3 n输出示例输出示例6输油管道问题输油管道问题 0 1 2 3 4321-1-2xy15输油管道问题输油管道问题 #inc
11、lude #include#define N 1000116输油管道问题输油管道问题O(nlogn) C+: sort(a, a+n);需要需要:#include17众数问题众数问题 n给定含有给定含有n 个元素的多重集合个元素的多重集合S，每个元素在，每个元素在S 中中出现的次数称为该元素的重数。多重集出现的次数称为该元素的重数。多重集S 中重数中重数最大的元素称为众数。最大的元素称为众数。例如，例如，S=1，2，2，2，3，5。多重集多重集S 的众数是的众数是2，其重数为，其重数为3。n编程任务：编程任务：对于给定的由对于给定的由n 个自然数组成的多重集个自然数组成的多重集S，编程计，编程
12、计算算S 的众数及其重数。的众数及其重数。18众数问题众数问题 n数据输入：数据输入：输入数据的第输入数据的第1 行多重集行多重集S 中元素个数中元素个数n；接下来；接下来的的n 行中，每行有一个自然数。行中，每行有一个自然数。n结果输出结果输出: 输出的第输出的第1 行给出众数，第行给出众数，第2 行是重数。行是重数。n输入示例输入示例61 2 2 2 3 5 n输出文件示例输出文件示例2319众数问题众数问题 int freq100000;/全局变量全局变量max是所有输入数据中是所有输入数据中的最大数；的最大数；temp是读取的数据；是读取的数据；freq对读取的数据累加对读取的数据累加
13、temp12345freq 13101输入示例输入示例 6 1 2 2 2 3 5 输出文件示例输出文件示例 2 320邮局选址问题邮局选址问题n在一个按照东西和南北方向划分成规整街区的城在一个按照东西和南北方向划分成规整街区的城市里，市里，n 个居民点散乱地分布在不同的街区中。个居民点散乱地分布在不同的街区中。用用x 坐标表示东西向，用坐标表示东西向，用y 坐标表示南北向。各居坐标表示南北向。各居民点的位置可以由坐标民点的位置可以由坐标(x,y) 表示。街区中任意表示。街区中任意2 点点(x1,y1) 和和(x2,y2) 之间的距离可以用数值之间的距离可以用数值|x1-x2|+|y1-y2|
14、 度量。度量。居民们希望在城市中选择建立邮局的最佳位置，居民们希望在城市中选择建立邮局的最佳位置，使使n 个居民点到邮局的距离总和最小。个居民点到邮局的距离总和最小。n编程任务：编程任务：给定给定n 个居民点的位置个居民点的位置, 编程计算编程计算n 个居民点到邮个居民点到邮局的距离总和的最小值。局的距离总和的最小值。21邮局选址问题邮局选址问题n数据输入：数据输入：第第1 行是居民点数行是居民点数n，1n 10000。接下来。接下来n 行是居民点的行是居民点的位置，每行位置，每行2 个整数个整数x 和和y，-10000x，y10000。n结果输出结果输出: 第第1 行中的数是行中的数是n 个
15、居民点到邮局的距离总和的最小值。个居民点到邮局的距离总和的最小值。n输入示例输入示例 5 1 2 2 2 1 3 3 -2 3 3 n输出示例输出示例10 0 1 2 3 4321-1-2xy22邮局选址问题邮局选址问题#define N 1001int n,i,j,min;int xN=0, yN=0, aN=0, bN=0;scanf(%d,&n);for(i=0; in; i+)scanf(%d %d,&xi, &yi);for(i=0; in; i+)for(j=0; jn; j+) if(i=j) continue;ai += abs(xi-xj);bi += abs(yi-yj);
16、0 1 2 3 4321-1-2xy23邮局选址问题邮局选址问题j=a0;/x的最小值及其坐标的最小值及其坐标int x0=0;for(i=1;iai) j=ai; x0=i;j=b0; /y的最小值及其坐标的最小值及其坐标int y0=0;for(i=1;ibi) j=bi; y0=i;min = ax0+by0;printf(%dn, min);return 0;0 1 2 3 4321-1-2xy24半数集问题半数集问题n给定一个自然数给定一个自然数n，由，由n开始可以依次产生半数集开始可以依次产生半数集set(n)中的数如下。中的数如下。 (1) nset(n)； (2) 在在n的左边
17、加上一个自然数，但该自然数不能超过最近添加的的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。按此规则进行处理，直到不能再添加自然数为止。 例如，例如，set(6)=6,16,26,126,36,136。半数集。半数集 set(6)中有中有6 个元素。个元素。 注意半数集是多重集。注意半数集是多重集。 n编程任务：编程任务： 对于给定的自然数对于给定的自然数n(1n 1000)，编程计算半数集，编程计算半数集set(n)中的元素个数。中的元素个数。 25半数集问题半数集问题n12n112, 212, 312, 412,
18、512, 612n1212n1312n1412, 241212412n1512, 2512 12512n1612, 2612 12612, 3612 13612nP(12)=20个个26半数集问题半数集问题设设set(n)中的元素的个数为中的元素的个数为f(n), 则显然有：则显然有：int f(int n ) int ans = 1;if(n 1 )for(int i = 1 ; i = n/2 ;i+) ans += f(i) ;return ans ;27半数集问题半数集问题28半数集问题半数集问题29半数半数单单集问题集问题n给定一个自然数给定一个自然数n，由，由n开始可以依次产生半数
19、集开始可以依次产生半数集set(n)中中的数如下。的数如下。(1) nset(n)；(2) 在在n的左边加上一个自然数，但该自然数不能超过最近添加的数的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；的一半；(3) 按此规则进行处理，直到不能再添加自然数为止。按此规则进行处理，直到不能再添加自然数为止。例如，例如，set(6)=6,16,26,126,36,136。半数集。半数集set(6)中有中有6 个元素。个元素。n注意该半数集不是多重集。注意该半数集不是多重集。集合中已经有的元素不再添加集合中已经有的元素不再添加到集合中。到集合中。n编程任务：编程任务：对于给定的自然数对于给定
20、的自然数n，编程计算半数集，编程计算半数集set(n)中的元素个中的元素个数。数。30半数半数单单集问题集问题n数据输入：数据输入：输入数据只有输入数据只有1 行，给出整数行，给出整数n。(0n201)n结果输出结果输出:输出只有输出只有1 行，给出半数集行，给出半数集set(n)中的元素中的元素个数。个数。n输入示例输入示例 6n输出示例输出示例631半数半数单单集问题集问题n示例：示例：99n199,299,399,499,599,699,799,899,999,n1099,1199,.,4999n999 1999,2999,3999,4999nn注意条件注意条件0n201，即，即0n/2
21、100。n在计算时可能产生重复的元素是在计算时可能产生重复的元素是2位数。位数。32半数半数单单集问题集问题n注意条件注意条件0n201，即，即0n/2100。n在计算时可能产生重复的元素是在计算时可能产生重复的元素是2位数。位数。n一个一个2位数位数x重复产生的条件是：在重复产生的条件是：在1位数位数y=x%10的半数集中已产生的半数集中已产生x,因此因此x/10 y/2，即：，即：2(x/10) x%102 5x/10 X%10y1 2 3 4 5 6 7 8 9 10 11 121233整数因子分解问题整数因子分解问题 n大于大于1 的正整数的正整数n可以分解为：可以分解为：n=x1*x
22、2*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，编程计算，编程计算n共有多少种不同的分解式。共有多少种不同的分解式。34整数因子分解问题整数因子分解问题 n数据输入：数据输入：第一行有第一行有1 个正整数个正整数n (1n2000000000)。n结果输出结果输出:计算出的不同的分解式数。计算出的不同的分解式数。n输入示例输入示例12n输出文件示例输出文件示例835整数因子分解
23、问题整数因子分解问题n对对n的每个因子递归搜索：的每个因子递归搜索：int total=0;/全局变量全局变量void solve(int n) if (n=1) total+;else for (int i=2; i=n; i+) if (n%i=0) solve(n/i);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。3612n%i=023456789101112n/i643x2xxxxx12 3 4 5 6 2 3 4 2 33 2 x x 1 2 x 1 x 1212 3 2x 1 1n%i=0n/in%i=0n/i21整数因子分解问题整数因子分解问题void solve(int n) if (n=1) total+; else for (int i=2; i=n; i+) if (n%i=0) solve(n/i);37
