算法分析实践环节习题集.doc

信息工程学院算法分析实践环节习题集（2011年）序号项目名称任务描述设计要求指导教师人数112二进制位串的压缩树算法设计与实现第一步输入：二进制位串，例如：0000010000001111输出：如下图1所示的二进制压缩树第二步输入：二进制压缩树，如图1输出：二进制路径码数组 如图2第三步：输入两个路径码数组， 如图2，图3输出：相与后的路径码数组，如图4两个路径码数组相与就是求子码的过程，对于两个路径码x,y， 如果x是y的前缀，那么y是x的子码，比如：0是0101的前缀，因此0101是0的子码。所以图2和图3相与后的路径码数组是图4.图1图2图3图4用Java语言，或者C语言，推荐用Java语言。要求：读文件，读取文件中所有的项，得到二进制串，然后构造每个项的二进制串的压缩树，并得到每个项的路径码。 刘全中134简单数据集跳跃显露模式挖掘算法设计与实现跳跃显露模式是指在样本的一个类别上发生次数为0，在另外一个类别上发生次数大于等于一个支持度计数阈值的模式。例如下表中数据，假定。那么在类别为上的跳跃显露模式有：，利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。刘全中15简单数据集频繁关闭模式挖掘算法设计与实现频繁模式是指在数据集中，出现的次数大于等于给定阈值的项集。如下表所示的数据集，假设。频繁模式：，, ., 等对于模式，如果不存在模式,. 使得包含的事物和包含的事物相同。那么就是一个关闭频繁模式。例如，假设，就是一个关闭频繁模式。利用Java语言或者C语言实现给定数据集、给定支持度阈值的所有的频繁关闭刘全中16利用分治思想设计循环赛日程表假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：(1). 每个选手必须与其他n-1个选手各赛一次(2). 每个选手一天只能赛一次(3). 循环赛一共进行n-1天利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。刘全中17工作分配问题设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。刘全中18无分隔符字典问题设 是n个互不相同的符号组成的符号集。是中字符组成的长度为k的字符串全体。是的1个无分隔符字典是指对任意和，则无分隔符字典问题要求对给定的n和以及正整数k,编程计算的最大无分隔符字典。 设计一个算法，对于给定的正整数n和k,编程计算的最大无分隔符字典数据输入：有文件input.txt给出输入数据。文件第1行有2个正整数n和k结果输出：将计算出的的最大无分隔符字典的元素个数输出到文件output.txt.输入文件示例：2 2输出：2.刘全中1910放行路线选择算法的设计与实现设有n个城市(或者景点),今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最小的路径)输入：各城市间的旅费表有输入文件提供输出：旅费最少的一条路径及总费用。利用Java, C实现所要求的算法。时间充分，设计一个图形化界面，读入文件后把N个城市的带权(花费)显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上刘全中111N色方柱问题设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染色。要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜色。试设计一个回溯算法，计算出n个立方体的一种满足要求的叠置方案。编程任务：对于给定的n个立方体以及每个立方体各面的颜色，计算出n个立方体的一种叠置方案，使得柱体的4个侧面的每一侧均有n中不同的颜色。数据输入：由文件input.txt给出输入数据。第1行有1个正整数n，0n27,表示给定的立方体个数和颜色均为n。第2行是n个大写英文字母组成的字符串。该字符串的第k个字符代表第k种颜色。接下来的n行中，每行有6个数，表示立方体各面的颜色。立方体各面的编号如图1所示：TLFRB D 502134 图1图1中F表示前面，B表示背面，L表示左面，R表示右面，T表示顶面，D表示底面。相应地，2表示前面，3表示背面，0表示侧面，1表示右面，5表示顶面，4表示底面。例如，在示例输出文件中，第3行的6个数0, 2 , 1, 3, 0, 0分别表示第1个立方体的左面的颜色为R，右面的颜色为，前面的颜色为，背面的颜色为，底面的颜色为，顶面的颜色为结果输出：将计算的个立方体的一种可行的叠置方案输出到文件output.txt。每行6个字符，表示立方体个面的颜色。如果不存在所要求的叠置方案，输出“No Solution”输入文件示例 输出文件示例Input.txt output.txt4 RBGYRRRGBY YRBGRG0 2 1 3 0 0 BGRBGY3 0 2 1 0 1 GYYRBB2 1 0 2 1 31 3 3 0 2 2刘全中112N个自然数中r个数组合求解设计与实现找出n个自然数(1,2,3,n)中r个数的组合。输入n,和r,输出所有的组合数。n个数中r的组合，其中每r个数中，数不能相同。另外，任何两组组合的数，所包含的数也不应相同。例如：当n=5,r=3时，所有组合为：5 4 3 ； 5 4 2 ； 5 4 15 3 2 ； 4 3 2 ； 4 2 13 2 1； total=10；分别用穷举搜索法、递归法、回溯法实现所要求的功能，并比较三者的时间复杂度刘全中113猜比赛名次问题的求解算法设计与实现五个学生A、B、C、D、E 参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如与，或者与等）。乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？利用穷举法，设计算法对以上问题求解。 利用Java或者C 对所描述任务进行求解。刘全中114计算合数问题的求解一个整数n（n=100）可以有多种划分，使其分划得一列整数之和为n.例如：输入:n=4输出文件result.out，格式内容为：43 12 22 1 11 1 1 1要求输入一个整数n，把划分序列输出到文件中。刘全中115查找数字对问题求解算法的设计与实现输入N（2=N=100）个数字(在0到9之间),然后统计出这组数中相邻两数字组成的链环数字对出现的次数。输入:N=200 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9输出：(7,8)=2 （8,7）=3指(7,8)、(8,7)数字对出现次数分别是2次、3次设计一个GUI界面，能够接受用户的输入，也能够从文件中读取数据。在界面上输出所要求的结果，并把结果存储到文件中刘全中116无向图最小代价生成树算法的实现（1） 掌握最小代价生成树算法思想。（kruskal算法），并利用贪心的思想改进该算法，降低其时间复杂性。（2） 设计一个有10个顶点的无向图，并用随机数产生其各边的代价。（3） 利用最小代价生成树算法思想，对其所产生的无向图，找出其最小代价生成树。（1） 设计一个界面，显示产生的无向图。（2） 实现最小代价生成树算法。（3） 在输出界面，显示结果。王湘桃117分治法在一个划分成网络的操场上，n名士兵散乱地站在网格点上。网格点由整数坐标（x,y）表示。士兵们可以沿网格边上下左右移动一步，但在同一时刻任意网格点上只能有一名士兵。按照军官的命令，士兵们要整齐的列成一个纵队，及排列成（x,y）,(x+1，y)（x+n-1,y）。如何选择x和y的值才能使士兵们以最小的总移动步数排成一列。设计一个分治算法，输出方案。王湘桃118有向图单源最短路径分支限界算法实现（1）掌握单源最短路径分支限界算法思想。（2）设计一个至少有10个顶点的有向图，并用随机数产生其各边的权值。（3）利用单源最短路径分支限界算法思想，对其所产生的有向图，找出从某源点出发，到其它各顶点的最短路。（1）设计一个界面，显示产生的有向图。（2）实现单源最短路径分支限界算法。（3）在输出界面，显示结果（在有向图中，标记出从源到各顶点的路径）。王湘桃119回溯算法实现部落卫队问题。原始部落中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌，部落酋长为了组织一只保卫部落的队伍，希望从部落的居民中选出最多居民入伍，并保证队伍中任何两个人都不是仇敌。给定该部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。（1） 实现回溯法的设计思想。王湘桃120装载问题的分支限界算法实现（1）有一批集装箱共n个，要装上两艘载重量分别为c1和c2的轮船，其中，集装箱i 的重量Wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）用文件导入集装箱的重量，和两艘船的载重量。（2）实现分支限界算法的设计思想。（3）设计一个输出界面，输出装载方案。王湘桃121最大团问题的回溯算法实现（1） 给定无向图G=(V,E)。如果，且对任意有，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）设计一个界面，显示产生的无向图。（至少有5个顶点）（2）实现回溯法的设计思想。（3）在输出界面，显示结果。王湘桃122最大团问题的分支限界算法实现（1）给定无向图G=(V,E)。如果，且对任意有，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）设计一个界面，显示产生的无向图。（至少有5个顶点）（2）实现分支限界算法的设计思想。（3）在输出界面，显示结果。王湘桃123最佳调度问题的回溯算法实现（1） 有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）用文件导入每个任务所需要的时间Ti。（至少10个任务）（2）实现回溯法（3）设计一个输出界面，输出调度方案。王湘桃124最佳调度问题的分支限界算法实现（1）有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）用文件导入每个任务所需要的时间Ti。（至少10个任务）（2）实现分支限界算法的设计思想。（3）设计一个输出界面，输出调度方案。王湘桃125N后问题的回溯法算法实现（1） 在格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在同一行或同一列或同一斜线上。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）设计一个棋盘界面。（至少有10个皇后）（2）实现回溯算法的设计思想。（3）在界面上，显示所有方案。王湘桃126N后问题的优先队列分支限界算法实现（1）在格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在同一行或同一列或同一斜线上。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）设计一个棋盘界面。（至少有10个皇后）（2）实现分支限界算法的设计思想。（3）在界面上，显示所有方案。王湘桃127N后问题的拉斯维加斯算法实现（1）在格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在同一行或同一列或同一斜线上。（2）使用拉斯维加斯算法的思想，设计一个解决该问题的算法。（1）设计一个棋盘界面。（至少有10个皇后）（2）实现拉斯维加斯算法的设计思想。（3）在界面上，显示结果。王湘桃128套汇问题的贪心算法实现（1） 利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如：1美元=0.7英镑，1英镑=9.5法郎，1法郎=0.16美元。1美元=0.7*9.5*0.16=1.064美元（2） 利用贪心算法的设计思想，设计一个解决该问题的算法。（3） 说明算法能产生最优解。（1）用文件导入每种货币的汇兑率。（2）实现贪心算法的设计思想。（3）设计一个输出界面，输出汇兑方案。王湘桃129设计一个寻找众数的算法并实现（1） 众数：在一个由元素组成的表中，出现次数最多的元素为众数。（2） 设计一个至少100个元素组成的表，用随机函数产生（19）之间的数作为表中的元素值。（3） 设计一个找众数的算法，并完成代码。（1）设计一个至少100个元素组成的表，用随机函数产生（19）之间的数作为表中的元素值。存入文件中。（2）设计一个输出界面，输出计算结果。王湘桃130最优购货方案设计与实现（1） 每种商品都有标价，当单独销售时，按单价出售，如果和其他商品组合促销，则每种物品都降价销售。（2） 设计一个算法，为顾客提供一种省钱的购买方案并完成代码。算法能产生最优解。（1）设计一个界面。（输入需要购买的货物及数量）（2）实现设计的算法思想。（先对5种商品进行处理，需要设计各种组合促销价。然后扩展到n种货物）（3）在界面上，显示结果。王湘桃131网球循环赛日程表设有n个运动员要进行网球循环赛。设计比赛日程表：（1） 每个选手必须与其他n-1个选手赛一次；（2） 每个选手一天只能赛一次；（3） 当n是偶数时，循环赛进行n-1天；当n是奇数时，循环赛进行n天；（1） 要求掌握分治法或者多边形方法；（2） 设计一个界面，显示产生的日程表；（3） 编程语言不限；李梅132泊松分酒描述:给你两个容量分别为A升和B升的壶。你可以进行如下操作：1.装满壶A或壶B。2.将壶A或壶B里的酒全部倒干净。3.将壶A里的酒倒入壶B，直到壶B被装满或壶A被倒空为止。或将壶B里的酒倒入壶A，直到壶A被装满或壶B被倒空为止。编写一个程序，算出得到C升酒需要的最少的操作次数。输入:输入仅一行，三个整数A、B、C(用空格隔开)。这三个整数都在1到100 之间，而且C=max(A,B)。输出:如果可以得到容量为C升的酒则输出最少的操作次数，如果不能则输出”impossible”。输入样例3 5 4输出样例6提示:类似于布线问题，这里每次有六种走法。 编程语言不限；李梅133段合并排序算法在合并排序算法的分割步骤中，将数组划分为个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将得到的个排好序的子数组合并成所要求的排好序的数组。（1） 要求掌握分治法；（2） 设计一个界面，显示计算结果；（3） 编程语言不限；李梅134坦克大战描述：我们小时候大都玩过坦克大战游戏，而且现在仍有很多人在玩。现在我们讨论这个游戏的简化版。题目给出一个由空地、河流、钢墙、砖墙组成的地图。你的任务就是在没有敌人干扰你的情况下尽快地拿到奖励(看附录图7)。你的坦克不能穿过河流或墙，但是可以通过射击摧毁砖墙。当你轰击砖墙时，它就会变成空地。但是你如果攻击钢墙，不会对它造成任何损害。在你所花费的每一分钟里，你可以选择往四邻域的空地移动一步，你也可以选择不移动，往四个方向之一开一炮，炮弹将会朝一个方向一直飞去直到轰击到墙为止。如果炮弹打到砖墙，砖墙就会消失，变成空地。现在我们给出地图，以及你的坦克的位置和目标位置，请你计算最短需要多长时间(以分钟计)才能到达目标位置？输入：输入的第一行包含两个整数M和N(2=M,N=300)代表地图的规模。第2行到第M+1行为N个大写字母组成的字符串，这些字母为Y(你的坦克的位置)、T(目标位置)、S(钢墙)、B(砖墙)、R(河流)、E(空地)之一。Y和E仅出现一次。输出：输出仅一行，如果你可以到达目标位置，输出最短时间，如果不可到达，输出-1。输入样例：3 4YBEBEERESSTE输出样例8（1） 编程语言不限；李梅135集合划分问题给定正整数n，计算出n个元素的集合1,2，3,n可以划分为多少个不同的非空子集。（1） 要求掌握分治法；（2） 设计一个界面，显示计算结果；（3） 编程语言不限；李梅136漂亮打印给定由n个英文单词组成的一段文章，每个单词的长度（字符个数）依序为，。要在一台打印机上将这段文章“漂亮”地打印出来。打印机每行最多可打印M个字符。这里所说的“漂亮”的定义如下：在打印机所打印的每一行中，行首和行尾可不留空格；行中每个单词之间留一个空格；如果在一行中打印从单词i到单词j的字符，则按打印规则，应在一行中恰好打印个字符（包括字间空格字符），且不允许将单词打破；多余的空格数为；除文章的最后一行外，希望每行多余的空格数尽可能少。因此，以各行（最后一行除外）的多余空格数的立方和达到最小最为“漂亮”的标准。用动态规划算法设计一个“漂亮”打印方案。（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。李梅137最长单调递增子序列比较和分析，设计一个较优算法找出n个数组成的序列的最长单调递增子序列（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。李梅138最短行驶路线给定一个的矩形网格，设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在若干网格点处设置了障碍，表示该网格点不可到达。试设计一个算法，求出汽车从起点S出发到达终点T的一条行驶路程最短的路线（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。李梅139最优旅行路线给定一张航空图，图中的定点表示城市，边表示城市间的直通航线。设计一个算法，计算出一条满足下述约束条件且含城市最多的旅行路线。（1） 从最西端的城市出发，单方向由西到东到达最东端的城市。然后，再单方向由东向西飞回起点（可途径若干城市）（2） 出起点城市外，每个城市最多只经过一次。（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。李梅140租用游艇问题长江游艇俱乐部在长江上设置了n个游艇出租站1,2，,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i,j），。设计一个算法，计算出从游艇出租站1到游艇出租站n所需要的最少租金。（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。李梅141抓住那头牛描述：农场主约翰的牛跑了，他被告知了牛的具体位置，他想要尽快抓住它。他现在在数轴上一点N(0=N=10000),他的牛在点K(0=K=10000)。约翰有两种移动方式：走路和远程托运。走路：约翰可以在一分钟内从点X移动到点X-1或X+1。远程托运：约翰可以在一分钟内从点X移动到点2X。假定这头牛不知道它的主人在抓它，丝毫不移动，求约翰最短用多少时间抓到它。假定约翰的活动范围在010000之间。输入：输入仅一行：两个用空格隔开的整数，N和K。输出：输出仅一行：约翰抓住这头牛所需的最少时间，以分钟计。输入样例：5 17输出样例：4提示样例中约翰抓住这头牛花费时间最少的路径为5-10-9-18-17, 花费了4分钟。李梅142收集样本问题机器人Rob在一个有个方格的方形区域F中收集样本，（i，j）方格中样本的价值为v（i，j）。Rob从方形区域F的左上角A点出发，向下或向右行走，直到右下角的B点，在走过的路上，收集方格中的样本。Rob从A点到B点共走2次，试找出Rob的2条行走路径，使其取得的样本总价值最大。（1） 给定方形区域F中的样本分布（2） 给出图形化收集样本路径李梅143数列极差问题在黑板上写了N个整数组成的一个数列，进行如下操作：没一次擦去其中2个数，设为a和b，然后在数列中加入一个数，如此下去直至黑板上只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数为max，最小的数记为min，则该数列的极差M定义为M=max-min（1）设计一个界面，显示运算过程（至少有5个顶点）（2）实现贪心算法的设计思想。（3）在输出界面，显示结果。李梅144棋盘分割描述将一个*的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差，其中平均值，xi为第i块矩形棋盘的总分。 请编程对给出的棋盘及n，求出均方差O的最小值。输入：第1行为一个整数n(1 n 15)。 第2行至第9行每行为8个小于100等于的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。输出：仅一个数，为均方差O（四舍五入精确到小数点后三位）。输入样例31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3输出样例1.633提示求均方差的最小值即是求方差的最小值，方差为由于均是不变量，所以求方差的最小值就是求分割后各块得分平方和的最小值。李梅145边界算法假设文本中包括的特征：outlook sunny, overcast, rainy/ 晴天、多云、下雨temperature hot, mild, cool / 热、温和的、冷humidity high, normal / high表示潮湿、normal表示正常windy True, False / True表示有风、False表示无风play yes, no /表示样本的类别： yes表示打网球,，no表示不打网球假设有14个样本如下：1 , Sunny , Hot , High , False, No 2 , Sunny , Hot , High , True , No 3 , Overcast , Hot , High , False, Yes 4 , Rain , Mild , High , False, Yes 5 , Rain , Cool , Normal , False, Yes 6 , Rain , Cool , Normal , True , No 7 , Overcast , Cool , Normal , True , Yes 8 , Sunny , Mild , High , False, No 9 , Sunny , Cool , Normal , False, Yes 10 , Rain , Mild , Normal , False, Yes 11 , Sunny , Mild , Normal , True , Yes 12 , Overcast , Mild , High , True , Yes 13 , Overcast , Hot , Normal , False, Yes 14 , Rain , Mild , High , True , No对上述14个样本进行训练学习，对测试样本进行分类，如对测试样本Tsunny, mild, high, True，判定其类别。方法:1: 获取每一个训练实例和测试集T的交集，即：和。2：从该选出最大的项集形成正例的最大边界，记作，同理从中选出最大的项集形成负例的最大边界，记作。3：计算：和李梅146通信系统描述最近我们要构建一个通信系统。这个系统包含若干个设备，对于每个设备，我们都可以从不同的商家购买。从不同商家购买的同种设备，在最大带宽和价格上都有所区别。整个系统的带宽B是指它包含的所有设备的最大带宽的最小值。整个系统的代价P是指，它包含的所有设备的价格之和。我们的目标是确定一个购买方案，使得整个系统的性价比B/P最高。输入输入包含多行。第1行为n(1=n=100)表示系统包含的设备数，接下来的n行格式是这样的，第i+1(1=i=n)行的第1个数为mi(1=mi=100)，表示提供第i种设备的商家数，接下来在这一行内便是mi对个正整数，分别表示对应商家提供的此种商品的最大带宽和价格。输出输出为一行，是一个3位浮点小数B/P即最优购买方案下系统的最优性价比。输入样例33 100 25 150 35 80 252 120 80 155 402 100 100 120 110输出样例0.649。张阳147机器人布线布线区域分成的方格阵列。要求确定连接方格s到方格d的最短布线方案。布线的时候，电路只能沿着直线或者直角布线，有障碍的方格做了封锁标记（X），其他线路不允许穿过被封锁的方格。(1)用文件保存布线区域，用1、0分别表示某个格子是否有障碍；S,D表示起点和终点；(2)给出最短的布线路径长度； (3)用文件保存布线路径，用*表示布线的方格；主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳148字符串距离开发计算两个字符串间的编辑距离，LCS距离和N-gram距离的函数。（1）编辑距离字符串a和b的编辑距离ED(i,j)表示把字符串a转换成b所需要的最少操作次数，这些操作可以是：插入一个字符，删除一个字符，替换一个字符。显然，ED(i,j)越小，a，b越相似。ED(i,j)可按下列公式计算：（2）LCS相似度字符串a和b的LCS(Longest Common Subsequence)相似度是a和b间的最大相同子串的长度。显然LCS(i,j)越大，a，b越相似。a，b的LCS相似度定义如下：（3）N-gram相似度设Ngram(a) 是字符串a中长度为N的子串的集合。两个字符串a,b的N-gram相似度NG(a,b)定义如下：NG(a,b)越大，字符串a，b越相似。张阳149马路边的树某城市，马路边上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，L，都种有一棵树。马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。输入输入的第一行有两个整数L（1 = L = 10000）和 M（1 = M = 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。输出输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。输入样例500 3150 300100 200470 471输出样例298张阳150切割电缆问题描述仓库里有N段的电缆，现在需要数目为K且长度相同电缆,如何切割这已有的N段电缆，才能得到K段长度相同的电缆且电缆的长度最长。输入输入第一行包含两个整数，N和K。N(1=N=10000)代表仓库中已有的电缆数目,K(1=K=10000)代表需要的电缆数目。接下来的N行对应于，仓库中已有的每一段的电缆长度(单位为米，包含两位小数)。电缆长度最短为1米最长为100千米。输出输出为在保证K段电缆的前提下，切割电缆的最大长度(保留两位小数)。输入样例4 118.027.434.575.39输出样例2.00张阳151推箱子推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个55的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.同时，房间里头还有若干障碍物（用阴影部分表示）。现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.(1)从文件中读出房间布局；(2)计算出推箱子的最小格数；主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳152跳马在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。（1）输入：每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。（2）输出：对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。（3）输入样例： 1 1 2 1 输出样例：3输入样例： 1 5 5 1 输出样例：4主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳153俄罗斯方块龙哥小时候最爱的游戏就是俄罗斯方块了,当年他可是个高手,每次游戏他都会选择最快的速度,以至于根本来不及将方块转向而仅仅能够进行左右移动.为了能够坚持更久,必须尽可能地使落下来方块与底下已有方块上表面完全贴合.在熟悉掌握程序设计后龙哥想要用程序来模拟小时候玩俄罗斯方块的过程,下面请你来帮龙哥参谋一下吧:-)（1）输入包括两个部分：1、落下来方块的矩阵(第一行两个小于5的整数a、b由空格隔开,从下一行开始是一个a行b列的矩阵,1表示方块,0表示空)2、底下已有方块的矩阵(第一行两个小于10的整数c、d由空格隔开,从下一行开始是一个c行d列的矩阵,1表示方块,0表示空.输入底下已有方块矩阵时需确保不存在朝下的表面)（2）输出：根据落下来方块和底下已有方块的形状,若落下来方块的下表面与底下已有方块的上表面可能完全贴合则输出一行“YES”否则输出一行“NO”Sample Input2 31110103 80010000010100011111101113 21110102 81100111011011111Sample OutputYESNO主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳154棋盘问题（OJ1255)在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。输入：每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n = 8 , k = n 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。输出：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C231）。输入样例：2 1#.#4 4.#.#.#.#.输出样例：21主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳155六数码问题现有一两行三列的表格如下：A B CD E F把1、2、3、4、5、6六个数字分别填入A、B、C、D、E、F格子中，每个格子一个数字且各不相同。每种不同的填法称为一种布局。如下：1 3 52 4 6布局12 5 64 3 1布局2定义变换如下：把A格中的数字放入B格，把B格中的数字放入E格，把E格中的数字放入D格，把D格中的数字放入A格。定义变换如下：把B格中的数字放入C格，把C格中的数字放入F格，把F格中的数字放入E格，把E格中的数字放入B格。问：对于给定的布局，可否通过有限次的变换和变换变成下面的目标布局：1 2 34 5 6输入：本题有多个测例，第一行为输入测例的个数n，下面是n行测例，每个测例的输入是1到6这六个数字的一个排列，空格隔开，表示初始布局ABCDEF格中依次填入的数字。输出：每个输出占一行。输出转换到目标格局需要变换的最少次数。（若不能转换则输出-1）输入样例：22 5 3 1 4 62 3 6 1 5 4输出样例：12注意不能转换到目标格局的情况应输出-1；输出格式为：printf(“%dn”,min);56求图像的周长（OJ1145）给一个用 . 和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。输入：首先给出m、n、x、y四个正整数，下面给出mn的图形，x、y表示点击的位置，全0表示结束。输出：点击的图形的周长。输入样例：2 2 2 2 XX XX 6 4 2 3 .XXX .XXX .XXX .X .X. X. 0 0 0 0输出样例：8 18主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳157算24每局4个整数，运用四则运算（可以加括号），但为了降低程序设计的难度，除法的结果只保留整数部分，即5/2=2。给出计算出24的方法。输入：本题包含多个测例。数据的第一行有一个整数N（0从第二行开始的N行，各包含4个不大于15的以空格分隔的非零整数。输出：对于每个测例，如果可以计算得到24，则输出“Yes”，否则输出“No”。每个输出占一行。输入样例：22 2 3 32 4 9 10输出样例：Yes Yes主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳158农场灌溉问题（OJ1144)一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。输入：给出若干由字母表示的最大不超过5050具体由(m，n)表示，的农场图输出：编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。输入样例：2 2 DK HF 3 3 ADC FJK IHE -1 -1输出样例：2 3主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳159城市之间（OJ1129)Vela在玩游戏时遇到麻烦了，需要你帮忙：这个游戏有M个城市，有的城市有传送点，可以直接到达另外一些城市，如a23表示可以从城市2直接到达3。无法直接到达的城市，有的可以通过某些城市中转到达。Vela在城市X，她想知道是否可以到达某城市Z。输入：此题第一行输入N表示城镇数目(N为小于10的正整数)；从第二行开始输入一个N*N的矩阵，若amk=1(0=m,kn),就可以从城市m直接到达k，否则不可以直接到达。第N+2行输入两个数字P,Q。输出：如果可以从P到达Q，输出1，否则输出0。输入样例：31 1 00 1 10 0 10 2输出样例：1提示：0不能直接到达2，但可以先到达1，再从1到达2。主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳160算12（OJ1199）给定三个数，问你使用加减乘除能否得到12，要求三个数的顺序可以改变，计算的中间结果必须为整数。输入：输入三个整数，均大于0，小于1000。输出：输出为一个整数，当可以得到12时输出1，否则输出0。输入样例：2 2 3输出样例：1提示：输出格式：printf(%dn,1);主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；张阳161易阵游戏单行列规则两子交换算法设计易阵游戏单行列循环移位规则：某行（列）向左（上）或向右（下）整体移位，移出的棋子回到该行的另一端，如图1。在这个规则下如何交换2个棋子（包括相邻、同行相间、不同行列相间等情况），交换后其他棋子仍在原位。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 武苏里162易阵单行列规则排序算法设计（逐位移位）在易阵单行列循环移位规则下，如何以较少的步数实现1个初始的杂乱的易阵排序？方案很多，逐位移位方案就是先将1号棋子以最少的步数移位到1号棋子位，再将2号棋子移到2号棋子位，。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 武苏里163易阵单行列规则排序算法设计(兼顾2子的逐位移位)在2号命题的解决方案中，移动1号棋子的过程中能够兼顾2号棋子，移动2号棋子的过程中能够兼顾3号棋子，这样会减少总的步数。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 武苏里164易阵单行列规则排序算法设计（逐位交换）对2号命题，逐位交换方案就是是先将1号棋子与1号棋子位的棋子进行2子交换，再将2号棋子与2号棋子位的棋子交换，。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 武苏里165易阵单行列规则排序算法设计（逐位替换）对2号命题，逐位替换方案就是进行多次扫描，每次扫描时比较右面和下面棋子的序号，若小则进行交换。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 武苏里166易阵游戏双行列规则两子交换算法设计易阵游戏双行列循环移位规则是选择2行（列），同时同向循环移位，移出的2个棋子回到另一端时，可以换位，也可不换位。在这个规则下如何交换2个棋子（包括相邻、同行相间、不同行列相间等情况），交换后其他棋子仍在原位。易阵游戏参见附录图1。1