约瑟夫斯问题(计数)

Question

挑战

编写一个函数，该函数以两个正整数n和k作为参数，并在计算出每个k-th person后，返回在n之外的最后一个人的数目。

这是一个代码-高尔夫挑战，所以最短的代码获胜。

问题

n人员(从1到n编号)站成一个圆圈，每个k-th都被计算出来，直到剩下一个人为止(参见相应的维基百科文章)。确定最后一个人的人数。

对于k=3，两人将被跳过，第三人将被计算在内。也就是说，对于n=7，数字将按顺序3 \, 6 \, 2 \, 7 \, 5 \, 1 (详细的\require{cancel}1 \, 2 \, \cancel{3} \, 4 \, 5 \, \cancel{6} \, 7 \, 1 \, \cancel{2} \, 4 \, 5 \, \cancel{7} \, 1 \, 4 \, \cancel{5} \, 1 \, 4 \, \cancel{1} \, 4)计算出来，因此答案是4。

示例

J(7,1) = 7      // people are counted out in order 1 2 3 4 5 6 [7]
J(7,2) = 7      // people are counted out in order 2 4 6 1 5 3 [7]
J(7,3) = 4      // see above
J(7,11) = 1
J(77,8) = 1
J(123,12) = 21

Answer 1

GolfScript，17字节

{{@+\)%}+\,*)}:f;

接受堆栈上的n k，并将结果留在堆栈上。

解剖

这使用递归g(n,k) = (g(n-1,k) + k) % n和g(1, k) = 0 (如维基百科文章中所描述的)，递归被折叠代替。

{          # Function declaration
           # Stack: n k
  {        # Stack: g(i-1,k) i-1 k
    @+\)%  # Stack: g(i,k)
  }+       # Add, giving stack: n {k block}
  \,*      # Fold {k block} over [0 1 ... n-1]
  )        # Increment to move from 0-based to 1-based indexing
}:f;

Answer 2

明斯基寄存器机(25个非停止状态)

从技术上讲，它不是一个函数，但它是在一个没有功能的计算范例中.

这与我的第一个MRM解释挑战的主要测试用例略有不同：

在寄存器n和k中输入；在寄存器r中输出；在输入时假定为r=i=t=0。前两个停止指令是错误情况。

Answer 3

Python，36

我还使用了维基百科的公式：

J=lambda n,k:n<2or(J(n-1,k)+k-1)%n+1

示例：

>>> J(7,3)
4
>>> J(77,8)
1
>>> J(123,12)
21