当前位置：文档之家 › 算法设计题目

算法设计题目

  • 格式：docx
  • 大小：36.93 KB
  • 文档页数：15

第2章1、大整数乘法的O(nm log(3/2))算法给定2个大整数u和v，它们分别有m位和n位数字，且mn。

用通常的乘法求uv的值需要O(mn)时间。

可以u和v均看作是有n位数字的大整数，用教材第2章介绍的分治法，在O(n log3)时间内计算uv的值。

当m比n小得多时，用这种方法就显得效率不够高。

试设计一个算法，在上述情况下用O(nm log(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 处理时需要时间a i，若由机器B来处理，则需要时间b i。

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

既不能将一个作业分开由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.txt615257105238411344、三角形问题问题描述：给定一个由n行数字组成的数字三角形，如下图所示。

试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。

738810274445265编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶到底的路径经过的数字和的最大值。

数据输入：由文件input.txt提供输入数据。

文件的第1行是数字三角形的行数n，1≤n≤100。

接下来n行是数字三角形各行中的数字。

所有数字在0~99之间。

结果输出：程序运行结束时，将计算结果输出到文件output.txt中。

文件第1行中的数是计算出的最大值。

输入文件示例输出文件示例Input.txt output.txt5307388102744452655、租用游艇问题问题描述：长江游艇俱乐部在长江上设置了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.txt312 5157第四章1、删数问题问题描述：给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。

对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。

编程任务：对于给定的正整数a，编程计算删去k个数字后得到的最小数。

数据输入：由文件input.txt提供输入数据。

文件的第1行是1个正整数a。

第2行是正整数k。

结果输出：程序运行结束时，将计算出的最小数输出到文件output.txt。

输入文件示例输出文件示例Input.txt output.txt1785431342、套汇问题问题描述：套汇是指利用货币兑换率的差异将一个单位的某种货币转换为大于一个单位的同种货币。

例如，嘉定1美元可以买0.7英镑，1英镑可以买9.5法郎，且1法郎可以买到0.16美元。

通过货币兑换，一个商人可以从1美元开始买入，得到0.79.50.16=1.064美元，从而获得6.4%的利润。

编程任务：给定n种货币c1，c2，…，c n的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。

数据输入：由文件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.txt3case1yesUSDollar case2noBritishPoundFrenchFranc3USDollar0.5BritishPoundBritishPound10.0FrenchFrancFrenchFranc0.21USDollar3、磁带最大利用率问题问题描述：设有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.txt95054923138802021222323138234、多元Huffman编码问题问题描述：在一个操场的四周摆放着n堆石子。

现要将石子有次序地合并成一堆。

规定每次至少选2堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。

试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。

编程任务：对于给定的n堆石子，编程计算合并成一堆的最大总费用和最小总费用。

数据输入：由文件input.txt提供输入数据。

文件的第1行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。

第2行有n个数，分别表示每堆石子的个数。

结果输出：程序运行结束时，将计算的最大总费用和最小总费用输出到output.txt。

输入文件示例输出文件示例input.txt output.txt735931994513121695225、最优分解问题问题描述：设n是一个正整数。

现在要求将n分解为若干互不相同的自然数的和，且使这些自然数的乘积最大。

编程任务:对于给定的正整数n，编程计算最优分解方案。

数据输入：由文件input.txt提供输入数据。

文件的第1行是正整数n。

结果输出：程序运行结束时，将计算出的最大乘积输出到文件output.txt。

输入文件示例输出文件示例input.txt output.txt1030第五章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.txt33441231313212222、运动员最佳配对问题问题描述：羽毛球有男女运动员各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。

合集下载

算法设计与分析复习题目及答案详解

算法设计与分析复习题目及答案详解

算法设计与分析复习题目及答案详解分治法1、二分搜索算法是利用（分治策略）实现的算法。

9.实现循环赛日程表利用的算法是（分治策略）27、Straen矩阵乘法是利用（分治策略）实现的算法。

34．实现合并排序利用的算法是（分治策略）。

实现大整数的乘法是利用的算法（分治策略）。

17．实现棋盘覆盖算法利用的算法是（分治法）。

29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。

不可以使用分治法求解的是（0/1背包问题）。

动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。

下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。

（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。

矩阵连乘问题的算法可由（动态规划算法B）设计实现。

实现最大子段和利用的算法是（动态规划法）。

贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。

回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。

剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。

分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。

分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是(分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除(栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

算法练习题及答案

算法练习题及答案

算法练习题及答案算法练习题及答案随着计算机科学的发展，算法成为了计算机科学的核心内容之一。

算法是一种解决问题的方法和步骤，它可以将复杂的问题简化为一系列简单的操作。

为了提高算法设计和分析的能力，许多学生和程序员经常进行算法练习。

在这篇文章中，我将给出一些常见的算法练习题及其答案，希望能对读者有所帮助。

1. 反转字符串题目：给定一个字符串，将其反转并返回。

解答：可以使用两个指针，一个指向字符串的开头，一个指向字符串的末尾。

然后交换两个指针指向的字符，然后分别向中间靠拢，直到两个指针相遇。

2. 判断回文数题目：给定一个整数，判断它是否是回文数。

回文数是指正序和倒序读都一样的整数。

解答：可以将整数转换为字符串，然后使用反转字符串的方法判断是否相等。

另一种方法是将整数反转后与原来的整数进行比较。

3. 寻找两个有序数组的中位数题目：给定两个有序数组，找出这两个数组合并后的中位数。

要求时间复杂度为O(log(m+n))。

解答：可以使用二分查找的思想。

首先将两个数组合并成一个有序数组，然后找到中位数的位置。

如果数组长度为奇数，中位数就是中间的元素；如果数组长度为偶数，中位数就是中间两个元素的平均值。

4. 搜索旋转排序数组题目：给定一个按照升序排列的整数数组，经过旋转后的数组，搜索一个给定的目标值。

如果目标值存在于数组中，则返回它的索引，否则返回-1。

解答：可以使用二分查找的思想。

首先找到数组的中间元素，然后判断中间元素与目标值的关系。

如果中间元素等于目标值，直接返回索引；如果中间元素小于目标值，说明目标值在右半部分，继续在右半部分进行二分查找；如果中间元素大于目标值，说明目标值在左半部分，继续在左半部分进行二分查找。

5. 最长公共前缀题目：给定一个字符串数组，找到这些字符串的最长公共前缀。

解答：可以将第一个字符串作为初始的最长公共前缀，然后逐个比较后面的字符串与最长公共前缀的相同部分。

如果相同部分为空，则返回空；如果相同部分不为空，则更新最长公共前缀。

2023高中信息技术学考算法设计操作题(6套含答案)

2023高中信息技术学考算法设计操作题(6套含答案)

2023高中信息技术学考算法设计操作题(6套含答案)第一套：题目：编写一个算法，输入一个正整数，输出它的阶乘。

输入：正整数 n输出：结果为 n 的阶乘示例：- 输入：5- 输出：120答案：def factorial(n):if n == 0:return 1else:return n * factorial(n-1)n = int(input())result = factorial(n)print(result)第二套：题目：编写一个算法，输入一个正整数，输出它的各位数字之和。

输入：正整数 n输出：各位数字之和示例：- 输入：123- 输出：6答案：def sum_of_digits(n):result = 0while n > 0:result += n % 10n = n // 10return resultn = int(input())print(sum_of_digits(n))第三套：题目：编写一个算法，输入一个字符串，输出它的长度。

输入：字符串 s输出：字符串长度示例：- 输入："Hello"- 输出：5答案：s = input()print(len(s))第四套：题目：编写一个算法，输入一个正整数，输出它的倒序。

输入：正整数 n输出：倒序后的整数示例：- 输入：123- 输出：321答案：def reverse(n):result = 0while n > 0:result = result * 10 + n % 10 n = n // 10return resultn = int(input())print(reverse(n))第五套：题目：编写一个算法，输入一个正整数，输出它的素因数分解。

输入：正整数 n输出：素因数分解后的列表示例：- 输入：28- 输出：[2, 2, 7]答案：def prime_factors(n):factors = []while n % 2 == 0:factors.append(2)n = n // 2for i in range(3, int(n**0.5) + 1, 2):while n % i == 0:factors.append(i)n = n // iif n > 2:factors.append(n)return factorsn = int(input())print(prime_factors(n))第六套：题目：编写一个算法，输入一个正整数，输出它的所有正约数。

《算法设计综合实训》题目讲解

《算法设计综合实训》题目讲解

算法设计综合实训题目0．逆序数字（借助栈）编写一个函数，接收一个4位整数值，返回这个数中数字逆序后的结果值。

例如，给定数7631，函数返回1367.输入：第一行一个正整数T（T<=10），表示有T组测试数据; 以下T行，每行一个非负的整数N。

输出：共T行，对于每组输入数据输出一行，即数字逆序后的结果值。

样本输入：3763110185158样本输出：1367810185151．人见人爱A+B这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

输入：输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。

题目保证所有的数据合法。

输出：对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0-59），每个输出占一行，并且所有的部分都可以用32位整数表示。

样本输入：21 2 3 4 5 634 45 56 12 23 34样本输出：5 7 947 9 302．敲七【问题描述】输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【要求】【数据输入】一个整数N。

(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。

【样例输入】20【样例输出】714173．统计同成绩学生人数问题【问题描述】读入N名学生的成绩，将获得某一给定分数的学生人数输出。

【要求】【数据输入】测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。

第3行：给定分数当读到N=0时输入结束。

其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。