11算法设计与分析课程设计题目

以下题目任选一题。

一、 使用C、C++、C#或JAVA 语言设计相关算法并编写一个完整 的程序，计算任意两个整数a,b 的最大公因数，其中0≤a,b≤10100。（要求：禁止网上下载大数类实现；10 分钟内输出结果）

二、 使用C、C++、C#或JAVA 语言设计相关算法并编写一个简单的中国象棋模拟程序。

三、 地图着色问题。对美国地图进行着色，两个共同边界的州着不同的颜色，当可以选择7、6、5、4种不同的颜色的情况下，由程序自动进行处理，给出具体的着色方案。

四、罗密欧与朱丽叶的迷宫问题。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这样一条道路。

五、宝石游戏：宝石游戏比较有趣，它在13X6 的格子里进行。游戏给出红色、蓝色、黄色、 橘黄色、绿色、和柴色的宝石。当任何三 个以上宝石具有相同颜色并且在一条直线（横竖斜）时，这些宝石 可以消去。游戏如图所示。现在给定当前游戏状态和一组新的石头， 请编程计算当所有石头落下时游戏的状态。

提示：

输入：第一行n 表示n 组测试数据。

下面每一个测试数据包含一个13 X 6 的字符表，其中B 表示蓝色，R 表示红色，O 表示橘黄色、Y 表示黄色，G 表示绿色，P 表示紫色，W 表示此处没有宝石。接下来三行，每行包含一个字符，表示新来的宝石下落的位置。 输出：

每一个测试样例，输出当所有宝石落下后游戏的状态。 样例输入： 1

WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW BBWWWW BBWWWW OOWWWW B B Y 3

样例输出： WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW

WWWWWW WWWWWW WWWWWW WWWWWW WWWWWW OOYWWW

六、若部分同学做以上五题均有难度，经指导老师同意可实现教材上任意三个经典算法。

以上题目总体要求及说明：

1、建议数据输入输出采用文件方式； 2、程序中要有注释；

3、程序中所有算法均要给出算法分析，特别是时间复杂性； 4、提交程序源代码及算法设计分析测试文档（纸质及电子版）； 5、按参考格式撰写程序算法报告及测试报告； 6、1 月13 号起接受检查；

7、提交格式(程序及文档打包)：学号姓名.rar。