12-04の頭の体操のつづき
http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/cactusman/20081201/p1
cards.remove(k)に伴う副作用を利用した実装。素直な実装かな？と一瞬オモタ。でもそれよりも、計算機なしでどうやってこの問題を解くのかが気になった次第。
というブクマコメントがあったので、どうやって手計算で解いたのかをご紹介します。
まず、カードの枚数が512枚、512=2^9なので、取り除く作業は9回行われます。
こういう場合、最初から追わずに最後から追っていくほうが理解しやすいので、そのようにします。
最後は9回目でこれは奇数回目なので奇数番目のカードが取り除かれます。
よって、1番目に来ているカードが取り除かれ、2番目のカード残る、というのがわかります。
以下、取り除かれる前の状態です。
a X
aは9回目に取り除かれるカードで、Xが最後に残るカードです。
では、8回目に除外されるものはどうなっているでしょうか？
8回目は偶数回目なので、偶数番目のカードが取り除かれることになります。
以下、取り除かれる前の状態です。
a b X b
bは8回目に取り除かれるカードです。
では、7回目はどうでしょうか？
7回目は奇数回目なので、奇数番目のカードが取り除かれます。
以下、取り除かれる前の状態です。
c a c b c X c b
cは7回目に取り除かれるカードです。
ここいらで、Xの位置について考えて見ましょう。
Xが1→2→3→6と順番に移動しています。
(1*2*2-1)*2となってるんじゃないかと、気づい方は感がいいです。
そのつぎは(1*2*2-1)*2*2-1=11となっているかどうか確認します。
6回目は偶数回目なので、偶数番目のカードが取り除かれます。
以下、取り除かれる前の状態です。
c d a d c d b d c d X d c d b
bは6回目に取り除かれるカードです。
Xが先ほどの予想通り11番目に来ています。*1
ということで、ここで*の数がカードを取り除いた回数ということなので、その回数分だけ演算してみます。
((((1*2*2-1)*2*2-1)*2*2-1)*2*2-1)*2
=342
となります。
それで、このカードの枚数が512枚という2のn乗になってる枚数だとうまくいくのですが、そうでない場合はうまくいきません。
そういう意味で汎用的でない方法というわけです。
N枚目の場合、n回取り除く、というnが自明に求まればこの方法で再帰的に行えば計算できることになります。
これだと、前に行った計算に比べ、断然早くなりますね。
