递归与分治策略doc

《递归与分治策略doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法》习题解答山东师范大学信息科学与工程学院软件工程研究所徐连诚第二章递归与分治策略习题2-27个二分搜索算法1）与教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。2）与教材中的算法BinarySearch相比，数组段左、右游标left和right的调整不正确，导致当x=a[n－1]时返回错误。3）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a[n－1]时返回错误。4）与正确算法BinarySearch5

2、相比，数组段左、右游标left和right的调整不正确，导致陷入死循环。5）算法正确，且当数组中有重复元素时，返回满足条件的最右元素。6）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a[n－1]时返回错误。7）与正确算法BinarySearch5相比，数组段左、右游标left和right的调整不正确，导致当x=a[0]陷入死循环。习题2-30输油管道最佳布局问题设M口油井的位置分别为pi=(xi,yi)，i=1,…,n。由于主输油管道是东西向的，因此可用其主轴线的y

3、坐标唯一确定其位置。主管道的最优位置y应使达到最小，其中d(y,yi)=

4、y-yi

5、。由带权中位数问题的解答即知，yi，i=1,…,n的中位数yk即为输油管道问题的最忧解。用任何—个线性时间找中位数算法均可在o(n)时间内解此问题。习题2-34构造Gray码的分治算法考察n=1,2,3的简单情形：n=10,1n=200,01,11,10n=3000,001,011,010,110,111,101,100设n位Gary码序列为G(n),G(n)以相反顺序排列的序列为G-1(n)。从上面的简单情形可以看出G(n)的构造规律：G

6、(n+1)=0G(n)1G-1(n)。注意到G（n）的最后一个n位串与G-1(n)的第一个n位串相同，可用数学归纳法证明G(n)的上述构造规律。由此规律容易设计构造G(n)的分治法如下。voidgray(intn)｛if(n==1)｛a[1]=0;a[2]=1;return;｝gray(n-1);for(intk=1<<(n-1),i=k;i>0;1--)a[2*k-i+1]=a[i]+k;}上述算法中将n位（0，1）串看作是二进进制整数，第i个串存储在a[i]k中。完成计算后，由out输出Gray码序列。voidout(

7、intn)第二章递归与分治策略4《算法》习题解答山东师范大学信息科学与工程学院软件工程研究所徐连诚{charstr[32];intm=1<

8、rna(n/2);copy(n);}其中，算法copy将左上角递归计算出的小块中的所有数字按其相对位置抄到右下角，将右上角小块中所有数字加n/2后按其相对位置抄到左下角，将左下角小块中的所有数字按其相对位置抄到右下角，这样就完成了比赛日程表。voidcopy(intn){intm=n/2;for(inti=1;i<=m;i＋＋)for(intj=1;j<=m;j＋＋)｛a[1][j＋m]=a[i][j]＋m;a[i＋m][j]=a[i][j＋m];a[i＋m][j＋m]=a[i][j];}}对于一般的正整数n，当n是奇数时

9、，增设一个虚拟选手n＋1,将将问题转换为n是偶数的情形。当选手与虚拟选手比赛时，表示轮空。因此只要关注n为偶数的情形即可。当n/2为偶数时，与n=2k的情形类似，可用分治法求解。当n/2为奇数时，递归返回的轮空的比赛要做进一步处理。其中一种处理方法是在前n/2轮比赛中让轮空选手与下一个未参赛选手进行比赛。一般情况下的分治法tournament可描述如下。voidtournament(intn){if(n==1)｛a[1][1]=1;return;｝第二章递归与分治策略4《算法》习题解答山东师范大学信息科学与工程学院软件工程

10、研究所徐连诚if(odd(n))｛tournament(n＋1);return;｝tournament(n/2);makecopy(n);}boolodd(intn){returnn＆1;}其中，算法makecopy与算法copy类似，但要区分n/2为奇数或偶数的情形。voidmakecopy(intn