c - 如何在C语言中找到约瑟夫斯问题中的消除顺序？

Question

Josephus 可以用以下算法求解：

int josephus(int n, int k)
{
  if (n == 1)
    return 1;
  else
    return (josephus(n - 1, k) + k-1) % n + 1;
}

不过，我也想知道游戏中第i个被杀的人是谁。例如，n=10，k=2，第一个被杀的人就是第二个。我怎样才能得到这个答案？无论如何我可以使用上面的算法找到它吗？

Answer 1

O(mlg(km)) 算法

n人围成一圈，按0顺时针n-1方向编号。从有 number 的人开始0，每隔m-th 执行一次，下面的程序给出k第 -th 被杀的人的号码。k从0.

def solve(n,m,k):
    if m==1: return k
    i = (k+1)*m-1
    while i>=n:
        i = (m*(i-n))//(m-1)
    return i

解释

我//用来表示floor divison。

假设每个人都将从 开始计数0，谁报告m-1是第0-th 个被杀的人。谁报告2m-1是第1-th 个被杀的人，依此类推。

说有人报道i。他最后的报告是j。当他报告j时，有j//m死有n-(j//m)活。

所以i = (n - (j//m)) + j->j-j//m = i-n

假设j = am + b; 0<=b<m-1; a,b is int，请注意这里，b!=m-1因为他不会死。

然后a(m-1) + b = (i-n) 。使用 bezout 引理和扩展欧几里得算法，我们得到a=-c; b=(i-n)+c*(m-1); with any int c. 并且b在区间 中只有一个解[0,m-1)，也((i-n)+c*(m-1)) %(m-1)就是我们需要的解，等于(i-n)%(m-1)。之后，您可以计算j=(i-n) + (i-n)//(m-1) = (m*(i-n))//(m-1).

通过这个递推关系，你可以计算出任何k第-个被杀的人。

时间复杂度O(mlg(mk))与空间O(1)。

O(nlg(n)) 模拟

如果m非常大，您可以使用 RedBlackTree 来实现 O(nlg(n)) 时间复杂度。

from sortedcontainers import SortedList
def simulate(n, m):
    # all index from 0
    people = SortedList(range(n))
    idx = 0
    while len(people)>0:
        idx = (idx+m-1)%len(people)
        yield people.pop(idx) # yield executed people number in order
    return