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

华侨大学首届程序设计大赛决赛试题第一题：汉诺塔（hanoi）是一种古老的游戏，用来锻炼人的思考能力。这种游戏中有三根柱子A,B,C，然后有一组大小不同的圆盘挂在柱子上，圆盘可以从一个柱子移动到另一个柱子，最初所有的圆盘都在柱子A上，并且上面的圆盘按照大小顺序，下面圆盘比上面的圆盘大。要求把所有的圆盘都移动到柱子C上，移动过程中圆盘只能放在柱子A、B、C上面，并且小的圆盘始终在大的圆盘之上。输入：要求用户用键盘输入圆盘的个数N输出：在屏幕上显示移动的过程，每行表示一个移动，包括要移动的圆盘号码（最小的圆盘为1,第二小的圆盘为2,……,最大的为N）、在移动之前这个圆盘所处的柱子（A,B,C中的一个）、在移动之后这个圆盘所处的柱子（A,B,C中的一个）。这三者彼此之间用空格隔开。输入输出举例：输入：3输出：1AC2AB1CB3AC1BA2BC1AC第二题：本题是一个人和机器人追逐游戏的一个模块，首先需要读入一个棋盘文件表示当前的游戏进度，棋盘是一个文本文件，里面只有下面提到的各种字符和空格：棋盘中有一个“人”由用户控制（棋盘中用符号”H”表示）；棋盘中有多个“机器人”由计算机控制（棋盘中用符号”R”表示活的机器人，用符号”*”表示死的机器人）；棋盘的上下边线用”-”表示；棋盘的左右边线用”|”表示；棋盘的四个角用”+”表示；棋盘中的空格表示对应的位置没有任何人和机器人。这个棋盘一定是长方形的，下面是一个输入文件的例子：第五题：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表示每三场比赛中甲队胜一场而乙队胜两场），就能得出平均的决赛场数。输入：用户通过键盘输入甲队对乙队的胜率。输出：在屏幕上显示平均的决赛场数。第六题：飞机机票搜索是携程网等国内外各大旅游网站的一个重要业务。本题中的输入文件给定了世界上主要城市之间是否有飞机直达航线，所有航线均为双向。求北京能够通过飞机到达的所有其他城市名字，允许转机，并且次数不限。输入文件格式：每行是两个城市的名字，用空格隔开。例如：BeijingLondonLondonParisWashingtonNewYorkWashingtonLosAngeles输出格式：每行是能够到达的一个城市的名字，例如：LondonParis输入：用户用键盘输入当前文件夹下面包含直达航线城市名的文件名字。输出：在屏幕上显示北京能够通过飞机到达的所有城市名字。注意：文件中城市可能很多，所以算法需要注意尽量减少程序的运行时间。第七题：词典是一个计算机可以实现的典型应用，目前国内最好的英汉词典是谷歌金山词霸。本题中要通过程序用一个包含英文和中文词义的文件来构建一个英汉词典，之后将用户输入的英文单词翻译成中文。这个词典中的单词数目可能很多，所以希望尽量减少查询时用户等待的时间。输入文件的每一行包括一个单词的英文和中文意思，之间用空格隔开。例如：China中国Japan日本Korea韩国Brazil巴西Argentina阿根廷输入：用户用键盘输入当前文件夹下面包含英汉词义的文件名字之后，在屏幕上显示对应的提示让用户输入英文单词。输出：用户用键盘输入英文单词之后在屏幕上显示单词对应的中文意思。之后反复循环，直到用户输入”exit”之后才退出整个程序。第八题：百度、谷歌等搜索引擎是目前互联网上最受欢迎的网站，也造就了IT行业技术最强的公司。搜索引擎的核心则是查询包含特定关键词的网页。本题中要求将给定的一系列网页读入后进行预处理，之后在用户输入关键词的时候进行搜索，显示出所有包含这一关键词的网页。输入：在屏幕上显示对应提示后由用户用键盘输入本文件夹下一系列网页的名字，然后程序对这些网页预处理之后显示对应的提示，再由用户用键盘输入要搜索的关键词。输出：在屏幕上显示刚才用户输入的本文件夹下的一系列网页中所有包含该关键词的网页名字。注意：这里的网页可能数目