問題描述
有n個小朋友圍成一圈玩游戲，小朋友從1至n編號，2號小朋友坐在1號小朋友的順時針方向，3號小朋友坐在2號小朋友的順時針方向，……，1號小朋友坐在n號小朋友的順時針方向，
游戲開始，從1號小朋友開始順時針報數，接下來每個小朋友的報數是上一個小朋友報的數加1，若一個小朋友報的數為k的倍數或其末位數（即數的個位）為k，則該小朋友被淘汰出局，不再參加以后的報數，當游戲中只剩下一個小朋友時，該小朋友獲勝，
例如，當n=5, k=2時：
1號小朋友報數1；
2號小朋友報數2淘汰；
3號小朋友報數3；
4號小朋友報數4淘汰；
5號小朋友報數5；
1號小朋友報數6淘汰；
3號小朋友報數7；
5號小朋友報數8淘汰；
3號小朋友獲勝，
給定n和k，請問最后獲勝的小朋友編號為多少？
輸入格式
輸入一行，包括兩個整數n和k，意義如題目所述，
輸出格式
輸出一行，包含一個整數，表示獲勝的小朋友編號，
樣例輸入
5 2
樣例輸出
3
樣例輸入
7 3
樣例輸出
4
資料規模和約定
對于所有評測用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9，
解題思路：用回圈鏈表來做，代碼中有詳細的注釋，直接貼上代碼
# 定義鏈表節點,var放的是小朋友的編號，next放的是這個小朋友報完后的下一個小朋友的資訊
class ListNode:
def __init__(self,var=0,next=None):
self.var = var
self.next = next
# n表示參加游戲人數，k表示報數為k的倍數或者末尾為k則淘汰
n,k = map(int,input().split())
# 因為是回圈串列，所以定義串列的頭節點，初始的時候放的是第一個小朋友
head = ListNode(1)
# 記錄前一個節點資訊
pre = head
# 初始化回圈串列
for i in range(n-1):
# 因為小朋友編號是從1開始的，而且第一個已經被加進鏈表了，所以var=i+2
p = ListNode(i+2)
# 將當前節點連接到前一個節點后面
pre.next = p
pre = p
# 如果到了最后一個節點，將它的next指向第一個節點，形成環
if i == n-2:
pre.next = head
# 用來判斷是否需要洗掉
def judgeDel(n,k):
t = n%10
if t == k or n%k == 0:
return True
return False
# 記錄當前報到哪個數了
ind = 1
# 記錄當前還剩余的人數
lens = n
# p表示當前游戲的人，pre表示它的前一個節點，為了方便洗掉當前
p = head
# pre的next指向p，val為最后一個小朋友的編號
pre = ListNode(n,p)
# 開始游戲，直到只剩余一個人時結束
while lens > 1:
# 如果需要洗掉
if judgeDel(ind,k):
# 需要洗掉的話只需要將p向后移動一位就可以，pre不需要移動
pre.next = p.next
p = pre.next
lens -= 1
# 不需要洗掉pre和p都向后移動一位
else:
pre = p
p = p.next
# 不管刪不洗掉，ind都得自增1
ind += 1
# 最后輸出p.val和pre.val都可以，因為是環，只剩一個元素了，pre和p都表示這個元素
print(p.var)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/216169.html
標籤：其他