算法设计题目.docx

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

试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。
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<bj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这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个作业需要的处理时间。
结果输出：将计算出的最短处理时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
6 15
2 5 7 10 5 2
3 8 4 11 3 4
4、三角形问题
问题描述：给定一个由n行数字组成的数字三角形，如下图所示。试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶到底的路径经过的数字和的最大值。
数据输入：由文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。
结果输出：程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。
输入文件示例 输出文件示例
Input.txt output.txt
5 30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
5、租用游艇问题
问题描述：长江游艇俱乐部在长江上设置了n个游艇出租站1，2，……，n。游客可在游艇站租用游艇，并在下游的任何一个游艇站归还游艇。游艇站i到游艇出租站j之间的租金为r(i,j)，1≤i<j≤n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。
编程任务：对于给定的游艇出租站i到游艇出租站j之间的租金为r(i,j)，1≤i<j≤n，编程计算从游艇出租站1到游艇出租站n所需的最少租金。
数据输入：由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n≤200），表示有n个游艇出租站。接下来的n-1行是r(i,j)，1≤i<j≤n。
结果输出：程序运行结束时，将计算出的从游艇出租站1到游艇出租站n所需的最少租金输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt output.txt
3 12
5 15
7

第四章
1、删数问题
问题描述：给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。
编程任务：对于给定的正整数a，编程计算删去k个数字后得到的最小数。
数据输入：由文件input.txt提供输入数据。文件的第1行是1个正整数a。第2行是正整数k。
结果输出：程序运行结束时，将计算出的最小数输出到文件output.txt。
输入文件示例 输出文件示例
Input.txt output.txt
178543 13
4
2、套汇问题
问题描述：套汇是指利用货币兑换率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，嘉定1美元可以买0.7英镑，1英镑可以买9.5法郎，且1法郎可以买到0.16美元。通过货币兑换，一个商人可以从1美元开始买入，得到0.79.50.16=1.064美元，从而获得6.4%的利润。
编程任务：给定n种货币c1，c2，…，cn的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。
数据输入：由文件input，txt提供输入数据。文件含多个测试数据项，每个测试数据项的第1行中只有个整数n（1≤n≤30），表示货币总数。其后n行给出n种货币的名称。接下来的一行中有1个整数m，表示有m种不同的货币兑换率，其后m行给出m种不同的货币兑换率，每行有3个数据项ci，rij和cj，表示货币ci和cj的兑换率为rij。文件最后以数字0结束。
结果输出：程序运行结束时，对每个测试数据项j，如果存在套汇的可能性则输出 “case j yes”,否则输出“case j no”。所有结果输出到文件output.txt。
输入文件示例 输出文件示例
Input.txt output.txt
3 case 1 yes
USDollar case 2 no
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
0
3、磁带最大利用率问题
问题描述：设有n个程序｛1,2，…，n｝要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。
程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。在保证存储最多程序的前提下还要求磁带的利用率达到最大。
编程任务：对于给定的n个程序放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占用磁带的长度。
数据输入：由文件input.txt给出输入数据。第1行是2个正整数，分别表示文件个数n和磁带的长度L。家下来的1行中，有n个正整数，表示程序存放在磁带上的长度。
结果输出：将编程计算出的最多可以存储的程序数和占用磁带上的每个程序的长度输出到文件output.txt。第1行输出最多可以存储的程序数和占用磁带的长度；第2行输出存放在磁带上的每个程序的长度。
输入文件示例 输出文件示例
input.txt output.txt
9 50 5 49
2 3 13 8 80 20 21 22 23 2 3 13 8 23
4、多元Huffman编码问题
问题描述：在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。
编程任务：对于给定的n堆石子，编程计算合并成一堆的最大总费用和最小总费用。
数据输入：由文件input.txt提供输入数据。文件的第1行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。
结果输出：程序运行结束时，将计算的最大总费用和最小总费用输出到output.txt。
输入文件示例 输出文件示例
input.txt output.txt
7 3 593 199
45 13 12 16 9 5 22
5、最优分解问题
问题描述：设n是一个正整数。现在要求将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大。
编程任务:对于给定的正整数n，编程计算最优分解方案。
数据输入：由文件input.txt提供输入数据。文件的第1行是正整数n。
结果输出：程序运行结束时，将计算出的最大乘积输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
10 30
第五章
1、最小重量机器设计问题
问题描述：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。高wij是从供应商j处购得的部件i的重量，cij是相应的价格。
试设计一个算法，给出总价格不超过c的最小重量机器设计。
编程任务：对于给定的机器部件重量和机器部件价格，编程计算总价格不超过d的最小重量机器设计。
数据输入：由文件input.txt给出输入数据。第一行有3个正整数n，m和d。接正业的2n行，每行n个数。前n行是c，后n行是w。
结果输出：将计算出的最小重量，以及每个部件的供应商输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
3 3 4 4
1 2 3 1 3 1
3 2 1
2 2 2
2、运动员最佳配对问题
问题描述：羽毛球有男女运动员各n人。给定2个n╳n矩阵P和Q。P[i][j]是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
编程任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。
数据输入：由文件input.txt给出输入数据。第一行有1个正整数n（1≤n≤20）。接下来的2n行，每行n个数。前n行是p，后n行是q。
结果输出：将计算出的男女双方竞赛优势的总和的最大值输出到文件output.txt。
输入文件示例 输出文件示例
Input.txt output.txt
3 52
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
3、无和集问题
问题描述：设S是正整数集合。S是一个无和集当且仅当x,y∊S蕴含x+y∉S。
对于任意正整数k，如果可将｛1，2，……，k｝划分为n个无和子集S1，S2，……，Sn，则称正整数k是n可分的。记F(n)=max{k|k是n可分的}。试设计一个算法，对任意给定的n，计算F(n)的值。
编程任务：对任意给定的n，编程计算F(n)的值。
数据输入：由文件input.txt给出输入数据。第一行有1个正整数n。
结果输出：将计算出的F(n)的值以及｛1，2，……，F(n)｝的一个n划分输出到文件output.txt。文件的第1行是F(n)的值。接下来的n行，每行是一个无和子集Si。
输入文件示例 输出文件示例
input.txt output.txt
2 8
1 2 4 8
3 5 6 7
4、整数变换问题
问题描述：关于整数i的变换f和g定义如下：f(i)=3i；g(i)= ⌊i/2⌋。
试设计一个算法，对于给定的2个整数n和m，用最少的f和g变换次数将n变换为m。
例如，可以将整数15用4次变换将它变换为整数4：4=gfgg(15)。当整数n不可能变换为整数m时，算法应如何处理？
编程任务：对任意给定的整数n和m，编程计算将整数n变换为整数m所需要的最少变换次数。
数据输入：由文件input.txt给出输入数据。第1行有2个正整数n和m。
结果输出：将计算出的最少变换次数以及相应的变换序列输出到文件output.txt。文件的第一行是最少变换次数。文件的第2行是相应的变换序列。
输入文件示例 输出文件示例
input.txt output.txt
15 4 4
gfgg
5、布线问题
问题描述：假设要将一组元件安装在一块线路板上，为此需要设计线路板布线方案。各元件的连线数由连线矩阵conn给出。元件i和元件j之间的连线数为conn(i,j)。如果将元件i安装在线路板上位置r处，而将元件j安装在线路板上位置s处，则元件i和元件j之间的距离为dist(r,s)。确定了所给的n个元件的安装位置，就确定了一个布线方案。与此布线方案相应的布线成本为。试设计一个算法找出所给n个元件的布线成本最小的布线方案。
编程任务：设计一个算法，对于给定的n个元件，计算最佳布线方案，使布线费用达到最小。
数据输入：由文件input.txt给出输入数据。第1行有1个正整数n（1≤n≤20）。接下来的n-1行，每行n-i个数，表示元件i和元件j之间连线数，1≤i<j≤20。
结果输出：将计算出的最小布线费用以及相应的最佳布线方案输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
3 10
2 3 1 3 2
3

第六章
1、0-1背包问题的栈式分支限界法
栈式分支限界法将活结点表以后进先出(LIFO)的方式存储于一个栈中。试设计一个解0-1背包问题的栈式分支限界法，并说明栈式分支限界法与回溯法的区别。
2、及时删除不用的结点
解装载问题的分支限界算法中，由EnQueue产生的结点可以在算法结束前一次性删除。然而那些没有活儿子结点或没有叶结点的扩展结点可以立即被删除。试设计一个在算法中及时删除不用结点的方案，并讨论其时间与空间之间的折中。
3、释放结点空间的优先队列式分支限界法
试修改解装载问题和解0-1背包问题的优先队列式分支限界法，使得算法在运行结束时释放所有类型为bbnode和HeapNode的结点所占用的空间。
4、电路板排列问题的队列分支限界法
试设计解电路板排列问题的队列式分支限界法，并使算法在运行结束是输出最优解和最优值。
5、最小重量机器设计问题
问题描述：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。高wij是从供应商j处购得的部件i的重量，cij是相应的价格。
试设计一个优先队列式分支限界法，给出总价格不超过d的最小重量机器设计。
编程任务：对于给定的机器部件重量和机器部件价格，编程计算总价格不超过d的最小重量机器设计。
数据输入：由文件input.txt给出输入数据。第一行有3个正整数n，m和d。接正业的2n行，每行n个数。前n行是c，后n行是w。
结果输出：将计算出的最小重量，以及每个部件的供应商输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
3 3 4 4
1 2 3 1 3 1
3 2 1
2 2 2