算法设计题目_pdf

《算法设计题目_pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章1、大整数乘法的O(nm)算法log(3/2)给定2个大整数u和v，它们分别有m位和n位数字，且m≤n。用通常的乘法求uv的值需要O(mn)时间。可以u和v均看作是有n位数字的大整数，用教材第2章介绍的分治法，在O(nlog3)时间内计算uv的值。当m比n小得多时，用这种方法就显得效率不够高。试设计一个算法，在上述情况下用O(nmlog(3/2))时间求出uv的值。2、O(1)空间子数组换位算法设a[0:n-1]是一个有n个元素的数组，k(1≤k≤n-1)是一个非负整数。试设计一个算法将子数组a[0:k-1]与a

2、[k+1:n-1]换位。要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。3、√段合并排序算法如果在合并排序算法的分割步骤中，将数组a[0:n-1]划分为⌊√⌋个子数组，每个子数组中有O(√)个元素。然后递归地对分割后的子数组进行排序，最后将所得到的⌊√⌋个排好序的子数组合并成所要的排好序的数组a[0:n-1]。设计一个实现上述策略的合并排序算法，并分析算法的计算复杂性。4、合并排序算法对拨给元素存储于数组和存储于链表中的2种情形，写出合并排序算法。5、非增序快速排序算法如何修改QuickSort才能使其将

3、输入元素按非增序排序？ 第三章1、整数线性规划问题考虑下面的整数线性规划问题∑=1∑≤=1为非负整数，1≤≤{试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。2、Ackermann函数Ackermann函数A(m,n)可递归地定义如下：+1=0A（m，n）={(−1,1)>0,=0(−1,(,−1))>0,>0试设计一个计算A(m,n)的动态规划算法，该算法只占用O(m)空间。3、独立任务最优调试问题问题描述：用2台机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间b

4、i。由于各作业的选战和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有ai

5、器焉得完这n个作业的时间最短。数据输入：由文件input.txt提供输入数据。文件的第1行是1个正整数n，表示要处理n个作业。在接下来的2行中，每行有n个正整数，分别表示处理机A和处理机B处理第i个作业需要的处理时间。结果输出：将计算出的最短处理时间输出到文件output.txt。输入文件示例input.txt6输出文件示例output.txt15257105238411344、三角形问题问题描述：给定一个由n行数字组成的数字三角形，如下图所示。试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最

6、大。737848512062445编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶到底的路径经过的数字和的最大值。数据输入：由文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。结果输出：程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。输入文件示例输出文件示例output.txt30Input.txt57 388102744452655、租用游艇问题问题描述：长

7、江游艇俱乐部在长江上设置了n个游艇出租站1，2，……，n。游客可在游艇站租用游艇，并在下游的任何一个游艇站归还游艇。游艇站i到游艇出租站j之间的租金为r(i,j)，1≤i

8、,j)，1≤i