算法分析与设计习题集.doc

序号项目名称任务描述设计要求1C语言词法分析算法设计与实现编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。输入：一段C语言程序输出：每个单词以及每个单词所在行号比如：输入如下一段C程序main() int a,b;输出为：( mian, ”line=1”);( ( , ”line=1“);( ) , ”line=1”）；( , ”line=2” ）;( int, “line=2”)；用Java语言，或者C语言，推荐用Java语言。完成所要有的C语言词法分析器。要求：读文件，或者命令行的形式读取C源程序，输出源程序中每个单词以及每个单词所在行号。要求：开发出图形化界面，读文件，把结果输出到界面上。2行程编码的设计与实现Run-Length Encoding（RLE）行程长度的原理是将一扫描行中的颜色值相同的相邻像素用一个计数值和那些像素的颜色值来代替。例如:aaabccccccddeee，则可用3a1b6c2d3e来代替。对于拥有大面积，相同颜色区域的图像，用RLE压缩方法非常有效。算法输入：图像算法输出：图像行程编码序列利用C语言，或者Java语言，完成算法对图像的行程编码.设计一个GUI界面，能够接受图像，输出图像的形成编码序列3特征权重排序信息增益算法的设计与实现在文本分类领域中，信息增益IG是一种常用的特征排序算法的标准。要求利用信息增益公式计算每个特征的信息增益值，并根据信息增益值从大到小输出。举例如下：假设文本中包括的特征：outlook sunny, overcast, rainy/ 晴天、多云、下雨temperature hot, mild, cool / 热、温和的、冷humidity high, normal / high表示潮湿、normal表示正常windy Strong, weak / TRUE表示有风、FALSE表示无风play yes, no yes表示打网球，no表示不打网球假设有14个样本如下：1 , Sunny , Hot , High , Weak , No 2 , Sunny , Hot , High , Strong , No 3 , Overcast , Hot , High , Weak , Yes 4 , Rain , Mild , High , Weak , Yes 5 , Rain , Cool , Normal , Weak , Yes 6 , Rain , Cool , Normal , Strong , No 7 , Overcast , Cool , Normal , Strong , Yes 8 , Sunny , Mild , High , Weak , No 9 , Sunny , Cool , Normal , Weak , Yes 10 , Rain , Mild , Normal , Weak , Yes 11 , Sunny , Mild , Normal , Strong , Yes 12 , Overcast , Mild , High , Strong , Yes 13 , Overcast , Hot , Normal , Weak , Yes 14 , Rain , Mild , High , Strong , No每一个样本中5个数据值分别表示上面5个特征的取值。显然样本中有两个类，正例(play=yes)有9个，负例(play=no)有5个。用s表示样本(Sample)。那么样本熵的公式Entropy(S) =-(p+)*log(p+)-(p-)*log(p-)其中，p+、p-分别为正例和负例占总记录的比例显然Entrop（S）= -(9/14)*log2(9/14)-(5/14)*log2(5/14)我们以属性Weak为例计算Weak的信息增益：样本中属性Wind中取值为Weak的记录有样本的记录有8条，其中正例6个，负例2个；同样，取值为Strong的记录6个，正例负例各3个。我们可以计算相应的熵为：Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811 Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0 那么wind 的信息增益为：Gain(Wind)=Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)=0.940-(8/14)*0.811-(6/14)*1.0=0.048 同理方法计算出其他属性的信息增益。最后得到5个属性的信息增益如下：Gain(Wind)=0.048 ；Gain(Humidity)=0.151 ； Gain(Outlook)=0.247 ；Gain(Temperature)=0.029那么根据信息增益大小特征排序的顺序为：Outlook ，Humidity， Wind，Temperature例题的详细请参考：/blog/cns!2053CD511E6D5B1E!130.entry利用Java语言实现样本中特征信息增益的计算，然后根据信息增益值从大到小排序。4蛇形矩阵算法的设计与实现生成一个按蛇形方式排列自然数1，2，3，4，5，N2的(1N10)阶方阵。 例如当N等于7时，输出如下;输入：N输出：蛇形方阵实现一个图形化界面，接收用户的输入N，输出蛇形方阵5填自然数问题算法设计与实现设有如图所示的3n2 个球互连，将自然数13n2分别为这些球编号，使如图：开发一个GUI界面，接受数据N,输出所要求的填号图形6利用分治思想设计循环赛日程表假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：(1). 每个选手必须与其他n-1个选手各赛一次(2). 每个选手一天只能赛一次(3). 循环赛一共进行n-1天利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。7字符串之间最小编辑距离算法设计与实现假设A和B是两个字符串。用最小的字符操作将字符串A转换为字符串B。字符串操作包括:（1） 删除一个字符（2） 插入一个字符（3） 将一个字符改为另一个字符利用Java语言做一个图形化界面，界面能够接受两个字符串或者从文件读取字符串，输出他们之间的编辑距离8成等差的素数的求解寻找6个成等差级数且小于160的素数。利用Java或者C实现所要的功能。9最少个数运算符求解算法的设计与实现关于整数的二元运算#定义为(X # Y) = 十进制整数X的各位数字之和 * 十进制整数Y的最大数字+Y的最小数字 例如，(9 # 30)=9*3+0=27.对于给定的十进制X和K,由X和#运算可以组成各种不同的表达式.试设计一个算法，计算由X和#运算组成的值为k的表达式最少需要用多少个#预算。利用Java实现所要求的算法，开发一个GUI界面，接受两个数据X和K, 然后在界面上输出需要#的个数。10放行路线选择算法的设计与实现设有n个城市(或者景点),今从某市出发遍历各城市，使之旅费最少(即找出一条旅费最小的路径)输入：各城市间的旅费表有输入文件提供输出：旅费最少的一条路径及总费用。利用Java, C实现所要求的算法。时间充分，设计一个图形化界面，读入文件后把N个城市的带权(花费)显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上11数组编码和解码问题的求解设计与实现设有一个数组A: array0.N-1;存放的元素为0-N-1(1N=10)之间的整数，且。例如当N=6时，有：A=(4,3,0,5,1,2)。此时，数组A的编码定义如下:A0编码为0；Ai编码为：在A0,A1,Ai-1中比Ai的值小的个数(i=1,2,N-1)上面数组A的编码为：B=(0,0,0,3,1,2)要求如下：（1） 给出数组A, 利用Java或者C 求解A的编码.（2） 给出数组A的编码后，求出A中原数据。如果时间充分，设计GUI界面，实现所要求的功能。12N个自然数中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；分别用穷举搜索法、递归法、回溯法实现所要求的功能，并比较三者的时间复杂度13猜比赛名次问题的求解算法设计与实现五个学生A、B、C、D、E 参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上邻接。例如与，或者与等）。乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了两对学生名次是相邻的。问比赛结果如何？利用穷举法，设计算法对以上问题求解。 利用Java或者C 对所描述任务进行求解。14计算合数问题的求解一个整数n（n=100）可以有多种划分，使其分划得一列整数之和为n.例如：输入:n=4输出文件result.out，格式内容为：43 12 22 1 11 1 1 1要求输入一个整数n，把划分序列输出到文件中。15查找数字对问题求解算法的设计与实现输入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界面，能够接受用户的输入，也能够从文件中读取数据。在界面上输出所要求的结果，并把结果存储到文件中16无向图最小代价生成树算法的实现（1） 掌握最小代价生成树算法思想。（kruskal算法），并利用贪心的思想改进该算法，降低其时间复杂性。（2） 设计一个有10个顶点的无向图，并用随机数产生其各边的代价。（3） 利用最小代价生成树算法思想，对其所产生的无向图，找出其最小代价生成树。（1） 设计一个界面，显示产生的无向图。（2） 实现最小代价生成树算法。（3） 在输出界面，显示结果。17有向图单源最短路径算法的实现（1）掌握单源最短路径算法思想。（Dijkstra算法）（2）设计一个至少有10个顶点的有向图，并用随机数产生其各边的权值。（3）利用单源最短路径算法思想，对其所产生的有向图，找出从某源点出发，到其它各顶点的最短路。（1）设计一个界面，显示产生的有向图。（2）实现单源最短路径算法。（3）在输出界面，显示结果（在有向图中，标记出从源到各顶点的路径）。18有向图单源最短路径分支限界算法实现（1）掌握单源最短路径分支限界算法思想。（2）设计一个至少有10个顶点的有向图，并用随机数产生其各边的权值。（3）利用单源最短路径分支限界算法思想，对其所产生的有向图，找出从某源点出发，到其它各顶点的最短路。（1）设计一个界面，显示产生的有向图。（2）实现单源最短路径分支限界算法。（3）在输出界面，显示结果（在有向图中，标记出从源到各顶点的路径）。19装载问题的回溯算法实现（1） 有一批集装箱共n个，要装上两艘载重量分别为c1和c2的轮船，其中，集装箱i 的重量Wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1） 用文件导入集装箱的重量，和两艘船的载重量。（2） 实现回溯法的设计思想。（3） 设计一个输出界面，输出装载方案。20装载问题的分支限界算法实现（1）有一批集装箱共n个，要装上两艘载重量分别为c1和c2的轮船，其中，集装箱i 的重量Wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）用文件导入集装箱的重量，和两艘船的载重量。（2）实现分支限界算法的设计思想。（3）设计一个输出界面，输出装载方案。21最大团问题的回溯算法实现（1） 给定无向图G=(V,E)。如果，且对任意有，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）设计一个界面，显示产生的无向图。（至少有5个顶点）（2）实现回溯法的设计思想。（3）在输出界面，显示结果。22最大团问题的分支限界算法实现（1）给定无向图G=(V,E)。如果，且对任意有，则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）设计一个界面，显示产生的无向图。（至少有5个顶点）（2）实现分支限界算法的设计思想。（3）在输出界面，显示结果。23最佳调度问题的回溯算法实现（1） 有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）用文件导入每个任务所需要的时间Ti。（至少10个任务）（2）实现回溯法的设计思想。（3）设计一个输出界面，输出调度方案。24最佳调度问题的分支限界算法实现（1）有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）用文件导入每个任务所需要的时间Ti。（至少10个任务）（2）实现分支限界算法的设计思想。（3）设计一个输出界面，输出调度方案。25N后问题的回溯法算法实现（1） 在格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在同一行或同一列或同一斜线上。（2） 使用回溯算法的思想，设计一个解决该问题的算法。（1）设计一个棋盘界面。（至少有10个皇后）（2）实现回溯算法的设计思想。（3）在界面上，显示所有方案。26N后问题的优先队列分支限界算法实现（1）在格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在同一行或同一列或同一斜线上。（2）使用分支限界算法的思想，设计一个解决该问题的算法。（1）设计一个棋盘界面。（至少有10个皇后）（2）实现分支限界算法的设计思想。（3）在界面上，显示所有方案。27N后问题的拉斯维加斯算法实现（1）在格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在同一行或同一列或同一斜线上。（2）使用拉斯维加斯算法的思想，设计一个解决该问题的算法。（1）设计一个棋盘界面。（至少有10个皇后）（2）实现拉斯维加斯算法的设计思想。（3）在界面上，显示结果。28套汇问题的贪心算法实现（1） 利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如：1美元=0.7英镑，1英镑=9.5法郎，1法郎=0.16美元。1美元=0.7*9.5*0.16=1.064美元（2） 利用贪心算法的设计思想，设计一个解决该问题的算法。（3） 说明算法能产生最优解。（1）用文件导入每种货币的汇兑率。（2）实现贪心算法的设计思想。（3）设计一个输出界面，输出汇兑方案。29设计一个寻找众数的算法并实现（1） 众数：在一个由元素组成的表中，出现次数最多的元素为众数。（2） 设计一个至少100个元素组成的表，用随机函数产生（19）之间的数作为表中的元素值。（3） 设计一个找众数的算法，并完成代码。（1）设计一个至少100个元素组成的表，用随机函数产生（19）之间的数作为表中的元素值。存入文件中。（2）设计一个算法，并实现。（3）设计一个输出界面，输出计算结果。30最优购货方案设计与实现（1） 每种商品都有标价，当单独销售时，按单价出售，如果和其他商品组合促销，则每种物品都降价销售。（2） 设计一个算法，为顾客提供一种省钱的购买方案并完成代码。算法能产生最优解。（1）设计一个界面。（输入需要购买的货物及数量）（2）实现设计的算法思想。（先对5种商品进行处理，需要设计各种组合促销价。然后扩展到n种货物）（3）在界面上，显示结果。31网球循环赛日程表设有n个运动员要进行网球循环赛。设计比赛日程表：（1） 每个选手必须与其他n-1个选手赛一次；（2） 每个选手一天只能赛一次；（3） 当n是偶数时，循环赛进行n-1天；当n是奇数时，循环赛进行n天；（1） 要求掌握分治法或者多边形方法；（2） 设计一个界面，显示产生的日程表；（3） 编程语言不限；32矩阵乘法使用Strassen算法实现矩阵乘法（2） 要求掌握分治法；（2） 设计一个界面，显示计算结果；（3） 编程语言不限；33段合并排序算法在合并排序算法的分割步骤中，将数组划分为个子数组，每个子数组中有个元素。然后递归地对分割后的子数组进行排序，最后将得到的个排好序的子数组合并成所要求的排好序的数组。（1） 要求掌握分治法；（2） 设计一个界面，显示计算结果；（3） 编程语言不限；34自然合并排序算法实现对n个元素进行排序，将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好的子集合合并成所要求的排好序的集合。（2） 要求掌握分治法；（2） 设计一个界面，显示计算结果；（3） 编程语言不限；35集合划分问题给定正整数n，计算出n个元素的集合1,2，3,n可以划分为多少个不同的非空子集。（1） 要求掌握分治法；（2） 设计一个界面，显示计算结果；（3） 编程语言不限；36漂亮打印给定由n个英文单词组成的一段文章，每个单词的长度（字符个数）依序为，。要在一台打印机上将这段文章“漂亮”地打印出来。打印机每行最多可打印M个字符。这里所说的“漂亮”的定义如下：在打印机所打印的每一行中，行首和行尾可不留空格；行中每个单词之间留一个空格；如果在一行中打印从单词i到单词j的字符，则按打印规则，应在一行中恰好打印个字符（包括字间空格字符），且不允许将单词打破；多余的空格数为；除文章的最后一行外，希望每行多余的空格数尽可能少。因此，以各行（最后一行除外）的多余空格数的立方和达到最小最为“漂亮”的标准。用动态规划算法设计一个“漂亮”打印方案。（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。37最长单调递增子序列比较和分析，设计一个较优算法找出n个数组成的序列的最长单调递增子序列（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。38最短行驶路线给定一个的矩形网格，设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在若干网格点处设置了障碍，表示该网格点不可到达。试设计一个算法，求出汽车从起点S出发到达终点T的一条行驶路程最短的路线（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。39最优旅行路线给定一张航空图，图中的定点表示城市，边表示城市间的直通航线。设计一个算法，计算出一条满足下述约束条件且含城市最多的旅行路线。（1） 从最西端的城市出发，单方向由西到东到达最东端的城市。然后，再单方向由东向西飞回起点（可途径若干城市）（2） 出起点城市外，每个城市最多只经过一次。（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。40租用游艇问题长江游艇俱乐部在长江上设置了n个游艇出租站1,2，,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i,j），。设计一个算法，计算出从游艇出租站1到游艇出租站n所需要的最少租金。（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。410-1背包问题的动态规划算法实现0-1背包问题：给定n种物品和一个背包。物品i的重量是，其价值为，背包的容量为c。采用动态规划算法设计选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对于每种物品耀目装入背包要么不装入，而且不能将物品装入背包多次，也不能只装入部分的物品（1）设计一个界面。（2）实现动态规划算法的设计思想。（3）在界面上，显示最佳方案。42收集样本问题机器人Rob在一个有个方格的方形区域F中收集样本，（i，j）方格中样本的价值为v（i，j）。Rob从方形区域F的左上角A点出发，向下或向右行走，直到右下角的B点，在走过的路上，收集方格中的样本。Rob从A点到B点共走2次，试找出Rob的2条行走路径，使其取得的样本总价值最大。（1） 给定方形区域F中的样本分布（2） 给出图形化收集样本路径43数列极差问题在黑板上写了N个整数组成的一个数列，进行如下操作：没一次擦去其中2个数，设为a和b，然后在数列中加入一个数，如此下去直至黑板上只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数为max，最小的数记为min，则该数列的极差M定义为M=max-min（1）设计一个界面，显示运算过程（至少有5个顶点）（2）实现贪心算法的设计思想。（3）在输出界面，显示结果。44运动员最佳配对问题羽毛球队友男女运动员各n人，给定2个矩阵P和Q。是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Qij是女运动员i和男运动员j配合的女运动员优势。由于技术配合和心理状态等各种因素影响，不一定等于。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为，设计一个算法，实现男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。（1）设计一个界面。（2）实现回溯算法的设计思想。（3）在界面上，显示最佳方案。4524点问题给定4个正整数，用算术运算符+，-，将这四个数连接起来，使最终的得数恰为24（1）设计一个运算界面。（2）实现回溯算法的设计思想。（3）在界面上，显示所有方案。46简单算术表达式运算给定简单的算术表达式，包括加减乘除括号这几种运算操作符，请计算表达式的值。(1)能够正确处理加减乘除这四种运算；(2)能够正确处理括号运算；实现提示： 首先将算术表达式转化成逆波兰式，然后针对逆波兰式进行运算。47机器人布线布线区域分成的方格阵列。要求确定连接方格s到方格d的最短布线方案。布线的时候，电路只能沿着直线或者直角布线，有障碍的方格做了封锁标记（X），其他线路不允许穿过被封锁的方格。(1)用文件保存布线区域，用1、0分别表示某个格子是否有障碍；S,D表示起点和终点；(2)给出最短的布线路径长度； (3)用文件保存布线路径，用*表示布线的方格；主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；48字符串距离开发计算两个字符串间的编辑距离，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越相似。49字符串操作编写程序，不使用标准库函数，实现字符串的拷贝、拼接、字串查找、长度计算等函数。(1)在不使用相关的标准库函数的情况下，完成本任务；(2)实现两个字符串拼接的函数strcat(str1, str2)；(3)实现字符串拷贝的函数strcpy(str1,str2)；(4)实现字符串查找的函数strcstr(str1,str2)；(5)实现字符串长度计算的函数strlen(str1)；(6)实现字符串查找字符的函数strcchar(str1,c)；(7)实现字符串替换的函数strcreplacestr(str1,str2,str3)；(8)实现字符串替换字符的函数strcreplacechar(str1,str2,c)；50集合操作用单链表模拟有序集合，实现集合的加入一个元素、删除一个元素、集合的交、并、差运算。(1)用单链表存放集合中的元素，链表中的元素按大小存放；(2)实现集合加入一个元素删除一个元素的元素操作；(3)实现集合的交、并、差集合操作；51推箱子推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个55的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.同时，房间里头还有若干障碍物（用阴影部分表示）。现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.(1)从文件中读出房间布局；(2)计算出推箱子的最小格数；主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；52跳马在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（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)向屏幕上打印出题目的计算结果；53俄罗斯方块龙哥小时候最爱的游戏就是俄罗斯方块了,当年他可是个高手,每次游戏他都会选择最快的速度,以至于根本来不及将方块转向而仅仅能够进行左右移动.为了能够坚持更久,必须尽可能地使落下来方块与底下已有方块上表面完全贴合.在熟悉掌握程序设计后龙哥想要用程序来模拟小时候玩俄罗斯方块的过程,下面请你来帮龙哥参谋一下吧:-)（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)向屏幕上打印出题目的计算结果；54棋盘问题（OJ1255)在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。输入：每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n = 8 , k = n 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。输出：对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C231）。输入样例：2 1#.#4 4.#.#.#.#.输出样例：21主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；55六数码问题现有一两行三列的表格如下：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)向屏幕上打印出题目的计算结果；57算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)向屏幕上打印出题目的计算结果；58农场灌溉问题（OJ1144)一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。输入：给出若干由字母表示的最大不超过5050具体由(m，n)表示，的农场图输出：编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。输入样例：2 2 DK HF 3 3 ADC FJK IHE -1 -1输出样例：2 3主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；59城市之间（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)向屏幕上打印出题目的计算结果；60算12（OJ1199）给定三个数，问你使用加减乘除能否得到12，要求三个数的顺序可以改变，计算的中间结果必须为整数。输入：输入三个整数，均大于0，小于1000。输出：输出为一个整数，当可以得到12时输出1，否则输出0。输入样例：2 2 3输出样例：1提示：输出格式：printf(%dn,1);主要功能：(1)从文件中读出题目的输入；(2)向屏幕上打印出题目的计算结果；61易阵游戏单行列规则两子交换算法设计易阵游戏单行列循环移位规则：某行（列）向左（上）或向右（下）整体移位，移出的棋子回到该行的另一端，如图1。在这个规则下如何交换2个棋子（包括相邻、同行相间、不同行列相间等情况），交换后其他棋子仍在原位。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 62易阵单行列规则排序算法设计（逐位移位）在易阵单行列循环移位规则下，如何以较少的步数实现1个初始的杂乱的易阵排序？方案很多，逐位移位方案就是先将1号棋子以最少的步数移位到1号棋子位，再将2号棋子移到2号棋子位，。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 63易阵单行列规则排序算法设计(兼顾2子的逐位移位)在2号命题的解决方案中，移动1号棋子的过程中能够兼顾2号棋子，移动2号棋子的过程中能够兼顾3号棋子，这样会减少总的步数。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 64易阵单行列规则排序算法设计（逐位交换）对2号命题，逐位交换方案就是是先将1号棋子与1号棋子位的棋子进行2子交换，再将2号棋子与2号棋子位的棋子交换，。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 65易阵单行列规则排序算法设计（逐位替换）对2号命题，逐位替换方案就是进行多次扫描，每次扫描时比较右面和下面棋子的序号，若小则进行交换。易阵游戏参见附录图1。1、把玩游戏2、体验算法3、存储结构设计4、描述算法5、算法设计6、测试算法7、算法效率分析8、撰写实习报告I 66易阵游戏双行列规则两子交换算法设计易阵游戏双行列循环移位规则是选择2行（列），同时同向循环移位，移出的2个棋子回到另一端时，可以换位，也可不换位。在这个规则下如何交换2个棋子（包括相邻、同行相间、不同行列相