华侨大学首届程序设计大赛决赛试题.doc

华侨大学首届程序设计大赛决赛试题第一题：汉诺塔（hanoi）是一种古老的游戏，用来锻炼人的思考能力。这种游戏中有三根柱子A, B,C，然后有一组大小不同的圆盘挂在柱子上，圆盘可以从一个柱子移动到另一个柱子，最初所有的圆盘都在柱子A上，并且上面的圆盘按照大小顺序，下面圆盘比上面的圆盘大。要求把所有的圆盘都移动到柱子C上，移动过程中圆盘只能放在柱子A、B、C上面，并且小的圆盘始终在大的圆盘之上。输入：要求用户用键盘输入圆盘的个数N输出：在屏幕上显示移动的过程，每行表示一个移动，包括要移动的圆盘号码（最小的圆盘为1, 第二小的圆盘为2, , 最大的为N）、在移动之前这个圆盘所处的柱子（A,B,C中的一个）、在移动之后这个圆盘所处的柱子（A,B,C中的一个）。这三者彼此之间用空格隔开。输入输出举例：输入：3输出：1 A C 2 A B 1 C B 3 A C 1 B A 2 B C 1 A C第二题：本题是一个人和机器人追逐游戏的一个模块，首先需要读入一个棋盘文件表示当前的游戏进度，棋盘是一个文本文件，里面只有下面提到的各种字符和空格：棋盘中有一个“人”由用户控制（棋盘中用符号”H”表示）；棋盘中有多个“机器人”由计算机控制（棋盘中用符号”R”表示活的机器人，用符号”*”表示死的机器人）；棋盘的上下边线用”-”表示；棋盘的左右边线用”|”表示；棋盘的四个角用”+”表示；棋盘中的空格表示对应的位置没有任何人和机器人。这个棋盘一定是长方形的，下面是一个输入文件的例子：人可以向上、下、左、右、左上、右上、左下、右下的任何一个方向移动一格。之后每个机器人会自动向人的方向移动一格：n 如果机器人处于人的上方就向下移动n 如果机器人处于人的下方就向上移动n 如果机器人处于人的左方就向右移动n 如果机器人处于人的右方就向左移动n 如果机器人处于人的左上方就向右下移动n 如果机器人处于人的左下方就向右上移动n 如果机器人处于人的右上方就向左下移动n 如果机器人处于人的右下方就向左上移动机器人移动之后可能产生各种碰撞：n 如果两个机器人相撞会一起死掉变成残骸（用符号”*”表示）n 如果机器人碰到机器人的残骸也会死掉变成残骸n 如果人碰到机器人，人就会死掉从而游戏结束。要求：在当前的棋盘情况下计算人的最佳移动方向，使得人不会死而且人移动后下一步机器人的移动造成最大数量的机器人死亡。输入：要求用户用键盘输入当前文件夹下面棋盘文件的名字。输出：在屏幕上显示人的最佳移动方向，用数字表示（左下为1、下为2、右下为3、左为4、不动为5、右为6、左上为7、上为8、右上为9）。如果几个方向都是最佳，则把这几个方向一起输出；如果向任何方向移动人都会死，则输出”+”。第三题：本题中要求从一组数据中查找一个数据。首先需要读入一个文本文件，其中每行包括一个学生的学号和对应的姓名，中间用空格隔开。学号已经按照升序排列，即后出现的学生的学号一定比先出现的大。但是由于某些学生已经转系或者退学，所以学号不一定连续。例如：0615122003 张三0615122005 王五0615122006 赵六0615122009 李九读入的数据存储在对应数组之后再读入另一个文件，这个文件里包括要查找的学生的学号，每行一个人，例如：06151220030615122009要求：程序输出第二个文件对应的每个学生的姓名，例如上面的文件的正确输出结果是：张三李九输入：要求用户用键盘输入当前文件夹下面一个包含学生学号和姓名的文件名字、一个包含要查找的学生学号的文件名字。输出：在屏幕上显示要查找的学生对应的姓名，每行一个人。注意：输入文件中可能学生数目很多，因此希望算法尽量减少查找中的运行时间。第四题：本题要求从一组整数中找到最大的和第二大的。输入文件包括一组整数，每行一个整数，例如：18453627要求：将输入文件中的整数存入数组后，从中找到其中最大的和第二大的整数，例如上面例子中最大的整数是8，第二大的整数是7。这个文件里面整数的个数可能很大，所以希望算法尽量减少两个整数比较的次数。输入：用户用键盘输入当前文件夹下面包含一组整数的文件名。输出：在屏幕上显示最大整数的值和第二大整数的值，第一行显示最大整数，第二行显示第二大整数。例如上面例子的输出结果为： 8 7第五题：NBA比赛的决赛采取系列赛的方式，即两队进行七场四胜比赛。先胜四场的球队获得比赛胜利，如果此时比赛不足七场则后面的比赛全部取消。这样决赛比分和比赛场数有以下几种可能：4 : 0 （4场）4 : 1 （5场）4 : 2 （6场）4 : 3 （7场）3 : 4 （7场）2 : 4 （6场）1 : 4 （5场）0 : 4 （4场）目前比赛场馆的负责人希望在赛前能够按双方实力估计决赛的场数，他要求只要给出两队之间的相互胜率（例如1.0表示双方实力相当，2.0表示每三场比赛中甲队胜两场而乙队胜一场，0.5表示每三场比赛中甲队胜一场而乙队胜两场），就能得出平均的决赛场数。输入：用户通过键盘输入甲队对乙队的胜率。输出：在屏幕上显示平均的决赛场数。第六题：飞机机票搜索是携程网等国内外各大旅游网站的一个重要业务。本题中的输入文件给定了世界上主要城市之间是否有飞机直达航线，所有航线均为双向。求北京能够通过飞机到达的所有其他城市名字，允许转机，并且次数不限。输入文件格式：每行是两个城市的名字，用空格隔开。例如：Beijing LondonLondon ParisWashington NewYorkWashington LosAngeles输出格式：每行是能够到达的一个城市的名字，例如：LondonParis输入：用户用键盘输入当前文件夹下面包含直达航线城市名的文件名字。输出：在屏幕上显示北京能够通过飞机到达的所有城市名字。注意：文件中城市可能很多，所以算法需要注意尽量减少程序的运行时间。第七题：词典是一个计算机可以实现的典型应用，目前国内最好的英汉词典是谷歌金山词霸。本题中要通过程序用一个包含英文和中文词义的文件来构建一个英汉词典，之后将用户输入的英文单词翻译成中文。这个词典中的单词数目可能很多，所以希望尽量减少查询时用户等待的时间。输入文件的每一行包括一个单词的英文和中文意思，之间用空格隔开。例如：China 中国Japan 日本Korea 韩国Brazil 巴西Argentina 阿根廷输入：用户用键盘输入当前文件夹下面包含英汉词义的文件名字之后，在屏幕上显示对应的提示让用户输入英文单词。输出：用户用键盘输入英文单词之后在屏幕上显示单词对应的中文意思。之后反复循环，直到用户输入”exit”之后才退出整个程序。第八题：百度、谷歌等搜索引擎是目前互联网上最受欢迎的网站，也造就了IT行业技术最强的公司。搜索引擎的核心则是查询包含特定关键词的网页。本题中要求将给定的一系列网页读入后进行预处理，之后在用户输入关键词的时候进行搜索，显示出所有包含这一关键词的网页。输入：在屏幕上显示对应提示后由用户用键盘输入本文件夹下一系列网页的名字，然后程序对这些网页预处理之后显示对应的提示，再由用户用键盘输入要搜索的关键词