但是今天小朋友很调皮,在教室里坐下来的时候没有按照身高的高低顺序。老师发现后,设计了一个“手拉手——找找好朋友的游戏” ,老师说:“请每位小朋友与后面第一个身高比自己高的小朋友手拉手”,但是有些小朋友后面没有比他高的小朋友,所以老师又说:“后面没有比自己高的小朋友和老师手拉手”。
如上图所示,若小朋友坐下时的身高顺序为“13254”,则每个小朋友拉手的座位顺序号是“24466”。(说明:第1个小朋友拉了2号座位小朋友的手,第2个小朋友拉4号座位小朋友的手,第3个小朋友也拉4号座位小朋友的手,第4个和第5个小朋友后面没有比他们高的小朋友,所以他们拉了老师的手)
小明根据这个游戏的规则,采用两种不同的算法编写Python 程序,根据小朋友坐下时的身高顺序求解每个小朋友拉手的座位顺序。请回答如下问题:
#第1个身高保存在s[1],第2个保存在s[2],…,人数保存在n中,代码略
s.append(n+1) # 老师在最后
for i in range(1, n+1): #遍历每个小朋友
for j in range(i+1, n+2): #向后找可以拉手的小朋友
if ▲ :
print(j, end="") #输出拉手的座位顺序号,用空格隔开
break
上述代码中,划线部分应填入代码为。
首先让每个小朋友与前后的小朋友都手拉手,然后从身高最矮的小朋友开始,逐个离开队伍,以5个小朋友坐下时的身高顺序为“13254"为例,过程如下图所示:
提示:每个小朋友离开队伍时,右链表链接的编号即为拉手的座位顺序号。
程序如下:
#第1个小朋友身高保存在s[1],第2个保存在s[2],…,人数保存在n中,代码略
s.append(n+1) # 老师在最后
a=[0]* (n+2) #保存不同身高小朋友的位置
L=[0]*(n+2) #左链表L[ ]存储位置i的小朋友的左链接位置
R=[0]*(n+2) #右链表R[j]存储位置i的小朋友的右链接位置
for i in range(1, n+1):
L[i],R[]=i-1, i+1 #每个小朋友与前后手拉手
for i in range(1, n+1): #从低到高让小朋友离队
=L[a[i]]
R[L[a[i]]=R[a[i]
for i in range(1, n+1):
print(, end="") #输出拉手顺序号,用空格隔开