1. 手拉手游戏幼儿园小朋友经常手拉手排队,老师为了让队伍比较整齐,会要求小朋友坐在教室里时按照身高的高低顺序来坐:(用数字1~n来表示身高且同一数字不重复)

但是今天小朋友很调皮,在教室里坐下来的时候没有按照身高的高低顺序。老师发现后,设计了一个“手拉手——找找好朋友的游戏” ,老师说:“请每位小朋友与后面第一个身高比自己高的小朋友手拉手”,但是有些小朋友后面没有比他高的小朋友,所以老师又说:“后面没有比自己高的小朋友和老师手拉手”。

如上图所示,若小朋友坐下时的身高顺序为“13254”,则每个小朋友拉手的座位顺序号是“24466”。(说明:第1个小朋友拉了2号座位小朋友的手,第2个小朋友拉4号座位小朋友的手,第3个小朋友也拉4号座位小朋友的手,第4个和第5个小朋友后面没有比他们高的小朋友,所以他们拉了老师的手)

小明根据这个游戏的规则,采用两种不同的算法编写Python 程序,根据小朋友坐下时的身高顺序求解每个小朋友拉手的座位顺序。请回答如下问题:

(1) 若小朋友坐下时的身高顺序为“31524”,则拉手的座位顺序号是
(2) 算法1.采用枚举算法求解:

#第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

上述代码中,划线部分应填入代码为

(3) 算法2.采用双向链表求解

首先让每个小朋友与前后的小朋友都手拉手,然后从身高最矮的小朋友开始,逐个离开队伍,以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="")      #输出拉手顺序号,用空格隔开

【考点】
枚举算法及程序实现; 基本数据结构;
【答案】

您现在未登录,无法查看试题答案与解析。 登录
综合题 困难
能力提升
换一批
2. 某校内活动需要n(1≤n≤10)名学生迎宾,要求是:男女生站成一排,男生不能相邻,男女生比例大于1/2。考虑到方案只包含了男和女两种情况,可以用二进制的0来代替女生,1来代替男生。当全部是0时最小,此数为0;当全部是1时最大。枚举从0到最大数的每一种情况,逐一判断是否包含男生相邻(二进制1相连),符合的0、1转换为女、男后输出,并在此基础上输出男女生比例较合适的方案(男:女>1/2)。

按上述要求,编写VB程序,功能如下:在文本框Text1中输入n的值,点击“开始枚举”按钮Command1,在列表框List1中输出所有方案,在列表框List2中输出比例合适方案。

实现上述功能的VB程序如下,回答下列问题:

(1) 如果输入的n值等于4,那么男女比例合适的方案有种。
(2) 请在划线处填入合适的代码。

Dim n As Integer, Getstr As String

Private Sub Command1_Click()

    Dim i As Integer, j As Integer, mAs Integer

    n = Val(Text1.Text)

    Getstr = ""

For i = 0 To 2 ^ n -1

        m = i

        If Then

            For j = 1 To n

                If m Mod 2 = 0 Then

                    Getstr = "女" + Getstr

                Else

                    Getstr = "男" + Getstr

                End If

                m = m \2

            Next j

            List1.AddItem Getstr

            If Team(Getstr) <> "" Then List2.AddItem (Team(Getstr))

            Getstr =""

        End If

    Next i

End Sub

Function search(i As Integer) As Boolean '判读男生是否相邻

    Dim j As Integer,t As Integer

    Dim a(1 To 15) As Integer

    t = i

    For j = 1 To n

        a(j) = t Mod 2

        t = t \2

    Next j

    flag = True

    For k = 1 To n -1

        If Then flag = False: Exit For

    Next k

search = flag

End Function

Function Team(ch As String) As String     '判读男女生比例是否合适

    Dim num As Integer, st As Integer, i As Integer,c(0 To 1) As Integer

    Team = “”

    For i = 0 To 1

        c(i) = 0

    Next i

    For i = 1 To n

        st= Mid(ch, i, 1)

        If st= "男" Then num=1: c(num)= c(num)+1 Else num =0: c(num)= c(num)+1

    Next i

    IfThen Team = ch

End Function

综合题 困难