算法设计和分析实验说明_08级软件信安专业

[说明](1)以下实验请同学们在课下进行积级的准备；提倡将程序编写为图形界面；实验报告必须完成，将程序的算法思想及程序运行的数据和结果写入报告；并要求对每一种算法的实现进行算法分析；实验分数将占整门课程的20%.

           (2)[1]至[4]实验必做，其它可选；

           (3)充分发挥你的聪明才智，做出与众不同的程序设计。

(4) 请记住：即使是一个非常小的算法，在实现时，也可能编写出非常优秀的程序及界面。

(5)将所有的程序算法，封装到一个工程中，学习软件文件组织的基本方法。

[综合实验一](必做) 分治策略—归并排序

归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：

（1）编写一个模板函数：

template

MergeSort(T *a, int n);

以及相应的一系列函数，采用分治策略，对任意具有:

bool operator<(const T&x,const T&y);

比较运算符的类型进行排序。

（2）与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的整数序列的排序列问题, 给出所用的时间比较。

[综合实验 二](必做) 动态规划--格路问题

    格路问题有多种方法求解，可采用多种方法求解，如：(1)动态规划方法; (2)　备忘录方法；(3) 递归方法。

    基本要求：

(1) 清晰地描述此问题；

(2) 采用动态规划方法求解；

(3) 给出相应类的封装及数据结构；

(4) 输出运算后的二维表格，或输出最短路径(如:写入一个文件)；

(5) 格路的数据文件采用以下形式的格式：

griddata.txt

5,4                              //代表m+1,n+1

1,-1   2,-1  1,-1  4,-1    -1,-1     //最右边点为终点E

4,11   3,27  2,9  7,6     -1, 2

1,15   3,19  2,59  7,16   -1, 18

7,10   3,20  2,31  7,12   -1, 47    //最左边点为起点O

这里：第1行数据为逗号隔开的两个整数值，分别代表m+1,n+1 即格路的列数与行数；每行数据代表格路上的一行数据，每组数据代表相应的点向右，向上的距离(均为整数)。

参考数据结构如下：

struct TPoint  //二维数据表中每个结点的数据结构

{

    int nUp,nRight;//此点到邻近上一个结点、右一个结点的距离

    int nShortest; //最短路径长

    int nFrom;     //最短路径上前一个结点的来源

                   //0:没有最短路径 1: 左, 2:右. -1:没有量短路径

    TPoint(): nUp(1),nRight(1),nFrom(-1){} //缺省无路径

    TPoint(int u,int r): nUp(u), nRight(r), nFrom(-1){}   //声明时，直接给出

};

class CGridRoad

{

private:

    int m, n; //指出格路共m+1列，n+1行。

    TPoint  **g;//格路数据结构:一个二维动态数组

public:

    CGridRoad();

    CGridRoad(char  *sFileName);  //构造时，就从指定的文件中读取格路数据，

//并动态生成表示格路的二维数组

    ~CGridRoad();                //析构函数，负责释放已经申请的内存

    //void CreateGridFromKeyBoard();     //从键盘上与用户交互，构建格路

    void CreateGridFromFile(char file[]);   //从文件中读出数据进行初始化；

    void Calculate(); //动态规划方法求解此问题；

    void OutputShortest(); //打印或输出最短路径

    //...其它需要的数据及函数

};

[综合实验三]（必做）贪心算法—Huffman树及Huffman编码

一个记录字符及出现频率的文件如下所示：

huffman.haf

7

a,45

b,13

c,12

d,16

e,

f,34

g,20

试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：

        CHuffman hm("huffman.dat");

        hm.CreateTree();

        hm.OutputTree();

        hm.OutputCode(); //二进制形式的字符串

对于输出树的形式可自行决定(如图形界面或字符界面)。

[综合实验四](必做)用回溯方法求解n后问题

问题：对任意给定的n求解n后问题。

具体要求：

1．封装n后问题为类，编写以下两种算法进行求解：

（1）递归回溯方法；

（2）迭代回溯方法。(选)

2．对任意给定的n，要求输出其解向量（所有解），并输出其解数；

3．构造n后问题的解数表格（由程序自动生成）:

class CQueen

{

public:

    CQueen(); //缺省构造函数

    CQueen(int n);

    ~CQueen();

    void SetN(int n);

    void ToPrintAll(); //求出所有的解并输出

    void ToPrint(int m); //输出前m个解;

void ToGetFirstAndSum(); //求出所有解的总和及第一个解; (为了生成以上所示的表格)

private:

    int m_n; //皇后数

    long m_sum;//总解数;

    int *m_x;  //解向量;

    int *m_FirstX;  //第一个解向量;

    bool m_bPlace(int k); //当主生了x[0]..x[k-1]时，判断x[k] 能否放置

    void BackTrack(int t);// BackTrack-Method

    //为了输出前m个解，可能需要增加其它的变量

};

[综合实验五](选做)最大子段和问题的求解

问题：对任意动态生成的n 个整数（可含负数），求最大子段及其和。

具体要求：

1．采用至少三种方法进行求解：

(1) 蛮力方法（枚举方法）;

(2) 分治策略；

（3）动态规划方法。

2．对算法和数据进行类的封装，编写好构造函数和析构函数；

3．对任意给定的n个整数，要求对以上的三种算法，都能够输出最大子段及其和。

注：教材中，对于分治策略及动态规划方法，并没有给出最大子段，只是给出了最大子段和；请注意在编写算法程序时的实现。

class CMaxSum

{

private:

    int *m_a;//存储n个整数;

    int m_n;

    int m_i,m_j;//最大子段

public:

    CMaxSum();

    ~CMaxSum();

    void ToIni();//初始化整数序列

    void BruteForce();//蛮力方法

    void DivideAndConquer(); //需要另一个递归算法

    void DynamicProg();//Dynamic Programming 动态规划算法

    void Output(); //输出解

};

 [综合实验六] (选做)背包问题的贪心算法

问题: 

给定如下n种物品的编号，及其价值；背包重量为c, 求最佳装包方案，才能使其装入背包的价值最大。

1．将背包问题进行类的封装；

2．能对任意给定的n种物品的重量、价值及背包限重，输出以上表格( 或纵向输出)；

3．输出背包问题的解；

4．本题要求采用STL库中的排序算法数据进行排序。

[综合实验 七] (选做)多机调度问题

    此问题是一个NP完全问题，到现在为止还没有一个有效的解法。对于这个问题，可以采用贪心算法，往往可以设计出较好的近似解法。解决此问题可以利用堆结构或优先队列数据结构。本实验要求，对于给定的任意n个作业，在m台机器上进行操作，求其最佳的任务调度方案。

    具体要求：

(1) 设计代表工作和机器的Ｃ＋＋类型；

(2) 采用C++提供的标准库中的优先队列 priorigy_quere组织数据；

(3) 作业数n及机器数m可任意指定，作业 i 的加工时间可由随机函数rand()生成；

(4) 以较为规范的形式输出条件及计算结果。

[综合实验 八] (选做) 0-1背包问题的求解

0-1背包问题有多种解法，如动态规划方法，回溯方法，分枝限界方法等。对于同一种问题，请参照教材中的算法，给出相应的程序实现。

[综合实验 九] (选做) 用分治策略解决棋盘覆盖问题

    教材中给出了基本的算法，同学们在实现时，应该有可视化的界面，且要求对任意的k, 以及特殊方格的位置进行设定，求出相应的解及图示。

（1）建议采用图形化的界面；

（2）或：在字符界面下，模拟棋盘。