05344: 最后的最后

http://cs101.openjudge.cn/practice/05344/

弗拉维奥·约瑟夫斯是1世纪的一名犹太历史学家。他在自己的日记中写道，在一次战中，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

在计算机科学与数学中，就有一个以此命名的问题：约瑟夫斯问题（有时也称为约瑟夫斯置换）。在计算机编程的算法中，类似问题又称为约瑟夫环。具体描述如下：有 $n$ 个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过 $k-2$ 个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过 $k-1$ 个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了 $n$ 和 $k$ ，一开始要站在什么地方才能避免被处决？

为了让大家熟悉循环链表的使用，对该题进行模拟。我们要求将之前的所有被kill掉的囚犯的编号输出。

输入

题中描述的囚犯数n（即编号为1至n，n不大于1000）和间隔数k（k大于等于2，小于n）

输出

顺序输出被kill掉的囚犯的编号，中间以空格隔开

样例输入

10 2

样例输出

2 4 6 8 10 3 7 1 9

python

class Node:
    def __init__(self, number):
        self.number = number
        self.next = None

def josephus_circle(n, k):
    # 创建循环链表
    head = Node(1)
    current = head
    for i in range(2, n + 1):
        new_node = Node(i)
        current.next = new_node
        current = new_node
    current.next = head  # 形成环

    result = []
    current = head
    prev = None

    while current.next != current:
        # 找到第k个节点
        for _ in range(k - 1):
            prev = current
            current = current.next
        # 杀掉第k个节点
        result.append(str(current.number))
        prev.next = current.next
        current = prev.next

    # 最后剩下的一个人
    #result.append(str(current.number))
    #return ' '.join(result[:-1])  # 根据题意，只输出被杀掉的编号
    return ' '.join(result)

# 读取输入
n, k = map(int, input().split())

# 计算并输出结果
print(josephus_circle(n, k))

该实现的时间复杂度为 O(n*k)，对于 n 和 k 较大的情况，可以考虑优化算法，如使用数学方法求解约瑟夫斯问题的位置，但本题要求模拟过程，故采用链表方法。

python

# 23n2300011119（武）
from collections import deque
n,k=map(int,input().split())
queue=deque(i for i in range(1,n+1))
flag=k
res=[]
# 1 2 3 4 5 6 7 8 9 10
while len(queue)>=2:
    a=queue.popleft()
    queue.append(a)
    if k-2!=0:
        for _ in range(k-2):
            a = queue.popleft()
            queue.append(a)
    b=queue.popleft()
    res.append(b)
res_new=[str(i) for i in res]
print(" ".join(res_new))

05344: 最后的最后 ​

05344: 最后的最后