算法设计实验报告讲解.docx
《算法设计实验报告讲解.docx》由会员分享，可在线阅读，更多相关《算法设计实验报告讲解.docx（41页珍藏版）》请在冰点文库上搜索。
算法设计实验报告讲解
华北电力大学
实验报告
|
|
实验名称算法设计与分析综合实验
课程名称算法设计与分析
|
|
专业班级：
学生姓名：
学号：
成绩：
指导教师：
实验日期：
[综合实验一]分治策略—归并排序
一、实验目的及要求
归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。
实验要求：
（1）编写一个模板函数：
template，MergeSort（T*a,intn）;以及相应的一系列函数，采用分治策略，对任意具有:
booloperator<（constT&x,constT&y）;比较运算符的类型进行排序。
（2）与STL库中的函数std:
:
sort（..）进行运行时间上的比较，给出比较结果,如：
动态生成100万个随机生成的附点数序列的排序列问题,给出所用的时间比较。
二、所用仪器、设备
计算机、VisualC++软件。
三、实验原理
分治原理：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。
当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。
对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。
如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。
这就是分治策略的基本思想。
归并原理：
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
四、实验方法与步骤
归并过程为：
比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
实现时间计量：
#define_CLOCK_T_DEFINED
srand（（unsigned）time（0））;
//定义一数组a[n];对每一个赋予一值。
a[i]=rand（）;得到随即数。
duration=（double）（finish-start）/CLOCKS_PER_SEC;
start=clock（）;将系统时间赋予Start。
以便以后进行比较。
std:
:
sort（b,b+1000）;系统执行1000个数据。
Finish-Start为最终结果。
五、实验结果与数据处理
实验结果截图：
实验代码：
#include
#include
#include
#include
#include
usingnamespacestd;
template
voidMergSort（Typea[],intn）{
Type*b=newType[n];
ints=1;
while（sMergPass（a,b,s,n）;
s+=s;
MergPass（b,a,s,n）;
s+=s;
}
}
template
voidMergPass（Typex[],Typey[],ints,intn）
{
inti=0;
while（i<=n-2*s）
{
Merg（x,y,i,i+s-1,i+2*s-1）;
i=i+2*s;
}
if（i+sMerg（x,y,i,i+s-1,n-1）;
else{
for（intj=i;j<=n-1;j++）{
y[j]=x[j];
}
}
}
template
voidMerg（Typec[],Typed[],intl,intm,intr）{
inti=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（intq=j;q<=r;q++）
d[k++]=c[q];
else
for（intq=i;q<=m;q++）
d[k++]=c[q];
}
floatrandf（floatbase,floatup）{
return（rand（）%（int）（（up-base）*RAND_MAX））/（float）RAND_MAX;//产生随机数
}
voidprintArray（float*a,intN）{
for（inti=0;i<=N;i++）{
if（（i%8==0）&&（i>0））
{
cout<}
else{
cout<}
}
}
voidmain（）{
intArrayLen=5;
cout<<"请输入元素个数：
"<cin>>ArrayLen;
float*array=newfloat[ArrayLen];
float*arrays=newfloat[ArrayLen];
floatmn,ene;
printf（"数组已建立：
\n"）;
srand（（unsigned）time（NULL））;//设置随机数的seed
for（inti=0;i{
mn=（float）rand（）;//产生小数
ene=randf（1,10000）+mn;
arrays[i]=ene;
array[i]=ene;
}
//cout<<"需要排序的归并数组:
\n";
//printArray（array,ArrayLen）;
intflag=1;
while（flag!
=0）{
cout<<"\n输入需要显示的排序方法：
"<cout<<"1.归并排序2.std排序0.退出"<cin>>flag;
switch（flag）{
case0:
break;
case1:
{
clock_ts=0,e=0;
s=clock（）;
MergSort（array,ArrayLen）;
e=clock（）;
//cout<<"排序后的序列为：
"<//printArray（array,ArrayLen）;
cout<<"\nMergSort运行了：
"<<（e-s）<<"ms"<break;
}
case2:
{
clock_tstart1=0,end1=0;
start1=clock（）;
std:
:
sort（&arrays[0],&arrays[ArrayLen]）;
end1=clock（）;
//printArray（array,ArrayLen）;
cout<<"\nstd:
:
sort运行了：
"<<（end1-start1）<<"ms"<break;
}
}
}
}
[综合实验二]贪心算法—Huffman树及Huffman编码
一、实验目的及要求
一个记录字符及出现频率的文件如下所示：
huffman.haf
7
a,45
b,13
c,12
d,16
e,89
f,34
g,20
试编写一个读取此种格式文件类CHuffman,内部机制采用优先队列，用于建立Huffman树及进行Huffman编码输出，其用法可以如下所示：
CHuffmanhm（"huffman.dat"）;
hm.CreateTree（）;
hm.OutputTree（）;
hm.OutputCode（）;//二进制形式的字符串
对于输出树的形式可自行决定（如图形界面或字符界面）。
二、所用仪器、设备
计算机、VisualC++软件。
三、实验原理
贪心原理：
（1）随着算法的进行，将积累起其它两个集合：
一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
（2）有一个函数来检查一个候选对象的集合是否提供了问题的解答。
该函数不考虑此时的解决方法是否最优。
（3）还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。
和上一个函数一样，此时不考虑解决方法的最优性。
（4）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
（5）最后，目标函数给出解的值。
（6）为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。
起初，算法选出的候选对象的集合为空。
接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。
如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。
每一次都扩充集合，并检查该集合是否构成解。
如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
Huffman原理：
给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（Huffmantree）。
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
四、实验方法与步骤
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
算法以个叶结点开始，执行次的“合并”运算后产生最终所要求的树T。
给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。
C的一个前缀码编码方案对应于一棵二叉树T。
字符c在树T中的深度记为。
也是字符c的前缀码长。
该编码方案的平均码长定义为：
B（T）使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。
一旦两棵具有最小频率的树合并后，产生的一颗新的树，起频率为合并的两棵树的频率之和，并将新树插入优先队列中。
优先队列，优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1）查找;2）插入一个新元素;3）删除.在最小优先队列（minpriorityqueue）中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列（maxpriorityqueue）,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.优先权队列中的元素可以有相同的优先权,查找与删除操作可根据任意优先权进行.
五、实验结果与数据处理
主要代码如下：
Huffman:
:
Huffman（char*sFileName1）
{
this->sFileName=sFileName1;
ifstreamfin（sFileName）;
charch[4];
fin.getline（ch,4）;
intn1=atoi（ch）;
cout<<"节点数目:
"<this->n=n1;
this->t=newTHaffmanNode[2*n1-1];
this->nNext=n1;
charch1;
for（inti=0;i{
fin.get（ch1）;
t[i].c=ch1;
fin.ignore（100,','）;
fin.getline（ch,4）;
t[i].f=atoi（ch）;
}
for（inti=0;i{
cout<}
for（inti=0;i{
t[i].idx=i;
PQ.push（t[i]）;
}
while（!
PQ.empty（））
{
if（（PQ.size（））>=2）
{
THaffmanNodenn,nr,nl;
nl=PQ.top（）;
PQ.pop（）;
nr=PQ.top（）;
PQ.pop（）;
nn.f=nl.f+nr.f;
nn.l=nl.idx;
nn.r=nr.idx;
nn.idx=nNext++;
t[nl.idx].p=nn.idx;
t[nr.idx].p=nn.idx;
t[nn.idx]=nn;
PQ.push（nn）;
}
else
{
t[2*n-2].p=-1;
break;
}
}
}
Huffman:
:
~Huffman（void）
{
}
voidHuffman:
:
OutputTree（）
{
for（inti=0;i<2*n-1;i++）
{
cout<<"权重：
"<cout<<"左孩子：
"<cout<<"右孩子：
"<cout<<"父节点：
"<cout<<"在数组的位置：
"<}
//现在数组中存的是哈弗曼数
}
voidHuffman:
:
OutputCode（）
{
//用stack来依次记录各编码的01编码
std:
:
stack:
list>sk;
THaffmanNodentemp,ntemp1;
for（inti=0;i{
ntemp=t[i];
while（ntemp.p!
=-1）
{
ntemp1=t[ntemp.p];
if（t[ntemp1.l].idx==ntemp.idx）
{
sk.push（0）;
ntemp=ntemp1;
}
else
{
sk.push
（1）;
ntemp=ntemp1;
}
}
inti1=sk.size（）;
cout<";
for（inti=0;i{
cout<sk.pop（）;
}
cout<}
}
实验结果截图：
[综合实验三]用回溯方法求解n后问题
一、实验目的及要求
问题：
对任意给定的n求解n后问题。
具体要求：
1．封装n后问题为类，编写以下两种算法进行求解：
（1）递归回溯方法；
（2）迭代回溯方法。
（选）
2．对任意给定的n，要求输出其解向量（所有解），并输出其解数；
3．构造n后问题的解数表格（由程序自动生成）:
n后数
解数
第一个解
4
2
（2,4,1,3）
5
…
…
6
…
…
…
…
…
二、所用仪器、设备
计算机、VisualC++软件。
三、实验原理
回溯原理：
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。
回溯算法的基本思想是：
从一条路往前走，能进则进，不能进则退回来，换一条路再试。
用回溯算法解决问题的一般步骤为：
1、定义一个解空间，它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
四、实验方法与步骤
n后问题等于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
即规定每一列放一个皇后，不会造成列上的冲突；当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。
K：
第K个皇后，也表示第K行
X[i]：
第K个皇后在第K行的第i列
皇后k在第k行第x[k]列时，x[i]==x[k]时，两皇后在同一列上;abs（x[i]-x[k]）==abs（i-k）时，两皇后在同一斜线上;两种情况两皇后都可相互攻击，返回false表示不符合条件。
五、实验结果与数据处理
实验结果截图：
实验代码：
#include
#include
classQueen
{
friendintnQueen（int）;
private:
boolPlace（intk）;
voidBacktrack（intt）;
intn,*x;//当前解
longsum;//当前已找到的可行方案数
};
boolQueen:
:
Place（intk）
{
for（intj=1;jif（（abs（k-j）==abs（x[j]-x[k]））||（x[j]==x[k]））returnfalse;
returntrue;
}
voidQueen:
:
Backtrack（intt）
{
if（t>n）
{
sum++;//达到叶结点
for（inti=1;i<=n;i++）
{
cout<}
cout<for（i=1;i<=n;++i）
{
for（intj=1;j<=n;++j）
{
if（x[i]!
=j）
cout<<".";
else
cout<<"#";
}
cout<}
cout<}
else
for（inti=1;i<=n;i++）{//搜索子结点
x[t]=i;//进入第i个子结点
if（Place（t））Backtrack（t+1）;
}
}
intnQueen（intn）
{
QueenX;
//初始化X
X.n=n;
X.sum=0;
int*p=newint[n+1];
for（inti=0;i<=n;i++）
p[i]=0;
X.x=p;
X.Backtrack
（1）;//对整个解空间回溯搜索
delete[]p;
returnX.sum;
}
voidmain（）
{
inta=0,b=0;
cout<<"********欢迎进入皇后问题*********"<intflag=1;
while（flag）{
cout<<"请输入皇后数"<cin>>a;
b=nQueen（a）;
cout<<"方案个数：
"<cout<<"是否继续？
1为是，0为否"<cin>>flag;
}
}
[综合实验四]背包问题的贪心算法
一、实验目的及要求
问题:
给定如下n种物品的编号，及其价值；背包重量为c,求最佳装包方案，才能使其装入背包的价值最大。
物品编号
1
2
…
n
重量
w[1]
w[2]
..
w[n]
价值
v[1]
v[2]
…
v[n]
具体要求：
将背包问题进行类的封装；
能对任意给定的n种物品的重量、价值及背包限重，输出以上表格（或纵向输出）；
输出背包问题的解；
本题要求采用STL库中的排序算法数据进行排序。
二、所用仪器、设备
计算机、VisualC++软件。
三、实验原理
贪心算法解决背包问题有几种策略：
（1）一种贪心准则为：
从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。
这种策略不能保证得到最优解。
例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105。
当利用价值贪婪准则时，获得的解为x=[1,0,0]，这种方案的总价值为20。
而最优解为[0,1,1]，其总价值为30。
（2）另一种方案是重量贪心准则是：
从剩下的物品中选择可装入背包的重量最小的物品。
虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。
考虑n=2,w=[10,20],p=[5,100],c=25。
当利用重量贪婪策略时，获得的解为x=[1,0], 比最优解[0,1]要差。
（3）还有一种贪心准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
四、实验方法与步骤
首先计算每种物品单位重量的价值Vi/Wi，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超出C，则选择单位重量价值次高的物品，并尽可能多的装入背包。
依此策略一直进行下去，直到背包装满为止。
采用贪婪准则：
每次选择p/w最大的物品放入背包。
注意在这之前的计算每种物品单位重量的价值Vi/Wi后，进行排序。
五、实验结果与数据处理
实验截图：
主要代码如下：
#include
#defineM4
structnode{
floatno;//编号
升级会员 