摘要:[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) 有問題歡迎提問