算法实验报告.docx

算法实验报告.docx

《算法实验报告.docx》由会员分享，可在线阅读，更多相关《算法实验报告.docx（32页珍藏版）》请在冰点文库上搜索。

算法实验报告

实验报告

2014学年第二学期任课老师：

课程名称

算法分析与设计

班级

学号

姓名

实验名称

实验一　排序算法的时间复杂度问题

实验时间

实验环境

PC/windows2000/2003/XP/JcreatorPro/JBuild/JDKEclipse/。

实验目的和内容要求

实验一　排序算法的时间复杂度问题

1．实验目的

掌握不同排序算法的原理，上机实验编程来验证归并排序和快速排序的时间复杂度。

2．实验内容

编写归并排序和快速排序的算法，验证相应的时间复杂度。

实验过程记录

1.归并排序

归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。

时间复杂度为O（nlogn）这是该算法中最好、最坏和平均的时间性能。

基本思想方法：

（1）假设已经有两个有序数列，分别存放在两个数组s，r中；并设i，j分别为指向数组的第一个单元的下标；s有n个元素，r有m个元素。

（2）再另设一个数组a，k指向该数组的第一个单元下标。

（3）算法分析（过程）：

proceduremerge（s,r,a,i,j,k）;

begin

i1:

=i;

j1:

=j;

k1:

=k;

while（i1

ifs[i1]<=r[j1]then

begin

a[k]:

=s[i1];

i1:

=i1+1;

k:

=k+1;

end

else

begin

a[k]:

=r[j1];

j1:

=j1+1;

k:

=k+1;

end;

whilei1<=ndo

begin

a[k]:

=s[i1];

i1:

=i1+1;

k:

=k+1;

end;

whilej1<=mdo

begin

a[k]:

=r[j1];

j1:

=j1+1;

k:

=k+1;

end;

end;

2.快速排序

快速排序是对冒泡排序的一种改进。

基本思想是：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：

i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]赋给A[i]；

4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]赋给A[j]；

5）重复第3、4步，直到i=j；（3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。

找到符合条件的值，进行交换的时候i，j指针位置不变。

另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

voidQuickSort（inta[],intp,intr）{

if（p

intq=partion（a,p,r）;

QuickSort（a,p,q-1）;

QuickSort（a,q+1,r）;

}

}

实验结果分析与总结

1、程序运行结果（请提供所完成的各道题运行结果界面截图）：

归并排序：

快速排序：

2.在实验过程中遇到的问题与解决方法：

因为快速排序是上个学期学的，所以出现了一些混乱，在每一趟的过程不是很清楚，快速排序的实现基于分治法，具体分为三个步骤。

假设待排序的序列为L[m..n]。

分解：

序列L[m..n]被划分成两个可能为空的子序列L[m..pivot-1]和L[pivot+1..n]，使L[m..pivot-1]的每个元素均小于或等于L[pivot]，同时L[pivot+1..n]的每个元素均大于L[pivot]。

其中L[pivot]称为这一趟分割中的主元（也称为枢轴、支点）。

解决：

通过递归调用快速排序，对子序列L[m..pivot-1]和L[pivot+1..r]排序。

合并：

由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列L[m..n]已排好

以中间元素518为基准就是518为枢轴，左边都是比它小得右边都是比它大的。

3.实验过程中的发现与收获，未解决或需进一步解决的问题：

收获是进一步巩固了关于排序的知识，之前在考虑软件的时候，考虑到了时间复杂度的问题，在java中是有一个专门的固定的函数记载时间的，可以调用那个函数与现在时间相减，然后就完成了一个运算时间的计算，而且C语言中本身就有一个自带的函数可以计算这个，但是因为程序运行时间实际非常快，所以基本检测不到，考虑过使问题复杂化或者用循环多次的方法来累积计算。

指导老师评阅意见

指导老师：

年月日

实验报告

2014学年第二学期任课老师：

课程名称

算法分析与设计

班级

学号

姓名

实验名称

实验二动态规划

实验时间

实验环境

PC/windows2000/2003/XP/JcreatorPro/JBuild/JDKEclipse/。

实验目的和内容要求

实验二动态规划

1．实验目的

掌握动态规划原理。

2．实验内容

利用动态规划原理，求矩阵连乘问题中的最小矩阵。

实验过程记录

动态规划算法通常用于求解具有某种最优性质的问题。

在这类问题中，可能会有许多可行解。

每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

我们可以用一个表来记录所有已解的子问题的答案。

不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

这就是动态规划法的基本思路。

具体的动态规划算法多种多样，但它们具有相同的填表格式。

voidMartrixChain（int*p,intn,int**m,int**s）

{

for（inti=1;i<=n;i++）m[i][i]=0;

for（intr=2;r<=n;r++）

for（inti=1;i<=n-r+1;i++）

{

intj=i+r-1;

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

s[i][j]=i;

for（intk=i+1;k

{

intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//选择最小的

if（t

}

}

}

voidTraceback（inti,intj,int**s）//返回一共记录的下个数

{

//s[i][j]记录了断开的位置，即计算A[i:

j]的加括号方式为

//（A[i:

s[i][j]]）*（A[s[i][j]+1:

j]）

//intk=0;

if（i==j）return;

Traceback（i,s[i][j],s）;//递归打印A[i:

s[i][j]]的加括号方式

Traceback（s[i][j]+1,j,s）;//递归打印A[s[i][j]+1:

j]的加括号方式

//cout<<"A"<

cout<<"multiplyA"<

cout<<"andA"<<（s[i][j]+1）<<","<

v[4*cou]=i;//记录乘法下标11,22,23等

v[4*cou+1]=s[i][j];

v[4*cou+2]=s[i][j]+1;

v[4*cou+3]=j;

cou=cou+1;

//returnk;

}

voidselectMultiply（Arry*A,intv[],intc,int*p,Arryt*temp）

{

intk;

ints;

intt;

intm;

intj,n,l,x,y;

//k=c;

//Arryt*temp=newArryt[c];

for（inti=0;i

{

if（v[i*4]==v[i*4+1]）

{

if（v[i*4+2]==v[i*4+3]）

{

k=v[i*4];//kk下标为11、22,33类型

s=v[i*4+2];//ss下标为11、22类型

temp[i].p=newint*[p[k-1]];

for（j=0;j

temp[i].p[j]=newint[p[s]];

temp[i].row=p[k-1];

temp[i].cowl=p[s];

temp[i].number=10*k+s;

for（j=0;j

for（n=0;n

{

intsum=0;

for（l=0;l

sum=sum+A[k-1].a[j][l]*A[s-1].a[l][n];

temp[i].p[j][n]=sum;

}

}

else

{

k=v[i*4];//kk下标为11、22类型

s=v[i*4+2];//}

//}st下标23、35类型

t=v[i*4+3];//}

for（j=0;j

if（temp[j].number=10*s+t）x=j;

temp[i].p=newint*[p[k-1]];

for（j=0;j

temp[i].p[j]=newint[temp[x].cowl];

temp[i].row=p[k-1];

temp[i].cowl=temp[x].cowl;

temp[i].number=10*k+t;

for（j=0;j

for（n=0;n

{

intsum=0;

for（l=0;l

sum=sum+A[k-1].a[j][l]*temp[x].p[l][n];

temp[i].p[j][n]=sum;

}

}

}

else

{

if（v[i*4+2]==v[i*4+3]）

{

k=v[i*4];//}

//}ks下标23、35类型

s=v[i*4+1];//}

t=v[i*4+2];//tt下标为11、22类型

for（j=0;j

if（temp[j].number=10*k+s）x=j;

temp[i].p=newint*[temp[x].row];

for（j=0;j

temp[i].p[j]=newint[p[t]];

temp[i].row=temp[x].row;

temp[i].cowl=p[t];

temp[i].number=10*k+t;

for（j=0;j

for（n=0;n

{

intsum=0;

for（l=0;l

sum=sum+temp[x].p[j][l]*A[t-1].a[l][n];

temp[i].p[j][n]=sum;

}

}

else

{

k=v[i*4];//}ks下标23、35类型

s=v[i*4+1];//}

///////

t=v[i*4+2];//tm下标23、35类型

m=v[i*4+3];

for（j=0;j

{

if（temp[j].number=10*k+s）x=j;

if（temp[j].number=10*t+m）y=j;

}

temp[i].p=newint*[temp[x].row];

for（j=0;j

temp[i].p[j]=newint[temp[y].cowl];

temp[i].row=temp[x].row;

temp[i].cowl=temp[y].cowl;

temp[i].number=10*k+m;

for（j=0;j

for（n=0;n

{

intsum=0;

for（l=0;l

sum=sum+temp[x].p[j][l]*temp[y].p[l][n];

temp[i].p[j][n]=sum;

}

}

}

}

}

voidoutputselect（intc,intn,Arryt*temp）

{

inti,j;

ints=10+n;

for（i=0;i

{

for（j=0;j

cout<

cout<

}

}

实验结果分析与总结

1、程序运行结果（请提供所完成的各道题运行结果界面截图）：

2、在实验过程中遇到的问题与解决方法：

实验中有出现过代码无错，但是输出结果错误的情况。

但是如果在定义数组时改为intm[n][n];ints[n][n];结果就对了，C语言定义数组应该后面是常量，但是我的这个程序，用常量错，用变量反而对。

后来仔细调试后和同学讨论了一下，m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];这句话调用到m[n][n],但是实际上只能调用到m[n-1][n-1]。

（因为从0开始的，不过有时候也能用，就是用了下一维的第0个），所以要写intm[7][7]（要不就8，8）。

至于intm[n][n]为什么会对，应该使用了内存的其他部分。

3、实验过程中的发现与收获，未解决或需进一步解决的问题：

对于动态规划有了一定的了解，算法实现是比较好考虑的。

但有时也会遇到一些问题，而使算法难以实现。

动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大。

而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。

另一方面，动态规划的高时效性往往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规模的问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题时一个普遍会遇到的问题。

一个思考方向是尽可能少占用空间。

如从结点的数据结构上考虑，仅仅存储必不可少的内容，以及数据存储范围上精打细算（按位存储、压缩存储等）。

当然这要因问题而异，进行分析。

指导老师评阅意见

指导老师：

年月日

实验报告

2014学年第二学期任课老师：

沙莎

课程名称

算法分析与设计

班级

计科1204班

学号

0909121917

姓名

周凌君

实验名称

实验三n皇后问题

实验时间

第十周星期日第一二节课

实验环境

PC/windows2000/2003/XP/JcreatorPro/JBuild/JDKEclipse/。

实验目的和内容要求

实验三　n皇后问题

1．实验目的

用编程代码实现理解回溯法。

2．实验内容

用回溯法表现n皇后问题的算法。

实验过程记录

n皇后问题最初为八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

回溯算法

（a）为解决这个问题，我们把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从1到8。

当某个皇后占了位置（i,j）时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。

用语句实现，可定义如下三个整型数组：

a[8],b[15],c[24]。

其中：

a[j-1]=1第j列上无皇后

a[j-1]=0第j列上有皇后

b[i+j-2]=1（i,j）的对角线（左上至右下）无皇后

b[i+j-2]=0（i,j）的对角线（左上至右下）有皇后

c[i-j+7]=1（i,j）的对角线（右上至左下）无皇后

c[i-j+7]=0（i,j）的对角线（右上至左下）有皇后

（b）为第i个皇后选择位置的算法如下：

for（j=1;j<=8;j++）/*第j个皇后在第j行*/

if（（i,j）位置为空））/*即相应的三个数组的对应元素值为1*/

{占用位置（i,j）/*置相应的三个数组对应的元素值为0*/

ifi<8

为i+1个皇后选择合适的位置；

else输出一个解

}

实验结果分析与总结

1、程序运行结果（请提供所完成的各道题运行结果界面截图）：

2.在实验过程中遇到的问题与解决方法：

n皇后问题在于输出的表达形式问题，网上关于这方面的资料很多，但是大多表达不符我心意。

根据书上的代码很容易将回溯法的思想弄清楚并转化为相应的C++代码，然后就是表达形式的问题，因为传统的八皇后问题的解答是92个，所以个人认为如果用表格代表棋牌的样子的话虽然很形象直观，但是却太占页面了，所以最后选择直接展示在每一行的位置，并且把所有解都输出，并且输出一个计数的输出总值。

3.实验过程中的发现与收获，未解决或需进一步解决的问题：

n皇后问题很有趣，给我的一种很直观的现实中的思想转化成代码的感觉，而且对于回溯法的了解更加深入了，那种算法上的明了的感觉就是代码非常漂亮，将思想很干净利落地展示了出来，毫不拖沓。

指导老师评阅意见

指导老师：

年月日

填写内容时，可把表格扩大。

附：

实验源程序代码

归并排序：

快速排序：

#include

usingstd:

:

cout;

usingstd:

:

endl;

intPartition（int*R,intlow,inthigh）{

//对记录子序列R[low..high]进行一趟快速排序，并返回枢轴记录

//所在位置，使得在它之前的记录的关键字均不大于它的关键字，

//而在它之后的记录的关键字均不小于它的关键字

R[0]=R[low];//将枢轴记录移至数组的闲置分量

intpivotkey=R[low];//枢轴记录关键字

cout<

"<

while（low

while（low=pivotkey）{

--high;

}

if（low=high而退出的循环，不需要移动数据

R[low++]=R[high];//将比枢轴记录小的记录移到低端

//cout<<"移动的hign数据：

"<

}

while（low

++low;

if（low

R[high--]=R[low];//将比枢轴记录大的记录移到高端

//cout<<"移动的low数据：

"<

}

}//while

R[low]=R[0];//枢轴记录移到正确位置

//cout<<"返回的pivotkey:

"<

for（inti=1;i<=10;i++）{

cout<

}

returnlow;//返回枢轴位置

}//Partition

voidQSort（int*R,ints,intt）{

//对记录序列R[s..t]进行快速排序

if（s

intpivotloc=Partition（R,s,t）;//对R[s..t]进行一趟快排，并返回枢轴位置

QSort（R,s,pivotloc-1）;//对低子序列递归进行排序

QSort（R,pivotloc+1,t）;//对高子序列递归进行排序

}//if

}//Qsort

intmain（）{

intli[10]={0,38,65,97,76,13,27,48,55,4};

cout<<"注意:

R[0]为数组的闲置分量"<

for（inti=1;i<=10;i++）{

cout<

}

cout<

QSort（li,1,9）;

cout<

for（inti=1;i<=10;i++）{

cout<

}

cout<

return0;

}

矩阵连乘

#include