切手を貼る方法(Haskell)

■問題:2セント,4セント,6セント,8セントの切手を封筒に一列に貼って10セントにしたい.何通りの方法があるか?(異なる並べ方は違う方法としてカウントする).

■注意:つまり「2,2,4,2」と「4,2,2,2」は違う方法としてカウントされる.

■問題出典:Pólya & Szegöの “Problems and Theorems in Analysis I”の問題3である.

{b_n}によって,『{n}セントを支払う方法の数』を表す.組み合わせについての簡単な考察により

{b_0 = 1.}
・負の添字に対して {b_n = 0.}
{b_n = b_{n-2} + b_{n-4} + b_{n-6} + b_{n-8}.}

がわかる.これを素直にHaskellのコードに移すと:

b :: Int -> Int
b n | (n < 0) = 0
    | (n ==0) = 1
    | otherwise = b (n-2) + b (n-4) + b (n-6) + b (n-8)

となる.よって b 10 を求めればよい.

$ ghci
Prelude> :l b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )

Ok, modules loaded: Main.
*Main> b 10
15

答えは15通りである.

■ Pólya & Szegöの “Problems and Theorems in Analysis I” では,さらに数列 {b_n}の母関数の閉じた式が扱われている.(今回は必要ないので扱わない.)

広告
コメントする

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。