算法设计与分析课程设计题目
以下任选一题，另请谨慎选择第六题。12月27日需告知选题。
一、 使用C、C++、C#或JAVA语言设计相关算法并编写一个完整的程序，计算任意两个整数a,b的最大公因数，其中0≤a,b≤10100。（禁止网上下载大数类实现！）
二、 使用C、C++、C#或JAVA语言设计相关算法并编写一个简单的模拟象棋程序。
三、 宝石游戏：宝石游戏比较有趣，它在13X6的格子里进行。游戏给出红、蓝、黄、 橘黄、绿、和柴的宝石。当任何三个以上宝石具有相同颜并且在一条直线（横竖斜）时，这些宝石可以消去。游戏如图所示。现在给定当前游戏状态和一组新的石头，请编程计算当所有石头落下时游戏的状态。
提示：
输入：
第一行n表示n 组测试数据。
下面每一个测试数据包含一个基于java的课程设计题目13X6的字符表，其中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
四、 现有一公式：Xa mod b = c. 对于给出a,b,c，编写算法求出所有满足条件的X。
提示：
输入：
输入包括多组数据，每组数据三个正整数1<=a,b,c<=109，b总是质数。
输出：
每组数据输出若干行，每一行代表了满足方程的一个X的解，解的顺序按照从小到大输出,最后输出一个空行。没有解输出“No Solution!”
样例输入：
3 13 8
2 3 2
样例输出：
2
5
6

No Solution！
五、 海军演习(提示：动态规划算法)
哪怕在和平的年代，许多国家也会举行演习来保持军队的警惕性。某个国家也发动了一次虚拟的海军战役。
    在演习阶段，海军上将打算评估两个战舰的战斗力，“胜利号”和“荣誉号”，所以他让两个战舰进行打击练习。两艘战舰的指挥官都是年轻有前途的青年，都以出的成绩毕业于海军学院。他们不仅有丰富的导航经验，也掌握了很深的科学知识，特别是数学方面的。
    这位海军上将指定了一个 有许多星罗棋布的小岛的区域。假设这些小岛都被敌方占领，而且敌方的火力点存在优势。虚拟情景和比赛的要求如下：
    (1) 所有被占领的小岛都是互相连接的。岛屿之间有若干路线， 但这些路线都是单向的。换句话说，如果我们把每个小岛看作结点，每条路线当作边，则可以得到一个有向无
环图。
    (2)图中有且仅有一个一号岛 屿。就是说我们从这个岛屿出发就能抵达任何其他小岛。（当然，一号岛屿并不一定是序号为一的岛屿）。
    (3)演习开始时，两艘战舰同时 到达一号岛屿然后一同消灭所有的敌方火力点。
    (4)这两艘战舰轮流导航并且每到达一个岛屿就交换导航权再一起航行。每次它们只能沿着 一条单向路线驶向下一个岛屿，然后消灭岛屿上的所有敌对火力点。注意，“胜利号”首先从一号岛屿开始导航。
    (5)因为每条路线都是单向的， 而且这是一个有向无环图，因此总有战舰无法继续导航的时候，此时演习终止。
    (6)演习终止后，计算沿途消灭的火力点数目，如果这个数目大 于某个上将指定的数目f则“胜利号”获胜，否则“荣誉号”获胜。
战舰的指挥官都是优秀的数学家。接到任务后，他们把其视为图论问题。在一张图上画出结点和边，每个结点有一个正数，两人轮流沿着一定 的路线移动，直到无法移动为止。计算这条路线上所有数字的和并和上将指定的f比较，决定最后的输赢。
    在此，我们认为两人总是做出对自己最有利的选择。
输入：
输入多组测试样例，每个样例第一行有三个数字n,m,f。n表示图中有n(1<n<10000)个结点。分别编号1到n。m表示图中 有m条边。接下来一行有n个正数，依次表示每个结点中的火力点数目。最后m行，每行两个整数a,b表示在a和b结点中有 一条路线。输入以EOF终结。
输出：
对于每个测试样例，如果“胜利号”获胜则输 出"Victory"，如果“荣誉号”获胜则输出"Glory"。每个输出占一行。
样例输入：
4 4 7
2 2 2 2
4 2
2 1
4 3
3 1
4 5 6
1 2 3 4
1 2
1 3
1 4
2 3
4 3
样例输出：
Glory
Victory
六、 若部分同学做以上五题均有难度，经指导老师同意可实现教材上任意三个经典算法。
以上题目总体要求及说明：
1、 建议数据输入输出采用文件方式；
2、 程序中要有注释；
3、 程序中所有算法均要给出算法分析，特别是时间复杂性；
4、 提交程序源代码及算法设计分析测试文档；
5、 按参考格式撰写程序算法报告及测试报告；
6、 30号起接受检查；
7、 提交格式(程序及文档打包)：学号姓名.rar。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。