03254: 约瑟夫问题No.2

implementation, http://cs101.openjudge.cn/practice/03254/

n 个小孩围坐成一圈，并按顺时针编号为1,2,…,n，从编号为 p 的小孩顺时针依次报数，由1报到m ，当报到 m 时，该小孩从圈中出去，然后下一个再从1报数，当报到 m 时再出去。如此反复，直至所有的小孩都从圈中出去。请按出去的先后顺序输出小孩的编号。

输入

每行是用空格分开的三个整数，第一个是n,第二个是p,第三个是m (0 < m,n < 300)。最后一行是: 0 0 0

输出

按出圈的顺序输出编号，编号之间以逗号间隔。

样例输入

8 3 4
0 0 0

样例输出

6,2,7,4,3,5,1,8

来源

cs10107 C++ Final Exam

约瑟夫问题的变种问题可以通过递推公式来解决。对于这个问题，我们需要按照指定的起始位置 ( p ) 和报数 ( m ) 来确定每个孩子出圈的顺序。递推公式可以帮助我们高效地解决这个问题。
递推公式
对于约瑟夫问题的变种，递推公式可以表示为： [ f(n, m, p) = (f(n-1, m, p) + m) % n ] 其中：
( f(n, m, p) ) 表示在 ( n ) 个孩子中，从第 ( p ) 个孩子开始报数，每数到 ( m ) 个孩子时，该孩子出圈，最后剩下的孩子的编号。
( f(n-1, m, p) ) 表示在 ( n-1 ) 个孩子中，从调整后的起始位置开始报数，每数到 ( m ) 个孩子时，该孩子出圈，最后剩下的孩子的编号。
详细步骤
初始化：
从编号为 ( p ) 的孩子开始报数。
使用一个列表来记录每个孩子出圈的顺序。
递推过程：
每次找到当前出圈的孩子后，更新起始位置，继续进行下一轮报数。
输出结果：
按照出圈顺序输出每个孩子的编号。
代码实现
以下是使用递推公式解决这个问题的代码实现：
python
def josephus(n, p, m):
    if n == 1:
        return [1]

    out_order = []
    pos = p - 1  # 将起始位置调整为0-based索引
    kids = list(range(1, n + 1))  # 孩子们的编号列表

    while len(kids) > 0:
        pos = (pos + m - 1) % len(kids)  # 计算当前出圈的孩子的位置
        out_order.append(kids.pop(pos))  # 将出圈的孩子添加到结果列表中

    return out_order

while True:
    n, p, m = map(int, input().split())
    if n + p + m == 0:
        break
    result = josephus(n, p, m)
    print(','.join(map(str, result)))
解释
初始化：
pos = p - 1：将起始位置调整为0-based索引。
kids = list(range(1, n + 1))：创建一个包含所有孩子编号的列表。
递推过程：
pos = (pos + m - 1) % len(kids)：计算当前出圈的孩子的位置。这里减1是因为我们从1开始报数，而列表索引是从0开始的。
out_order.append(kids.pop(pos))：将出圈的孩子添加到结果列表中，并从孩子列表中移除。
输出结果：
print(','.join(map(str, result)))：将结果列表中的编号用逗号连接成字符串并输出。

用队列实现

python

from collections import deque

while True:
    n, p, m = map(int, input().split())
    if n == p == m == 0:
        break
    queue = deque([i for i in range(p, n + 1)] + [i for i in range(1, p)])
    out = []
    while queue:
        for _ in range(m - 1):
            queue.append(queue.popleft())
        out.append(queue.popleft())
    print(*out, sep=",")

python

from collections import deque
n, p, m = map(int, input().split())

def Joseph(n, p, m):
    ans = []
    lst = deque(i for i in range(1, n + 1))
    lst.rotate(1 - p)
    while lst:
        lst.rotate(1 - m)
        ans.append(lst.popleft())
    return ans

while n != 0:
    print(*Joseph(n, p, m), sep=",")
    n, p, m = map(int, input().split())

【付麟瑞 24数学学院】：链表写上瘾了写个链表先（竟然没超时）

python

# 付麟瑞 24数学学院
class Node:
    def __init__(self,val,next=None):
        self.val = val
        self.next = next
while 1:
    head=a=Node(1)
    n,p,m=map(int,input().split())
    if (n,p,m)==(0,0,0):
        break
    for i in range(1,n):
        a.next=Node(i+1)
        a=a.next
    a.next=head
    ans=[]
    for i in range(p-1):
        a=a.next
    while a.next!=a:
        for i in range(1,m):
            a=a.next
        b=a.next
        a.next=b.next
        ans.append(b.val)
    ans.append(a.val)
    print(*ans,sep=',')

神奇，头一次知道deque的rotate用法，之前是一点都没有接触到（或许是我忘了也说不定？），太适合解这种问题了。

python

#张洺瑜 地空学院
from collections import deque
def rotate_(n,p,m):
    if n==0:return
    queue=deque(range(1,n+1))
    queue.rotate(-p+1)
    ans=[]
    while queue:
        queue.rotate(-m+1)
        ans.append(queue.popleft())
    print(','.join(map(str,ans)))

while True:
    n,p,m=map(int,input().split())
    if n==p==m==0:
        break
    rotate_(n,p,m)

03254: 约瑟夫问题No.2 ​

03254: 约瑟夫问题No.2