《递归与分治策略doc.doc》由会员分享，可在线阅读，更多相关《递归与分治策略doc.doc（4页珍藏版）》请在金锄头文库上搜索。
1、算法习题解答山东师范大学信息科学与工程学院软件工程研究所 徐连诚第二章 递归与分治策略习题2-2 7个二分搜索算法1）与教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。2）与教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致当x=an1时返回错误。3）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=an1时返回错误。4）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。5）算法正
2、确，且当数组中有重复元素时，返回满足条件的最右元素。6）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=an1时返回错误。7）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a0陷入死循环。习题2-30 输油管道最佳布局问题设M口油井的位置分别为pi=(xi,yi)，i=1,n。由于主输油管道是东西向的，因此可用其主轴线的y坐标唯一确定其位置。主管道的最优位置y应使达到最小，其中d(y,yi)=| y-yi |。由带权中位数问题的解答即知，yi，i=1,n的中位数yk即为输油管道问题的最
3、忧解。用任何个线性时间找中位数算法均可在o(n)时间内解此问题。习题2-34 构造Gray码的分治算法考察n=1,2,3的简单情形：n=1 0,1n=2 00,01,11,10n=3 000,001,011,010,110,111,101,100设n位Gary码序列为G(n),G(n)以相反顺序排列的序列为G-1(n)。从上面的简单情形可以看出G(n)的构造规律：G(n+1)=0G(n)1G-1(n)。注意到G（n）的最后一个n位串与G-1(n)的第一个n位串相同，可用数学归纳法证明G(n)的上述构造规律。由此规律容易设计构造G(n)的分治法如下。void gray(int n) if(n=1
4、)a1=0;a2=1;return; gray(n-1); for(int k=10;1-)a2*k-i+1=ai+k;上述算法中将n位（0，1）串看作是二进进制整数，第i个串存储在a ik中。完成计算后，由out输出Gray码序列。void out(int n) char str32; int m=1n; for (int i=1;im;i) _itoa(ai,str,2); int s=strlen(str); for(int j=0;jn-s;j)cout0; coutstr; coutendl;习题2-35 网球循环赛日程表用分治法，教材中的分治法应描述如下：void tourna(i
5、nt n) if(n=1)a1 1=1;return; tourna(n/2); copy(n);其中，算法copy将左上角递归计算出的小块中的所有数字按其相对位置抄到右下角，将右上角小块中所有数字加n/2后按其相对位置抄到左下角，将左下角小块中的所有数字按其相对位置抄到右下角，这样就完成了比赛日程表。void copy(int n) int m=n/2; for(int i=1;i=m;i) for(int j=1;j1odd(n/2)copyodd(n); else copy(n);算法copyodd实现n/2为奇数时的复制。void copyodd(int n) int m=n/2; for(int i=1;i=m;i) b1=mi;bmi=bi; for(i=1;im)aij=bi;amij=bim)%n; else amij=aijm; for(j=2;j=m;j aimj=bij-1; ab ij-1mj=I; 用上述算法计算出的n=10的比赛日程表如下表所示。表 分治法n=10的比赛日程表12345678910215374891063812459106745913210678542101367896789101543276108291543836791021549104687321510975684321第二章 递归与分治策略4
