[Visual Basic 6.0] 使用 LinkList 解 國王下山來點名 (約瑟夫殺人遊戲)

摘要:[Visual Basic 6.0] 使用 LinkList 解 國王下山來點名 (約瑟夫殺人遊戲)

[Visual Basic 6.0] 使用 LinkList 解 國王下山來點名 (約瑟夫殺人遊戲)

 


 在童年時,總有許多說不完的趣事。為了玩"捉迷藏"遊戲,所以需決定一個人當鬼。我們設計一種決定鬼的方法:就是先將N個人排成一圈,然後由第一人開始邊數、邊唸:「國王下山來點名點到誰是好運氣」所以第十四個人運氣很好,就不用當鬼,繼續由第十五人,按同方法繼續數。如果人數不足14人,則繞回第一人繼續數。所以每數完一次"國王下山…"就有一人好運。最後剩下的一人就是要當鬼了!

所以若N有2個人,則當鬼的人是1號,若N有3個人,則當鬼的人是3號,若N有4個人,則當鬼的人是1號,若N有5個人,則當鬼的人是5號。若N有14個人,則…

※註,本題類似於所謂的「約瑟夫殺人遊戲」,可用的方法有環狀串列、陣列、或虛擬化後的陣列等。

〔輸入檔格式〕本問題的輸入有多組樣本,每行是一組樣本,而每組樣本有一個整數N (N的範圍為1~100)

〔輸出檔格式〕對於每一組樣本印出一行,並且先印出N接著印出”-->”,再印出最後要當鬼的號碼。

〔範例輸入與輸出結果〕

2-->1

3-->3

4-->1

5-->5

14-->13

 

 

 


'# [Visual Basic 6.0] 使用 LinkList 解 約瑟夫殺人遊戲
'# 0xDe

Private Type LinkList ' 建立連結串列的資料型態
    Next As Integer ' 後一個指標
    Back As Integer ' 前一個指標
End Type

Private Sub Form_Activate()
Open App.Path & "/In.txt" For Input As #1
Open App.Path & "/Out.txt" For Output As #2


Do While Not EOF(1)
    Input #1, InNumber
    
    ' 建立連結串列
    ReDim LinkListData(1 To InNumber) As LinkList
    
    For I = 1 To InNumber
        If I = 1 Then ' 如果是第一個它的前一個指標必須指定為最後一筆資料
            LinkListData(I).Next = I + 1
            LinkListData(I).Back = InNumber
        ElseIf I = InNumber Then ' 如果是最後一個它的下一筆必須為第一筆資料
            LinkListData(I).Next = 1
            LinkListData(I).Back = I - 1
        Else
            LinkListData(I).Next = I + 1
            LinkListData(I).Back = I - 1
        End If
    Next I
    
    ' 約瑟夫殺人遊戲 (設定每次第 14 個人就被殺直到只剩下一個幸運逃生的人)
    
    KillNumber = 0 ' 預設殺人數為 0
    LinkNow = 1 ' 從第一個人開始
    
    
    Do While KillNumber < InNumber  ' 殺光全部 (實際上沒有殺光)
        For I = 1 To 13 ' 14 個
            LinkNow = LinkListData(LinkNow).Next ' 它的下一個
        Next I
        
        Ou = Ou & LinkNow & "," ' 紀錄被殺的人編號
        ' 殺掉目前這個人 (等於移除 LinkList )
        
        ' 目前這個的前一個指標必須指定到他的下一個指標
        LinkListData(LinkListData(LinkNow).Back).Next = LinkListData(LinkNow).Next
        ' 目前這個的後一個指標的前指標必須指定到上一個的指標
        LinkListData(LinkListData(LinkNow).Next).Back = LinkListData(LinkNow).Back
        ' 從死掉的下一個開始
        LinkNow = LinkListData(LinkNow).Next
        KillNumber = KillNumber + 1
    Loop
    
    Over = Split(Ou, ",")
    
    Outputs = Outputs & InNumber & "-->" & Over(UBound(Over) - 1) & vbCrLf  ' 最後一個被殺的就是倖存者
Loop
    Print #2, Outputs
    Close
    End
End Sub

 

 

[Visual Basic 6.0] 使用 LinkList 解 約瑟夫殺人遊戲.rar

#0xDe 從分享中學習

#Facebook:ProgrammerDe (https://www.facebook.com/MicrosoftDes) 有問題歡迎提問