11

上周我参加了 Facebook Hacker Cup 的第 1b 轮比赛。

问题之一基本上是约瑟夫斯问题

我之前研究过约瑟夫斯问题作为一个离散数学问题，所以我基本上了解如何获得递归：

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

但这在 Facebook 黑客杯中不起作用，因为 n 的最大值是 10^12。k 的 mak 值为 10^4。

Wikipedia 提到了一种当 k 很小而 n 很大时的方法。基本上从一轮中删除人员，然后重新编号。但它的描述并不多，我不明白为什么重新编号有效。

我查看了解决方案的示例工作源代码，但我仍然不明白最后一部分。

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

我真的不明白的部分是从res-=n%k（以及之后的行）开始。您如何得出这是调整结果的方法？

有人可以说明这是如何得出的背后的原因吗？还是派生它的链接？（我在 UVA 或 topcoder 论坛上没有找到任何信息）

4

1 回答 1

4

对，我想我破解了它。

让我们看看在 n=10, k=3 时迭代是如何进行的：

0 1 2 3 4 5 6 7 8 9    n=10,k=3
1 2   3 4   5 6   0    n=7,k=3

观察第二次迭代的元素如何映射到第一个：它们被 转置n%k，因为圆圈环绕。这就是为什么我们通过减去来纠正结果10%3。第二行中的数字以 为组出现k-1，因此以 为单位进行修正res/(k-1)。

另一种情况在迭代中受到进一步影响

0 1 2 3 4     n=5,k=3
2 3   0 1     n=4,k=3

现在 j(4,3) 返回 0，经修正后5%3结果为 -2。只有当第二行的结果在最后一组时才会发生这种情况，在这种情况下，添加n到结果中将为我们提供原始索引。

于 2011-01-30T22:37:58.433 回答