プログラム脳を鍛える数学パズル 第四弾

どうも、小野氏です。

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

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

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

今回は、メモ化という手法について解説があったため、そちらをについても軽く触れていきたいと思います。

Q11 フィボナッチ数列

問題

フィボナッチ数列のうち、各桁の数字を足した数で割り切れる144より大きい数を、小さいほうから5個あげよ

いくらでも時間がかかっていいのであれば実装自体は難しくないのですが、何も考えずに再帰を使うと痛い目を見ます。

回答

自分で考えて実装したものが以下のものです。

やっていることは以下の通り。

1. フィボナッチ数列を計算するメソッドの実装
   • def Fibonacci_number(n)がそれにあたります
2. 初期変数・回答を計算するための配列を宣言
3. 配列の長さが9つになるまで、(フィボナッチ数列の計算結果)/(各桁の数字を足した数)の剰余が0のものを配列に追加

ちなみに二日かけても実行が終わらなかったので、途中で実行を中止しました。

(そのため、そもそも間違っている可能性も否めないです。)

解説

フィボナッチ数列の実装方法に絞って解説していきます。

フィボナッチ数列は以下の漸化式で定義することが出来ます。

そのため上述の式を愚直に実装すると、先述のコードのようになります。

ただ上述の方法で計算すると、同じ計算を複数回する必要があります。

下図は再帰でフィボナッチ数列の5番目の値を求める際の計算の流れをざっくり表したものです。

黄色の箇所について、まったく同じ計算を二度行っていることがわかると思います。

桁数が少ないときはこれでも問題がないのですが、nが大きくなると計算に時間にかかる時間が大きくなってしまいます。

そのため、同じ計算を二回行わないために、以下の二つの対策が考えられます。

1. メモ化:すでに計算した値を保存しておく
2. ボトムアップ型:トップダウンに計算するのではなく、ボトムアップに計算する

それぞれの実装についてざっくり説明をしていきます。

メモ化

Wikipediaの定義は以下の通りです。

プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である

ざっくりいうと、すでに計算した値を保存しておくことを指すと理解しました。

計算値の格納先としては、可変長のものが好ましいので、リスト or ハッシュが良いかなと思います。

rubyで実装すると以下のようになります。

ボトムアップ型

再帰でフィボナッチ数列を解く場合、トップダウンでn項目の値を計算します。

具体的にいうと、5番目の項を求めるため4番目の項と3番目の項を計算していきます。

これをボトムアップで、つまり1番目の項と2番目の項を足し合わせ3番目の項を求めるという方法で、n番目の項を求めるという手法も考えられます。

こちらについてもメモ化と併用することで、回答を高速で計算できるようになります。

rubyで実装すると以下のようになります。

所感

• このプログラム遅いだろうなとおもいつつ、どうやって修正すればよいのかわからなかったため、解説を読んでとてもすっきりした。
• 今回の解法に感動したので、今後はアルゴリズムに特化した勉強をしていきたいなという気持ちが強くなった。
• 調べたりないという気持ちがあるので、今後フィボナッチ数列だけを特集した記事を作成するかもしれない
• プログラムのベンチマークを評価するため、rubyにはBenchmarkというものがあるらしい。自分のプログラムにも今後適用してアルゴリズムの評価をしていきたい。

プログラム脳を鍛える数学パズル 第三弾

どうも、小野氏です。

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

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

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

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

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

Q9 つりあわない男女

問題

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

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

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

回答

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

1. 変数の宣言
2. 回答を計算するための配列を宣言
3. 配列を利用して、男女の人数が同じにならない順列の数を求める
   • 後に説明

解説

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

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

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

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

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

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

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

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

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

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

所感

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

プログラム脳を鍛える数学パズル 第二弾

どうも、小野氏です。

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

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

今週は本書のQ5について紹介いたします。

正直答えを見ながら解いたので、ほとんど模範解答をなぞる形になってしまう気がしますが、頑張って解説していきます。

Q5 いまだに現金払い？

問題(要約)

1000円札を10円玉、50円玉、100円玉、500円玉で両替するとき、両替後の硬貨の枚数が15枚以下に組み合わせは何通りか。

(なお、使わない硬貨があっても構わない。)

また、問題には拡張性を意識した実装を行ってくださいとの記載がありました。

(正直、両替後の金額が1000円であることを固定してしまえるなら、簡単だと思います。)

回答

書籍に記載があった模範解答のうち、私の考えに近かったものを記載します。

ざっくり処理の流れを説明すると以下の通りです。

1. 変数の宣言
2. repeated_combinationメソッドを配列の要素の重複組み合わせを作成
   • 後に説明を記載
3. それぞれの配列の合計値を計算し、1000になるものの個数を数え上げる

解説

repeated_combinationメソッドは、引数の長さの配列の重複組み合わせを作るメソッドです。

(重複組み合わせなので、取り出した元の並びは考慮しないが、同じ元を複数取り出すことが許容する)

具体例として、引数を2とした場合を書き出します。

[500, 100, 50, 10].repeated_combination(2).to_a 
#=> 
　[
        [500, 500], [500, 100], [500, 50], [500, 10],
        [100, 100], [100, 50],  [100, 10],
        [50, 50], [50, 10],
        [10, 10]
    ]

上述の処理を行うことで、硬貨2枚の重複を許す全ての組み合わせが洗い出さます。

そして、戻り値となる配列の元のうち和が1000になるものを探すことで、硬貨2枚の場合に1000円となる組み合わせを洗い出すことが出来ます。 (上述の具体例だと、[500, 500]が相当します。)

上述の処理を硬貨2枚～15枚の場合にわたって行うことによって、硬貨15枚以下で1000円となる通りを全て洗い出すことができます。

所感

本問題を解くうえで、上述のメソッドを知らなかったので、以下の方法で実装しようと考えました。

1. coinの種類を配列で宣言
   • 上述のコードの[500, 100, 50 , 10]にあたる部分
2. コイン枚数の配列を宣言し、配列の和が2~15となるパターンを全て洗い出す
   • 具体的には長さ4の配列[0 ,0 ,0 ,0 ]の要素に対して値を加算することで、全パターンを洗い出そうと考えておりました。
3. coinの種類の配列のi番目とコイン枚数の配列のi番目をかけ合わせ、1000円となるものの個数を数える(0≦i≦3)

自分のプログラミングスキルだと上述の2にあたる処理を実装することができず、今回はあきらめてしまいました。

おそらくrepeated_combinationメソッドのソースコードでは、上述の2の処理のようなことをやっているとは思うので、復習のために確認しようと思います。

また、本問題の回答として再帰メソッドを使った以下の方法も紹介されておりました。

行っている処理は以下の通りです。

(十分に理解できていない中で記載を行っているので、わかりにくいかもしれません。。。)

1. 変数targetを配列coinsの要素を変数usable個までつかって実現するメソッドとしてchange(target, coins, usable)メソッドを宣言
   • 今回のケースとしては、target=1000, coins=[500, 100, 50, 10], usable = 15である
2. 配列coinsの最初の要素を抜き出し、変数coinに代入する
   • shiftメソッドは破壊的メソッドなので、本処理を行った後に配列coinsから最初の要素は消える
3. 配列coinsの要素が0ではない場合、0を下限にtarget/coinの回数を上限に硬貨の枚数を変え、changeメソッドを呼び出す
   • 例えば、coinが500でiが1の場合、change(500, [100, 50, 10], 14)を呼び出す
     • つまり、500円を100円玉、50円玉、10円玉を14枚以下で実現するメソッドを呼び出す
   • coinsはcloneすることで別オブジェクトとして生成する(つまり、元の配列coinsに影響を与えないよう処理を進める)
4. 配列coinsの要素が0の場合、変数targetを変数coinで割った数がusable以下になる場合、条件を満たす通りとしてカウントする
   • 配列coinsは、処理の中で[500, 100, 50, 10]→[100, 50, 10]→[50, 10]→[10]と変化するため、coins.sizeが0となる場合coinはかならず10となる。
     • target/coin = 0/10 = 0 <= usable を満たす場合には、条件を満たすものとしてのカウントが行われますため、10円を使わない場合でも条件を満たすものとしてカウントされるものは存在する。

正直、上述の方法はなにたべてたら思いつくのかわからないくらい異次元の回答に見えました。。。

ただ本記事を書くために処理を追うなかで、何をやっているのかは大体わかるようになりました。

自分でコードを実装する際に、上述の方法も考慮できるようになれるよう、学習を進めていければと思いました。 プログラミングは奥が深いなぁ。。。。

以上

プログラマ脳を鍛える数学パズルを解いてみる 第一弾

どうも、小野氏です。

プログラミングのネタを探していたところ、以下の本を見つけました。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

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

(プログラミング初心者なので温かい目で見守っていただけると幸いです。)

Q2 数列の四則演算

問題(要約)

4桁の数字の各桁の間に四則演算の演算子を入れて計算を行う(演算子を入れない箇所があったもよいが、かならず1つは演算子を入れるものとする) この時、計算結果が元の数の桁を逆から並べた数字と同じになるものを求めよ

例

3桁の数字だと以下のものが考えられます。

• 351(3*51=153)
• 621(6*21=126)
• 886(8*86)

回答

自分のコードをgistに挙げているので、そちらを紹介します。

ざっくり処理の流れを説明すると以下の通りです。

1. 変数の宣言
2. 配列numberに1000~9999までの数字を代入
3. 配列numberに対して拡張for文で要素となる四桁の数字をそれぞれ取り出し、処理を実施
4. 配列ope×3に対して、拡張for文でオペランドをそれぞれ取り出し、数式valを構成
5. 数式valに対して、以下の条件を満たすかを確認
   • valが4文字より多いか(オペランドを少なくとも一つ含むか)
   • 0での割り算が含まれていないか
6. 0n(nは任意の数字)という形式になっているものを、xとなるようにgsub関数で置換
7. 数式valを数式評価し、元の四桁の数字を反転したものと一致するかを確認する

解説

上述の記載の6が一番苦労をしたので、そこについてある程度解説します。

最初、6の処理を入れていなかったところ以下のエラーが発生しました。

'eval':(eval):1: Invalid octal digit (SyntaxError)

ぱっと見何のことかわからなかったですが、eval関数にかけて文字列→数式で評価する際に不正な8進数」というエラーが発生したので、おそらく文字列→数式に変換するときに変なことになったと予想しました。

それでRubyでの8進数のprefixを確認したところ、以下の通りでした。

項目	prefix
2進数	0bで始まる数値は 2進数とみなされる
8進数	0で始まる数値は 8進数とみなされる
10進数	0dで始まる数値は10進数とみなされる
16進数	0xで始まる数値は16進数とみなされる

0n(nは任意の数字)という並びでオペランドが挿入されなかった場合、そいつが8進数とみなされエラーが発生している模様。。。

解決するためには、0nという並びのときに0を削除してからeval関数にかける必要があり、0を削除する必要があります。

そのため、gsub関数で「{オペランド}0n」という並びになっている個所を探し、最初の0だけを削除しています。

例えば005など、削除した結果再度8進数と判断されてしまう数字の可能性を考慮して、while文で複数回本処理を施しております。

(複数回処理を行うことで005→05→5と置換されうまくいっているはず。。。)

所感

• 純粋に処理を考えるのは楽しかったです。
• 仕事でプログラミングをしないので、メソッドを調べるのに時間がかかってしまいました。慣れていければ嬉しいです。
  • evalとか、gsubとか
• 本には10分で解けるって書いてありましたが、絶対に無理です。60分くらいは余裕でかかりました。
• if文3つくらいnestしてるけど、可読性は問題ないのか不安です。

今後も、本書ので解いた問題を週1程度で紹介できればいいかなと思います。

以上

はじめまして

この度ブログを開設することとなりました小野と申します。

勢いで作ったブログなので今後何をしていくかはあまり決まっておりませんが、読んだ本のレビューや資格試験の学習履歴を記載できれば良いかなと思ってます。

以上