2019-2020学年第二学期《算法设计与分析》
补考题目与要求
• 题目分配方法
• 共5道不同的题面（题目0~题目4，具体题面内容见附件1）；
• 按照每位同学学号排序依次循环分配题目0~4，具体分配如下：
学号
姓名
题号
0314011702726
龙云芬
0
0314011702730
王艺凝
1
0314011702739
赵逾欣
2
0314011702803
夏玉龙
3
0314011702805
黄锡永
4
0314011702806
何俊
0
0314011702810
裴浩文
1
0314011702812
薛尊
2
0314011702813
王涵石
3
0314011702820
杨萍
4
0314011702825
王薪贺
0
0314011702827
王琪
1
0314011702833
敖伶俐
2
• 完成要求
撰写和提交算法设计报告。（截止到2020年5月31日晚8：00，过时不收，按未通过考试处理。）
需要提交的内容：
1、电子档设计报告；2、源程序和输出数据文件。
注：内容1和内容2放在一个文件夹中，文件夹以“学号+姓名”命名，如：123456张三。
• 评分标准（100 points in total）：
1、问题分析清楚完整
2、算法思想阐述清楚
3、算法伪代码书写规范
4、算法渐进时间复杂性分析完整合理
5、实验数据设计合理
6、后验分析和结论完善
格式：
排版规范，逻辑层次清楚（参考附件2）。
附件1：《算法设计与分析》补考题面（题目0～题目4）
• 【求最大公因数】
使用C、C++、C#或JAVA 语言设计相关算法并编写一个完整的程序，计算任意两个整数a、b 的最大公因数，其中0≤a,b≤10100。（要求：禁止网上下载大数类实现；10 分钟内输出结果）
• 【矩阵连乘问题】
给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求使用动态规划法计算出这n个矩阵的连乘积A1A2…An。注意给出动态规划的递推表达式。
• 【会场安排问题】
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(提示：这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)
• 【飞机加油问题】
F国际航空公司在世界范围有n个国际机场。第i个国际机场到中心机场的距离为di，i=1，…，n。从国际机场j到国际机场i的飞行费用为c(i,j) s(dj di)2，s为地面加油费用。从任何国际机场飞往中心机场的飞机可以在任一国际机场加油后继续飞行。飞机加油问题要求确定从距中心机场最远的国际机场飞到中心机场的最少费用，即，对于给定的n个国际机场到中心机场的距离d1 ,d2 ,… , dn，以及地面加油费用s，设计算法计算从距中心机场最远的国际机场飞到中心机场的最少费用。
• 【罗密欧与朱丽叶的迷宫问题】
罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这样一条道路。
附件2：书写规范
正文内容：
一、题目描述与设计要求
给出问题的原始描述与要求。
二、问题分析
给出对问题的具体分析，详细描述所设计的算法的主要思想。注意：如果要用流程图阐述算法的思路，要求画出求解思想流程（可以借助Microsoft Visio工具），不要画详细的程序流程图。
三、算法设计
给出解决问题算法的伪代码描述（包括具体数据结构的设计）。注意：伪代码按照书写规范，不允许用程序源代码充数。
四、复杂性分析
运用课上学习的非递归算法和递归算法的复杂性分析过程，详细分析设计的算法的时间和空间复杂性，要求有分析的过程，条理要清楚，不要直接给出渐进复杂性结果。
五、样本测试、分析与总结
测试样本中的数据规模要足够大，要结合渐进复杂性用学过的方法进行后验分析，同时给出自己的结论。
参考文献（如果有）：列出算法设计过程中所查阅的相关文献，如果来自于互联网，要求给出网址。
附录（可选）：附录部分可以给出实现的源程序代码，要求程序中有适当注释。
排版要求：
正文要求恰当使用编号，层次清楚，内容完整，图和表要有编号和标题（表1 ××，图1 ××……），并在正文中有所引用（如表1所示，如图1所示……），可参考以下模板（仅供参考，在保证主要内容齐全的前提下，允许在内容和格式上有所改动）：
2019-2020（2）算法设计报告
楷体_GB2312，三号，加粗，为了整齐，可以使用word表格实现
楷体_GB2312，三号，加粗，为了整齐，可以使用word表格实现
科目名称
：
算法设计与分析
设计题目
：
题目1. 矩阵连乘问题
学号及姓名
：
123456张三
所在院系
：
管理科学与信息工程学院
计算机科学与技术系
提交时间
：
××××年××月
宋体，四号，加粗，居中
宋体，四号，加粗，居中
目 录
一、题目描述与设计要求 1
1. 题目描述 1
2. 设计要求 1
2.1 设计任务 1
2.2 数据输入 1
2.3 结果输出 1
2.4 示例 1
二、问题分析 1
参考文献 2
附录 3
为了整齐，要求使用word的自动生成目录功能将目录生成到3级
为了整齐，要求使用word的自动生成目录功能将目录生成到3级
1级标题，宋体，四号，加粗，段前段后距离为0.5行
1级标题，宋体，四号，加粗，段前段后距离为0.5行
2级标题，宋体，小四，段前段后距离为0.5行
2级标题，宋体，小四，段前段后距离为0.5行
正文宋体，小四，英文字体为times new roman
正文宋体，小四，英文字体为times new roman
2. 设计要求
2.1 设计任务
3级标题，宋体，小四
3级标题，宋体，小四
2.2 数据输入
data文件夹中的各输入文件的第1 行是居民点数n，1n10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000x，y10000。
2.3 结果输出
程序运行结束时，将计算结果输出到文件output.out中。文件的第1 行中的数是n 个居民点到邮局的距离总和的最小值。
2.4 示例
post0.in output0.out
5 10
1 2
2 2
1 3
3 -2
3 3
二、问题分析
……
五号，页码从正文开始，起始页码为1，首页和目录不能出现页码
五号，页码从正文开始，起始页码为1，首页和目录不能出现页码
宋体，四号，加粗，居中
宋体，四号，加粗，居中
• Adelson-Velsky, G.M. and Landis, E.M. An algorithm for organization of information. Soviet Mathematics Doklady, vol. 3, 1962, 1259–1263.
• Adleman, L.M. Molecular computation of solutions to combinatorial problems. Science, vol. 266, 1994, 1021–1024.
• Agrawal, M., Kayal, N., and Saxena, N. PRIMES is in P. Annals of Mathematics, vol. 160, no. 2, 2004, 781–793.
……
Times new roman，小四
Times new roman，小四
宋体，四号，加粗，居中
宋体，四号，加粗，居中
邮局选址问题源代码
int KnapSack(int n, int w[ ], int v[ ])//求解
{
for (i=0; i<=n; i++) //初始化第0列
中文宋体，小四
英文Times new roman
中文宋体，小四
英文Times new roman
for (j=0; j<=C; j++) //初始化第0行
V[0][j]=0;
for (i=1; i<=n; i++)
//计算第i行，进行第i次迭代
for (j=1; j<=C; j++)
if (j
{
if (V[i][j]>V[i-1][j]) {
x[i]=1;
j=j-w[i];
}
else x[i]=0;
}
return V[n][C];
//返回背包取得的最大价值
}