程序设计专题实验指导书.doc

程序设计专题实验指导书信息工程学院计算机系目 录实验一 简单计算问题11、数字求和12、两倍数13、Number Sequence24、肿瘤检测35、填词46、垂直直方图57、谁拿了最多奖学金68、简单密码89、化验诊断910、密码10实验二 进制、日期及转换问题121、十进制到R进制122、R进制到十进制123、电话号码134、字符串判等155、All in All156、不吉利日期167、循环数178、计算2的N次方189、拼装模型1910、摘花生20实验三 大数、枚举问题221、数字三角形222、数字三角形最大路径233、大整数加法244、大整数乘法245、大整数除法256、菲波那契数列267、最小数268、求大整数的阶乘279、赋值问题27实验四 基础算法问题291、Red and Black292、放苹果313、迷宫324、八皇后问题33实验一 简单计算问题1、数字求和问题描述给定一个正整数a，以及另外的5个正整数，问题是：这5个整数中，小于a的整数的和是多少？输入形式输入一行，只包括6个小于100的正整数，其中第一个正整数就是a。输出形式输出一行，给出一个正整数，是5个数中小于a的数的和。样例输入10 1 2 3 4 11样例输出102、两倍数问题描述给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。 比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2的两倍，18是9的两倍。 输入形式输入包括多组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。输入的最后一行只包括一个整数-1，这行表示输入数据的结束，不用进行处理。输出形式对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。样例输入1 4 3 2 9 7 18 22 02 4 8 10 07 5 11 13 1 3 0-1样例输出3203、Number Sequence问题描述A number sequence is defined as follows:f(1) = 1， f(2) = 1， f(n) = (A * f(n - 1) + B * f(n - 2) mod 7.Given A， B， and n， you are to calculate the value of f(n).输入形式The input consists of multiple test cases. Each test case contains 3 integers A， B and n on a single line (1 = A， B = 1000， 1 = n = 100，000，000). Three zeros signal the end of input and this test case is not to be processed.输出形式For each test case， print the value of f(n) on a single line.样例输入1 1 31 2 100 0 0样例输出254、肿瘤检测问题描述一张CT扫描的灰度图像可以用一个N*N（0N100）的矩阵描述，矩阵上的每个点对应一个灰度值（整数），其取值范围是0255。我们假设给定的图像中有且只有一个肿瘤。在图上监测肿瘤的方法如下：如果某个点对应的灰度值小于等于50，则这个点在肿瘤上，否则不在肿瘤上。我们把在肿瘤上的点的数目加起来，就得到了肿瘤在图上的面积。任何在肿瘤上的点，如果它是图像的边界或者它的上下左右四个相邻点中至少有一个是非肿瘤上的点，则该点称为肿瘤的边界点。肿瘤的边界点的个数称为肿瘤的周长。现在给定一个图像，要求计算其中的肿瘤的面积和周长。输入形式输入第一行包含一个正整数N（0N100），表示图像的大小；接下来N行，每行包含图像的一行。图像的一行用N个整数表示（所有整数大于等于0，小于等于255），两个整数之间用一个空格隔开。输出形式输出只有一行，该行包含两个正整数，分别为给定图像中肿瘤的面积和周长，用一个空格分开。样例输入699 99 99 99 99 9999 99 99 50 99 9999 99 49 49 50 5199 50 20 25 52 9940 50 99 99 99 9999 99 99 99 99 99样例输出9 8测试数据2：样例输入799 99 99 99 99 99 6599 99 99 50 99 99 2599 99 49 49 50 49 3499 50 20 25 52 99 3840 50 99 99 99 99 3599 99 99 99 99 99 5599 99 99 99 99 99 77样例输出14 135、填词问题描述Alex喜欢填词游戏。填词是游戏是一个非常简单的游戏。填词游戏包括一个N * M大小的矩形方格盘和P个单词。玩家需要把每个方格中填上一个字母使得每个单词都能在方格盘上找到。每个单词都能找到要满足下面的条件： 每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的。 你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。 如果你还不了解规则，我们可以具一个例子，比如在下图中寻找单词BEG和GEE。 输入形式输入的第一行包括三个整数N，M和P (2 = M， N = 10， 0 = P 80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（85），并且班级评议成绩高于80分（80）的学生均可获得； 3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（90）的学生均可获得； 4) 西部奖学金，每人1000元，期末平均成绩高于85分（85）的西部省份学生均可获得； 5) 班级贡献奖，每人850元，班级评议成绩高于80分（80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。 输入形式输入的第一行是一个整数N（1 = N = 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。输出形式输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。样例输入4YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1样例输出ChenRuiyi9000287008、简单密码问题描述Julius Caesar曾经使用过一种很简单的密码。对于明文中的每个字符，将它用它字母表中后5位对应的字符来代替，这样就得到了密文。比如字符A用F来代替。如下是密文和明文中字符的对应关系。 密文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 明文 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 你的任务是对给定的密文进行解密得到明文。 你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。输入形式输入中的测试数据不超过100组。每组数据都有如下的形式，而且各组测试数据之间没有空白的行。 一组测试数据包括三部分 起始行：一行，包括字符串 START 密文：一行，给出密文，密文不为空，而且其中的字符数不超过200 结束行：一行，包括字符串 END 在最后一组测试数据之后有一行，包括字符串 ENDOFINPUT。 输出形式对每组数据，都有一行输出，给出密文对应的明文。样例输入STARTNS BFW， JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJXENDSTARTN BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJENDSTARTIFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJENDENDOFINPUT样例输出IN WAR， EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE9、化验诊断问题描述下表是进行血常规检验的正常值参考范围，及化验值异常的临床意义： 给定一张化验单，判断其所有指标是否正常，如果不正常，统计有几项不正常。化验单上的值必须严格落在正常参考值范围内，才算是正常。正常参考值范围包括边界，即落在边界上也算正常。输入形式输出形式对于每组测试数据，输出一行。如果所有检验项目正常，则输出：normal；否则输出不正常的项的数目。样例输入2female 4.5 4.0 115 37 200male 3.9 3.5 155 36 301样例输出normal310、密码问题描述Bob 和 Alice 开始使用一种全新的编码系统。它是一种基于一组私有钥匙的。他们选择了n个不同的数a1 ， . . .，an， 它们都大于0小于等于n。 机密过程如下：待加密的信息放置在这组加密钥匙下，信息中的字符和密钥中的数字一一对应起来。信息中位于i位置的字母将被写到加密信息的第ai个位置， ai 是位于i位置的密钥。加密信息如此反复加密，一共加密 k 次。 信息长度小于等于n。如果信息比 n 短， 后面的位置用空格填补直到信息长度为n。 请你帮助 Alice 和 Bob 写一个程序，读入密钥，然后读入加密次数 k 和要加密的信息，按加密规则将信息加密。 输入形式输入包括几块。每块第一行有一个数字n， 0 n = 200. 接下来的行包含n个不同的数字。数字都是大于0小于等于n的。下面每行包含一个k和一个信息字符串，它们之间用空格格开。每行以换行符结束，换行符不是要加密的信息。每个块的最后一行只有一个0。 最后一个块后有一行，该行只有一个0。 输出形式输出有多个块，每个块对应一个输入块。每个块包含输入中的信息经过加密后的字符串，顺序与输入顺序相同。所有加密后的字符串的长度都是 n。 每一个块后有一个空行。 样例输入104 5 3 7 2 8 1 6 10 91 Hello Bob1995 CERC00样例输出BolHeol bC RCE实验二 进制、日期及转换问题1、十进制到R进制问题描述把一个十进制正整数转化成R进制输入形式输入只有一行，包含两个整数a，R。a表示十进制整数，R表示需要转换的进制。1R=16。输出形式输出包含一行，为转换后的R进制整数。输出时字符号全部用大写表示，即（0 ，1，.，9，A，B，C，D，E，F）。样例输入12 16样例输出C2、R进制到十进制问题描述把一个R进制正整数转化成十进制输入形式一行，包含一个R进制表示的正整数a和进制数R，a的十进制表示的范围是(0， 65536)，1R=9。输出形式一行，a的十进制表示样例输入1011 2样例输出113、电话号码问题描述企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Ginos订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。 电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下： A， B， 和C 映射到 2 D， E， 和F 映射到 3 G， H， 和I 映射到 4 J， K， 和L 映射到 5 M， N， 和O 映射到 6 P， R， 和S 映射到 7 T， U， 和V 映射到 8 W， X， 和Y 映射到 9 Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。 TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。 如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号） 你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。 输入形式输入的格式是，第一行是一个正整数，指定电话号码薄中号码的数量（最多100000）。余下的每行是一个电话号码。每个电话号码由数字，大写字母（除了Q和Z）以及连接符组成。每个电话号码中只会刚好有7个数字或者字母。输出形式对于每个出现重复的号码产生一行输出，输出是号码的标准格式紧跟一个空格然后是它的重复次数。如果存在多个重复的号码，则按照号码的字典升序输出。如果输入数据中没有重复的号码，输出一行： No duplicates. 样例输入124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-3279样例输出310-1010 2487-3279 4888-4567 34、字符串判等问题描述判断两个由大小写字母和空格组成的字符串在忽略大小写和压缩掉空格后是否相等输入形式第1行是测试数据的组数n，每组测试数据占2行，第1行是第一个字符串s1，第2行是第二个字符串s2。 每组测试数据之间有一个空行，每行数据不超过100个字符（注意字符串的长度可能为0）输出形式n行，相等则输出YES，否则输出NO样例输入3a A bb BB ccc CCCAa BBbb CCCccca dfadf fasdfadasddfsfsaf样例输出YESYESNO5、All in All问题描述You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method， however， it is necessary to write a program that checks if the message is really encoded in the final string. Given two strings s and t， you have to decide whether s is a subsequence of t， i.e. if you can remove characters from t such that the concatenation of the remaining characters is s. 输入形式The 输入形式 contains several testcases. Each is specified by two strings s， t of alphanumeric ASCII characters separated by whitespace.The length of s and t will no more than 100000.输出形式For each test case 输出形式 Yes， if s is a subsequence of t，otherwise 输出形式 No.样例输入sequence subsequenceperson compressionVERDI vivaVittorioEmanueleReDiItaliacaseDoesMatter CaseDoesMatter样例输出YesNoYesNo6、不吉利日期问题描述在国外，每月的13号和每周的星期5都是不吉利的。特别是当13号那天恰好是星期5时，更不吉利。已知某年以及该年一月一日是星期w（w=1.7），求出这一年所有13号那天是星期5的月份，按从小到大的顺序输出月份数字。输入形式输入有一行，第一个整数为年份，第二个整数为该年一月一日是星期几（w）。（1=w=7）输出形式输出有一到多行，每行一个月份，表示该月的13日是星期五。样例输入2006 7样例输出1107、循环数问题描述n 位的一个整数是循环数（cyclic）的条件是：当用一个 1 到 n 之间的整数去乘它时， 会得到一个将原来的数首尾相接循环移动若干数字再在某处断开而得到的数字。也就是说，如果把原来的数字和新的数字都首尾相接，他们得到的环是相同的。只是两个数的起始数字不一定相同。例如，数字 142857 是循环数，因为: 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142 输入形式写一个程序确定给定的数是否是循环数。输入包括多个长度为 2 位到 60 位的整数。(注意，先导的0也是合理的输入不应该被忽略，例如 01是 2 位数，1 是 1 位数。) 输出形式对于每一个输入的整数，输出一行表明它是否是循环数。 样例输入142857142856142858010588235294117647样例输出142857 is cyclic142856 is not cyclic142858 is not cyclic01 is not cyclic0588235294117647 is cyclic8、计算2的N次方问题描述任意给定一个正整数N(N=100)，计算2的N次方的值。输入形式输入只有一个正整数N。输出形式输出2的N次方的值。样例输入5样例输出329、拼装模型问题描述Dzx从日本回来了，并为TN准备了礼物-一个恐龙模型。TN想把它尽快拼好，但是由于模型很庞大，TN又实在比较懒，所以他希望你为他寻找一个最节省时间的拼装方案。 模型是由N个零件组成的，每次TN可以选取两个零件拼装在一起来组成一个新的零件，直到得到完整的模型。由于零件的复杂程度不同，TN每次拼装所需要的时间也是不同的，对于两个零件A和B，假设他们的复杂程度分别为a和b，则TN要将这两个零件拼装在一起所需要的时间为a+b，而这由两个零件所组成的新零件的复杂程度为a+b。 现在TN已经统计出了每个零件的复杂程度，你能告诉他最快的拼装方发需要多少时间么？输入形式Line 1： N (1 = N = 10000)，零件数目 Line 2： N Integers，表示每个零件的复杂程度输出形式最快的拼装方案所需要的时间样例输入31 2 9样例输出1510、摘花生问题描述鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件： 1) 从路边跳到最靠近路边（即第一行）的某棵花生植株； 2) 从一棵植株跳到前后左右与之相邻的另一棵植株； 3) 采摘一棵植株下的花生； 4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。 例如在图2所示的花生田里，只有位于(2， 5)， (3， 7)， (4， 2)， (5， 4)的植株下长有花生，个数分别为13， 7， 15， 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。 输入形式输入的第一行包括一个整数T，表示数据组数 每组输入的第一行包括三个整数，M， N和K，用空格隔开；表示花生田的大小为M * N（1 = M， N = 50），多多采花生的限定时间为K（0 = K = 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 = Pij = 500）表示花生田里植株(i， j)下花生的数目，0表示该植株下没有花生。输出形式输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。样例输入6 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0样例输出37实验三 大数、枚举问题1、数字三角形问题描述将A、B、C、D、E、F这六个变量排成如图所示的三角形。AB F C D E这六个变量分别取1，6上的整数，且均不相同，构成的三角形三条边上的变量之和相等。当给出三角形顶点A的取值后，给出能构成这样三角形的全部解。输入形式仅含一个十进制表示的整数A(1 = A =6)输出形式多行，每行为一个解，按ABCDEF形式输出，并且各解的输出顺序是按其所组成的整数由小到大顺序输出。样例输入1样例输出1452361534261624351632542、数字三角形最大路径问题描述73 88 1 02 7 4 44 5 2 6 5图中给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。 输入形式输入的是一行是一个整数N (1 N = 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。输出形式输出最大的和。样例输入573 88 1 0 2 7 4 44 5 2 6 5样例输出303、大整数加法 问题描述求两个不超过200位的非负整数的和。输入形式有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出形式一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。 样例输入2222222222222222222233333333333333333333样例输出555555555555555555554、大整数乘法问题描述求两个不超过200位的非负整数的积。输入形式有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出形式一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。 样例输入1234567890098765432100样例输出12193263111263526900005、大整数除法问题描述求2个大的正整数相除的商输入形式第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符输出形式n行，每组测试数据有一行输出是相应的整数商样例输入324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451样例输出0100000000000000000000000000000054096567750978508956870567980689709345465465756767686784354353456、菲波那契数列 问题描述菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。输入形式第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 = a = 1000000)。输出形式n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。样例输入452191样例输出5118117、最小数问题描述将给定的整数M，从中去掉K位后使所得数最小。 例：整数：1342426735 去掉4位 结果最小为122635输入形式一行，第一个数为十进制表示的整数M，M位长最多为20；第二个数为整数K。输出形式去掉K位后的最小值。样例输入1342426735 4样例输出1226358、求大整数的阶乘问题描述给定一个大整数，计算其阶乘。输入形式一行，仅含一个小于100的整数N。输出形式N的阶乘。样例输入4样例输出249、赋值问题问题描述在很多程序设计语言中，忘记给变量赋初值的错误常令人头疼。请编程求出含N(0N100)行的程序段运行以后有哪些变量中有确定的值。在下面的问题中，最开始仅有变量a中有确定的值。变量为单个小写字母，每行恰好有三个字符，中间一个是赋值运算符=。 输入形式输入有多组数据，每组数据的第一行有一个整数N，表示程序段的行数。以下N行，每行3个字符，为一条语句。最后一组数据N=-1表示输入结束，不需要处理。 输出形式对每一组数据输出一行结果，按字母表顺序给出所有有确定值的变量名。如果没有变量有确定的值，输出none。 样例输入4b=ac=dd=be=f-1样例输出a b d实验四 基础算法问题1、Red and Black问题描述There is a rectangular room， covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile， he can move to one of four adjacent tiles. But he cant move on red tiles， he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above. 输入形式The 输入形式 consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions， respectively. W and H are not more than 20. There are H more lines in the data set， each of which includes W characters. Each character represents the color of a tile as follows. . - a black tile # - a red tile - a man on a black tile(appears exactly once in a data