読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(1)

Google Code Jamの季節になると活発になるこのblog。今日(今年w)は数学系パズル本であるAlgorithmic Puzzlesの問題を解いてみましょう。この本、出たばっかりの時にKindleで買ったんですが最近日本語にもなったみたいですね。本屋で見かけた、というか、手にとって見たらどこかで見たことある問題だらけだったので。

120. Penny Distribution Machine (石分配マシーン)

横に長い配列があり、一番左のセルに石が何個か入っている。2個の石が同じセルの中にあった場合は、1個にし右のセルに移動する操作をできなくなるまで行う時;

1)最終結果は石の移動の順番に依存するか?

2)n個の石で始めた時、何個セルが必要か?

3)この操作が止まるまで何回の操作がされるか?

というのが問題の趣旨(超訳)。詳しい解説は本を購入して頂くとして、これをプログラムを組んで解こうというのがこの記事の趣旨。コンピュータに関連する問題だしね 1)、2)は簡単。この操作の最終結果が2進数表現になることが分かれば、1)は依存しないし(厳密には加法の可換性)、2)は2進数にした時のビット数だ。 ただし、3がちょっとすぐには分からなかった。結局何回繰り上げするかだけど、何か法則があるのかどうか? こういう時にサクッとプログラムを作って実験するのが個人的にいいと思う。紙と鉛筆のオールドスクールを否定しているわけじゃないけど。一度プログラムを組むと、コードのパラメータをいじることで、3つの石になったら分配するとかに応用がすぐ効く。また、結構な数の例を見ることが出来るので、洞察を得やすい。

#!ruby
class PDM
    attr_reader :dist_num
    def initialize(n)
        @boxes=Array.new(10,0)
        @boxes[0]=n
        @dist_num=0
    end

    def dist!
        @boxes.each_with_index{|penny,idx|
            if penny>1
                @boxes[idx]-=2
                @boxes[idx+1]+=1
                @dist_num+=1
                return idx
            end
        }
        nil
    end

    def to_s
        @boxes.join(" ")
    end
end

1.upto(20){|n|
    box=PDM.new(n)
    while box.dist!
    end
    puts "%2d: %d"%[n,box.dist_num]
}

早速実行してみると

 1: 0
 2: 1
 3: 1
 4: 3
 5: 3
 6: 4
 7: 4
 8: 7
 9: 7
10: 8
11: 8
12: 10
13: 10
14: 11
15: 11
16: 15
17: 15
18: 16
19: 16
20: 18

増加列なのはそうだけど、パターンがなかなか見えてこない。列? 困った時のオンライン整数列大辞典で検索すると A011371 - OEIS

a(n) = n minus (number of 1’s in binary expansion of n)

nからnの2進数表現に出てくる1の数を引くってどういうことだ??

アハ!

この石分配マシーンの動作をもう一度考えてみよう。2個の石を右に移動する操作のトータル数を求めるんだけど、1操作につき1つ石が減ってる! すなわち石が減った数を数えれば良い、すなわち最初の石の数-残った石の数 それにしても、OEISはすごい。こんな数列まで載っているとは。

こんな感じで数学パズル本の問題をプログラムで解くのは結構面白いし教育的だ。競技プログラミングに特化している本の問題は、アルゴリズミックな問題だらけで初学者が楽しめないんだよね。それにこう言った問題は紙と鉛筆で解くことが前提なので、Straightforwardなプログラムで結構解けちゃったりする。問題のサイズが大きくなると解けないんだけど、そんなものはあまり求められない。いろいろな解法があったりするのも興味深い。というわけで、結構面白いので皆さんも試してみよう!

www.amazon.com