第二篇：计算机算法与设计分析实验报告 计科11-5班 孙龙龙(08113490)
计算机算法与设计分析实验报告
班级：计科11-5班
姓名：孙龙龙
学号：08113490
指导老师： 张永平
计算机科学与技术学院
20##-12-30
目录
实验一 分治与递归 ……………………………………………………………………………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 <iostream>
using namespace std;
int main()
{
int a,b,c;
int q(int n,int m);
cout<<"请输入整数及大于最大加数的数"<<endl;
cin>>a>>b;
c=q(a,b);
cout<<"所需要的划分数为："<<c<<endl;
return 0;
}
int q(int n,int m)
{
if ((n<1)||(m<1)) return 0;
if ((n==1)||(m==1)) return 1;
if (n<m) return q(n,n);
if (n==m) return q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
实验结果：
结果分析：
实验时入得数据为：所要划分的整数是6，他的划分的最大加数的值不得大于6，根据实际其划分的情况为11种，因而可知其程序的运行结果是正确的。
二：棋盘覆盖问题
一、实验目的与要求
1、掌握棋盘覆盖问题的算法；
2、初步掌握分治算法
二、实验题：
盘覆盖问题：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、程序代码：
#include <iostream>
using namespace std;
int tile=0; //全局变量，表示特殊格的号
int board[1000][1000];
int main()
{
int tr, tc, dr, dc, size;
int tile=0; //全局变量，表示特殊格的号
void chessBoard(int tr, int tc, int dr, int dc, int size);
cout<<"输入数据"<<endl;
cin>>tr>>tc>>dr>>dc>>size;
cout<<endl<<endl;
chessBoard(tr, tc, dr, dc, size);
for(int i=1;i<=size;i++)
{
for(int j=1;j<=size;j++)
cout<<board[i][j]<<" ";
cout<<endl;
}
return 0;
}
void chessBoard(int tr, int tc, int dr, int dc, int size)//左上角行号、列号，特殊格的行号、列号棋盘大小
{
if (size == 1)
return; //???????tiao chu
int t = ++tile, // L型骨牌号 ？？？？？？
s = size/2; // 分割棋盘 // 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中
chessBoard(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 < tr + s && dc >= 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 < tc + s)
// 特殊方格在此棋盘中
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 <iostream>
using namespace std;
int main()
{
int const length=100;
int n,x;
int a[length];
cout<<"依次输入数组的长度，数组内容，要查找的数"<<endl;
cin>>n; //输入数组的长度
for(int i=0;i<n;i++)
cin>>a[i];
cin>>x;
void BinarySearch(int a[],int n,int x);
BinarySearch(a, n, x);
return 0;
}
void BinarySearch(int a[],int n,int x) //n:数组长度，i，j分别表示下标
{
int i,j,mid=0,left=0;
int right=n-1;
while(left<right+1&&left>=0)
{
int mid=(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<<"所找的数据在数组中下标为："<<i<<endl;
else
{
i=right;
j=left;
cout<<"所找的数据不在数组中，其前后下标为："<<i<<','<<j<<endl;
}
}
如上图所示数组的长度为5，其内容依次为1 2 3 4 5，所要找的数据位3，他的下表正好是2，结果是正确的
如上图数组的长度为7，输入的数组是1 3 4 6 7 8 9，所要查找的数字式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<iostream>
using namespace std;
int fun(char *x)
{
char *y=x;
while(*y++){};
return y-x-1;
}
void LCSLength(char *x ,char *y,int m,int n, int **c, int **b)
{
int i ,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;
}
else if (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;
}
}
}
void LCS(int i ,int j, 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]);
}
else if (b[i][j]== 2)
LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
int main()
{
char x[50],y[50];
int m,n;
int **c =new int*[50],**b =new int*[50];
for(int i=0;i<50;i++)
{
c[i] =new int[50];
b[i] =new int[50];
}
//int c[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<<endl;
return 0;
}
四、运行结果
二：最大子段和问题
一、实验目的与要求
1、熟悉最长最大字段和问题的算法；
2、进一步掌握动态规划算法；
二、实验题
若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。
三、程序清单
#include<iostream>
using namespace std;
int MaxSum(int n,int *a,int &besti,int &bestj)
{
int sum=0;
for(int i=0;i<n;i++)
{
int thissum=0;
for(int j=i;j<=n;j++)
{
thissum+=a[j];
if(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
int main()
{
int *a=new int[50];
int x,n,besti,bestj;
cout<<"请输入字符串的个数：";
cin>>n;
cout<<"请输入字符串中的每个数字：" ;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
x=MaxSum(n,a,besti,bestj);
cout<<"最大子段和为："<<"起始位置："<<besti+1<<"至"<<bestj+1<<"结果为："<<x<<endl;
return 0;
}
四、运行结果
实验小结
第一个求公共子序列感觉和递归查询差不多，然后再查询第二列进行对比！最大子段和感觉就像求整列的和！
实验三贪心算法（2学时）
一：多机调度问题
一、实验目的与要求
1、熟悉多机调度问题的算法；
2、初步掌握贪心算法；
二、实验题
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
三、实验程序
#include <iostream>
using namespace std;
typedef struct Job
{
int ID;//作业号
int time;//作业所花费的时间
}Job;
Job J[10];
typedef struct JobNode //作业链表的节点
{
int ID;
int time;
JobNode *next;
}JobNode,*pJobNode;
typedef struct Header //链表的表头,不同的机器？？
{
int s; //表示其最大的容量
pJobNode next;
}Header,*pHeader; //
int l=1;
int main()
{
//Job J[10];
Header M[10];
int m,n; //机器的个数
cout<<"请输入数据作业的个数与机器的个数"<<endl;
cin>>n>>m;
cout<<"请输入所有的任务的相关数据"<<endl;
for(int i=1;i<=m;i++)
M[i].s=0; //表示其最大容量
for( l=1;l<=n;l++)//所有的任务作业
cin>>J[l].ID>>J[l].time;
int SelectMin(Header* M,int m);//SelectMin(M,m);
for(l=1;l<=n;l++)
cout<<"第"<<l<<"个任务在第"
<<"M"<<SelectMin(M,m)<<"台机器上完成"<<endl;
return 0;
}
int SelectMin(Header* M,int m) //有几台机器，就创建几个链表
{
int k=1;
for(int i=1;i<=m;i++)
{
if(M[i].s<=M[1].s) //最小的加入,s标识时间的和值
k=i;
}
M[k].s+=J[l].time;
return k; //k是标识第几台机器加入作业
}
五、实验结果
二： 用贪心算法求解最小生成树
一、实验要求与目的
1、 熟悉贪心算法的基本原理与适用范围。
2、 使用贪心算法编程，求解最小生成树问题。
二、实验内容
1、 任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算法进行描述和复杂性分析。
编程实现，并给出测试实例
三、实验程序
#include <iostream>
using namespace std;
int const inf=100;
int main()
{
int n=6;
cout<<"所给图的最小生成树一次选定的边是表示为："<<endl;
int c[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;
void prim(int n,int c[7][7]);
prim(n,c);
return 0;
}
void prim(int n,int c[7][7])
{
int lowcost[7];
int closet[7];
bool s[10];
s[1]=true;
for(int i=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closet[i]=1;
s[i]=false;
}
int j=1;
for(i=1;i<n;i++)
{
int min=inf;
int j=1;
for(int k=2;k<=n;k++)
if((lowcost[k]<min)&&(!s[k])&&(lowcost[k]>0))
{
min=lowcost[k];
j=k;
}
cout<<j<<"<->"<<closet[j]<<endl;
s[j]=true;
for(k=2;k<=n;k++)
if((c[j][k]<lowcost[k])&&(!s[k]))
{
lowcost[k]=c[j][k];
closet[k]=j;
}
}
}
四、实验结果
五、实验小结
贪心算法上课老师讲的时候也能听懂，讲的例子也能明白，但是在实际调度时遇到了不小的麻烦！最后在老师和同学的帮助下完成了！尽管自己没有做出来，但是对贪心算法的实际操作有了更一步的把握！
实验四回溯算法和分支限界法（2学时）
一：符号三角形问题
一、实验目的与要求
1、掌握符号三角形问题的算法；
2、初步掌握回溯算法；
二、实验题图
下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相
三、实验程序
#include <iostream>
using namespace std;
typedef unsigned char uchar;
int sum; uchar** p; //符号存储空间；//表示满足要求的三角形个数
char ch[2]={'+','-'}; int n; //第一行符号总数
int half; int count; //用来计算‘-’的个数
void BackTrace(int t)
{
if (t>n)
{
sum++;
cout<<"第"<<sum<<"个三角形："<<endl;
for (int i=1;i<=n;i++)
{
for (int j=1;j<i;j++)
cout<<" ";
for (j=1;j<=n-i+1;j++)
cout<<ch[p[i][j]]<<" ";
cout<<endl;
}
}
else
{
for (int i=0;i<=1;i++)
{
p[1][t]=i; //确定第一行第t个的值；
count+=i; //用来计算‘-’的个数；
for (int j=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 (j=2;j<=t;j++) //回溯，判断另一种符号情况；
{
count-=p[j][t-j+1];
}
count-=p[1][t];
}
}
}
int main()
{
cout<<"请输入第一行符号的个数：";
cin>>n;
count=0;
sum=0;
half=n*(n+1)/2;
if (half%2==0)
{
half=half/2;
p=new uchar* [n+1];
for (int i=0;i<=n;i++)
{
p[i]=new uchar[n+1];
memset(p[i],0,sizeof(uchar)*(n+1));
}
BackTrace(1);
for (i=0;i<=n;i++)
{
delete[] p[i];
}
delete[] p;
cout<<"满足要求的三角形符号共有："<<sum<<"个";
}
else
{
cout<<"不存在这样的三角形符号！";
}
return 0;
}
五、实验结果
二：0—1背包问题
一、实验目的与要求
1、掌握0—1背包问题的回溯算法；
2、进一步掌握回溯算法；
二、实验题：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
三、实验程序
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品数
int *w;//物品重量数组
int *p;//物品价值数组
int cw;//当前重量
int cp;//当前价值
int bestp;//当前最优值
int *bestx;//当前最优解
int *x;//当前解
};
int Knap::Bound(int i)
{
//计算上界
int cleft=c-cw;//剩余容量
int b=cp;
//以物品单位重量价值递减序装入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子树
{ x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子树
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//装入所有物品
//依物品单位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;K.cw=0;
K.c=c;K.n=n;
K.bestp=0;//回溯搜索
K.Backtrack(1);K.print();
delete [] Q;delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;int *w; int c=0;int n=0;int i=0;
cout<<"请输入背包个数："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;w[0]=0;
cout<<"请输入各背包的价值："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"请输入各背包的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"请输入背包容量："<<endl;
cin>>c;
cout<<Knapsack(p,w,c,n)<<endl;
}
四、实验结果
实验小结：
符号三角形问题以前在学C++时，自己做出来过这种图形，不过没有这么多，而且算法也不一样！原打算上周交的，最近在复习软件工程就一直没有弄这个！0-1背包问题也学了好多，但是学的不是很深，感觉有点看不透！最后感谢老师和同学的帮助及指导！！