精华内容
下载资源
问答
  • 任务调度的合理性

    2016-07-18 21:11:59
    任务调度”包括一组子任务、以及每个子任务可以执行所依赖子任务集。 比如完成一个专业所有课程学习和毕业设计可以看成一个本科生要完成一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如...

    假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

    比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如英语和C程序设计,它们没有必须先修哪门的约束;有些课程则不可以同时开设,因为它们有先后的依赖关系,比如C程序设计和数据结构两门课,必须先学习前者。

    但是需要注意的是,对一组子任务,并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B,子任务B依赖于子任务C,子任务C又依赖于子任务A”,那么这三个任务哪个都不能先执行,这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

    输入格式:

    输入说明:输入第一行给出子任务数NNN≤100\le 100100),子任务按1~NNN编号。随后NNN行,每行给出一个子任务的依赖集合:首先给出依赖集合中的子任务数KKK,随后给出KKK个子任务编号,整数之间都用空格分隔。

    输出格式:

    如果方案可行,则输出1,否则输出0。

    输入样例1:

    12
    0
    0
    2 1 2
    0
    1 4
    1 5
    2 3 6
    1 3
    2 7 8
    1 7
    1 10
    1 7
    

    输出样例1:

    1
    

    输入样例2:

    5
    1 4
    2 1 4
    2 2 5
    1 3
    0
    

    输出样例2:

    0

    题目链接:https://pta.patest.cn/pta/test/1300/exam/4/question/17965

    这道题把它想象成图即可。你会发现这就是个判断成不成环的问题~((*・∀・)ゞ→→



    #include <iostream>
    #include <bits/stdc++.h>
    
    using namespace std;
    const int MAXN=110;
    int G[MAXN][MAXN];
    int in[MAXN];
    int n, m, x, y;
    int i, j;
    int flag = 1;
    void toposort()
    {
        for(i = 1; i <= n; i++)
        {
          
            int k = 1;
            while(in[k] != 0)
            {
                k++;
                if(k > n)
                {
                    flag = 0;
                    break;
                }
            }
    
            in[k] = -1;//表示这个点找完了
            
            for(int j = 1; j <= n; j++)
            {
                if(G[k][j])
                    in[j]--;
            }
        }
    }
    
    void init()
    {
        memset(in,0,sizeof(in));
        memset(G,0,sizeof(G));
    }
    
    int main()
    {
        scanf("%d",&n);
        
            init();
            for(i = 1; i <= n; i++)
            {
                scanf("%d",&m);
                for(int j = 0; j < m; j++)
                {
                    scanf("%d",&y);
                    G[i][y] = 1;
                    in[y]++;
                }
            }
            toposort();
            if(!flag)
            {
                printf("0\n");
            }
            else
                printf("1\n");
        
        return 0;
    }
    


    
    展开全文
  • 任务调度的合理性 pta

    2018-03-15 13:42:25
    //https://pintia.cn/problem-sets/15/problems/861//任务调度的合理性//思路:与其从下往上搜索母节点,不如使用母节点主动去消灭子节点中牵扯到的子节点//征北军的铁蹄踏上了远东的领土……//为了清除敌方残余力量...
    //https://pintia.cn/problem-sets/15/problems/861
    //任务调度的合理性
    //思路:与其从下往上搜索母节点,不如使用母节点主动去消灭子节点中牵扯到的子节点
    //征北军的铁蹄踏上了远东的领土……
    //为了清除敌方残余力量,他们挑选出自己信任的当地百姓
    //给予他们以下一项决定生死的权利:担保——信任的力量
    //这些百姓在使用这项权利之前,他们的怀疑值f[x][0]已经变成了0.
    //行使这项权利(或者说完成这项任务)之后,他们被征北军视作死忠
    //他们的怀疑值f[x][0]将会变成-1——以后你就不用再来做这种容易引发选择困难症的苦差事了^-^
    //回归正题:
    //在每一轮过程中,这些拥有权利的百姓会依次上场
    //此时,在场其他的被怀疑百姓如果正好拥有当前担保百姓的信物,那么他们的怀疑值就会减1
    //每轮结束后:那些新成为怀疑值为0的百姓就会在下一轮履行担保任务的职责
    //如果一轮中没有新的良善人士——
    //要么已经排除异己结束,要么就是敌对分子的怀疑值没有被完全消除
    //看看是否全部变成死忠(只要上过场就可以),若是,输出1;若否,输出0.
    #include<cstdio>
    #include<iostream>
    #include<string.h>
    using namespace std;
    #define MAX 105
    int f[MAX][MAX];
    //f[x][0]用来记录动态的剩余未被确认可行元素个数
    //f[x][y>0]用来记录先行任务编号
    int n;
    int num[MAX];
    //num[x]用来记录静态的一开始每个任务的先行任务个数
    int main()
    {
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
    cin>>f[i][0];
    num[i]=f[i][0];
    for(j=1;j<=f[i][0];j++) cin>>f[i][j];
    }
    int cnt;
    //cnt用来记录每次原非母节点被改变为母节点的个数,如果没有,说明存在环或者已经全部确认是可以完成的任务
    //存在环==f[x][0]!=-1;(已经用于确认过其他节点的母节点的f[x][0]会被打上-1的标记,
    //被打上f[x][0]=0的标记意味着还没有被用于确认过其他节点)
    do
    {
    cnt=0;
    for(j=1;j<=n;j++)
    {
    if(f[j][0]==0)
    {
    for(k=1;k<=n;k++)
    {
    if(f[k][0]>0)
    {
    for(int l=1;l<=num[k];l++)
    {
    if(f[k][l]==j) 
    {
    f[k][0]--;
    break;
    }
    }
    }
    }
    f[j][0]=-1;
    }
    }
    for(i=1;i<=n;i++)
    {
    if(f[i][0]==0) cnt++;
    }
    }while(cnt>0);
    for(i=1;i<=n;i++)
    {
    if(f[i][0]!=-1) break;
    }
    if(i==(n+1)) cout<<1;
    else cout<<0;
    return 0;
    }
    展开全文
  • pta 任务调度的合理性

    2016-07-13 15:00:04
    5-2 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的...
    5-2 任务调度的合理性   (25分)
    

    假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

    比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如英语和C程序设计,它们没有必须先修哪门的约束;有些课程则不可以同时开设,因为它们有先后的依赖关系,比如C程序设计和数据结构两门课,必须先学习前者。

    但是需要注意的是,对一组子任务,并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B,子任务B依赖于子任务C,子任务C又依赖于子任务A”,那么这三个任务哪个都不能先执行,这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

    输入格式:

    输入说明:输入第一行给出子任务数NN\le 100100),子任务按1~NN编号。随后NN行,每行给出一个子任务的依赖集合:首先给出依赖集合中的子任务数KK,随后给出KK个子任务编号,整数之间都用空格分隔。

    输出格式:

    如果方案可行,则输出1,否则输出0。

    输入样例1:

    12
    0
    0
    2 1 2
    0
    1 4
    1 5
    2 3 6
    1 3
    2 7 8
    1 7
    1 10
    1 7
    

    输出样例1:

    1
    

    输入样例2:

    5
    1 4
    2 1 4
    2 2 5
    1 3
    0
    

    输出样例2:

    0


    #include <iostream>
    #include <cstring>
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 110;
    int visit[N], s[N][N], num[N];
    const int inf=9999999;


    int main()
    {
        int n, m, x, y;
        cin>>n;
        memset(visit,0,sizeof(visit));
        memset(s,0,sizeof(s));
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++)
        {
            scanf("%d", &m);
            for(int j=0;j<m;j++)
            {
                scanf("%d", &x);
                s[x][i]=1;
            }
            num[i]=m;
        }
        y=n;
        int flag=1;
        while(y--)
        {
            int Max=inf,k;
            for(int i=1;i<=n;i++)
            {
                if(visit[i]==0&&num[i]<Max)
                {
                    Max=num[i];
                    k=i;
                }
            }
            visit[k]=1;
            if(Max!=0)
            {
                flag=0;
                break;
            }
            for(int i=1;i<=n;i++)
            {
                if(s[k][i]==1)
                {
                    num[i]--;
                }
                s[k][i]=0;
            }
        }
        if(flag==1)
        {
            cout<<1<<endl;
        }
        else
        {
            cout<<0<<endl;
        }
        return 0;
    }


    展开全文
  • 7-6任务调度的合理性(25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集...

    7-6 任务调度的合理性 (25 分)

    假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

    比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如英语和C程序设计,它们没有必须先修哪门的约束;有些课程则不可以同时开设,因为它们有先后的依赖关系,比如C程序设计和数据结构两门课,必须先学习前者。

    但是需要注意的是,对一组子任务,并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B,子任务B依赖于子任务C,子任务C又依赖于子任务A”,那么这三个任务哪个都不能先执行,这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。

    输入格式:

    输入说明:输入第一行给出子任务数N(≤100),子任务按1~N编号。随后N行,每行给出一个子任务的依赖集合:首先给出依赖集合中的子任务数K,随后给出K个子任务编号,整数之间都用空格分隔。

    输出格式:

    如果方案可行,则输出1,否则输出0。

    输入样例1:

    12
    0
    0
    2 1 2
    0
    1 4
    1 5
    2 3 6
    1 3
    2 7 8
    1 7
    1 10
    1 7
    

    输出样例1:

    1
    

    输入样例2:

    5
    1 4
    2 1 4
    2 2 5
    1 3
    0
    

    输出样例2:

    0

     

    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    
    const int MAXV = 1005;
    vector<int> G[MAXV];
    int n, m, inDegree[MAXV];
    
    bool topologicalSort(){
    	int num = 0;	//记录拓扑序列的顶点数 
    	queue<int> q;
    	for(int i = 1; i <= n; i++){
    		if(inDegree[i] == 0)	// 如果顶点i的入度为 0 入队 
    			q.push(i);
    	}
    	while(!q.empty()){
    		int u = q.front();
    		q.pop();
    		for(int i = 0; i < G[u].size(); i++){
    			int v = G[u][i];	//u的后继结点v 
    			inDegree[v]--;		//顶点v的入度-1 
    			if(inDegree[v] == 0){	//如果顶点v的入度为 0 入队 
    				q.push(v);
    			}
    		}
    		G[u].clear();	//清空定顶点u的所有出边 
    		num++;	//加入拓扑序列的定点数+1 
    	}
    	if(num == n) return true;	//拓扑序列的顶点数为n,说明拓扑排序成功 
    	else	return false;	//加入拓扑序列的顶点数小于n,说明失败 
    }
    
    int main (){
    
    	cin >> n;
    	memset(inDegree, 0, sizeof(inDegree));
    	int x, y;
    	
    	for(int i = 1; i <= n; i++){
    		cin >> x;
    		inDegree[i] = x;
    		for(int j = 0; j < x; j ++){
    			cin >> y;
    			G[y].push_back(i);
    		}
    	}
    	if( topologicalSort() ){
    		cout << "1" << endl;
    	}
    	else
    		cout << "0" << endl;
    	return 0;
    }
    

     

    展开全文
  • L3-2 任务调度的合理性 (30分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子...
  • 7-14 任务调度的合理性(25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的...
  • 7-7 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 7-13 任务调度的合理性 (25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务...
  • 5-2 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的...
  • 7-3 任务调度的合理性 (25 分)

    千次阅读 2018-10-30 21:19:34
    7-3 任务调度的合理性 (25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子...
  • 7-34 任务调度的合理性(25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖...
  • 7-9 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集...
  • 7-34 任务调度的合理性 (25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集...
  • 5-34 任务调度的合理性 (25分)

    千次阅读 2016-08-30 11:21:56
    5-34 任务调度的合理性 (25分)假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 7-34任务调度的合理性(25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 5-18 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的...
  • 7-3 任务调度的合理性 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。 比如...
  • 7-13 任务调度的合理性 (25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子...
  • 7-13 任务调度的合理性 (25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子...
  • 任务调度”包括一组子任务、以及每个子任务可以执行所依赖子任务集。 比如完成一个专业所有课程学习和毕业设计可以看成一个本科生要完成一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如...
  • 7-2 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 7-12任务调度的合理性(25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 7-9 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 7-34 任务调度的合理性 (25 分)假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集...
  • 5-4 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的...
  • 5-1 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。...
  • 7-1 任务调度的合理性

    2020-10-25 17:25:32
    这道题就是个最基本拓扑排序,然后需要指出子任务的意思是依靠当前任务的任务。比如说第三行输入2 1 2, 指任务1和任务2需要依赖于任务3。 (我觉得应该这样理解吧?
  • 5-34 任务调度的合理性 (25分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务...
  • 任务调度”包括一组子任务、以及每个子任务可以执行所依赖子任务集。 比如完成一个专业所有课程学习和毕业设计可以看成一个本科生要完成一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如...
  • 7-10 任务调度的合理性(25 分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 337
精华内容 134
关键字:

任务调度的合理性