第15题

15.某工厂要生产一个产品，需要经过n个工序(工序间不存在循环前置关系)。每道工序之间有一定先后关系，一道工序可以有若干个前置工序，每道工序最多是某一道工序的前置工序。若n=6，表a表示工序间的依赖关系，从中可知:完成工序4必须先完成工序0与工序5，完成工序3必须先完成工序1与工序4。

现根据各道工序间的依赖关系，安排各道工序的可行的先后顺序:0一1-5-4-3-2.

(1)写出表b各道工序可行的先后顺序:____

(2)实现编码功能的Python程序如下，请在划线处填入合适的代码。

def MakeMatrix(n,a):
    ma=[[0 for i in range(n)]for j in range(n)]#记录工序i与工序j之间的关系
    #ma[i][j]=1表示工序i是工序j的前导工序，否则表示没有前后关系
    for i in range(len(a)):
    ma[_①_][_ ②_] =1
    return ma
#获取各道工序的前后关系表存入数组a中，工序总数量存放至变量n中，代码略。

#如表 a各个工序关系存入数组a为:[[0,4],[1,3],[5,4]，[4,3],[3,2]]
remat=MakeMatrix(n,a)
flag=[False]*n
que=[0]*n
pre=[0]*n
head=tail=0
for i in range(n):
    for j in range(n):
        _____③_____
    s=''
for i in range(n):
    if pre[i]==0:
        que[tail]=i
        flag[i]=True
        tail+=1
        s=s+str(i)+"→"

while head<tail:
    p=que[head]
    head+=1
    for k in range(n):
        if _____④_____:
            pre[k]-=1
            if pre[k]==0 :
                _____⑤_____
                tail+=1
                flag[k]=True
                s=s+str(k)+"→"
print ("工序为:")
print(s[:-1])

知识点理解： https://blog.csdn.net/aliyonghang/article/details/130449038

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com