《算法设计与分析》实验报告
班级：xxxxx_ 姓名：_xxxxx学号：_xxxxxxxxx__日期 xxxx-xx-xx
实验三、贪心算法
实验目的：
1、 理解贪心算法的概念；
2、 掌握贪心算法的基本要素；
3、 理解贪心算法与动态规划算法的差异；
4、 理解贪心算法的一般理论。
实验项目：
1、 活动安排问题；
2、 最优装载问题；
3、 多机调度。
实验步骤
（请附上编写的程序及其运行结果截图!!）:
1.活动安排问题
代码：
#include <iostream>
using namespace std;
#define MAXCOUNT 100
#define TRUE 1
#define FALSE 0
typedef int Time;
typedef struct
{
Time start;
Time finish;
int index;
bool abc;
}HuoDong;
typedef struct
{
HuoDong r[MAXCOUNT+1];
int length;
}HDS;
int Partition(HDS &L,int low,int high)
{
int shuzhou;
L.r[0]=L.r[low];
shuzhou=L.r[low].finish;
while(low<high)
{
while(low<high && L.r[high].finish>=shuzhou)
--high;
L.r[low]=L.r[high];
while(low<high && L.r[low].finish<=shuzhou)
++low;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QuickSort(HDS &L,int low,int high)
{
int shuzhou;
if(low<high)
{
shuzhou=Partition(L,low,high);
QuickSort(L,low,(shuzhou-1));
QuickSort(L,(shuzhou+1),high);
}
}
void GreedySelector(HDS &L)
{
int n=L.length-1;
L.r[1].abc=true;
int j=1;
for(int i=2;i<=n;i++)
{
if(L.r[i].start>=L.r[j].finish)
{
L.r[i].abc=true;
j=i;
}
else
L.r[i].abc=false;
}
}
void Listr(HDS L)
{
int n=L.length-1;
int count=0;
for(int i=1;i<=n;i++)
{
if(L.r[i].abc==true)
{
cout<<"第个"<<L.r[i].index<<"活动被选中"<<endl;
count++;
}
}
cout<<"可以安排的活动总数为："<<count<<endl;
}
int main()
{
int n;
HDS L;
cout<<"请输入可选择的活动个数（注意：最大数目不能超过 100个!）："<<endl;
cin>>n;
if(n>100)
{
cout<<"你输入的活动个数太大!!!"<<endl;
return FALSE;
}
L.length=(n+1);
cout<<"请输入各个活动开始的时间： "<<endl;
for(int i=1;i<=n;i++)
{
cout<<"请输入第个"<<i<<"活动开始的时间：";
cin>>L.r[i].start;
L.r[i].index=i;
cout<<endl;
}
cout<<"请输入各个活动结束的时间"<<endl;
for(int i=1;i<=n;i++)
{
cout<<"请输入第个"<<i<<"活动结束的时间："<<endl;
cin>>L.r[i].finish;
cout<<endl;
}
QuickSort(L,1,n);
GreedySelector(L);
Listr(L);
return TRUE;
}
运行结果：
2.最优装载问题
代码：
#include<iostream>
using namespace std;
class Loading
{
friend int MaxLoading(int [] ,int ,int ,int []);
private:
//int Bound(int i);
void Backtrack(int t);
int n;//集装箱数
int *x;//当前解
int *bestx;//当前最优解
int *w;//集装箱重量数组
int c;//第一艘轮船的载重量
int cw;//当前重量
int bestw;//当前最优载重量
int r;//剩余集装箱重量
};
void Loading::Backtrack(int i)
{
if(i>n)
{
if(cw>bestw)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestw=cw;
}
return;
}
r-=w[i];
if(cw+w[i]<=c)
{
x[i]=1;
cw+=w[i];
Backtrack(i+1);
cw-=w[i];
}
if(cw+r>bestw)
{
x[i]=0;
Backtrack(i+1);
}
r+=w[i];
}
int MaxLoading(int w[],int c,int n,int bestx[]){
Loading X;
X.x=new int[n+1];
X.w=w;
X.c=c;
X.n=n;
X.bestx=bestx;
X.bestw=0;
X.cw=0;
X.r=0;
for(int i=1;i<=n;i++)
X.r+=w[i];
X.Backtrack(1);
delete[] X.x;
return X.bestw;
}
int main()
{
int *w;
int *bestx;
int n;
int c;
cout<<"请输入集装箱数:";
cin>>n;
cout<<"请输入第一艘轮船载重量:";
cin>>c;
w=new int[n+1];
w[0]=0;
cout<<"请输入重量:"<<endl;
for(int i=1;i<=n;i++)
cin>>w[i];
bestx=new int[n+1];
for(int i=1;i<=n;i++)
bestx[i]=0;
int m=MaxLoading(w,c,n,bestx);
cout<<"最大装载数量:"<<m<<endl;
return 0;
}
运行结果：
3.多机调度
代码：
#include <iostream>
#include <iomanip>
using namespace std;
typedef struct Job
{
int ID;
int time;
}Job;
typedef struct JobNode
int ID;
int time;
JobNode *next;
}JobNode;
typedef struct Header
{
int s;
JobNode *next;
}Header;
int SelectMin(Header* M,int m)
{
int k=0;
for(int i=1;i<m;i++)
{
if(M[i].s<M[k].s)
k=i;
}
return k;
}
void QuickSort(Job *job,int left,int right)
{
int middle=0,i=left,j=right;
Job itemp;
middle=job[(left+right)/2].time;
do
{
while((job[i].time>middle)&&(i<right))
i++;
while((job[j].time<middle)&&(j>left))
j--;
if(i<=j)
{
itemp=job[j];
job[j]=job[i];
job[i]=itemp;
i++;
j--;
}
}
while(i<=j);
if(left<j)
QuickSort(job,left,j);
if(right>i)
QuickSort(job,i,right);
}
void display(Header *M,int m)
{
JobNode *p;
for(int i=0;i<m;i++)
{
cout<<"\n第"<<i<<"台机器上处理的工作序号；";
if(M[i].next==0)
continue;
p=M[i].next;
do{
cout<<p->ID<<' ';
p=p->next;
}while(p!=0);
}
}
void outSort(Job *job,int n)
{
cout<<"\n按工作时间由大到小为：\n时间：\t";
for(int i=0;i<n;i++)
cout<<setw(4)<<job[i].time;
cout<<"\n序号：\t";
for(int i=0;i<n;i++)
cout<<setw(4)<<job[i].ID;
}
void solve(Header *head,Job *job,int n,int m)
{
int k;
for(int i=0;i<m&&i<n;i++)
{
JobNode *jobnode = new JobNode;
jobnode->time = job[i].time;
jobnode->ID = job[i].ID;
jobnode->next = 0;
head[i].s = jobnode->time;
head[i].next = jobnode;
}
if(n<=m)
{
for(int i=0;i<m;i++)
{
head[i].s=0;
head[i].next=0;
}
}
if(n>m)
{
for(int i=0;i<n;i++)
{
JobNode *p;
JobNode *jobnode = new JobNode;
jobnode->time = job[i].time;
jobnode->ID = job[i].ID;
jobnode->next = 0;
k=SelectMin(head,m);
p=head[k].next;
head[k].s+=jobnode->time;
while(p->next!=0)
p=p->next;
p->next = jobnode;
}
}
}
int main()
{
int m,n;
cout<<"\t\t《多机调度问题》\n";
cout<<"请输入机器台数m:";
cin>>m;
Header *head=new Header[m];
cout<<"请输入作业个数n:";
cin>>n;
Job *job=new Job [n];
cout<<"\n请按序号输入每个作业调度所需时间time：";
for(int i=0;i<n;i++)
{
cin>>job[i].time;
job[i].ID=i;
}
QuickSort(job,0,n-1);
outSort(job,n);
solve(head,job,n,m);
display(head,m);
cout<<endl<<endl;
return 0;
}
运行结果：
实验中遇到的问题及解决方法：
（包括本实验中遇到的问题、具体的解决方法、还没有解决的问题、实验收获等）
(要仔细写实验反思，这将有助于你不断进步！)
实验心得：
通过活动安排问题，最优装载问题，多机调度的编写让我理解了贪心算法的概念和掌握贪心算法的基本要素以及理解了贪心算法的基本理论。在编写代码时，我也遇到了很多问题，比如动态数组的构建数组数据的传递等等。我通过翻书和查资料最后还是一一解决了。
第二篇：《算法设计与分析》上机实验报告模板
《算法设计与分析》
上 机 实 验 报 告
【排版说明】
（1）一级标题用宋体四号，加粗。
（2）如有二级标题，请使用宋体、小四、加粗。
（3）正文汉字均用宋体5号，英文用Times New Roman字体。
（4）正文行距建议设置为1.5倍行距。
（5）实验报告中有图、表的，图、表格式必须标准，有编号，有标题。如下所示（图的标题在下方、表的标题在上方）：
图1 XXXXXXX图
表1 XXXXXXX表
1. 上机题目及实验环境
1.1上机题目：计算能存放的程序数
1.2实验环境：
CPU：
内存：
操作系统：xp
软件平台：vc6.0
2. 算法设计与分析
基本思想
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
就该题而言
算法设计
(1）将数据集 S 均分为 S1 和 S2；
（2）求解 S1 和 S2 中的最大和最小值；
（3）最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；
（4）采用同样的处理方法递归处理 S1 和 S2。
min_max(S, min, max) {
if |S| = 2 then
min ß min(S)
max ß max(S)
else
split S evenly into S1 and S2
min_max(S1, min1, max1)
min_max(S2, min2, max2)
min ß min(min1, min2)
max ß max(max1, max2)
}
给出具体的原理，算法设计与分析细节等。
3. 核心代码
void min_max(int arry[],int i,int j,int *min,int *max)//找出最大值和最小值
{
int mid,min1,min2,max1,max2;
if(i==j)
{
*max=arry[i];
*min=arry[i];
}
else
{
if(j==i+1)
if(arry[i]>arry[j])
{
*min=arry[j];
*max=arry[i];
}
else
{
*min=arry[i];
*max=arry[j];
}
else
{
mid=(i+j+1)/2;
min_max(arry,i,mid,&min1,&max1);
min_max(arry,mid+1,j,&min2,&max2);
*min = min1<min2 ? min1:min2;
*max = max1>max2 ? max1:max2;
}
}
在main函数中通过产生随机数给出数据通过调用min_max函数实现找出最大值，最小值并把他们返回main（）函数输出。
4. 运行与调试
给出程序的运行结果。建议给出不同情况下的运行结果并加以比较（如排序算法可以给出输入数据规模不等时的运行结果比较，如数组规模为100时的实验结果、数组规模为1000时的实验结果、数组规模为10000时的实验结果等）。程序运行有屏幕输出的，应给出屏幕截图。
图1 显示随机产生100个0到100个整数 找出了之间的最大值和最小值
图2 显示随机产生1000个0到100个整数 找出了之间的最大值和最小值
图3 显示随机产生10个0到100个整数 找出了之间的最大值和最小值
图1
图2
图3
5. 结果分析和小结
（1）对结果的分析。分析结果可以采用图或者表的形式给出。
运行时由于没有加随机数初始化函数 srand(time(0));每次运行结果都一样 这个问题在设计代码时由于时间匆忙也没有发现 知道被老师检查时 被老师发现 ，以致于我以后再也不会犯这个错误了。
（2）本次上机实验的收获、心得体会。
上机可以督促我自己写代码 每次上机前我都会先把代码大致写好，上机是运行并检查错误，这样不仅提高我的写代码能力，同时对算法这门课也有了更深刻的认识。老师检查运行结果可以发现我们的问题所在。对我们学习提供很大帮助。
附录（C/C++源代码）
列出程序源码。程序设计时注意设计风格。
/*用分治法查找数组元素的最大值和最小值。*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define M 10
void min_max(int arry[],int i,int j,int *min,int *max)
{
int mid,min1,min2,max1,max2;
if(i==j)
{
*max=arry[i];
*min=arry[i];
}
else
{
if(j==i+1)
if(arry[i]>arry[j])
{
*min=arry[j];
*max=arry[i];
}
else
{
*min=arry[i];
*max=arry[j];
}
else
{
mid=(i+j+1)/2;
min_max(arry,i,mid,&min1,&max1);
min_max(arry,mid+1,j,&min2,&max2);
*min = min1<min2 ? min1:min2;
*max = max1>max2 ? max1:max2;
}
}
}
void main()
{
int max,min,i,j,arry[M],k;
// srand(time(0));
printf("随机产生10个整数:\n");
for(k=0;k<M;k++)
{
arry[k]=rand()%100+1;
printf("%d ",arry[k]);
}
i=0;
j=M-1;
min_max(arry,i,j,&min,&max);
printf("\n最小值和最大值分别是：%d %d\n",min,max);
}