4

子供たちのグループがリングを形成します。最初の子が選択され、その子から時計回りにカウントを開始し、固定数 (ゲームの開始時に与えられる n) に達するまでカウントします。カウントが n に達すると、n 番目のスポットの子が削除されます。ゲームは次の子から再開し、残りの子が 1 人になるまでこのプロセスが続きます。最後まで残った子の位置を出力することが目的です。

例えば、子供が10人で固定数nが6の場合、最後まで残った最後の子供の位置は3になります。

この問題を解決するためのより良いプログラム アルゴリズムはありますか?

PS配列やその他のデータ構造を使用してこれを簡単に実行できることを私は知っています。最善の戦略、できれば数学的アプローチが欲しいだけです。

4

1 に答える 1

2

最も簡単な方法は、再発を書くことだと思います（ウィキペディアが言っていることのほとんどは、ヤン・ドヴォルザークに賛成票を投じることです）：

T(1) = 0
T(c) = (T(c-1)+n) mod c

または、C として (再帰なしで) 次のように記述します。

int non_fatal_josephus(int children, int n) {
    int result = 0;
    for(int i=2; i<=children; i++)
        result = (result + n) % i;

    return result + 1; //to make it one-based
}

繰り返しの説明:

T(c) は、「c 人の子供から始めた場合、どちらの子供が勝つか」を意味します。

T(1) = 0 となるのは、子供が 1 人しかいない場合、彼女はすでに勝っているからです (最初の子供、インデックス 0)。

一般的なケースでは、常に n 番目の子 (インデックス n-1) を削除します。彼女を削除するとすぐに、(c-1) 個の子で再びカウントを開始しますが、今回は、インデックス 0 から開始する代わりに、インデックス n. これが +n の説明です: T(c-1) はカウントが 0 から始まると仮定します。+n を使用して、インデックス n から開始したかのように子インデックスをシフトします。

于 2013-02-20T21:11:07.170 に答える