算法设计与分析实验报告文档格式.docx
《算法设计与分析实验报告文档格式.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告文档格式.docx（19页珍藏版）》请在冰点文库上搜索。
r。
该过程假设A[p..q]和A[q+1..r]都已排序，并将它们合并成一个已经排好序的子数组代替当前子数组A[p..r]。
函数模板的声明是在关键字template后跟随一个或多个模板在尖括弧内的参数和原型。
与普通函数相对，它通常是在一个转换单元里声明，而在另一个单元中定义，你可以在某个头文件中定义模板。
template＜classT＞Tmax（Tt1,Tt2）
{return（t1＞t2）?
t1:
t2;
}
＜classT＞定义T作为模板参数，或者是占位符，当实例化max（）时，它将替代具体的数据类型。
max是函数名，t1和t2是其参数，返回值的类型为T。
你可以像使用普通的函数那样使用这个max（）。
proceduremergesort（varr,r1:
listtype;
s,t:
integer）
{r,r1：
均为链表，存储排序数据；
过程mergesort（r,r1,s,t）完成把链表r中的关键字进行归并排序、并存放到链表r1中，其中s是下界t是上界}<
BR>
{过程merge（r2,s,m,t,r1）把链表r2中排好序的子链r2[s..m]和子链r2[m+1..t]合并到r1中}。
实现时间计量：
#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<
iostream.h>
time.h>
#include<
algorithm>
#ifndef_CLOCK_T_DEFINED
#definelongclock_t;
#endif
voidMSort（Tr[],Tr1[],ints,intt）
{
if（s=t）
r1[s]=r[s];
else
{
intm=（s+t）/2;
MSort（r,r1,s,m）;
MSort（r,r1,m+1,t）;
Merge（r,r1,s,m,t）;
for（inti=1;
i<
=t;
i++）
r1[i]=r[i];
}
template<
voidMerge_sort（Tr[],Tr1[],intn）
MSort（r,r1,1,n）;
voidMerge（Tr[],Tr1[],ints,intm,intt）
inti=s;
intk=s;
intj=m+1;
while（（i<
=m）&
&
（j<
=t））
if（r[i]<
=r[j]）
r1[k]=r[j];
j=j+1;
if（i<
m）
for（intq=j;
q<
q++）
r[q]=r1[q];
for（intq=i;
=m;
r1[q]=r[q];
voidmain（）
int*r=newint[1000000];
int*a=newint[1000000];
int*r1=newint[1000000];
=1000000;
r[i]=rand（）;
a[i]=r[i];
longstart,finish;
doubleduration;
Merge_sort（r,r1,1000000）;
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
cout<
<
"
算法时间：
duration<
s"
endl;
start=clock（）;
std:
sort（a,a+1000000）;
sort函数时间：
动态规划--格路问题
格路问题有多种方法求解，可采用多种方法求解，如：
（1）动态规划方法;
（2） 备忘录方法；
（3）递归方法。
基本要求：
（1）清晰地描述此问题；
（2）采用动态规划方法求解；
（3）给出相应类的封装及数据结构；
（4）输出运算后的二维表格，或输出最短路径（如:
写入一个文件）；
（5）格路的数据文件采用以下形式的格式：
griddata.txt
5,4//代表m+1,n+1
1,-12,-11,-14,-1-1,-1//最右边点为终点E
4,113,272,97,6-1,2
1,153,192,597,16-1,18
7,103,202,317,12-1,47//最左边点为起点O
这里：
第1行数据为逗号隔开的两个整数值，分别代表m+1,n+1即格路的列数与行数；
每行数据代表格路上的一行数据，每组数据代表相应的点向右，向上的距离（均为整数）。
动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
格路问题是求一起点到终点的最短路径。
采用递归算法可以解决，而且程序的代码教为简单，但是它的时间复杂度是很大的，因为每次求当前的最短路径的时候要不断地利用其子问题的比较来实现。
而采用动态规划的基本要素便是最优子结构性质和重叠子问题性质。
在算法的具体实现中试递归的定义最优值而且采用自底向上的方式计算最优值。
这样的方法在格路问题中的优势是很明显的，因此它的效率要比纯递归算法的高。
用（x,y）来表示坐标,用坐标来指示格路问题的解。
虽然最后没能成功输出结果。
但是通过对代码的编写基本了解了格路问题的基本思想。
以及动态规划这一重要解决问题的方法。
同时学习如何引入文件。
数据结构：
structTPoint{
intnUp,nRight;
intnShortest;
intnFrom;
TPoint（）:
nUp
（1）,nRight
（1）,nFrom（-1）{}
TPoint（intu,intr）:
nUp（u）,nRight（r）,nFrom（-1）{}
};
classCGridRoad
private:
intm,n;
TPoint**g;
public:
CGridRoad（）;
CGridRoad（char*sFileName）;
~CGridRoad（）;
//voidCreateGridFromKeyBoard（）;
voidCreateGridFromFile（charfile[]）;
voidCalculate（）;
voidOutputShortest（）;
贪心算法—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（）;
对于输出树的形式可自行决定（如图形界面或字符界面）。
贪心算法通过一系列的选择来得到一个问题的解。
它所作的每一个选择都是当前状态下某种意义的最好选择。
哈夫曼提出了一种构造哈夫曼前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
算法以个叶结点开始，执行次的“合并”运算后产生最终所要求的树T。
给定编码字符集C及其频率分布f，即C中任一字符c以频率f（c）在数据文件中出现。
C的一个前缀码编码方案对应于一棵二叉树T。
字符c在树T中的深度记为。
也是字符c的前缀码长。
该编码方案的平均码长定义为：
B（T）使平均码长达到最小的前缀码编码方案称为C的一个最优前缀码。
哈弗曼算法是自底向上的方式构造表示最优前缀码的二叉树。
以每个字符出现的频率作为键值的优先队列用在贪心算法选择中有效地确定当前要合并的两颗具有最小频率的树。
一旦两棵具有最小频率的树合并后，产生的一颗新的树，起频率为合并的两棵树的频率之和，并将新树插入优先队列中。
通过本次实验了解了贪心算法的基本思想，以及构建哈夫曼树的方法。
通过对优先队列的构建方法解决问题。
基本算法：
structHTNode
intl,r,p
charc;
floatf;
HTNode（）:
l（-1）,p（-1）,p（-1）,f（0）{}
intidx;
booloperator>
（ConstHTNode&
x,constHTNode&
y）
returnx.f>
y.f;
THNode
*t=newHTNode[2*n-1];
for（inti=0;
n;
t[i].c=N;
t[i].f=N;
t[i].idx=i;
priority-queue<
HTNode,vector<
HTNode>
greater<
THNode>
>
PQ;
PQ.push（t[i]）;
//以下生成N-1个内节点的标注，即左右父节点标注
for（inti=n;
2*n-1;
THNodel=PQ.top（）;
PQ.pop（）;
THNoder=PQ.top（）;
THNodep;
p.idx=i;
p.l=l.idx;
p.r=r.idx;
p.f=l.f+r.f;
t[l,idx].p=i;
t[r,idx].p=i;
t[i]=p;
PQ.push（p）;
代码：
#include
iostream>
fstream>
queue>
stack>
stdio.h>
list>
using
namespace
std;
struct
THaffmanNode
char
c;
int
idx;
l,r;
p;
f;
THaffmanNode（）:
idx
（1）,l（NULL）,r（NULL）,p（NULL）,c（0）,f（0）{}
class
CHuffman
THaffmanNode
nn,nr,nl/*,ntemp,ntemp1*/;
*sFileName;
FILE
*rf;
*t;
nNext;
CHuffman（）;
//读取此格式
CHuffman（char
*sFileName）;
CHuffman（int
t）;
void
CreateTree（）;
OutputTree（）;
OutputCode（）;
friend
bool
operator
>
（const
x,const
return
x.f>
priority_queue<
THaffmanNode,std:
vector<
THaffmanNode>
std:
greater<
~CHuffman（）;
CHuffman:
CHuffman（）
this->
n=0;
*sFileName1）
sFileName=sFileName1;
ifstream
fin（sFileName）;
ch[4];
fin.getline（ch,4）;
n1=atoi（ch）;
cout<
n1<
n=n1;
t=new
THaffmanNode[2*n1-1];
nNext=n1;
ch1;
for
（int
i=0;
n1;
fin.get（ch1）;
t[i].c=ch1;
fin.ignore（100,'
'
t[i].f=atoi（ch）;
k=0;
k<
k++）
t[k].c<
t[k].f<
for（int
s=0;
s<
s++）
t[s].idx=i;
PQ.push（t[s]）;
while
（!
PQ.empty（））
if
（（PQ.size（））>
=2）
nl=PQ.top（）;
PQ.pop（）;
nr=PQ.top（）;
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
;
t1）
n=t1;
nNext=t1;
THaffmanNode[2*t1-1];
~CHuffman（void）
CreateTree（）
{
PQ.push（t[i]）;
//构造HaffmanTree
OutputTree（）
{
权重：
t[i].f<
左孩子：
t[i].l<
右孩子：
t[i].r<
父节点：
t[i].p<
在数组的位置：
t[i].idx<
//现在数组中存的是哈弗曼数
OutputCode（）
//用stack
来依次记录各编码的0
1
编码
stack<
int,
list<
int>
sk
ntemp,ntemp1;
ntemp=t[i];
while（ntemp.p!
=-1）
ntemp1=t[ntemp.p];
（t[ntemp1.l].idx==ntemp.idx）
sk.push（0）;
ntemp=ntemp1;
sk.push
（1）;
i1=sk.size（）;
：
i1;
sk.top（）;
sk.pop（）;
main（）
CHuffman
chf（"
C:
\\Users\\qzb\\Desktop\\算法实验\\huffman.txt"
chf.OutputTree（）;
chf.OutputCode（）;
system（"
pause"
用回溯方法求解n后问题
问题：
对任意给定的n求解n后问题。
具体要求：
1．封装n后问题为类，编写以下两种算法进行求解：
（1）递归回溯方法；
（2）迭代回溯方法。
（选）
2．对任意给定的n，要求输出其解向量（所有解），并输出其解数；
3．构造n后问题的解数表格（由程序自动生成）:
升级会员 