algorithm - 教师对 Josephus 排列的输出无法重现

Question

我在上数据结构课，无法重现教师给出的示例数据。该问题是经典的 Josephus 问题，其中包含用户提供的成员数量、步长间隔和起始位置。

具体来说，我被告知有 99 人，从 23 人开始，数到 5 应该留下 84 人作为最后一个站着的人。

我得出:65。我再次运行时认为输入可能是 99 人，从 5 开始，间隔为 23。结果是:42。

我的赋值解决方案涉及一个循环链表，但是这个 c 代码在所有情况下都产生相同的输出:

#include <stdio.h>

int josephus(int n, long k)
{
  if (n == 1)
    return 1;
  else
  /* The position returned by josephus(n - 1, k) is adjusted because the
   *        recursive call josephus(n - 1, k) considers the original position 
   *               k%n + 1 as position 1 */
 return (josephus(n - 1, k) + k-1) % n + 1;
}

int main()
{
int n = 99;
int k = 23;
printf("The chosen place is %d\n", josephus(n, k) + 5);
return 0;
}

再次感谢。

Answer 1

LaFore 认为倒计时是跨步。也就是说，从 1 开始，以 2 计数将首先杀死第 4 个人。文本中确实有一个例子。这是不直观的，LaFore 似乎是唯一以这种方式计算的作者。