CSP-游戏Python实现
程序员文章站
2022-03-28 16:11:53
问题描述 有n个小朋友围成一圈玩游戏,小朋友从1至n编号,2号小朋友坐在1号小朋友的顺时针方向,3号小朋友坐在2号小朋友的顺时针方向,……,1号小朋友坐在n号小朋友的顺时针方向。 游戏开始,从1号小朋友开始顺时针报数,接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数(即数的个位)为k,则该小朋友被淘汰出局,不再参加以后的报数。当游戏中只剩下一个小朋友时,该小朋友获胜。 例如,当n=5, k=2时: 1号小朋友报数1; 2号小朋友报数2淘汰; 3号...
问题描述
有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://blog.csdn.net/qq_43155260/article/details/109641371
上一篇: 百度语音唤醒踩坑合集