算法实验报告

发布时间：

实验报告

1

计算机科学与技术学院

课程名称：算法设计与分析专业：网络工程班级：网络092学号：200913136054姓名：吴晓指导老师：王晓峰

1


实验一递归算法

实验名称：递归算法实验日期：2011年10月21日

2

一实验目的

掌握递归算法的概念和基本思想。

二、实验内容

N阶Hanoi塔问题要求：（1）（2）

写出相应问题的递归算法及程序要求输出整个搬动过程。

三、实验仪器、设备及材料

PC机，C/C++程序设计语言应用环境。

四、实验原理

递归算法

五、实验步骤

1.问题描述

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

2.算法描述

其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n–1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放ABC；

3.程序部分核心代码

voidhanoi(intn,chara,charb,charc{

}

2

if(n==1move(a,c;else

{

hanoi(n-1,a,c,b;move(a,c;hanoi(n-1,b,a,c;

}


六、实验原始记录

1.测试方案

将盘子数量设为1,2,3,4个，以此对程序进行测试。

3

2.测试结果

程序能实现汉诺塔问题

七、实验数据计算结果

由程序运行结果看出，1个的时候是1次，结果n个的时候为（2的n次方减1）次。实验结果分析

通过本次实验，我明白了递归的用法以及其使用范围。就本实验的汉诺塔问题而言，递归可以轻松的将N个盘子的问题转化成两个盘子的问题，简化了问题的难度，并且更加适应人的思维方式。只要抓住问题的递归关系和递归终止条件就不难掌握递归的使用了。

3


附录：源代码及说明

#include

usingnamespacestd;

voidmove(charbegin,charend{cout<移动到"<}

voidhanoi(intn,chara,charb,charc{

if(n==1move(a,c;else{

}

hanoi(n-1,a,c,b;move(a,c;

hanoi(n-1,b,a,c;

4

}

voidmain({}

4

intm;

cout<<"pleaseinputnumberm:";

cin>>m;

cout<<"汉诺塔的移动过程为：";

hanoi(m,'a','b','c';


5

实验二分治算法

实验名称：分治算法实验日期：2011年10月28日

一实验目的

1.利用分治策略编程实现合并排序;2.基本掌握分治策略的原理方法。

二、实验内容

1、残缺棋盘问题2、大整数相乘问题

三、实验仪器、设备及材料

PC机，C/C++程序设计语言应用环境。

四、实验原理

分治算法

五实验步骤

（1）残缺棋盘问题

问题描述

描述：残缺棋盘是一个有2k2k个方格的棋盘，其中恰有一个方格残缺。现在要求用三格板覆盖残缺棋盘，覆盖过程中两个三格板不能重叠，不能覆盖残缺方格，但必须覆盖其它的所有方格。

算法描述：基本算法

棋盘用二维数组来表示，数组的行标表示单元格所在的行数，列标表示所在的列数，数组的元素是来存放是用第几块三格板来覆盖的三格板号。而子棋盘用它左上角的单元格所在的行，列位置来表示。棋盘的规模用行数来表示

5


算法描述：

Cover（）

{

If（行数<2）

返回；

三个板数目加1；If（残缺方格位于左上棋盘）{Cover（）；

标记覆盖1号三格板；

Cover（）；再覆盖其它的部分Cover（）；Cover（）；

}

If（残缺方格位于右上棋盘）{

Cover（）；

标记覆盖2号三格板；

6

Cover（）；再覆盖其它的部分Cover（）；Cover（）；

}

If（残缺方格位于左下棋盘）{

Cover（）；

标记覆盖3号三格板；

Cover（）；再覆盖其它的部分Cover（）；Cover（）；

}

If（残缺方格位于右下棋盘）{

Cover（）；

标记覆盖4号三格板；

Cover（）；再覆盖其它的部分Cover（）；Cover（）；}}

6


程序核心代码

voidCover(inttr,inttc,intdr,intdc,intsize{ints,t;if(size<2return;

7

7

amount++;

t=amount;

s=size/2;

if(dr

Cover(tr,tc,dr,dc,s;Board[tr+s-1][tc+s]=t;Board[tr+s][tc+s-1]=t;

Board[tr+s][tc+s]=t;

Cover(tr,tc+s,tr+s-1,tc+s,s;Cover(tr+s,tc,tr+s,tc+s-1,s;

Cover(tr+s,tc+s,tr+s,tc+s,s;

}

elseif(dr=tc+s{Cover(tr,tc+s,dr,dc,s;

Board[tr+s-1][tc+s-1]=t;Board[tr+s][tc+s-1]=t;

Board[tr+s][tc+s]=t;

Cover(tr,tc,tr+s-1,tc+s-1,s;Cover(tr+s,tc,tr+s,tc+s-1,s;

Cover(tr+s,tc+s,tr+s,tc+s,s;

}

elseif(dr>=tr+s&&dc

Cover(tr+s,tc,dr,dc,s;Board[tr+s-1][tc+s-1]=t;Board[tr+s-1][tc+s]=t;

Board[tr+s][tc+s]=t;

Cover(tr,tc,tr+s-1,tc+s-1,s;Cover(tr,tc+s,tr+s-1,tc+s,s;

Cover(tr+s,tc+s,tr+s,tc+s,s;

}

elseif(dr>=tr+s&&dc>=tc+s{

}

Cover(tr+s,tc+s,dr,dc,s;Board[tr+s-1][tc+s-1]=t;Board[tr+s-1][tc+s]=t;

Board[tr+s][tc+s-1]=t;

Cover(tr,tc,tr+s-1,tc+s-1,s;Cover(tr,tc+s,tr+s-1,tc+s,s;

Cover(tr+s,tc,tr+s,tc+s-1,s;


（2）大整数相乘问题1.问题描述

在某些情况下，需要处理很大的整数，它无法在计算机硬件能直接允许的范围内进行表示和处理。设计一个有效的算法，可以进行两个n位的大整数乘法运算。

8

2算法描述

要有效的存储大整数信息和运算，首先必须定义其结构为字符数组。因为要处理的数范围很大，不能直接用蛮力法来解决，这时候就必须采用分治的思想，将n位的大整数分解成n/2位的整数，拆分之后根据相应数学公式进行转化，然后再根据递归的思想进行依次分解下去。另外考虑到n位分解最终分解不均匀已经两个大整数位数不同的问题，我们可以在执行核心算法之前，自动将两个大整数转化为位数相同并且均为2的整数次幂，然后再进行分治。

3.程序核心代码

voidmul(intlefta,intrighta,intleftb,intrightb,inttimes{

8

if(lefta==righta&&leftb==rightb{

}

inttemp=c[times]-48+(a[lefta]-48*(b[leftb]-48;if(temp>=10{

}

ints=temp/10;

c[times]=temp%10+48;intstart=times+1;while(s>0{

}

temp=c[start]-48+s;c[start]=temp%10+48;

s=temp/10;

elsec[times]=temp+48;

return;

intmida=(lefta+righta/2;intmidb=(leftb+rightb/2;

intlength=righta-lefta+1;

mul(mida+1,righta,midb+1,rightb,times;

if(midb>=k-m

mul(mida+1,righta,leftb,midb,length/2+times;if(mida>=k-n

mul(lefta,mida,midb+1,rightb,length/2+times;


}

if(mida>=k-n&&midb>=k-m

mul(lefta,mida,leftb,midb,length+times;

9

六、实验原始记录

（1）残缺棋盘问题

1.测试方案

在测试中，我们设k=3，即为8*8棋盘，同时设置残缺位置的坐标为（4，5），以此对程序进行测试。2.测试结果

（2）大整数相乘问题

1.测试方案

在测试中，我们设第一个大整数为1384542，第二个大整数为3458789451，这样程序会首先进行位数转化，空闲位补零，然后执行分治算法，以此对程序进行测试。2.测试结果

七、实验数据计算结果

（1）残缺棋盘问题

由程序运行结果看出，图中的矩阵即表示三隔板填充情况，矩阵中为0的位置即为残缺点位置，点数相同的位置即属于同一块三隔板，填充过程如程序结果截图。经验证与实际结果相符，程序运行正确无误。

9


（2）大整数相乘问题

由程序运行结果看出，这两个大整数相乘结果为4697748463976442，运算结果如程序结果截图。经验证与实际结果相符，程序运行正确无误。

10

八、实验结果分析

1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。

本题在思路上和折半查找很相似，可以利用折半查找一分为二、二分为四，然后和每一小组的边界比较，即不难得出其解。

本次实验考察的分治算法感觉和之前的递归算法有异曲同工之妙。从某种程度上来说，递归是在时间上划分为若干小块，然后分块求解；而分治则是在空间上划分为若干部分，然后分部分求解。虽算法不同，但是其基本原理是一样的，学好了能解决很多问题。

附录：程序代码

#include#include#include

chara[100],b[100],c[200];

intn,m,k;

voidmul(intlefta,intrighta,intleftb,intrightb,inttimes{

10

if(lefta==righta&&leftb==rightb{

}

inttemp=c[times]-48+(a[lefta]-48*(b[leftb]-48;if(temp>=10{}

else

c[times]=temp+48;

return;

ints=temp/10;

c[times]=temp%10+48;intstart=times+1;while(s>0{

}

temp=c[start]-48+s;c[start]=temp%10+48;

s=temp/10;


}

intmida=(lefta+righta/2;

intmidb=(leftb+rightb/2;

intlength=righta-lefta+1;

mul(mida+1,righta,midb+1,rightb,times;if(midb>=k-m

mul(mida+1,righta,leftb,midb,length/2+times;

if(mida>=k-n

mul(lefta,mida,midb+1,rightb,length/2+times;if(mida>=k-n&&midb>=k-m

mul(lefta,mida,leftb,midb,length+times;

11

voidmain({}

11

charta[50],tb[50];

cout<<"输入第一个乘数"<cin>>ta;

cout<<"输入第二个乘数"<cin>>tb;n=strlen(ta;

m=strlen(tb;

inttemp=log(n/log(2;k=(intpow(2,temp;if(kk*=2;for(inti=0;ia[i]='0';for(i=0;ib[i]='0';strcat(a,ta;

strcat(b,tb;

for(i=0;i

c[i]='0';

mul(0,k-1,0,k-1,0;

cout<<"它们的乘积是:"<if(c[n+m-1]!='0'

cout<for(i=n+m-2;i>=0;i--cout<cout<

12

实验三贪心算法

实验名称：贪心算法实验日期：2011年11月11日

一实验目的

1.掌握最小生成树的Kruskal算法;2.基本掌握贪心算法的一般设计方法。

二、实验内容

1.用Kruskal算法生成最小生成树

2.【汽车加油问题】一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。

三、实验仪器、设备及材料

PC机，C/C++程序设计语言应用环境。

四、实验原理

贪心算法

实验步骤

（1）最小生成树问题1.问题描述

给出结点数量N，以及每个结点到相邻结点的距离，要求给出一条最短连通路径，连通所有结点

2.算法描述Kruskal算法的精髓就是依次选取最短并且没有构成回路的边，直至图中所有顶点都在同意连通分量上。3数据结构与变量定义#include#include#include

#include

#defineMAX_VERTEX_NUM20

typedefstructArcCell{intadj;

intinfo;

intarcvisited;

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{intvexs[MAX_VERTEX_NUM];//图的顶点信息

12


AdjMatrixarcs;//图的边的信息

intvexnum,arcnum;//图的顶点和边的个数}mgraph,*MGraph;//构造的图算法或程序模块

voidInitMGraph(MGraph&G{

inti,j;

G=(MGraphmalloc(sizeof(mgraph;

13

G->vexnum=0;G->arcnum=0;

}

for(i=0;i

for(j=0;j

}

G->arcs[i][j].adj=0;

G->arcs[i][j].info=0;

G->arcs[i][j].arcvisited=-1;

voidAddvexs(MGraph&G{printf("请输入顶点个数:";scanf("%d",&G->vexnum;

for(inti=0;ivexnum;i++{

G->vexs[i]=i;

printf("第%d个顶点名称:%d\n",i,G->vexs[i];}

}

voidAddarcs(MGraph&G{

13

inti,n,m,data;

printf("请输入边的个数

:";

scanf("%d",&G->arcnum;for(i=0;iarcnum;i++{printf("请分别输入第%d条边的两个顶点和权值:",i+1;

scanf("%d",&n;

scanf("%d",&m;

scanf("%d",&data;

if(n>-1&&m>-1&&nvexnum&&mvexnum{

}

G->arcs[n][m].adj=1;G->arcs[m][n].adj=1;G->arcs[n][m].arcvisited=0;G->arcs[m][n].arcvisited=0;G->arcs[n][m].info=data;

G->arcs[m][n].info=G->arcs[n][m].info;

else{printf("输入有误,请重新输入\n";

i--;


}

}

}

voidCreateMGraph(MGraph&G{Addvexs(G;

}

Addarcs(G;

14

voidKruskal(MGraphG{inti,j,count=0,k,p,q,n;

intvisit[MAX_VERTEX_NUM];

intmin=1000;

for(i=0;ivexnum;i++

visit[i]=0;

printf("求得最小生成树的边依次为:\n";{

14

for(k=0;kvexnum-1;k++{min=1000;

for(i=0;ivexnum;i++for(j=i;jvexnum;j++{if(G->arcs[i][j].arcvisited==0{

}

if(G->arcs[i][j].info>0&&G->arcs[i][j].infoif(!(visit[i]!=0&&visit[j]!=0&&visit[i]==visit[j]

}

min=G->arcs[i][j].info;p=i;q=j;

}

else{

}

G->arcs[i][j].arcvisited=1;

G->arcs[j][i].arcvisited=1;

}

G->arcs[p][q].arcvisited=1;G->arcs[q][p].arcvisited=1;if(visit[p]==0&&visit[q]==0{

count++;

visit[p]=count;

visit[q]=count;

}

else

if(visit[p]!=0&&visit[q]==0

visit[q]=visit[p];

elseif(visit[q]!=0&&visit[p]==0

visit[p]=visit[q];


}

}

else{

}

if(visit[p]n=visit[q];for(i=0;ivexnum;i++if(visit[i]==n

}

visit[i]=visit[p];

15

else{n=visit[p];

}

for(i=0;ivexnum;i++

if(visit[i]==n

visit[i]=visit[q];

printf("第%d条边

:%d-->%d\n",k+1,G->vexs[p],G->vexs[q];

（2）汽车加油问题

1.问题描述

一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。2.算法描述这个问题可以通过贪心算法求出其相对最优解。核心思想就是汽车能不加油就不加油，一次能走过几个加油站就走过几个，不考虑其他因素，这样的思想可以达到局部最优，进而可能达到全局最优。程序代码

intmain(intargc,char*argv[]{intOilStationNum;//加油站的数目

15

intMaxDist;//汽车加满油以后行驶的最大距离intDiscOfCar;//汽车一次加油后已经行驶的距离

intCount;

int*OilStationDist;

printf("请输入加油站的段数(用整数表示:";

scanf("%d",&OilStationNum;

printf("------------------------------\n";

printf("汽车加满油以后行驶的最大距离(用整数表示:";

scanf("%d",&MaxDist;

printf("---------------------------------------\n";

OilStationDist=newint[OilStationNum-1];

printf("请输入各各加油站之间的距离(假设不能有环路:\n";for(Count=0;Count<=OilStationNum-1;

{


//

scanf("%d",&OilStationDist[Count];if(OilStationDist[Count]<=MaxDistCount++;

else

16

printf("你输入的加油站之间的距离大于汽车加满油以后行驶的最大距离,请重新输入当前距离!\n";

}

printf("-----------------------------------------\n";printf("下面是你输入的加油站之间的顺序间隔:\n";for(Count=0;Count<=OilStationNum-2;Count++{

//

printf("加油站编号:%d,到下一站距离

:%d\n",Count,OilStationDist[Count];

加

油

站

编

号

:%d,

到

终

点

站

距

}

printf("

离:%d\n",OilStationNum-1,OilStationDist[OilStationNum-1];DiscOfCar=0;Count=0;

while(1{

if(DiscOfCar<=MaxDist{//DiscOfCar+=OilStationDist[Count];

}

Count+=1;

else{//

Count-=1;

printf("当前汽车需要在%d号加油站处加油,此时汽车行驶了%d公

里

\n",Count,DiscOfCar-OilStationDist[Count];DiscOfCar=0;

}

if(Count>OilStationNum

{

printf("当前汽车到达终点,此时汽车距上一次加油行驶了%d公里\n",DiscOfCar-OilStationDist[Count];

}

16

}

if(Count>OilStationNumbreak;

}

return0;


17

六、实验原始记录

（1）最小生成树问题1.测试方案

在测试中，顶点的值是程序自动给定的，只要输入顶点和边的个数以及边的权值即能求出其最小生成树，以此对程序进行测试。2.测试结果

（2）汽车加油问题

1.测试方案

在测试中，只要构造好汽车以及加油站的信息，就能求出最佳的加油方案，以此对程序进行测试。2.测试结果

17


18

七、实验数据计算结果（1）最小生成树问题

由程序运行结果看出，当构造如图所示的连通图后，其最小生成树包含五条边，分别如程序结果截图。经验证与实际结果相符，程序运行正确无误。（2）汽车加油问题由程序运行结果看出，当构造如图所示的汽车和加油站信息后，其最佳加油方案为第一站第二站第三站第四站第五站第六站第七战第九站，如程序结果截图。经验证与实际结果相符，程序运行正确无误。

八、实验结果分析

1.已知有n个独立的作业J1，J2…，Jn由m台相同的机器进行加工处理。作业i所需的处理时间为t1，t2…，ti。现约定，任何作业Ji可以在任何一台机器上处理，但未完成前不允许间断，划分。试用贪心法设计一种调度方案，把n项作业分配到m台机器上完成，所需时间T=MAX{Ti}(1≦i≦m,其中Ti为分配给各机器的处理作业时间之和。

本题可以利用贪心算法选取那些最可能到达解的情况来考虑，即可以先按作业处理时间来排序，先安排处理时间长的进行加工，然后哪一个处理完了就补上剩下未处理的；同时我们也可以就按作业编号来排序，编号在前的先进行加工，处理完了再接着处理后续的。这两种方案都有可能获得最短总处理时间。

从本次实验我们可以得知，贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。但是要注意选择的贪婪策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的决策影响。

18


实验四动态规划算法

实验名称：动态规划算法实验日期：2011年11月18日

19

实验目的

1.掌握求解0-1背包问题的动态规划递推算法;2.掌握动态规划法的原理方法

.

二、实验内容

0-1背包问题

三、实验仪器、设备及材料

PC机，C/C++程序设计语言应用环境。

四、实验原理

动态规划算法

五、实验步骤

1.问题描述

一个商人带着一个能装m千克的背包去乡下收购货物，准备将这些货物卖到城里获利。现有n种货源，且知第i种货物有Wi千克，可获利Pi元。要求编写程序帮助上任收购货物，以获得最高的利润。注意：每种商品的数量是不能拆分的。算法描述

采用动态规划的思想，就是逐个决定一个物品的取舍情况，但是不能根据少数几个物品的重量和利润就得出取舍结论。但在肯定当前背包的范围时，一个物品选取的可能性是可以确定的。利用一个数组存储信息，从而利用局部最优求得全局最优。

程序核心代码

voidknap9(intm,intn{inty=0,i=0;

19

for(y=0;y<=m;y=y+1f[n][y]=0;for(y=w[n];y<=m;y=y+1f[n][y]=p[n];for(i=n-1;i>1;i=i-1{

for(y=0;y<=m;y=y+1

f[i][y]=f[i+1][y];

for(y=w[i];y<=m;y=y+1if(f[i+1][y]>f[i+1][y-w[i]]+p[i]

f[i][y]=f[i+1][y];else

f[i][y]=f[i+1][y-w[i]]+p[i];


}

}

if(m>=w[1]if(f[1][m]>f[2][m-w[1]]+p[1]f[1][m]=f[2][m];else

f[1][m]=f[2][m-w[1]]+p[1];

20

voidsolution(intm,intn{inti=0;

for(i=1;i

if(f[i][m]==f[i+1][m]

x[i]=0;else{x[i]=1;

}

m=m-w[i];

}

if(f[n][m]!=0x[n]=1;else

x[n]=0;

}

六、实验原始记录1.测试方案在测试中，只要构造好货物的重量和获利信息以及背包容量信息，就能求出最佳的选择方案，以此对程序进行测试。2.测试结果

20


七实验数据计算结果

由程序运行结果看出，当构造如图所示的背包和货物信息后，其最佳方案为选取第一种、第二种和第五种货物，此时可以得到最大利润为83元，如程序结果截图。经验证与实际结果相符，程序运行正确无误。八、实验结果分析

1.用动态规划方法设计一个解决最优二分检索树的算法。

假定T0为最优二分检索树，它的根是ak，则ak的左子树必然包含a1~ak-1，右子树必然包含ak+1~an，而且最优树的任何一颗子树也必然是关于子树中结点的最优树。这样根据动态规划的思想，每次动态地构造最优的子树，即能得到全局的最优子树解。

通过本次实验我们可以得知，动态规划是全面考虑各种不同情况分别进行决策，而不是线性的，最后通过多阶段决策逐步找出问题的最终解。当各个阶段采取决策后，会不断决策出新的数据，直到找到最优解。相比之前的贪婪算法，动态规划才是真正从全局出发，全面考虑的算法，因而其可靠性也更高。

21

附录：程序代码

#include

intw[100],p[100],x[100],f[100][100];voidsolution(intm,intn;

voidknap9(intm,intn;

voidmain({printf("************0-1背包问题*************\n";

21

inttw,tp,m,n,s,i,j,Num;

printf("请输入背包能容纳货物的重量（kg）:";

scanf("%d",&m;

printf("请输入货物的种类:";

scanf("%d",&Num;

i=0;

s=0;

printf("请输入第1种货物的重量和获利

:";


scanf("%d%d",&tw,&tp;for(j=0;js=s+tw;if(tw<=m{i=i+1;

w[i]=tw;

p[i]=tp;

22

}

if(j

}

printf("请输入第%d种货物的重量和获利:",i+1;

scanf("%d%d",&tw,&tp;

}

n=i;

if(s<=m{printf("可以将全部货物装入包中!";return;

}

knap9(m,n;

solution(m,n;

printf("最佳方案时分别选择了

:\n";

intLastOne;

for(i=n;i>=1;i--{if(x[i]==0continue;

}

elseif(x[i]==1{LastOne=i;

}

break;

for(i=1;i<=LastOne;i++{if(x[i]==1&&i!=LastOne

}

printf("第%d种货物+",i;elseif(i==LastOne

printf("第%d种货物

\n",i;

printf("最高利润为:%d元

\n",f[1][m];

}

voidknap9(intm,intn{

22

inty=0,i=0;

for(y=0;y<=m;y=y+1

f[n][y]=0;

for(y=w[n];y<=m;y=y+1

f[n][y]=p[n];


for(i=n-1;i>1;i=i-1{}

for(y=0;y<=m;y=y+1f[i][y]=f[i+1][y];for(y=w[i];y<=m;y=y+1if(f[i+1][y]>f[i+1][y-w[i]]+p[i]

f[i][y]=f[i+1][y];else

f[i][y]=f[i+1][y-w[i]]+p[i];

23

if(m>=w[1]

if(f[1][m]>f[2][m-w[1]]+p[1]

f[1][m]=f[2][m];

else

f[1][m]=f[2][m-w[1]]+p[1];

}

voidsolution(intm,intn{}

23

inti=0;

for(i=1;iif(f[i][m]==f[i+1][m]

}

x[i]=0;else{

}

x[i]=1;

m=m-w[i];

if(f[n][m]!=0x[n]=1;else

x[n]=0;


实验五图的搜索之回溯算法

实验名称：动态规划算法实验日期：2011年11月18日

24

一、实验目的

1.掌握回溯法解题的基本思想；2.掌握回溯算法的设计方法；

3.针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。

二、实验内容

8皇后问题

三、实验仪器、设备及材料

PC机，C/C++程序语言应用环境。

四、实验原理

回溯算法

五、实验步骤

1.问题描述

要求在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则是皇后能吃掉同一行、同一列、同一对角线的任意棋子。算法描述

由题意可知我们要探讨的是一个二维数组问题，但是因为规定八个皇后彼此都不能在同一行、同一列、同一对角线上，我们可以简化为一个一维数组问题，a[k]=i即表示选定棋盘第k行、第i列的位置放置一个皇后。通过回溯法的思想，走不通就掉头，走通了即得到了一种方案，输出了再接着掉头找下一种方案。3.数据结构与变量定义voidbackdate(intn{

24

intk;a[1]=0;k=1;while(k>0{

a[k]=a[k]+1;

while((a[k]<=n&&(check(k==0

a[k]=a[k]+1;

if(a[k]<=nif(k==n

output(;


}

}

else{

}

k=k+1;

a[k]=0;

25

else

k=k-1;

intcheck(intk

{

inti;

for(i=1;i<=k-1;i=i+1if((abs(a[i]-a[k]==abs(i-k||(a[i]==a[k]return(0;

return(1;

}

voidoutput(

{

inti;for(i=1;i<=n;i++}

printf("%d",a[i];printf("\n";

count++;

六、实验原始记录

1.测试方案

在测试中，鉴于8个皇后的方案太多，多达92种，故设定了6个皇后，以此对程序进行测试。2.测试结果

25


26

实验数据计算结果

由程序运行结果看出，当设定皇后为6个时，共有四种安排方案，分别如程序结果截图。经验证与实际结果相符，程序运行正确无误。八、实验结果分析

1．用回溯法设计一个解决0-1背包问题的算法。

采用回溯法解决0-1背包问题时，必须要考虑到几个操作：一要累加所取物品的重量，回溯时还要做现场清理，也就是将当前物品置为不取状态，且从累加重量中减去当前物品的重量。当每搜索完一个分支就要计算该分支的获利情况，并记录当前的最大获利情况。这样即能求出最优解。

从本实验我们可以得知，回溯法是对解空间的深度优先搜索，每找到一个解就输出并继续找下一个，每到走投无路的时候就回溯，知道全部情况都已遍历完。相对于递归而言，回溯法更加省时省力，并且当存在多种解时，回溯法的优势便更加明显了。

附录：程序代码#include#include#include

inta[20],n;intcount=0;

voidbackdate(intn;intcheck(intk;voidoutput(;

voidmain({

}

printf("请输入皇后的数目:";scanf("%d",&n;backdate(n;

printf("%d",count;

voidbackdate(intn

{

26


}

intk;a[1]=0;k=1;while(k>0{

}

a[k]=a[k]+1;

while((a[k]<=n&&(check(k==0

a[k]=a[k]+1;

27

if(a[k]<=n

if(k==noutput(;else{

}

k=k+1;

a[k]=0;

else

k=k-1;

intcheck(intk{

}

inti;

for(i=1;i<=k-1;i=i+1if((abs(a[i]-a[k]==abs(i-k||(a[i]==a[k]

return(0;

return(1;

voidoutput(

{

inti;

}

27

for(i=1;i<=n;i++printf("%d",a[i];printf("\n";

count++;


算法实验报告

推荐内容

相关推荐