goodarrange.cpp

本程序实现了给出一些进程运行时间找出他们的最佳调度顺序

#include <stdio.h>

#include <malloc.h>

void  sort(int *P,int *D,int n)

{              //将作业按效益值非递增次序排序

int i,k,t;

for(k=1;k<n;++k)

for(i=k+1;i<=n;++i)

if(P[k]<P[i])

{

t=P[k];

P[k]=P[i];

P[i]=t;

t=D[k];

D[k]=D[i];

D[i]=t;

}

}

void JS(int *D,int *P,int *J,int n)

{     //J[i]是最优解中的第i个作业，终止时最优解中的作业的期限值按非递减次序排序

int i,j,k,r;

sort(P,D,n);

k=1;

J[1]=1;    //计入作业1

for(i=2;i<=n;++i)//按p的非增次序考虑作业。找i的位置并检查插入的可行性

{

r=k;

while((D[J[r]]>D[i])&&(D[J[r]]!=r))

--r;
if((D[J[r]]<=D[i])&&(D[i]>r))

{           //把i插入J

for(j=k;j>=r+1;--j)

J[j+1]=J[j];

J[r+1]=i;

k++;

}

}

printf("最优解为:");

printf("\n");

for(i=1;i<=k;++i)

{         //按顺序输出最优解中作业的期限值和效益值

printf("第%d个作业的期限值为%d，效益值为%d",i,D[J[i]],P[J[i]]);

printf("\n");

}

}

void main()

{

int n,j;

printf("请输入作业的个数:");

scanf("%d",&n);

int *D,*P,*J;

D=(int *) malloc(sizeof(int *)(n+1));

P=(int *) malloc(sizeof(int *)(n+1));

J=(int *) malloc(sizeof(int *)(n+1));

D[0]=P[0]=J[0]=0;  //初始化

printf("请输入每个作业的效益值：");

for(j=1;j<=n;j++)

scanf("%d",&P[j]);

printf("请输入每个作业的期限值：");

for(j=1;j<=n;j++)

scanf("%d",&D[j]);

JS(D,P,J,n);     //

}