算法作业5

#include
#include
using namespace std;

struct job{  //定义作业结构体 
    int id;  //作业id 
    int time;  //作业运行时间 
};
    
bool compareMethod(job j1,job j2){
    if(j1.time ==j2.time ){  //如果有作业运行时间相同,则按照id递增的顺序进行作业调度 
        return j1.id>number;
     
    job task[number]; 
    cout<<"n 请输入每个作业的各自运行时间:";
    for(int i=0;i>task[i].time;
    } 
    cout<<"n 每个作业的id和各自运行时间显示如下:"< 
所有的作业执行时间之和不会因为调度顺序而改变，因此不同的调度顺序只会导致不同的等待时间。由题可知，等待时间也属于作业的调度时间，因此需要尽量减少所有作业的等待时间，即采用贪心的思想，执行越快的作业优先级越高。总体的等待时间就会越短，因此就先比较执行时间，如果执行时间相同则比较作业的进入顺序，总的来说就是最短作业优先。
 因此该方法可以得到最优解
 
p250.a Prim算法 
树中顶点余下的顶点a(-,-)b(a,5),c(a,7),d(-,∞),e(a,2)e(a,2)b(e,3),c(e,4),d(e,5)b(e,3)c(e,4),d(e,5)c(e,4)d(c,4)d(c,4)
p255.1.1 Kruskal 
树中边边的有序列表bc 1bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6de2bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6bd3bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6ab5bc1 de 2 bd3 dc 4 ab 5 ce 6 ad 6
2 判断正误 
a.如果e是加权连通图中权重最小的边，它至少是图的一棵最小生成树的边
 正确
 b.如果e是加权连通图中权重最小的边，它必定是图的一棵最小生成树的边
 错误，如果有几条相同的最小权重的边，则有可能不会将其中一条最小边加入最小生成树
 c.如果加权连通图中每条边的权重都是互不相同的，该图必定只有一棵最小生成树
 正确
 d.如果加权连通图中每条边的权重都是互不相同的，该图必定不止有一棵最小生成树
 错误，图中存在环时会有可能只有一棵或几棵最小生成树
 
P259 2.a 
树中顶点余下的顶点a(-,0)b(-,∞),c(-,∞),d(a,7),e(-,∞)d(a,7)b(d,2),c(d,5),e(-,∞)b(d,2)c(b,4),e(-,∞)c(b,4)e(c,6)e(c,6)
P264 1 
a
 
 
ABCD_0.40.10.20.150.150100111101110
b
 ABACABAD 0100011101000101
 c
 
100010111001010BAD_ADA					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5692601.html