欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

相关标签: CSP刷题 链表