实验部分
一、要求
1.算法设计与分析班实验课统一上课分为三次，分别在2013年10月9号（第六周周三）、2013年11月27号（第十三周周三）和2014年1月1号（第十八周周三）晚上19:00-22：00.
2.实验要求独立完成，发现抄袭则实验为0分（包括网上的代码），没有分组。
3.要求提交实验源码，可执行程序以及实验报告。实验报告包括程序的输入，输出，结果，演示界面，算法语言描述，原理等。要求把所有实验打包成一个rar文件后提交到软件学院教学辅助系统，并且命名文件格式为学号+姓名（eg. 学号_NAME），不符合命名格式的一律不批改。
4.程序语言不做特别要求，C、C++、JAVA均可
5.实验提交截止时间：2014/ 01/ 12 23:59:00 之前
二、题目
题目主要包括两部分：练手题（2道）和正式题目（2道）。对于练手题目，均来自ACM程序设计比赛中的常见预热题目，在实验报告中请给出详细的解题思路，并给出两个输入数据样例对应的数据输出。对于正式题目，实验报告请根据每个题目后面红色字体给出的提示完成，请重视代码编写完成以后的性能分析部分。
<一> 练手题
1.整数划分类
输入：
每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)
输出：
对于每组输入，请输出六行。
第一行：将n划分成若干正整数之和的划分数。
第二行：将n划分成k个正整数之和的划分数。
第三行：将n划分成最大数不超过k的划分数。
第四行：将n划分成若干奇正整数之和的划分数。
第五行：将n划分成若干不同整数之和的划分数。
第六行：打印一个空行。
Sample Input
5 2
Sample Output
7
2
3
3
2.幻方矩阵
幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。
幻方的定义为：
1 到N*N 的整数填入N*N的方格中，每行和每列以及对角线的数字之和必须是相等的。你作为八卦公司的顶级程序员，现在需要你解决一个问题，将任意奇数阶的幻方找出来。
输入：
输入包括多个测试集，每行为一个正奇数N(1 <= N < 1000)，0作为输入的结束且不需要处理。
输出：
对于输入的每一个N，输出一个它所对应的N阶幻方，如果存在多个，任意一个即可。
每个幻方为N*N的矩阵，
对于每个幻方，每行输出幻方的一行，每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个空行分开。
Sample Input
1
3
Sample Output
1
4 9 2
3 5 7
8 1 6
<二> 正式题目
1.（必做题）常见排序算法的实现与性能比较
问题描述：实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法
实验要求：
A．在随机产生的空间大小分别N = 10，1000，10000，100000
的排序样本上测试以上算法。
B．结果输出:
（1）N=10时，排序结果。
（2）N=1000，10000，100000时，每个排序用不同的样本多试验几次（最
低5次）得出平均时间，比较不同排序算法所用的平均时间。
实验报告要点：总结对各种排序的性能分析。
2. 必选题）最长递增子序列
问题描述：随机生成小于等于n的自然数的一个序列，输出其最长递增子序列（任意一个即可）。
n 分别取1000，3000，10000。
例：n=5 随机序列为5 1 4 2 3，正确输出为1 2 3，即长度为3的递增子序列。
提示：参考LCS，思考能否达到时间复杂度（O(nlogn)）
实验报告要点：描述动态规划思想，总结时间和空间复杂度。
