算法课程设计题目-最终

每一个题目要求至少用两种方法，如蛮力法和算法策略方法解决。 题目：

1. 果园篱笆

某大学ACM集训队，不久前向学校申请了一块空地，成为自己的果园。全体队员兴高采烈的策划方案，种植了大批果树，有梨树、桃树、香蕉……。后来，发现有些坏蛋，他们暗地里偷摘果园的果子，被ACM集训队队员发现了。因此，大家商量解决办法，有人提出：修筑一圈篱笆，把果园围起来，但是由于我们的经费有限，必须尽量节省资金，所以，我们要找出一种最合理的方案。由于每道篱笆，无论长度多长，都是同等价钱。所以，大家希望设计出来的修筑一圈篱笆的方案所花费的资金最少。有人已经做了准备工序哦，统计了果园里果树的位置，每棵果树分别用二维坐标来表示，进行定位。现在，他们要求根据所有的果树的位置，找出一个n边形的最小篱笆，使得所有果树都包围在篱笆内部，或者在篱笆边沿上。

本题的实质：凸包问题。请使用蛮力法和分治法求解该问题。 2. 利用分治法求解空中飞行管理问题。

随着空中各种飞机数量的增加，飞行安全控制变得尤为重要，要想提高空中飞行的安全系数，其中一个亟需解决的问题就是预先知道空中哪两架飞机之间具有最大碰撞危险。如果知道了这两架具有最大碰撞危险的飞机,我们就预先通知飞行员进行相应的安全飞行，以避免碰撞。从穷举法的角度很容易解决这个问题，但是效率太低，时间复杂度是O(n2)，不符合实际需要，利用分治法分而制之的思想，降低问题复杂度,通过建模求解，把时间复杂度降到O(nlogn)，可以较好地解决实际问题。1分治法分治法基本思想：任何一个用计算机求解的问题时间复杂度都与其规模N有关。

求解该问题，至少使用蛮力法和分治法求解，并比较时间复杂性。

3. 问题描述：

键盘输入一个高精度的正整数n(n<10位)，去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数，寻求一种方案，使得新的正整数最小。 问题分析

1） 贪心法求解：删k个数符的全局最优解，包含了删除1个数符的子问题的最优解。 2） 以字符串形式输入s，使用尽可能逼近目标的贪心法来逐一删去其中的k个数符，

每一步总是选择一个能使剩下的数最小的数符删去。

4. 问题描述：在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。对于给定的数列，编程计算出极差M。

解题提示：当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。

下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论：假设经（Ｎ－3）次变换后得到３个数：a,b,max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为 ， ，则有： ＝（ａ×ｂ＋１）×max＇＋１， ＝（ａ×max＇＋１）×ｂ+１ 所以 － ＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ

≥ｂ）且ｍ不为（Ｎ－２）次变换后的最大值，即ｍ＜max＇则此时所求得的最大值为： ＝（ａ×ｂ+１）×ｍ+１ 此时 － ＝（１+ａｂ）（max＇－ｍ）＞０ 所以此时不为最优解。 所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的性质2，最有子结构性质），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心策略性质1，贪心选择性质），因此此题可用贪心策略求解。讨论完毕。

在求ｍｉｎ时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。 5. 最优合并问题

问题的提出

给定k个排好序的序列S1，S2?，Sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。 原理分析

这个程序比较适合用堆，最优用最小堆，最差用最大堆； 以最优合并为例：

（1）使用各序列的长度建堆；

（2）两个最小的元素出堆，计算这两序列合并需要的比较次数，该次数入堆； （3）重复（2），直到堆只剩下一个元素； 最后剩下的元素即为题目的解。

6. 在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标面局（目标状态），找到一种移动方法，实现从初始布局到目标布局的转变。 解题提示：

状态表示：显然用二维数组来表示布局比较直观，S（i，j）表示第i行第j列格子上放的棋子数字。空格则用0来表示。

移动规则：根据题意空格周围的棋子可以向空格移动。为便于解决问题，显然从另一个角度来看，“空格周围的棋子可以向空格移动”相当于“空格向四周移动”，这样就把四枚棋子的移动转化为一个空格的移动，从而便于问题的处理。设空格位置在（i0，j0），则根据题意有四条移动规则：

（1）空格向上移动。If i0-1>=1 then s(i0,j0)：=s(i0-1,j0); s(i0-1,j0)：=0 （2）空格向下移动。If i0+1<=3 then s(i0,j0)：=s(i0+1,j0); s(i0+1,j0)：=0 （3）空格向左移动。If j0-1>=1 then s(i0,j0)：=s(i0,j0-1); s(i0,j0-1)：=0 （4）空格向右移动。If j0+1<=3 then s(i0,j0)：=s(i0-1,j0); s(i0,j0+1)：=0 搜索策略：

（1）把初始状态作为当前状态；

（2）从当前状态出发，运用四条移动规则，产生新的状态； （3）判断新的状态是否达到目标状态，如果是，转（5）；

（4）把新的状态记录下来，取出下一个中间状态作为当前状态，返回（2）； （5）输出从初始状态到目标状态的路径，结束。

如果初始状态和目标状态如图1所示。按上述策略，可以得到如图2所示的状态搜索图。为了减少搜索节点个数，大家可以自己设计适当的剪枝函数。 7. 商店购物

某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）；一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ；2个花瓶加1朵花是10 ICU不是12 ICU。

编一个程序，计算某个顾客所购商品应付的费用。 要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量， 即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:

1朵花加2个花瓶: 优惠价:10 ICU 2朵花 正常价: 4 ICU 输入数据

用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。 两个文件中都只用整数。

第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。

第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然， 优惠价要低于该组合中商品正常价之总和。

输出数据

在输出文件OUTPUT．TXT中写 一个数字（占一行）， 该数字表示顾客所购商品（输入文件指明所购商品）应付的最低货款。

输入/输出数据举例

┌────────┐ ┌────────────┐┌────────┐ │ INPUT │ │ OFFER．TXT ││ OUTPUＴ．TXT │ ├────────┤ ├────────────┤├────────┤ │ 2 │ │ 2 ││ 14 │ │ ７ ３ ２ │ │ 1 7 3 5 ││ │ │ ８ ２ ５ │ │ 2 7 1 8 2 10 ││ │ └────────┘ └────────────┘└────────┘

简述： 本题竞赛时有一个很长的文件测试数据，用动态规划可较快的出答案。 8. 旅游预算

一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。

旅游预算有如下规则： 若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。

输入格式：

从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况：

第一行为起点到终点的距离（实数）

第二行为三个实数，后跟一个整数，每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量（升），第二个数是每升汽油行驶的公里数，第三个数是在起点加满油箱的费用，第四个数是加油站的数量。（〈=50）。接下去的每行包括两个实数，每个数据之间用

一个空格分隔，其中第一个数是该加油站离起点的距离，第二个数是该加油站每升汽油的价格（元/升）。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。

输出格式：

答案输出到当前目录下的文本文件“route.out”中。 该文件包括两行。第一行为一个实数和一个整数，实数为旅行的最小费用，以元为单位，精确到分，整数表示途中加油的站的N。第二行是N个整数，表示N个加油的站的编号，按升序排列。数据间用一个空格分隔，此外没有多余的空格。

输入输出举例：

输入文件：（route.dat） 输出文件（route.out） 516.3 38.09 1

15.7 22.1 20.87 3 2 125.4 1.259 297.9 1.129 345.2 0.999

9. 胖男孩 【问题描述】

麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。

每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。

当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。

请编写一个程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。

【输入格式】

输入文件中共有三行，每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。 【输出格式】

输出文件中的第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。

你可以相信问题一定有解，但解不一定是唯一的。 【输入输出样例】 输入：

cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukd 输出： cevapiluk