0

私はジョセフス問題のアルゴリズムを読んでいました。

私は次のアルゴリズムに出くわしました:

int josephusIteration(int n,int k) {
    int a=1;
    for(int i=1;i<=n;i++) {
        a=(a+k-1)%i+1;
    }
    return a;
}

そのロジックが理解できませんでした。n=5、k=2 とします。

i=1, a=1
i=2, a=1
i=3, a=3
i=4, a=1
i=5, a=3

誰かが例を挙げてこれを説明できますか?

4

1 に答える 1

5

n = 5との場合k = 2、安全な位置は3です。まず、2 位の人が殺され、4 位の人が殺され、1 位の人が殺されます。最後に、位置 5 の人が殺されます。したがって、位置 3 の人は生き残ります。

私はあなたのコードを読みましたが、理解しやすい以下の再帰的な解決策を提案したいと思います.

// this function returns the position of the person alive
int josephus(int n, int 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;
}

最初の人 (最初から k 番目) が殺されると、n-1 人が残ります。したがってjosephus(n – 1, k)、n-1 人の位置を取得するために呼び出します。

しかし、 によって返された位置はjosephus(n – 1, k)、位置 1 から再び考慮されます。そのため、要素があるk-1ため、それに足し、そのモジュラスを取り、 1 を加えて位置を作成します。nn1-indexed0-indexed

参照: http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/

于 2015-07-27T15:49:59.790 に答える