一万円を崩す方法(Haskell)

一万円を両替して崩す方法は何通りあるだろうか.ただし:
・百円玉,五百円玉,千円札を自由に(好きなだけ)使って良い.
・五百円記念硬貨は10枚までしか使えない.
・二千円札は2枚までしか使えない.

この問題は以前の千円を崩す方法(Haskell)の変種である.新しい要素は五百円記念硬貨(普通の五百円玉と区別される)と二千円札である.どちらも個数(枚数)に制限がある.

答えは1561通りになるはず.

以前の記事では組み合わせ的な考察だけから漸化式を導いて解いたが,今回は母関数を使わねば漸化式を導くことができなかった.

これを求めためのHaskellプログラムは次のようになる:

p n = if n < 0 then 0
      else if n `rem` 100 == 0 then 1
      else 0
q n | (n < 0) = 0
    | otherwise = p n + q (n-500)
r n | (n < 0) = 0
    | otherwise = q n + r (n-1000)
s n | (n < 0) = 0
    | otherwise = r n - r (n-5500) + s (n-500)
t n | (n < 0) = 0
    | otherwise = s n - s (n-6000) + t (n-2000)

問題の答えは t 10000として求まる.

ブログに数式を書くのが面倒になったので,数列を母関数を通して扱う話からはじめて,このプログラムを導く過程をPDFにまとめてみた.(文字を大きくしておいたのでスマホでも読めると思う):数列と母関数

広告

切手を貼る方法(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}の母関数の閉じた式が扱われている.(今回は必要ないので扱わない.)

千円を崩す方法(Haskell)

次のような問題を考えてみましょう:

千円を両替して崩す方法は何通りあるだろうか.ただし,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って良いものとする.

まず問題を一般化し,つぎのように考えます.{A_n}によって「{n}円を一円玉で崩す方法の数」を表すことにします.(と言っても{n\ge 0}ならば常に{A_n = 1}なのですが).

また,{B_n}によって「{n}円を一円玉と五円玉で崩す方法の数」を,

{C_n}によって「{n}円を一円玉と五円玉と十円玉で崩す方法の数」を,

{D_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉で崩す方法の数」を,

{E_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉で崩す方法の数」を,

最後に{F_n}によって「{n}円を一円玉と五円玉と十円玉と五十円玉と百円玉と五百円玉で崩す方法の数」を表すことにします.

このように定式化すると,クイズの答えは{F_{1000}}と表されます.あとはこの具体的な数値を求めれば良いわけです.

さて,{F_n}はを「n円を五百円玉を一枚も使わないで表した場合の数」と「(n-500)円をすべてのコインを好きなだけ使って表した場合の数」の和だと考えられます.
(追記2018/08/27 少し説明を補います.{n}円を全てのコインを使って崩した場合を全て列挙した集合を{X}としましょう.{X}を (i)五百円玉を一つも含まないもの (ii)少なくとも1枚の五百円玉を含むもの に分割できます.それぞれの場合からなる集合を{X_1,X_2}としましょう.{X = X_1 + X_2} (非交和)ですから,{|X| = |X_1| + |X_2|} となります.明らかに{|X_1| = E_n}です.{X_2}の全ての要素から五百円玉を一つ抜くと,それぞれは{n-500}円を崩したものになっています.したがって{|X_2| = F_{n-500}}です.
).よって

{F_n = E_n + F_{n-500}}

となります.よって,{F_n}の計算を{E_{n},\,F_{n-500}}の計算に還元できます.

同様に考えれば
{E_n = D_n + E_{n-100}}などの式が得られます.ただし,負のインデックスに対しては{A_n, B_n, C_n, D_n, E_n, F_n}はいずれもゼロとします.この考えをそのままHaskellコードにすれば次のようになります:

fA n | (n < 0) = 0
     | otherwise = 1

fB n | (n < 0) = 0
     | otherwise = fA n + fB (n-5)

fC n | (n < 0) = 0
     | otherwise = fB n + fC (n-10)

fD n | (n < 0) = 0
     | otherwise = fC n + fD (n-50)

fE n | (n < 0) = 0
     | otherwise = fD n + fE (n-100)

fF n | (n < 0) = 0
     | otherwise = fE n + fF (n-500)

これらの定義を書いてGHCiで:l 1000yen.hs してやってから fF 1000 を計算させると248908という答えが得られます.

したがって,一円玉,五円玉,十円玉,五十円玉,百円玉,五百円玉を自由に(好きなだけ)使って千円を両替する方法は全部で248908通りあることになります.

この問題はポリア他『組合せ論入門』p.11(近代科学社)で扱われている問題を改変したものです.(元の問題は1ドルを1セント,5セント,10セント,25セント,50セントで崩す問題です.)この問題はポリアのお気に入りだったのか,Pólya & Szegö “Problems and Theorems in Analysis I” にも収録されています.)

この記事では漸化式を組み合わせ論的な考えで導きましたが,ポリアの本では母関数を利用して漸化式を導いています.興味のある方は是非ポリアの『組合せ論入門』を読んでみてください.

ココナツの問題をC++で解く

■前回の記事「Maybeの(>=>)を使って問題を解く」ではHaskellでココナツ問題を解いてみたが、もし使える言語がC++しかなかったらどうするか考えてみた。Haskellでは失敗する可能性のある関数を「合成」することができたが、C++にはそのような機能がないのでif文で分岐することになる。

#include <iostream>
#include <utility>

#define MAX 100000

using namespace std;

pair<bool,int>  g(int n, int r)
{
  pair<bool,int> retval = make_pair(false,0);
  if(0 == (n-r) % 5){
    const int x = 4*((n-r)/5);
    retval = make_pair(true,x);
  }
  return retval;
}

typedef pair<bool,int> mint;

bool check_num(int n)
{
  //1,1,1,1,1,0
  const mint n1 = g(n,1);
  if(n1.first){
    const mint n2 = g(n1.second,1);
    if(n2.first){
      const mint n3 = g(n2.second,1);
      if(n3.first){
        const mint n4 = g(n3.second,1);
        if(n4.first){
          const mint n5 = g(n4.second,1);
          if(n5.first){
            const mint nfin = g(n5.second,0);
            if(nfin.first){
              return true;
            }
          }
        }
      }
    }
  }
  return false;
}

int get_ans(){
  for(int n = 0; n < MAX; ++n){
    if(check_num(n)){
      return n;
    }
  }

  return -1;
}

int main()
{
  const int n = get_ans();
  cout << n << endl;
  return 0;
}

関数check_numをもう少し読みやすく出来ないかと考えてみたが、良い考えを思いつかなかった。

昔の自分なら、マクロを使って

bool check_num(int n)
{
  //1,1,1,1,1,0
  const mint n1 = g(n,1);

  #define MY_MACRO(X,Y,R)   g(X.second,R);if(! Y.first){return false;}

  const mint n2 = MY_MACRO(n1,n2,1);
  const mint n3 = MY_MACRO(n2,n3,1);
  const mint n4 = MY_MACRO(n3,n4,1);
  const mint n5 = MY_MACRO(n4,n5,1);
  const mint nfin = MY_MACRO(n5,nfin,0);

  return true;
}

のように書いたかもしれないが、疲れているときにこのようなコードを書くことの恐ろしさを何度か経験したのであまり乗り気にはなれない。

■結論は特にない。(HaskellがすごいとかC++がダメだと主張したいわけではない)。

Maybeの(>=>)を使って問題を解く

■マーティン・ガードナーのパズル本を見ていたらこんな問題が載っていた:

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、1つ余ったので、彼はそれを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。やはりココナツは1つ余り、それは猿のものになった。こうして5人の男たちが順番に同じことをした。つまり1人ずつ目を覚ましては、ココナツの山を5つに分けて、残った1つを猿にあげて、自分の取り分を画した。朝になり、残ったココナツ全部を分けると、今度はきれいに5等分された。
(略) さて、最初にココナツはいくつあったのだろうか?

計算機で総当りしてももちろんこの問題は解ける。本には、これを少ない労力で解くためのトリックが紹介されていた。(「ガードナーの数学娯楽」/日本評論社)。そのトリックについてはこの記事では触れない。

この問題を見たとき、HaskellのMaybeモナドを使ったら素直に解けそうだと感じた。(そして実際に解けた)。ココナツの数をNとすると
N = 5A +1 ;  4A個の山を残す # 1人目の男
4A = 5B + 1 ; 4B個の山を残す # 2人目の男
4B = 5C + 1 ; 4C個の山を残す # 3人目の男
4C = 5D + 1 ; 4D個の山を残す # 4人目の男
4D = 5E +1 ; 4E個の山を残す # 5人目の男
4E = 5F ; きれいに5等分された
のようになる。「与えられた数から1を引いておけば5で割り切れる」という状況が続き、そうして得られた商の4倍だけ残すという操作が5回行われている。そこでこんな関数を考えてみよう:

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

こうすると、それぞれの男が行った操作は g 1 として表現できる:

g 1 :: Int -> Maybe Int

一般に、モナドMに対して X -> M Yの形の関数は、(>=>)で合成できるのだった。
(この記事では説明しないし、知っている必要もないが、この形の関数はこのモナドの与えるKleisli圏の射とみなす事ができ、(>=>)はこのタイプの射の「合成」とみなせるのだった)。

よって、5人の男がココナツに対して行った操作とその結果は

f :: Int -> Maybe Int
f = g 1 {- 1人目の男 -} >=> g 1{- 2人目の男 -} >=> g 1{- 3人目の男 -} >=> g 1{- 4人目の男 -} >=> g 1{- 5人目の男 -} >=> g 0

として表せる。もちろんこれはもっとコンパクトに

f = foldl1 (>=>) [g 1, g 1, g 1, g 1, g 1, g 0]

と書いてもいいし、さらにこれは

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

と書いてもいい。こうして得られたfInt -> Maybe Int という型を持つ。元のクイズの答をNとするとき、 f N Just ...という形をしているはずである。そこで、こんな関数を用意してみよう:

--  f の答がNothing ではない場合の引数を得るように変形する
getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

この関数を使えば、問題のNは map (getJustArg f) [1 ..] というリストに含まれる「Just x」の形をした最初の元から得られることがわかる。Data.List の

find :: (a -> Bool) -> [a] -> Maybe a

を使えば最初の元を取ってこられそうだ。findMaybeをかぶせて返してくるおかげで、
find isJust (map (getJustArg f) [1 ..])Maybe(Maybe Int) 値になる。そこで join してMaybe を一段に落としてやると、得られる答は Just n の形をしているので fromJustInt値を引っ張り出せる:

fromJust . join $ find isJust (map (getJustArg f) [1 ..])

以上をまとめると次のようなプログラムが得られる:

import Control.Monad
import Data.List
import Data.Maybe

g :: Int -> Int -> Maybe Int
g r n
    |  (n-r) `rem` 5 == 0  = Just( ((n-r) `quot` 5) * 4 )
    |  otherwise           = Nothing

f = foldl1 (>=>) $ map g [1,1,1,1,1,0]

getJustArg :: (a -> Maybe b) -> (a -> Maybe a)
getJustArg f x
    | isJust (f x)  = Just x
    | otherwise     = Nothing

main = do{
  print $ fromJust . join $ find isJust (map (getJustArg f) [1 ..])
  }

答は3121となる。

■まとめ
Maybeモナドに対するKleisli射の合成演算(>=>)を用いてクイズを解いてみた。

■おまけの問題

5人の男と一匹の猿が難破して無人島に漂着した。1日目、彼らは食糧としてたくさんのココナツを集めて回った。そしてその夜、すべてのココナツを積み上げて彼らは眠りについた。
 しかし全員が眠りについたあと、1人の男がふと目を覚ました。朝になってココナツを分けるとき、ひと悶着起きるかもしれないではないか。心配になった彼は自分の取り分を先取りしようと考えた。彼がココナツを5つの山に等分してみると、4つ余ったので、彼は余ったココナツを猿にあげてから、自分の取り分を隠して、残りを元通りに積んでおいた。
 しばらくして別の男が目を覚まして、同じことを考えた。今度は3つ余ったので、彼はやはり余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
三番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は2つ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
四番目の男も同じことを考えたが、彼がココナツを5つの山に分けようとすると今度は1つだけ余った。やはり彼は余ったココナツを猿に与え、自分の取り分を隠してから残りを積んでおいた。
五番目の男も同じことを考えたが、彼だけは仲間を裏切ることを恥ずかしく思い、結局何もしなかった。
朝になり、残ったココナツ全部を分けると、きれいに5等分された。
さて、最初にココナツはいくつあったのだろうか?

最小の答は3089個になるはずである。