完整word版计算机算法与设计分析实验报告.docx
《完整word版计算机算法与设计分析实验报告.docx》由会员分享，可在线阅读，更多相关《完整word版计算机算法与设计分析实验报告.docx（31页珍藏版）》请在冰点文库上搜索。
完整word版计算机算法与设计分析实验报告
计算机算法与设计分析
实
验
报
告
班级：
姓名：
学号：
实验一分治与递归……………………………………………………………………………1
1、基本递归算法………………………………………………………………………………1
2、棋盘覆盖问题………………………………………………………………………………2
3、二分搜索……………………………………………………………………………………3
4、实验小结……………………………………………………………………………………5
实验二动态规划算法………………………………………………………………………5
1、最长公共子序列问题……………………………………………………………………5
2、最大子段和问题……………………………………………………………………………7
3、实验小结……………………………………………………………………………………8
实验三贪心算法………………………………………………………………………………8
1、多机调度问题………………………………………………………………………………8
2、用贪心算法求解最小生成树………………………………………………………………10
3、实验小结……………………………………………………………………………………12
实验四回溯算法和分支限界法………………………………………………………………12
1、符号三角形问题……………………………………………………………………………12
2、0—1背包问题………………………………………………………………………………14
3、实验小结……………………………………………………………………………………18
实验一分治与递归（4学时）
一：
基本递归算法
一、实验目的与要求
1、熟悉C/C++语言的集成开发环境；
2、通过本实验加深对递归过程的理解
二、实验内容：
掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题
任意输入一个整数，输出结果能够用递归方法实现整数的划分。
#include
usingnamespacestd;
intmain（）
{
inta,b,c;
intq（intn,intm）;
cout<<"请输入整数及大于最大加数的数"<cin>>a>>b;
c=q（a,b）;
cout<<"所需要的划分数为：
"<return0;
}
intq（intn,intm）
{
if（（n<1）||（m<1））return0;
if（（n==1）||（m==1））return1;
if（nif（n==m）returnq（n,m-1）+1;
returnq（n,m-1）+q（n-m,m）;
}
实验结果：
结果分析：
实验时入得数据为：
所要划分的整数是7，他的划分的最大加数的值不得大于7，根据实际其划分的情况为15种，因而可知其程序的运行结果是正确的。
二：
棋盘覆盖问题
一、实验目的与要求
1、掌握棋盘覆盖问题的算法；
2、初步掌握分治算法
二、实验题：
盘覆盖问题：
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、程序代码：
#include
usingnamespacestd;
inttile=0;//全局变量，表示特殊格的号
intboard[1000][1000];
intmain（）
{
inttr,tc,dr,dc,size;
inttile=0;//全局变量，表示特殊格的号
voidchessBoard（inttr,inttc,intdr,intdc,intsize）;
cout<<"输入数据"<cin>>tr>>tc>>dr>>dc>>size;
cout<chessBoard（tr,tc,dr,dc,size）;
for（inti=1;i<=size;i++）
{
for（intj=1;j<=size;j++）
cout<cout<}
return0;
}
voidchessBoard（inttr,inttc,intdr,intdc,intsize）//左上角行号、列号，特殊格的行号、列号棋盘大小
{
if（size==1）
return;//?
?
?
?
?
?
?
tiaochu
intt=++tile,//L型骨牌号？
？
？
？
？
？
s=size/2;//分割棋盘//覆盖左上角子棋盘
if（drchessBoard（tr,tc,dr,dc,s）;
else
{//此棋盘中无特殊方格
//用t号L型骨牌覆盖右下角
board[tr+s-1][tc+s-1]=t;
//覆盖其余方格
chessBoard（tr,tc,tr+s-1,tc+s-1,s）;
}//覆盖右上角子棋盘
if（dr=tc+s）//特殊方格在此棋盘中
chessBoard（tr,tc+s,dr,dc,s）;
else
{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角
board[tr+s-1][tc+s]=t;//覆盖其余方格
chessBoard（tr,tc+s,tr+s-1,tc+s,s）;
}//覆盖左下角子棋盘
if（dr>=tr+s&&dc//特殊方格在此棋盘中
chessBoard（tr+s,tc,dr,dc,s）;
else
{//用t号L型骨牌覆盖右上角
board[tr+s][tc+s-1]=t;//覆盖其余方格
chessBoard（tr+s,tc,tr+s,tc+s-1,s）;
}//覆盖右下角子棋盘
if（dr>=tr+s&&dc>=tc+s）//特殊方格在此棋盘中
chessBoard（tr+s,tc+s,dr,dc,s）;
else
{//用t号L型骨牌覆盖左上角
board[tr+s][tc+s]=t;//覆盖其余方格
chessBoard（tr+s,tc+s,tr+s,tc+s,s）;
}
}
试验运行结果
三：
二分搜索
一、实验目的与要求
1、熟悉二分搜索算法；
2、初步掌握分治算法；
二、实验题
1、设a[0:
n-1]是一个已排好序的数组。
请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。
当搜索元素在数组中时，I和j相同，均为x在数组中的位置。
三、程序代码：
#include
usingnamespacestd;
intmain（）
{
intconstlength=100;
intn,x;
inta[length];
cout<<"依次输入数组的长度，数组内容，要查找的数"<cin>>n;//输入数组的长度
for（inti=0;icin>>a[i];
cin>>x;
voidBinarySearch（inta[],intn,intx）;
BinarySearch（a,n,x）;
return0;
}
voidBinarySearch（inta[],intn,intx）//n:
数组长度，i，j分别表示下标
{
inti,j,mid=0,left=0;
intright=n-1;
while（left=0）
{
intmid=（left+right）/2;
if（x==a[mid]）
{
i=j=mid;
break;
}
if（x>a[mid]）
left=mid+1;
else
right=mid-1;
}
if（（i==j）&&（i>=0））
cout<<"所找的数据在数组中下标为：
"<else
{
i=right;
j=left;
cout<<"所找的数据不在数组中，其前后下标为：
"<}
}
如上图所示数组的长度为5，其内容依次为12345，所要找的数据位3，他的下表正好是2，结果是正确的
如上图数组的长度为7，输入的数组是1346789，所要查找的数字式5，它不在数组中，其前后的下表分别为2,3结果是正确的。
实验小结：
第一个实验自己做了出来，然而第二个实验卡了很久，对棋盘覆盖问题上课听懂了但是应用到实际上就有点问题了，最后还是在同学的帮助下完成的！
后面的这个提高题也是查考同学的，虽然自己没能做出来，但是感觉还是应该去学习！
实验二动态规划算法
一：
最长公共子序列问题
一、实验目的与要求
1、熟悉最长公共子序列问题的算法；
2、初步掌握动态规划算法；
二、实验题
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：
zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
三、实验程序
#include
usingnamespacestd;
intfun（char*x）
{
char*y=x;
while（*y++）{};
returny-x-1;
}
voidLCSLength（char*x,char*y,intm,intn,int**c,int**b）
{
inti,j;
for（i=1;i<=m;i++）c[i][0]=0;
for（i=1;i<=n;i++）c[0][i]=0;
for（i=1;i<=m;i++）
for（j=1;j<=n;j++）
{if（x[i]==y[j]）
{c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
elseif（c[i-1][j]>=c[i][j-1]）
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
voidLCS（inti,intj,char*x,int**b）
{
if（i==0||j==0）return;
if（b[i][j]==1）
{
LCS（i-1,j-1,x,b）;
printf（"%c",x[i]）;
}
elseif（b[i][j]==2）
LCS（i-1,j,x,b）;
elseLCS（i,j-1,x,b）;
}
intmain（）
{
charx[50],y[50];
intm,n;
int**c=newint*[50],**b=newint*[50];
for（inti=0;i<50;i++）
{
c[i]=newint[50];
b[i]=newint[50];
}
//intc[50][50],b[50][50];
cout<<"请输入第一组字符串：
";
cin>>x;
cout<<"请输入第二组字符串：
";
cin>>y;
m=fun（x）;
n=fun（y）;
LCSLength（x,y,m,n,c,b）;
LCS（m,n,x,b）;
cout<return0;
}
四、运行结果
二：
最大子段和问题
一、实验目的与要求
1、熟悉最长最大字段和问题的算法；
2、进一步掌握动态规划算法；
二、实验题
若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。
三、程序清单
#include
usingnamespacestd;
intMaxSum（intn,int*a,int&besti,int&bestj）
{
intsum=0;
for（inti=0;i{
intthissum=0;
for（intj=i;j<=n;j++）
{
thissum+=a[j];
if（thissum>sum）
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
returnsum;
}
intmain（）
{
int*a=newint[50];
intx,n,besti,bestj;
cout<<"请输入字符串的个数：
";
cin>>n;
cout<<"请输入字符串中的每个数字：
";
for（inti=0;i{
cin>>a[i];
}
x=MaxSum（n,a,besti,bestj）;
cout<<"最大子段和为：
"<<"起始位置：
"<"<return0;
}
四、运行结果
实验小结
第一个求公共子序列感觉和递归查询差不多，然后再查询第二列进行对比！
最大子段和感觉就像求整列的和！
实验三贪心算法（2学时）
一：
多机调度问题
一、实验目的与要求
1、熟悉多机调度问题的算法；
2、初步掌握贪心算法；
二、实验题
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。
作业不能拆分成更小的子作业。
三、实验程序
#include
usingnamespacestd;
typedefstructJob
{
intID;//作业号
inttime;//作业所花费的时间
}Job;
JobJ[10];
typedefstructJobNode//作业链表的节点
{
intID;
inttime;
JobNode*next;
}JobNode,*pJobNode;
typedefstructHeader//链表的表头,不同的机器？
？
{
ints;//表示其最大的容量
pJobNodenext;
}Header,*pHeader;//
intl=1;
intmain（）
{
//JobJ[10];
HeaderM[10];
intm,n;//机器的个数
cout<<"请输入数据作业的个数与机器的个数"<cin>>n>>m;
cout<<"请输入所有的任务的相关数据"<for（inti=1;i<=m;i++）
M[i].s=0;//表示其最大容量
for（l=1;l<=n;l++）//所有的任务作业
cin>>J[l].ID>>J[l].time;
intSelectMin（Header*M,intm）;//SelectMin（M,m）;
for（l=1;l<=n;l++）
cout<<"第"<<<"M"<return0;
}
intSelectMin（Header*M,intm）//有几台机器，就创建几个链表
{
intk=1;
for（inti=1;i<=m;i++）
{
if（M[i].s<=M[1].s）//最小的加入,s标识时间的和值
k=i;
}
M[k].s+=J[l].time;
returnk;//k是标识第几台机器加入作业
}
五、实验结果
二：
用贪心算法求解最小生成树
一、实验要求与目的
1、熟悉贪心算法的基本原理与适用范围。
2、使用贪心算法编程，求解最小生成树问题。
二、实验内容
1、任选一种贪心算法（Prim或Kruskal），求解最小生成树。
对算法进行描述和复杂性分析。
编程实现，并给出测试实例
三、实验程序
#include
usingnamespacestd;
intconstinf=100;
intmain（）
{
intn=6;
cout<<"所给图的最小生成树一次选定的边是表示为：
"<intc[7][7]=
{
{inf,inf,inf,inf,inf,inf,inf},
{inf,inf,6,1,5,inf,inf},
{inf,inf,inf,5,inf,3,inf},
{inf,1,5,inf,5,6,4},
{inf,5,inf,5,inf,inf,2},
{inf,inf,3,6,inf,inf,6},
{inf,inf,inf,4,2,6,inf}
};
//c[1][2]=6;c[1][4]=5;c[1][3]=1;c[2][3]=5;c[3][4]=5;c[2][5]=3;c[2][6]=2;
//c[3][5]=6;c[3][6]=4;c[5][6]=6;c[2][1]=6;c[4][1]=5;c[3][1]=1;c[3][2]=5;c[4][3]=5;c[5][2]=3;c[6][2]=2;
//c[5][3]=6;c[6][3]=4;c[6][5]=6;
voidprim（intn,intc[7][7]）;
prim（n,c）;
return0;
}
voidprim（intn,intc[7][7]）
{
intlowcost[7];
intcloset[7];
bools[10];
s[1]=true;
for（inti=2;i<=n;i++）
{
lowcost[i]=c[1][i];
closet[i]=1;
s[i]=false;
}
intj=1;
for（i=1;i{
intmin=inf;
intj=1;
for（intk=2;k<=n;k++）
if（（lowcost[k]s[k]）&&（lowcost[k]>0））
{
min=lowcost[k];
j=k;
}
cout<"<s[j]=true;
for（k=2;k<=n;k++）
if（（c[j][k]s[k]））
{
lowcost[k]=c[j][k];
closet[k]=j;
}
}
}
四、实验结果
五、实验小结
贪心算法上课老师讲的时候也能听懂，讲的例子也能明白，但是在实际调度时遇到了不小的麻烦！
最后在老师和同学的帮助下完成了！
尽管自己没有做出来，但是对贪心算法的实际操作有了更一步的把握！
实验四回溯算法和分支限界法（2学时）
一：
符号三角形问题
一、实验目的与要求
1、掌握符号三角形问题的算法；
2、初步掌握回溯算法；
二、实验题图
下面都是“-”。
下图是由14个“+”和14个“-”组成的符号三角形。
2个同号下面都是“+”，2个异号下面都是“-”。
在一般情况下，符号三角形的第一行有n个符号。
符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相
三、实验程序
#include
usingnamespacestd;
typedefunsignedcharuchar;
intsum;uchar**p;//符号存储空间；//表示满足要求的三角形个数
charch[2]={'+','-'};intn;//第一行符号总数
inthalf;intcount;//用来计算‘-’的个数
voidBackTrace（intt）
{
if（t>n）
{
sum++;
cout<<"第"<"<for（inti=1;i<=n;i++）
{
for（intj=1;jcout<<"";
for（j=1;j<=n-i+1;j++）
cout<cout<}
}
else
{
for（inti=0;i<=1;i++）
{
p[1][t]=i;//确定第一行第t个的值；
count+=i;//用来计算‘-’的个数；
for（intj=2;j<=t;j++）
{
p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//第一行大于等于2时确定后面从第2行开始增加的一
count+=p[j][t-j+1];//列中符号，计算‘-’个数；
}
if（count<=half&&（t*（t+1）/2-count）<=half）//约束条件；
{
BackTrace（t+1）;
}
for（
升级会员 