CSP-游戏Python实现

游戏Python实现"/>

CSP-游戏Python实现

问题描述
　　有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 = varself.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+2p = ListNode(i+2)# 将当前节点连接到前一个节点后面pre.next = ppre = p# 如果到了最后一个节点，将它的next指向第一个节点，形成环if i == n-2:pre.next = head
# 用来判断是否需要删除
def judgeDel(n,k):t = n%10if t == k or n%k == 0:return Truereturn 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.nextp = pre.nextlens -= 1# 不需要删除pre和p都向后移动一位else:pre = pp = p.next# 不管删不删除，ind都得自增1ind += 1
# 最后输出p.val和pre.val都可以，因为是环，只剩一个元素了，pre和p都表示这个元素
print(p.var)