实验四 贪心算法
- 格式：doc
- 大小：79.50 KB
- 文档页数：7
实验四 贪心算法
一、 实验目的
进一步理解贪心算法的基本思想，学会根据具体问题设计贪心选择策略，会使用贪心算法解决一些实际问题。
二、 实验要求
1、上机前的准备工作
根据实验内容中所给题目，利用所学贪心算法的基本设计思想设计算法并编写好上机程序，以提高上机效率；
2、独立上机，输入、调试所编程序；
3、上机结束后，写出实验报告。
4、上机时间：2学时
三、 实验内容
1、4-1 会场安排问题
#include
using namespace std;
const int MAX=100;
struct sport
{
int start;//开始时间
int end;//结束时间
};
int m[MAX];
void sort(struct sport t[],int n)// 由小到大排序
{
int i,j;
for(i=1;i
for(j=1;j
if(t[j].start>t[j+1].start)
{
struct sport temp;
temp=t[j];
t[j]=t[j+1];
t[j+1]=temp;
}
}
void main()
{
int max=1,count=1,n;
cout<<"请输入活动的个数：";
cin>>n;
sport t[MAX];
for(int k=1;k<=n;k++)
{ cout<<"请输入第"<
cin>>t[k].start;
cin>>t[k].end;
}
m[0]=t[1].end;
sort(t,n);
for(int i=2;i<=n;i++)
{
int j=0;
while(j
{
j++;
}
m[j]=t[i].end;
count=j+1;
if(count>max)
max=count;
}
cout<<"活动场所共需个数："<
}
运行结果：
2、4-2 最优合并问题
#include
using namespace std;
const int MAX=100;
void sort(int r[],int n)
{
int j;
for(int i=2;i<=n;i++)
{
r[0]=r[i];
j=i-1;
while(r[0]
{
r[j+1]=r[j]; j=j-1;
}
r[j+1]=r[0];
}
}
int max(int r[],int n)
{
int sum=0;
for(int i=n;i>1;i--)
{
sum+=r[i]+r[i-1]-1;
r[i-1]=r[i]+r[i-1];
}
return sum;
}
int min(int r[],int n)
{
int sum=0;
for(int i=1;i
{
sum+=r[i]+r[i+1]-1;
r[i+1]=r[i]+r[i+1];
}
return sum;
}
void main()
{
int n,a[MAX],b[MAX];
cout<<"请输入序列的个数:";
cin>>n;
cout<<"请输入各个序列的长度："<
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a,n);
for(int j=1;j<=n;j++)
b[j]=a[j];
cout<<"最多比较次数："<
cout<<"最少比较次数："<
}
运行结果：
3、数列极差问题
在黑板上写了N个正整数组成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+3，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。
另一种思路：
1）先排序
2）求最小：利用两个最大数（正）相乘得到最大数
3）求最大：两个最小数相乘结果插入到已排序好的数列中。
编程实现之。
#include
using namespace std;
const int MAX=100;
void sort(int r[],int n)//将数列由小到大排序
{
int j;
for (int i=2; i<=n; i++)
{
r[0]=r[i]; j=i-1;
while (r[0]
{
r[j+1]=r[j];
j=j-1;
}
r[j+1]=r[0];
}
}
int min(int a[],int n)//求最小值
{
int m;
for(int i=n;i>1;i--)
{
m=a[i]*a[i-1]+3;
a[i-1]=m;
}
return m;
} int max(int a[],int n)//求最大值
{
int j,m;
for(int i=1;i
{
m=a[i]*a[i+1]+3;
j=i+2;
while(a[j]
{
a[j-1]=a[j];
j++;
}
a[j-1]=m;
}
return m;
}
void main()
{
int a[MAX],b[MAX];
cout<<"请输入数列包含正整数的个数：";
int n;
cin>>n;
cout<<"请依次输入数列元素：";
for(int count=1;count<=n;count++)
{
cin>>a[count];
}
sort(a,n);
for(int i=1;i<=n;i++)
b[i]=a[i];
int maxi=max(b,n);
int mini=min(a,n);
cout<<"最小值："<
cout<<"最大值："<
cout<<"数列的极差为："<
}
运行结果：
4、4-6
#include
#include
using namespace std;
const int MAX=100;
struct customer
{
int time;//等待时间
int no;//顾客的服务次序号
};
void sort(struct customer t[],int n)
{
int i,j;
for(i=1;i
for(j=1;j
if(t[j].time>t[j+1].time)
{
struct customer temp;
temp=t[j];
t[j]=t[j+1];
t[j+1]=temp;
}
}
float serve(struct customer t[],int n)
{
int k=n;
float sum=0;
for(int i=1;i<=n;i++)
{
sum+=t[i].time*k;
k--;
}
return sum/n;
}
void main()
{ int n;
customer t[MAX];
cout<<"请输入顾客的数量：";
cin>>n;
cout<<"请依次输入顾客的等待时间："<
for(int i=1;i<=n;i++)
{
cin>>t[i].time;
t[i].no=i;
}
sort(t,n);
cout<
cout<<"顾客平均等待时间："<
cout<<"顾客的服务次序为："<
for(int k=1;k<=n;k++)
cout<
cout<
cout<
}
运行结果：
