}
getchar();
}
五、实验结果截图
六、实验总结
分治算法是很有用的算法,分治法的设计一般是递归的。
两路合并排序是一个典型的分治算法,其基本运算为元素比较,最坏情况下的时间为W(n)=O(nlogn),在排序过程中需要使用与原序列相同长度的辅助数组temp,因此它所需的额外空间为O(n)。
通过编写代码,我很好的掌握了分治法的步骤:
划分;求解子问题;合并。
对“分治策略”有了更深的体会,它将原问题划分为彼此独立的、规模较小而结构相同的子问题。
实验2贪心法作业调度
一、实验目的
1.掌握贪心算法的基本思想
2.掌握贪心算法的典型问题求解
3.进一步多级调度的基本思想和算法设计方法
4.学会用贪心法分析和解决实际问题
二、实验内容
设计贪心算法实现作业调度,要求按作业调度顺序输出作业序列。
如已知n=8,效益p=(35, 30, 25, 20, 15, 10, 5, 1),时间期限 d=(4, 2, 4, 5, 6, 4, 5, 7),求该条件下的最大效益。
三、实验环境
Window7;惠普笔记本;VC++6.0.
四、算法描述和程序代码
#include
usingnamespacestd;
constintWork[8]={35,30,25,20,15,10,5,1};//所有作业按收益从大到小排序
constintmaxTime[8]={4,2,4,5,6,4,5,7};
classHomeWork{
private:
intres[8];
boolflag[8];
intmaxReap;
public:
voiddealWith(){
//遍历所有作业:
inti;
for(i=0;i<8;i++){
intTime=maxTime[i]-1;
if(!
flag[Time]){
//如果最大期限那一天还未安排作业,则将当前作业安排在所允许的最大期限那天
res[Time]=Work[i];
flag[Time]=true;
}
else{
//如果当前作业所允许的最大期限那一天已经安排的其他作业,就向前搜索空位,将该作业安排进去
for(intj=Time-1;j>=0;j--)
if(!
flag[j]){
res[j]=Work[i];
flag[j]=true;
break;
}
}
}
cout<<"作业完成顺序为:
";
for(i=0;i<7;i++){
cout<}
cout<cout<";
intj;
for(j=0;j<7;j++)
maxReap+=res[j];
cout<}
HomeWork(){
inti;
for(i=0;i<8;i++)
flag[i]=false;
maxReap=0;
}
};
voidmain(){
HomeWorka=HomeWork();
a.dealWith();
getchar();
}
五、实验结果截图
六、实验总结
通过实验编写代码使得我对应用贪心法求解问题有了很大的提高。
贪心法是一种求解组合优化问题的算法设计技术,其求解过程由一些列决策构成。
贪心算法的关键在于贪心策略,两要素是:
最优子结构和贪心策略,对带时限的作业进行排序是一个典型的贪心算法,在本次实验中我使用了改进后的可行解判定方法来解决这个问题,使算法的时间从Θ(n2)减少到接近O(n)。
实验3动态规划法求多段图问题
一、实验目的
1.掌握动态规划算法的基本思想
2.掌握多段图的动态规划算法
3.选择邻接表或邻接矩阵方式来存储图
4.分析算法求解的复杂度
二、实验内容
设G=(V,E)是一个带权有向图,其顶点的集合V被划分成k>2个不相交的子集Vi,1
图中所有边的始点和终点都在相邻的两个子集Vi和Vi+1中。
求一条s到t的最短路线。
参考课本P124图7-1中的多段图,试选择使用向前递推算法或向后递推算法求解多段图问题。
三、实验环境
Window7;惠普笔记本;VC++6.0.
四、算法描述和程序代码
#include
usingnamespacestd;
struct{
intr[50];
intlength;
}SqList,L;
voidMSort(intSR[],intTR1[],ints,intt);
voidMerge(intsR[],intTR[],inti,intmid,intn);
voidmain()
{
cout<<"请输入待排序的数目:
";
cin>>L.length;
cout<<"请输入待排序的数:
";
for(intc=0;ccin>>L.r[c];
cout<<"合并排序前的数组为:
";
for(intd=0;dcout<cout<MSort(L.r,L.r,0,L.length-1);
cout<<"合并排序后的数组为:
";
for(inti3=0;i3cout<cout<}
voidMSort(intSR[],intTR1[],ints,intt)//两路合并排序
{
intmid;
intTR2[100];
if(s==t)
TR1[s]=SR[s];
else//若序列的长度超过1,则划分为两个子序列
{
mid=(s+t)/2;//将待排序的序列一分为二
MSort(SR,TR2,s,mid);//对左子序列排序
MSort(SR,TR2,mid+1,t);//对右子序列排序
Merge(TR2,TR1,s,mid,t);//将两个有序子序列合并成一个有序序列
}
}
voidMerge(intSR[],intTR[],inti,intmid,intn)//将两个有序序列合并成一个有序序列
{
intj,k;
for(j=mid+1,k=i;i<=mid&&j<=n;++k)
{
if(SR[i]<=SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if(i<=mid)//如果左子序列还有元素未输出,则将左子序列剩余元素依次输出
{
intk1=k;
for(inti1=i;i1<=mid;i1++)
{
TR[k1]=SR[i1];
k1++;
}
}
if(j<=n)//如果右子序列还有元素未输出,则将右子序列剩余元素依次输出
{
intk2=k;
for(intj2=j;j2<=n;j2++)
{
TR[k2]=SR[j2];
k2++;
}
}
}
五、实验结果截图
六、实验总结
通过这次实验使得我对应用动态规划法求解问题有了很大的提高。
动态规划算法将原问题归约为规模较小、结构相同的子问题,建立原问题与子问题优化函数间的依赖关系,从规模较小的子问题开始,利用上述依赖关系求解规模更大的子问题,直到得到原始问题的解为止。
采用逐步向前递推的方式,由子问题的最优解来计算原问题的最优解。
算法所用空间除邻接矩阵和最优解path以外,还需要长度为n的cost和d两个局部以为数组。
这一算法的时间分析与DFS和BFS相似,总的执行时间为Θ(n)
实验4回溯法求n皇后问题
一、实验目的
1.掌握回溯算法的基本思想
2.通过n皇后问题求解熟悉回溯法
3.使用蒙特卡洛方法分析算法的复杂度
二、实验内容
要求在一个8*8的棋盘上放置8个皇后,使得它们彼此不受“攻击”。
两个皇后位于棋盘上的同一行、同一列或同一对角线上,则称它们在互相攻击。
现在要找出使得棋盘上8个皇后互不攻击的布局。
三、实验环境
Window7;惠普笔记本;VC++6.0.
四、算法描述和程序代码
#include
usingnamespacestd;
#defineN8
intres[100][8];
intcountRes=0;
boolPlace(intk,inti,int*x){
for(intj=0;jif(x[j]==i||abs(x[j]-i)==abs(j-k))
returnfalse;
returntrue;
}
voidNQueen(intk,intn,int*x){
for(inti=0;iif(Place(k,i,x)){
x[k]=i;
if(k==n-1){
for(i=0;ires[countRes][i]=x[i];
cout<}
countRes++;
cout<}else{
NQueen(k+1,n,x);
}
}
}
voidNQueen(intn,int*x){
NQueen(0,n,x);
}
intmain(){
intx[N];
for(inti=0;i*(x+i)=-10;
NQueen(N,x);
cout<charshow;
cout<<"是否显示图示?
(Y/N)"<cin>>show;
if(show=='Y'||show=='y'){
for(intn=0;ncout<<"第"<"<for(inti=0;ifor(intj=0;jif(res[n][i]==j)
cout<<"Q"<<"\t";
else
cout<<"*"<<"\t";
}
cout<}
}
}
return0;
}
五、实验结果截图
六、实验总结
通过这次试验我对皇后问题的知识点有了很大的了解,编写代码和调试代码的能力有所提高。
在算法设计策略中,回溯法是比贪心法和动态规划法更一般的方法。
n皇后问题以检查两皇后是否冲突作为基本运算,该算法的最坏情形复杂性为O(3n×2nn)=O(nn+1)。
n皇后问题有n!
个叶子节点,遍历时间为Ω(n!
)。