どうも、小野氏です。

前回に引き続き、プログラム脳を鍛える数学パズルの問題を解いていきたいと思います。

今週は本書のQ9についてRubyで実装したので、そちらについて紹介いたします。

ほとんど模範回答をなぞる形になってしまいましたが、頑張って解説していきます。

(解けなかった問題を記事にするので、毎回答えをなぞる形になってるような気がします。。。)

Q9 つりあわない男女

問題

男性20人・女性10人を1列に並べ任意の箇所で2つに分割する際に、いずれのグループも男女の数が異なってしまうような並べ方は何通りあるか。

書籍には「2つのグループのいずれかで男女の数が異なってしまう」と記載されていましたが、さすがに問題がミスだと思うので「2つのグループのいずれかで男女の数が同じになる」という解釈で問題を解きます。

(男女の人数がそもそも違うので、「2つのグループのいずれかで男女の数が異なってしまう」だとどのような分割をしても必ず満たすと思います。)

書籍に記載があった模範解答を見ながら、実装した回答を記載します。

本問題を以下のように読み替えることで簡単に解けます。

以下の図の中で、男女の到着人数または到着していない人数が同じとなる箇所を通らず、右上の点に達する最短経路はいくつあるか。

(簡単のため、図は男10人、女性5人の場合で記載しました。)

f:id:kugelmulai:20200419210218p:plain

上述の問題であれば皆さん一度は解いたことがあると思います。

道の交点に数字を記載していくやつですね。

こちらをプログラムで実装したのが先ほどのコードとなります。

二次元配列で、上述の図の交点における最短経路の数をそれぞれ格納しています。

answer配列の宣言では、以下のように記載してしまうと配列に入るオブジェクトが共通となってしまい正しく計算できなくなってしまいます。

answers = Array.new( boys + 1 , Array.new( girls + 1 ) )

各セルに違うオブジェクトを格納したい場合には、ブロックを利用して記述しましょう。

最初は男20人・女10人の配列の組み合わせをすべて作り、右からカウントしていき男女の人数 or 残りの男女の人数が同じになったところで処理を中断するという方法で考えましたが、組み合わせが作れず断念しました。
- 今後、断念した方法で実装する記事も作りたいと思います(おそらくアルゴリズムの効率としては悪い気がいますが)。
この問題については、考えれば解けた気もするので悔しいです。
- 算数の問題を解く時の頭の使い方と、プログラムを作成する時の頭の使い方の差にまだ戸惑っております。
アルゴリズムの勉強をしっかりしたことがないので、ちゃんとやってみたいなと思いました。