日曜研究室 LLVMによるプログラミング言語の実装 xv6ソースコードリーディング 技術 日記
日曜研究室

日曜研究室

まだ庭の小石の数を数え終わっていない

技術

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

投稿日
2015/6/19 金曜日
カテゴリー
技術
タグ
著者
Take it easy!

ひょんな事から次のような問題（いわゆるパズル問題ですね）を発見し、面白そうだと思ったので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 を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。