約瑟夫斯爲大n（Facebook黑客杯）

上週我參加了Facebook黑客杯的第1b輪。約瑟夫斯爲大n（Facebook黑客杯）

一個問題基本上是Josephus problem

我作爲一個離散數學問題之前，約瑟夫問題的研究，所以我基本上了解如何獲得復發：

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

但是，沒在Facebook黑客杯中工作，因爲n的最大值是10^12。 k的mak值是10^4。

當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論壇上找到任何信息）

來源

2011-01-30 Edward Tonai

最後一個`else`屬於哪個`if`？ – biziclop 2011-01-30 21:06:36

@biziclop - 是不是很明顯它屬於最後一個...？ – IVlad 2011-01-30 21:14:49

對，我想我已經破解了它。

讓我們看看迭代如何與去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

現在Ĵ（4,3）返回0，其通過5%3原來是-2校正進一步擊中。只有當第二行的結果在最後一組時，纔會發生這種情況，在這種情況下，將n添加到結果中會給我們提供我們的原始索引。

來源

2011-01-30 22:37:58 biziclop

約瑟夫斯爲大n（Facebook黑客杯）

回答

相關問題