技術

整数もしくは浮動小数点数の計算誤差の検出問題

ひょんな事から次のような問題(いわゆるパズル問題ですね)を発見し、面白そうだと思ったのでPythonでやってみました。
中学生にも解けるパズルを解くのに向いたプログラミング言語は? – Yahoo!知恵袋
リンク先ではなるべく実行が速く、なるべくコードが短いという点が 評価軸になっているようですが、極めて個人的な趣味によりその辺りは無視し(おいw)読み易さを優先して書いたので、ここで公開します。
あと、リンク先の問題文が分かりづらかったので、私なりに書きなおしたものも置いておきます。

問題(1):

4つの一桁の数値に対する四則演算の結果が 分数の計算をちゃんとやれば本当は10になるのに 整数演算だと誤った結果になる例を全て出力。
例: (((1 / 2) * 5) * 4) = 10 (0)
一番右のカッコ内は整数で演算したときの誤った答え。

問題(2):

問題(1)の浮動小数点数版。

ソースはこちら

peta-okechan/calc-error-detection

アルゴリズムの概要

まず4つの数値の組を総当りで生成(再帰yield)しつつ、
さらにその数値の組で可能な式の組み合わせを総当りで生成(再帰yield)し、
その式を評価して問題の条件を満たす場合表示、となります。
式(と演算の優先順位)の表現にツリーを用いています。
(Binomialがノード、Constantがリーフに相当)
あと、分数を扱うためにFractionクラスを実装しましたが、
これはPython 2.6から標準ライブラリとなったfractionsモジュールのFractionクラスにそのまま置き換え可能です。
(標準ライブラリのFractionクラスは高機能なのでちょっと遅いですけど)

感想

柔軟性もそれなりに持たせつつ、そしてPythonらしくすっきりと記述出来た気がします。
だいたい最初のイメージどおりのコードで解けたのでちょっと気分が良いです。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください