习题1
1、在一个地图上有n个地窖(n≤20)，每个地窖中埋有一定数量的地雷，同时，给出地窖之间的联系路径。例如下图给出了一个示例，其中V1，V2，V3，...，V6表示地窖。
[题目要求]
当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖的过程中不允许某人重复经过地窖。当无连接时，挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。 输入：n (表示地窖的个数)
W1 W2 W3......Wn a12.........a1n a23.......a2n ......... a(n-1，n)
表示地窖之间连接路径（其中aij表示地窖i，j之间是否有通路：通aij=1，不通aij=0） 输出：R1-R2-...-Rk (挖地雷的顺序) max （为挖地雷的数量）
2、设有1g，2g，3g，5g，10g，20g的砝码各若干枚（其总重≤1000g），要求：
输入：a1 a2 a3 a4 a5 a6(表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个) 输出：Total=n (n表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况)
3、将整数n分成k份，且每种拆分方案不能为空，任意两种拆分方案不能相同（不考虑顺序）。例如：n＝7，k＝3，下面三种分法被认为是相同的。 1， 1， 5； 1， 5， 1； 5， 1， 1； 问有多少种不同的分法。
输入：n，k (6 4、有一个箱子容量为v（正整数，0≤v≤20000），同时有n个物品（0 要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入：箱子的容量v和物品数n。接下来n行，分别表示这n个物品的体积 输出：箱子剩余空间 5、某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算这套系统最多能拦截多少导弹。 输入：导弹数n和n颗依次飞来的高度(1≤n≤1000) 输出：一套系统最多拦截的导弹数best，并依次列出被拦截导弹的序号 6、今年是国际数学联盟确定的“2000—世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。 在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛活动，你的好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为n的数字串，要求选手使用k个乘号将它分成k+1个部分，找出一种分法，使得这k+1个部分的乘积最大。 同时，为了帮助选手能够理解题意，主持人还举了如下一个例子： 有一个数字串：312，当n=3，k=1时会有两种分法： ⑴3*12=36 ⑵31*2=62 这时，符合题目要求的结果是：31*2=62。现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入：程序的输入共有两行：第一行共有2个自然数n，k（2≤n≤40，1≤k≤6），第二行是一个长度为n的数字串。 输出：结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 7、给出一个长度不超过200的由小写英文字母组成的字母串（约定：该字串以每行20个字母的方式输入，且保证每行一定为20个）。要求将此字母串分成k份（1＜k≤40），且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可以包含this和is，选用this之后就不能包含t）。在给出的一个不超过6个单词的字典中，要求输出最大的单词个数。 输入：全部输入数据放在文本文件input3.dat中，其格式如下： 第一行为一个正整数（0＜n≤5）表示有n组测试数据，每组的第一行有二个正整数：（p，k），其中p表示字串的行数；k表示分为k个部分。 接下来的p行，每行均有20个字符。 再接下来有一个正整数s，表示字典中单词个数。（l≤s≤6） 接下来的s行，每行均有一个单词。 输出：结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。 8、求最大连续子序列的和 输入：n(n≤500)和n个整数； 输出：该序列中最大的连续子序列的和max。 9、2台处理机a和b承担n个作业的任务。设第I个作业交给机器a处理时需要ai时间，交给机器b处理时需要bi时间。由于各作业的特点和机器性能的关系，很可能对于某些I有ai≥bi，而对于某些作业j(j≠i)有aj 10、有F束花由左而右插在V个花瓶内（1≤F≤V≤100）。花与瓶分别用1—F与1—V的整数标识。花要按照花的标识数递增排列，不同的花插在不同的瓶子里产生不同的美学价值（-50到50之间）。求最大的美学价值及其一种摆放方式。 11、有四个圆柱a，b，C，D。n个圆盘按照由小至大的顺序摞在a柱上(如下图)。如何以最少次数将圆盘从a柱移至D柱 移动必须满足三个条件： ⑴能利用a，b，C，D四个圆柱； ⑵一次只能搬动一个圆盘； ⑶小的圆盘只能往大的圆盘上摞； 12、设给定n个变量x1，x2，?，xn，将这些变量依序作底和各层幂，可得出如下图的n重幂： xn?x3x2x1 这里将上述n重幂看作是不确定的，当在其中加入适当的括号后，才能成为一个确定的n重幂。通常将n重幂的理解为上图所示的形状： 不同的加括号方式导致不同的n重幂。例如，当n=4时，x1，x2，x3，x4的全部4重幂有5个。试设计一个算法，对n个变量计算出有多少个不同的n重幂。 13、给定由n个英文单词组成的的一段文章，每个单词的长度（字符个数）依序为l1，l2，?，ln。我们要在一台打印机上将这段文章“漂亮地”打印出来。打印机每行最多可打印m个字符。这时所说的“漂亮”的定义如下。在打印机所打印的每一行中，行首和行尾可不留空格，行中每2个单词之间留一个空格。这 j样如果在一行中打印从单词i到单词j的字符，则按打印规则，应在一行中恰好打印 jkk?i?lk?ik?j?i个字符（包 M?j?i??l括字间空格字符），且不允许将单词打破。多余的空格数为。除文章的最后一行外，希望每行多余的空格数尽可能少。因此，我们以各行（最后一行除外）的多余空格数的立方和达到最小作为“漂亮”的标准。请设计一个“漂亮打印”方案。 14、设a和b是2个字符串。我们要用最少的字符操作，将字符串a转换为字符串b。这里所说的字符操作包括 a.删除一个字符； b.插入一个字符； c.将一个字符改为另一个字符。 将字符串a变换为字符串b所用的最少字符操作数称为字符串a到b的编辑距离，记为δ（a，b）。试设计一个有效算法，对任给的2个字符串a和b，计算出它们的编辑距离δ（a，b）。 15、在一个操场上摆放着一行共n堆石子。现要将石子有序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。请计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 16、在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 17、输入硬币的n种不同面值（各种面值的硬币个数不限）和m，输出找出钱数1‥m元的最少硬币数。 18、寻宝游戏要求参赛者根据“藏宝图”（n*m个数的表格）和不同地点的提示信息（数列），在最短时间内找出埋藏在某处的“宝物”。当前位置与“藏宝点”的距离为数列与表格的接近程度。“接近程度”的定义：假设提示数列为{ai}，那么“藏宝图”中找出与其最接近的数列{bi}(数列项数为len)，这两个数列 的接近程度就是数列与表格的接近程度，其中数列的接近程度D=，D越小表示越接近。除此而外，数列{bi}还有以下限制：用（xi，yi）表示数列{bi}中第i项在表格中的位置，则要求 1?i?len?(ai?bi)2xi?xi?1?yi?yi?1?1(1?i?len)，且同一位置可能在数列中出现多次。 输入：n m(“藏宝图”的规模，2≤n，m≤50)；n*m的“藏宝图”（矩阵元素值小于100）；数列{ai}的项数len（1≤len≤150）；长度为len的数列{ai}（数列的元素值小于100）； 输出：数列与表格的接近程度。 19、某港口有一批尺寸规格相同的箱子，编号为1?n。现在要将其中某些箱子按照如下规则叠放起来 1. ⑴每个箱子上最多只能直接叠放一个箱子； 2. ⑵编号小的箱子不能放在编号大的箱子之上； 3. ⑶每个箱子给出了自身重量和可承受重量，每个箱子之上的所有箱子重量之和不得超过该箱子的可承 受重量； 为了节省堆放场地，希望在满足条件的情况下，叠放的箱子数最多。 输入：箱子数n(1≤n≤500)；以下为n行，其中第i行为箱子i的自身重量和可承受重量； 输出：最多可叠放的箱子数m；按照由上至下（即编号递减）的叠放顺序，给出m个箱子的编号。 20、一个羽毛球队有男女运动员各n人。给定2个n*n矩阵P[1..n，1..n]和Q[1..n，1..n]。其中P[i，j]是男运动员i和女运动员j配对组成混合双打时的竞赛优势；而Q[i，j]是女运动员i和男运动员j配合时的竞赛优势，显然，由于技术的配合和心理状态等各种因素的影响，P[i，j]不一定等于Q[i，j]。设计一个算法，确定男女运动员最佳配对方案，使该方案中各对男女竞赛乘积的总和达到最大。 21、多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符号“+”或“*”。所有边依次用整数从1到n编号。游戏第一步，将一条边删除。随后n-1步按以下方式操作。 ① 选择一条边E以及由E连接着的2个V1和V2； ② 用一个新顶点取代边E以及由E连接着的2个顶点V1和V2。将标点V1和V2的整数值通过边E 上的运算得到的结果赋予新顶点。 最后，所有边都被删除，游戏的得分就是所剩顶点上的整数值。 编程任务： 对于给定的多边形，编程计算出最高得分，并且列出所有得到这个最高得分首次被删除的边的编号。 输入：由文件POLYGOn.In文件输入数据。文件的第一行是所给多边形的顶点数n；第2行包含所有边1到边n所对应的运算符，以及与相邻2边关联的顶点数值（1号边与2号边之间是1号顶点的数值，2号边与3号边之间是2号顶点的数值，?，依次类推，最后的一个数值对应于与n号边和1号边相关联的顶点）。运算符与数值之间由一个空格分隔。字母t代表运算符“+”，字母x代表符“*”。文件名由键盘输入。约束条件：3≤矩形数≤50。无论删除顺序如何，所有顶点的数值均在[-32768，32767]范围内。 输出：程序运行结束时，将计算结果写入文件POLYGOn.OUT中。文件的第1行是计算出的最高得分。第2行是所有得到这个最高得分首次被删除的边按升序排列的编号。