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

本履歴

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

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

マーチン・ガードナーのサム・ロイド本を眺めていたら見つけた問題。解けそうだったので頭の中で組み合わせ考えたけど結局解けなかった。悔しいからRuby書いてしまいました(笑)

56. How can you score exactly 50 points?

ようは、与えられた数の集合{25, 27, 3, 12, 6, 15, 9, 30, 21, 19}から選んで合計が50にできるかというもの。O(n*k)で解けますね。っていうか、解けないから解無しだと思ったんですけどね。こういうテキ屋の景品って当たり無しが当然じゃないですか。 ちなみに、このパズル作家サム・ロイドですが(音がメトロイドっぽいよね(笑))相当古いみたいでpublic domain入りしてましたので、実際の紙面(MathPuzzle.comより)も載せておきます。マーチン・ガードナーの本と結構説明が違う感じですね。差別的な表現が抑えられているような。まあ、合法的にオリジナル本を参照できるなら、マーチン・ガードナー本を買う必要はあまりないかな。

points=[25, 27, 3, 12, 6, 15, 9, 30, 21, 19].sort

N = 50

dp = Array.new(N + 1, false)
dp[0] = []

points.each{|p|
    (N + 1).downto(0){|i|
        next if i + p > N
        if dp[i]
            dp[i + p] = dp[i].dup
            dp[i + p] << p
        end
    }
}

p dp[N] # => [6, 19, 25]

f:id:uru:20170429002831j:plain

Mathematical Puzzles of Sam Loyd (Dover Recreational Math)

Mathematical Puzzles of Sam Loyd (Dover Recreational Math)