11

ですから、これが与えられた質問です。

あなたは 100 脚の椅子が円形に並んだ部屋にいます。椅子には 1 から 100 までの番号が付けられています。

ある時点で、椅子 #1 の人は退席するように求められます。椅子 #2 の人はスキップされ、椅子 #3 の人は退席するよう求められます。1 人を飛ばして次の人に退場を求めるこのパターンは、生存者が 1 人残るまで円を回り続けます。

で、たどり着いた答えがこれです。私はこれが正しい答えだと信じています.紙の上でも約10回行い、毎回74を思いつきました. これはひっかけ問題か何かですか？ここからどうすればいいのかわからないからです。

これがjsfiddle http://jsfiddle.net/cQUaH/です

var console = {
    log : function(s) {
        document.body.innerHTML += s + "<br>";
    }
};

var chairArr = [];
for (var i = 1; i <= 100; i++){
    chairArr.push(i);
}

var j = 2;
while(chairArr.length > 1) {
    console.log('removing ' + chairArr[j]);
    chairArr.splice(j, 1);
    j++;
    if(j >= chairArr.length) {
       console.log('--- Finished pass');
       console.log('--- Array state:');
       console.log(chairArr);
       j = (j == chairArr.length) ? 0 : 1;   
    } 
}
console.log('--- Final result: ' + chairArr); 
//result 74
4

4 に答える 4

6

インデックスを少し変更すると、Josephus 問題が発生します。従来の定式化では、1 人が 2 人を殺し、3 人が 4 人を殺す、というようになります。この形式に変換するには、問題が示すように 1 人を殺し、1 を引いて 2 人から 100 人の番号を付け直し、1 人から 99 人を与えます。

70-73 CE のユダヤ人反乱におけるその起源の説明を含むヨセフス問題の適切な扱いは、具体的な数学、第 2 版、グラハム、クヌース、およびパタシニク、セクション 1.3 にあります。ウィキペディアと Wolfram MathWorld の両方に問題に関する記事があり、ウィキペディアにはユダヤ戦争でのヨセフスによる元の説明も含まれています。

この本は、ソリューションのやや複雑な再帰と、より単純なアルゴリズムを示しています。人数がnで、n = 2^l + mがlできるだけ多い場合、答えは2m+1です。したがって、 であるため99 = 2^6 + 35、解は2*35 + 1 = 71です。しかし、再番号付けを逆にする必要があるため、本当の答えは72.

ただし、プログラミングの問題に関しては、基本的な操作として、円の最初の人を削除し、2 番目の人を最後に移動してみませんか。 したがって、5人の[1,2,3,4,5]場合は、最初の get を削除し[2,3,4,5]、新しい最初の要素を末尾の get に移動し[3,4,5,2]ます。

var killAndRotate = function(array) { // say [1,2,3,4,5]
    var dead    = array.shift(),      // dead    = 1, array = [2,3,4,5]
        skipped = array.shift();      // skipped = 2, array = [3,4,5]
    array.push(skipped);              //              array = [3,4,5,2]
}

そして、メインループは次のようになります。

while (chairArray.length > 1) {
    killAndRotate(chairArray);
}
alert(chairArray[0]); // or console.log, or return.
// In turn, array is:
// [1,2,3,4,5]
// [3,4,5,2]
// [5,2,4]
// [4,2]
// [2] and we alert, log, or return 2.

追加した

元のヨセフスの問題の結果を見つける簡単な方法は、次のことを確認することです。

人がいる場合2^l、最初のパスで偶数の人がすべて殺されるため、最初の人は生き続けます。

1 2 3 4 5 6 7 8

  X   X   X   X

今、2^(l - 1)人がいます。繰り返しますが、最初の人が生き残ります。

1 2 3 4 5 6 7 8

  X   X   X   X

    X       X

プロセスを繰り返します。最初の人が各パスで生き残り、最後の生き残りもそうです。

ここで、m余分な の人がいるとしm < 2^lます。ここで、l = 3とm = 5. 最初mに死ぬ人を殺します。

1 2 3 4 5 6 7 8 9 10 11 12 13

  X   X   X   X    X  Y

今、2^l人が残っていて、人2 m + 1 = 11が最初に並んでいます。だから彼は生き残る。

また、新しいインデックス変数の追加とスプライシングがプログラマ エラーにつながる可能性があることも指摘しておく必要があります。前から外して後ろに足すだけなので、配列の基本的な方法を使います。

于 2013-09-07T02:28:26.703 に答える
3

ここで説明したのはジョセフス問題であり、動的計画法を使用して解決できます。

function josephus(n, k) 
{ 
    if (n == 1) { 
        return 1; 
    } else { 
        return ((josephus(n-1, k) + k - 1) % n) + 1; 
    }
}

alert(josephus(100, 2));

出典：ウィキペディア

nは椅子の数を表し、kk人ごとに退席することを示します。

ここでの結果は 73 です。

アップデート

残念ながら、私は問題を正しく読んでいませんでした。上記のコードは、少し異なる問題を解決します。ラウンド1で最初の人を殺す代わりに、2人目が殺されます。生存者であることは詳細にかかっています:)

コードの問題を解決するのはかなり簡単です。最初のラウンドで 3 番目の人ではなく、最初の人から始めます。

var chairArr = [];

for (var i = 1; i <= 100; i++){
    chairArr.push(i);
}

var j = 0;
while (chairArr.length > 1) {
    chairArr.splice(j, 1);
    j = (j + 1) % n;
}
于 2013-09-07T02:25:38.983 に答える