计算机算法设计与分析实验报告大学论文.doc

华北电力大学
实 验 报 告
|
|

实验名称 算法设计实验
课程名称 算法设计与分析
|
|
专业班级：信安1301 学生姓名：
学 号： 成 绩：
指导教师：胡朝举 实验日期： 2015年11月

华 北 电 力 大 学 实 验 报 告
实验一、归并排序(Merging Sort)——分治策略
一、  实验内容
归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求：
（1）编写一个模板函数：
template <typename T>
MergeSort(T *a, int n);
以及相应的一系列函数，采用分治策略，对任意具有:
bool operator<(const T&x,const T&y);
比较运算符的类型进行排序。
（2） 与STL库中的函数std::sort(..)进行运行时间上的比较，给出比较结果,如：动态生成100万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。
归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。
二、 主要思想
假设初始序列含有n个记录，则可看成n个有序的子序列，每个字序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，...，如此重复，直到一个长度为n的有序序列为止。
例 已知待排序记录的关键字序列为{49,38,65,97,76,13,27}，给出2-路归并排序法进行排序的过程

2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。相邻两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上：R[low..mid]和R[mid+1..high]，每次分被从两个表中取出一个记录进行关键字的比较，将较小者放入T[low..high]中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。
三、  实验结果
四、 算法分析
1)时间复杂度
当有n个记录时，需进行[log2n]趟归并排序,每一趟归并,其关键字比较次数不超过n,元素移动次数都是n,因此,归并排序的时间复杂度为O(nlog2n)。
2)空间复杂度
用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为O(n);
五、  实验代码
#include<iostream.h>
#include<algorithm>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
template<class Type>
void MergSort(Type a[], int n){
Type *b = new Type[n];
int s = 1;
while (s < n){
MergPass(a, b, s, n);
s += s;
MergPass(b, a, s, n);
s += s;
}
}
template<class Type>
void MergPass(Type x[], Type y[], int s, int n)
{
int i = 0;
while (i <= n - 2 * s)
{
Merg(x, y, i, i + s - 1, i + 2 * s - 1);
i = i + 2 * s;

}
if (i + s < n)
Merg(x, y, i, i + s - 1, n - 1);
else{ //如果剩下的不够i+s，则把剩下的放入y中
for (int j = i; j <= n - 1; j++){
y[j] = x[j];
}
}
}
template<class Type>
void Merg(Type c[], Type d[], int l, int m, int r){
int i = l, j = m + 1, k = l;
while ((i <= m) && (j <= r)){
if (c[i] <= c[j])
d[k++] = c[i++];
else
d[k++] = c[j++];

}
if (i>m)
for (int q = j; q <= r; q++)
d[k++] = c[q];
else
for (int q = i; q <= m; q++)
d[k++] = c[q];
}

float randf(float base, float up){

return (rand() % (int)((up - base) * RAND_MAX)) / (float)RAND_MAX ; //产生随机数
}
void printArray(float *a,int N){
for(int i=0;i<=N;i++){
cout<<a[i]<<endl;
}
}

void main(){
int ArrayLen = 5;
float *array = new float[ArrayLen];
float *arrays = new float[ArrayLen];
float mn, ene;
printf("数组已建立： \n");
srand((unsigned)time(NULL)); //设置随机数的seed

for (int i = 0; i < ArrayLen; i++)
{
mn = (float)rand(); //产生小数
ene = randf(1,10000)+mn;
arrays[i] =ene;
array[i] = ene;
}

int fflag = 2;
while (fflag != 0)
{
printf("输入需要显示的归并数组：\n 1.归并排序 0.exit\n");
cout<<"需要显示的归并数组:";
printArray(array, ArrayLen);
cin>>fflag;
switch (fflag)
{
case 0:
break;
case 1:
MergSort(array, ArrayLen);
printArray(array, ArrayLen);
break;
}
}
printf("=========================================\n");
printf("\n");
clock_t s = 0, e = 0;
s = clock();
MergSort(array, ArrayLen);
e = clock();
cout << "MergSort运行了：" << (e - s) << "ms" << endl;
clock_t start1 = 0, end1 = 0;
start1 = clock();
std::sort(&arrays[0], &arrays[ArrayLen]);
end1 = clock();
cout << "std::sort运行了：" << (end1 - start1) << "ms" << endl;
int flag = 1;
while (flag != 0){
cout<<"输入需要显示的排序方法："<<endl;
cout << "1.归并排序 0.exit" << endl;
cin >> flag;
switch (flag){
case 1:
printf("归并排序序列:\n");
MergSort(array, ArrayLen);
printArray(array, 5);
break;
case 0:
break;
}
}
}

[综合实验 二]贪心算法—Huffman树及Huffman编码
一． 实验内容
一个记录字符及出现频率的文件如下所示：
huffman.haf
7
a,45
b,13
c,12
d,16
e,9
f,5
试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：
CHuffman hm("huffman.dat");
hm.CreateTree();
hm.OutputTree();
hm.OutputCode(); //二进制形式的字符串
对于输出树的形式可自行决定(如图形界面或字符界面)。

二、 主要思想
该程序已封装为类在HuffmanCode.cpp中，该代码读取E:\h.dat路径下的数据文件，可以更改为用户输入的指定路径，但鉴于算法核心功能已经实现，不再加强此功能。另一点，此程序在建立完哈夫曼树后，不是使用遍历二叉树求解的方法而是使用直接从叶子节点出发，直接沿路径返回至根节点进行哈夫曼编码确定，不足之处是，结构体中多加了存储字段，消耗了更多内存。此外，向量已经给出了类似栈的操作，直接利用这一点，模仿优先队列进行操作，具体说明及实现在注释中已给出。
这个霍夫曼编码本身用到了贪心的思想，所以也在这里列举了出来。这个问题本身在计算机系的很多教材上都出现过。这里权且记录下来。霍夫曼的编码是这样的。假设我有一组带压缩的文本，里面各个字符出现的频率不同，现在需要对他们进行压缩。比如

假设我们有100,000个字符的文本.最直观的压缩办法就是原来每个字符要8个bits。现在我一共只有6个字符，那我就把每个字符用3个二进制 位来表示，这样所有100,000个字符用300,000个bit就可以表示了。这种是最直观的方案。但是霍夫曼提出的方案更精妙一些。他提出，基于每个 字符出现的频率不同，可以让出现次数多的字符用更少的二进制位来描述，出现次数少的字符用多一些二进制来描述。比如上图显示的这个Variable-length codeword里面。a出现的频率最高，所以用一个二进制位0来表示。而f出现的频率很小，所以用4个二进制位来表示。这样总共(45 · 1 + 13 · 3 + 12 · 3 + 16 · 3 + 9 · 4 + 5 · 4) · 1,000 = 224,000 bits。可以看到这个是比原来的方案更优化的解法。
我们一样的还是用一张图来描述霍夫曼编码的流程：

这个过程概括的说就是一个根据频率建立二叉树的过程。建完之后对应的编码也就完成了。
第一步a. 这个a就和之前的活动选择问题一样，把需要的所以字符按照频率排序。
第二部b. 选取出现频率最小的两个节点 f 和e。组成一个新的节点，新的节点的频率就是e和f的和。原来的e和f分别成了新节点的左子节点和右子节点。(注意这里一个默认的规则就是频率小的是左子节 点，大的是右子节点。)然后把之前的两个节点从原来的组中删除，加新的节点加入排序。
第三部c. 其实和第二部雷同，就是一个循环的过程。这里再次去除队列中的最小频率的两项（这时是c和b）。组成新的节点加入队列排序。
如此循环往复，最后就形成了(f)这个二叉树。现在有了二叉树只有，我们把左子树这条边标记为0，右子树标记为1。这样就差生了对应的编码方式 a=0; b=101;....
三、 实验结果
四、算法分析
五、实验代码
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
struct Node
{
char Content;
float Frequency;
Node*Left;
Node*Right;
Node*Parent;
string Code;//编码串
char LOR;//该节点作为左孩子（0）还是右孩子（1）
};
bool Compare(Node*a,Node*b){
return a->Frequency>b->Frequency;
}
class HuffmanCode
{
public:
vector<Node*>Show;//显示结果的向量
//输入文件绝对路径
HuffmanCode(char*file);
~HuffmanCode();
void Executing();
private:
char*FilePath;
Node*Root;//哈夫曼树根节点
vector<Node*>AsQueue;//作为队列的向量
//读取文件内容,扫描字符出现频率，形成初始队列
void ReadAndScan();
//生成哈夫曼树
void CreateHuffmanTree();
//设置编码
void ErgodicTree();
//释放节点
void Delete(Node*n);
};
HuffmanCode::HuffmanCode(char*file)
{
FilePath=file;
}
HuffmanCode::~HuffmanCode()
{
//释放节点
Delete(Root);
}
void HuffmanCode::Executing(){
//读取文件内容,扫描字符出现频率，形成初始队列
ReadAndScan();
//生成哈夫曼树
CreateHuffmanTree();
//遍历整棵树并设置编码
ErgodicTree();
}
//读取文件内容,扫描字符出现频率，形成初始队列
void HuffmanCode::ReadAndScan(){
ifstream fin;
fin.open("E:\\h.dat",ios::binary);
string str;
fin>>str;
fin.close();
bool used;
int temp1,temp2;
temp1=str.length();
for(int i=0;i<temp1;i++)
{
used=false;
temp2=AsQueue.size();
for(int j=0;j<temp2;j++)
{
if(AsQueue[j]->Content==str[i])
{
AsQueue[j]->Frequency++;
used=true;
break;
}
}
if(!used)
{
Node*n=new Node();
n->Content=str[i];
n->Frequency=1;
n->Left=NULL;
n->Right=NULL;
AsQueue.push_back(n);
}
}
sort(AsQueue.begin(),AsQueue.end(),Compare);
temp2=AsQueue.size();
for(int i=0;i<temp2;i++)
{
Show.push_back(AsQueue[i]);
}
}
//生成哈夫曼树
void HuffmanCode::CreateHuffmanTree(){
while(AsQueue.size()!=1)
{
int s=AsQueue.size()-1;
Node*n=new Node();
n->Frequency=AsQueue[s]->Frequency+AsQueue[s-1]->Frequency;
n->Left=AsQueue[s];
AsQueue[s]->LOR='0';
n->Right=AsQueue[s-1];
AsQueue[s-1]->LOR='1';
AsQueue[s]->Parent=n;
AsQueue[s-1]->Parent=n;
AsQueue._Pop_back_n(2);
AsQueue.push_back(n);
sort(AsQueue.begin(),AsQueue.end(),Compare);
}
Root=AsQueue[0];
Root->LOR=-1;
}
//设置编码
void HuffmanCode::ErgodicTree(){
//从叶子节点向树顶端搜索直至根节点获取编码
int temp=Show.size();
for(int i=0;i<temp;i++)
{
Node*n=Show[i];
string c;
while(-1!=n->LOR)
{
c.push_back(n->LOR);
n=n->Parent;
}
int temp2=c.size();
for(int j=temp2-1;j>-1;j--)
{
Show[i]->Code.push_back(c[j]);
}
}
}
//释放节点
void HuffmanCode::Delete(Node*n){
if(n->Left)
{
Delete(n->Left);
}
if(n->Left)
{
Delete(n->Right);
}
delete n;
}
[测试代码段]
void main(){
HuffmanCode h("E:\\h.dat");
h.Executing();
vector<Node*>n=h.Show;
int k=n.size();
string b;
for(int i=0;i<k;i++)
{
cout<<n[i]->Content<<""<<n[i]->Frequency<<""<<n[i]->Code<<endl;
}
}

[综合实验三]用回溯方法求解n后问题
一、 实验内容
问题：对任意给定的n求解n后问题。
具体要求：
1．封装n后问题为类，编写以下两种算法进行求解：
（1）递归回溯方法；
（2）迭代回溯方法。(选)
2．对任意给定的n，要求输出其解向量（所有解），并输出其解数；
3．构造n后问题的解数表格（由程序自动生成）:
n 后数
解数
第一个解
4
2
(2,4,1,3)
5
…
…
6
…
…
…
…
…
参考类的封装如下：
二、  主要思想
（1）问题描述
在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

（2）算法设计思想
1.要解决n皇后问题，其实就是要解决好怎么放置这n个皇后，每一个皇后与前面的所有皇后不能在同一行、同一列、同一对角线，在这里我们可以以行优先，就是说皇后的行号按顺序递增，只考虑第i个皇后放置在第i行的哪一列，所以在放置第i个皇后的时候，可以从第1列判断起，如果可以放置在第1个位置，则跳到下一行放置下一个皇后。如果不能，则跳到下一列...直到最后一列，如果最后一列也不能放置，则说明此时放置方法出错，则回到上一个皇后向之前放置的下一列重新放置。这也就是回溯法遍历所有可行解的一个搜索方式。当第n个皇后放置成功后，即得到一个可行解，此时再回到上一个皇后重新放置寻找下一个可行解...如此后，即可找出一个n皇后问题的所有可行解。

2.设计剪枝函数：
可以用n元组x[1:n]来表示n后问题的解，其中x[i]表示皇后i放在棋盘的第i行的第x[i]列。
由于不允许两个皇后在同一列上，所以解向量中的x[i]互不相同。对于任意两个皇后不能在同一对角线上这个条件，可以这样来表示：
对n*n的方阵，两个皇后的位置分别是（i,j）和（k,l），则若有i-k=k-l或i+j=k+l,则说明这两皇后处于同一条对角线上。以上两个方程可以一起表示为|i-k|=|j-l|,若此式成立，则说明两个皇后位于同一条对角线上。可以利用这一个条件来设计相应的剪枝函数。

3．用回溯法解决n后问题时，使用完全n叉数来表示解空间，利用剪枝函数Place（）来剪去不满足条件的子树。利用一个Backtrack（）函数实现对整个解空间的回溯搜索，使用sum记录当前已经找到的可行方案数。
三、 实验结果

四、 实验代码
动态规划算法解决矩阵连乘问题源程序代码
#include <iostream>
using namespace std;

int MatrixChain(int n, int **m, int **s, int *p);
void Traceback(int i, int j, int **s);

int main()
{
int n;
cout << "请输入矩阵数量n：";
cin >> n;
int *p = new int[n + 1];
int **s = new int *[n + 1];
int **m = new int *[n + 1];
for (int i = 0; i<n + 1; i++)
{
s[i] = new int[n + 1];
m[i] = new int[n + 1];
}
cout << endl;
cout << "输入" << n + 1 << "个数据：\n";
for (int i = 0; i <= n; i++)
{
cout << "第" << i + 1 << "个数据" << endl;
cin >> p[i];
}
cout << "矩阵的最少计算次数为：" << MatrixChain(n, m, s, p) << endl;
cout << "矩阵最优计算次序为：" << endl;
Traceback(1, n, s);
system("pause");
return 0;
}

int MatrixChain(int n, int **m, int **s, int *p)
{
for (int i = 1; i <= n; i++)
{
m[i][i] = 0;
}
for (int r = 2; r <= n; r++)
{
for (int i = 1; i <= n - r + 1; i++)
{
int j = i + r - 1;

m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];

s[i][j] = i;

for (int k = i + 1; k<j; k++)
{
int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (t<m[i][j])
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
return m[1][n];
}

void Traceback(int i, int j, int **s)
{
if (i == j) return;
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j, s);
cout << "Multiply A" << i << "," << s[i][j];
cout << " and A" << (s[i][j] + 1) << "," << j << endl;
}

回溯法解决n后问题源程序代码
#include <iostream>
#include<math.h>
using namespace std;
class Queen
{
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n, //皇后个数
*x; //当前解
long sum; //当前已找到的可行方案数
};
bool Queen::Place(int k)
{
for (int j = 1; j<k; j++)
{
if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))
{
return false;
}
}
return true;
}
void Queen::Backtrack(int t)
{
if (t>n)
{
sum++;
for (int i = 1; i <= n; i++)
{
cout << "x[" << i << "]=" << x[i] << " ";
}
cout << endl;
}
else
{
for (int i = 1; i <= n; i++)
{
x[t] = i;
if (Place(t))
{
Backtrack(t + 1);
}
}
}
}
int nQueen(int n)
{
Queen X;
//初始化X
X.n = n;
X.sum = 0;
int *p = new int[n + 1];
for (int i = 0; i <= n; i++)
p[i] = 0;
X.x = p;
X.Backtrack(1);
delete[]p;
return X.sum;
}
void main()
{
cout << "Question n queen,please input n:";
int p, q;
cin >> p;
q = nQueen(p);
cout << "The number of the solution is:" << q << endl;
system("pause");
}

[综合实验四] 背包问题的贪心算法
一、 实验内容
问题:
给定如下n种物品的编号，及其价值；背包重量为c, 求最佳装包方案，才能使其装入背包的价值最大。
物品编号
1
2
…
n
重量
w[1]
w[2]
..
w[n]
价值
v[1]
v[2]
…
v[n]
具体要求：
1． 将背包问题进行类的封装；
2． 能对任意给定的n种物品的重量、价值及背包限重，输出以上表格( 或纵向输出)；
3． 输出背包问题的解；
4． 本题要求采用STL库中的排序算法数据进行排序。

二、  主要思想
三、 实验结果
四．实验代码
#include "stdafx.h"
#include<iostream>
using namespace std;
class beibao
{
public:
void chushishuzu();
void jiazhipaixu();
void shuchuxulie();

private:
int n;//物件个数
double v[20];//价值数组
double w[20];//质量数组
double c[20];//单位价值数组
double m;//背包质量
int y[20];//排序数组
double x[20];//物件分量
};
void beibao::chushishuzu()//初始化背包
{
cout << "请输入物件个数：" << endl;
cin >> this->n;
cout << "请依次输入价值：" << endl;
for (int i = 1; i <this->n + 1; i++)
{
cin >>this-> v[i];
}
cout << "请依次输入质量：" << endl;
for (int i = 1; i <this->n + 1; i++)
{
cin >>this-> w[i];
}
cout << "请输入背包质量" << endl;
cin >>this-> m;
}
void beibao::jiazhipaixu()//背包排序
{
for (int i = 1; i < this->n + 1; i++)
{
this->c[i] = this->v[i] / this->w[i];
}
int max = 0;
for (int i = 1; i <this->n + 1; i++)
{
max = 1;
for (int j = 1; j <this->n + 1; j++)
{
if (this->c[max] < this->c[j])
max = j;
}
this->c[max] = 0;
this->y[i] = max;
}

cout << "按单位价值排序为：" << endl;
for (int i = 1; i <this->n + 1; i++)
{
cout << this->w[y[i]] << " 　";
}
cout<<endl;
}
void beibao::shuchuxulie()//输出背包序列
{
for (int i = 1; i <this->n + 1; i++)
this->x[i] = 0;
int i = 0;
for (i = 1; i<this->n + 1; i++)
{
if (this->w[y[i]]>this->m)
break;
this->x[i] = 1;
this->m = this->m - this->w[y[i]];
}
if (i <= n) this->x[i] = this->m / this->w[y[i]];
cout << "输出分量为：" << endl;
for (i = 1; i < this->n + 1; i++)
{
cout << this->x[i] << " ";
}
}

void main()
{
beibao a;
a.chushishuzu();
a.jiazhipaixu();
a.shuchuxulie();
system("pause>nul");
}
五、实验心得
通过本次实验，我较为透彻的理解了动态规划算法的几个基本步骤。完成实验后，我认为建立递归关系是很关键的一步，同时也是整个动态规划算法的精髓。掌握了递归的思想，就可以完成很多不必要的重复计算。虽然已经了解了动态规划算法的基本思想，而且也参考了书上的算法，但是实际的情况却并不是那么顺利，我按照书上编写程序之后，发生了很多错误，所以出现了一系列的问题。我也体会到，想要理解一个新的算法，必须要通过自己不断的编写程序，不断的思考才能真正的领悟，因此我会不断朝着这个方向努力。

[实验五](选做)矩阵连乘问题
一、 实验内容
矩阵连乘问题，给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,An。
二、 主要思想
由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已经完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为： (1) 单个矩阵是完全加括号的；(2) 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。
运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行：
1、分析最优解的结构
设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在Ak和Ak+1之间将矩阵链断开，1≤k≤n,则其相应的完全加括号方式为((A1…Ak)(Ak+1…An))。依此次序，先计算A[1:k]和A[k+1:n],然后将计算结果相乘得到A[1:n]。
2、建立递归关系
设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A[i:j]，1≤i≤j≤n，所需的最少数乘次数为m[i][j]，原问题的最优值为m[1][n]。
当i=j时，A[i:j]=Ai为单一矩阵，无需计算，因此m[i][i]=0，i=1,2,…n。
当i<j时，可利用最优子结构性质来计算m[i][j]。m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。由于在计算时并不知道断开点k的位置，所以k还未定。
3、计算最优值
根据计算m[i][j]的递归式，容易写一个递归算法计算m[1][n]。动态规划法解决此问题，可依据递归式以自底向上的方式进行计算，在计算过程中保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法matrixChain。(见实验代码部分)。
4、构造最优解
算法matrixChain只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。S[i][j]中的数表明