学进去

一列货运列车有n节车厢，每节车厢将停放在不同车站。假定n个车站的编号分别为1~n，列车按照第n站至第1站的顺序停靠，车厢编号与目的站序号相同。为了到每个站时只需卸掉最后一节车厢，必须将任意次序的车厢进行重排，使得各车厢从前往后的编号是1~n。重排车厢的工作在一个转轨站里完成，如图所示，在转轨站中有一个入轨，一个出轨和k（k=3）个缓冲轨H1，H2，H3。开始时n节车厢从入轨处进入转轨站，转轨结束后车厢按编号1~n的次序离开转轨站。

编写程序模拟有n（n=9）节车厢的“入轨”和“出轨”过程，（入轨车厢次序满足缓冲轨为3的情况）。车厢可以从入轨的前部移动到一个缓冲轨的顶部或者是出轨处的后部。进入缓冲轨的车厢编号要满足：

①小于要进入的缓冲轨的栈顶元素编号。
②满足条件①里面栈顶元素编号最小的缓冲轨。
③若没有满足条件①的缓冲轨，则进入空的缓冲轨。

（1）若在入轨处的车厢次序是3,6,9,2,4,7,1,8,5，则2号车厢进入的缓冲轨是_____(填：H1或H2或H3)。
（2）实现上述功能的程序如下，请在划线处填入合适的代码。

def inputStack(bh,stacks,n): # 将车厢移到缓冲轨处

       global minNum, minStack,k

       bestStack = -1 # bestStack 记录最小车厢编号所在的缓冲轨编号

       bestTop = n + 1 # bestTop 记录缓冲轨中的最小车厢编号

       for i in range(k):

             if len(stacks[i])>0:

                    top = stacks[i][-1]

                    if ______ :

                           bestTop = top

                           bestStack = i

                    else:

                           if bestStack == -1:

                                 bestStack = i

       if bestStack == -1:

             return False

       stacks[bestStack].append(bh)

       print('将 %d 号车厢从入轨处移到缓冲轨道 H%d 处。' % (bh, bestStack+1))

       if bh < minNum:

             minNum = bh

             minStack = bestStack

       return True

def output(stacks,n):

       # 将缓冲轨中的剩余车厢按顺序依次移到出轨处，代码略

# 主程序开始

list = [3,6,9,2,4,7,1,8,5] #车厢的原始编号存放在列表 list 中

n = len(list)

k = 3

hStacks=[ _______ for i in range(k)]

curBH=1

minStack = -1

print("车厢重排过程如下：")

i=0

while i < n:

       if list[i] == curBH:

             print("将 %d 号车厢从入轨处直接移到出轨处。" % list[i])

________

             i += 1

             continue

       while True:

             minNum = n + 1

             for j in range(k):

                    if len(hStacks[j]) > 0:

                           if hStacks[j][-1] < minNum:

                                 minNum = hStacks[j][-1]

                                 minStack=j

             if minNum == curBH:

                    print("将%d号车厢从缓冲轨道H%d移到出轨处。" %(minNum,minStack+1))

                    hStacks[minStack].pop()

                    curBH += 1

             else:

_____

                    i += 1; break

while curBH<n+1:

       output(hStacks,n); curBH += 1

print("完成车厢重排!")