算法设计题目

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

1、第2章1、大整数乘法的O(nmlog(3/2))算法给定2个大整数u和v，它们分别有m位和n位数字，且mn。用通常的乘法求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(1kn-1)是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求

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

3、规划问题试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。2、Ackermann函数Ackermann函数A(m,n)可递归地定义如下：A（m，n）=试设计一个计算A(m,n)的动态规划算法，该算法只占用O(m)空间。3、独立任务最优调试问题问题描述：用2台机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的选战和机器的性能关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有ai

4、态规划算法，使得这2台机器处理完这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总时间）。研究一个实例：（a1，a2，a3，a4，a5，a6）=（2，5，7，10，5，2）；（b1，b2，b3，b4，b5，b6）=（3，8，4，11，3，4）。算法设计：对于给定的2台处理机A和B处理n个作业，找出一个最优调试方案，使2台机器焉得完这n个作业的时间最短。数据输入：由文件input.txt提供输入数据。文件的第1行是1个正整数n，表示要处理n个作业。在接下来的2行中，每行有n个正整数，分别表示处理机A和处理机B处理第i个作业需要的处

5、理时间。结果输出：将计算出的最短处理时间输出到文件output.txt。输入文件示例输出文件示例input.txtoutput.txt615257105238411344、三角形问题问题描述：给定一个由n行数字组成的数字三角形，如下图所示。试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。738810274445265编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶到底的路径经过的数字和的最大值。数据输入：由文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1≤n≤100。

6、接下来n行是数字三角形各行中的数字。所有数字在0~99之间。结果输出：程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。输入文件示例输出文件示例Input.txtoutput.txt5307388102744452655、租用游艇问题问题描述：长江游艇俱乐部在长江上设置了n个游艇出租站1，2，……，n。游客可在游艇站租用游艇，并在下游的任何一个游艇站归还游艇。游艇站i到游艇出租站j之间的租金为r(i,j)，1≤i

7、对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j)，1≤i

8、数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。编程任务：对于给定的正整数a，编程计算删去k