スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

切符番号の問題を解くRubyプログラムの例 (1)

切符番号の問題とは、以下のような問題です。

4つの数字が与えられたときに、それら数字の間に適当な四則演算を挿入して、その計算式の結果を10にせよ。

テンパズル(10 Puzzle)やメイクテン(Make 10)といった名称で呼ばれることのほうが多いかもしれません。

新納浩幸『入門Common Lisp 関数型4つの特徴とλ計算』(毎日コミュニケーションズ)に、高階関数を利用したCommon Lispプログラムの例として、切符番号の問題を解くプログラムが掲載されています。そこでは、要点を明確にするため、以下の条件を付けています:

  • 数字は1~9まで。0を使わない
  • 括弧を使わない
  • 数字の並べ替えはしない

この記事では、まず、上記の書籍に掲載されているCommon Lispプログラムを参考にして、同じ条件で切符番号の問題を解くプログラムをRubyで書き直します。以下に示すプログラムではゼロ除算対策を施したので、0の使用が可能です。次に、

  • 括弧を使用した場合
  • 数字を並べ替えた場合
  • 2つの数字を併せて2桁の数字を作る場合

に対応するように、Rubyプログラムを拡張します。

まず、括弧は使わず、数字の並べ替えもない場合におけるRubyプログラムの例です。実行すると、以下のようになります:

[1, 3, 4, 3]:
1 + 3 * 4 - 3 = 10
1 - 3 + 4 * 3 = 10
1 * 3 + 4 + 3 = 10

以下が、ソースコードです:

#!ruby -Ks

require "rational"  # Ruby 1.9では不要

# 切符番号の計算
# a:4つの整数値を要素とする配列
def ticket_number(a)
  puts "[#{a[0]}, #{a[1]}, #{a[2]}, #{a[3]}]:"

  # 式(をトークン(字句)に分解した配列)の構成
  fms = []  # fms:「式をトークンに分解した配列(fm)」からなる配列
  op = ['+', '-', '*', '/']
  op.each do |op1|
    op.each do |op2|
      op.each do |op3|
        fms << [a[0], op1, a[1], op2, a[2], op3, a[3]]
      end
    end
  end
  fms_str = fms  # 結果表示に使う

  # 計算と結果表示
  fms_rtnl = fms.map{ |fm| fm.map{ |tk|  # 整数の要素を分数に変換
    tk.instance_of?(Fixnum) ? Rational(tk, 1) : tk }}
  fms_rtnl.zip(fms_str).each do |fm_rtnl, fm_str|
    val = fm_to_val(fm_rtnl)
    if val == 10
      puts "#{fm_str.join(' ')} = #{val.to_i}"
    end
  end
end

# 式を解析して値を計算する
# fm:式をトークン(字句)に分解した配列
def fm_to_val(fm)
  begin  # エラーが出たらnilを返す(特に、ゼロ除算のとき)
    if not fm.instance_of?(Array)  # 配列でない
      fm
    elsif fm.size == 1  # 要素が1つだけ
      fm[0]
    elsif fm[1] == '+'
      fm[0] + fm_to_val(fm[2..-1])
    elsif fm[1] == '-'  
      # a - b を a + (-b) に変形
      fm[0] + fm_to_val(fm[3..-1].unshift(-fm[2]))
    elsif fm[1] == '*'
      fm_to_val(fm[3..-1].unshift(fm[0] * fm[2]))
    elsif fm[1] == '/'
      fm_to_val(fm[3..-1].unshift(fm[0] / fm[2]))
    else  # 文法エラー
      return
    end
  rescue
    return
  end
end

# ======================================

if __FILE__ == $0

ticket_number([1,3,4,3]); puts

end

ticket_numberメソッドが窓口となり、与えられた4つの数字から式を構成します。式の計算は、fm_to_valメソッドが担当します。

fm_to_valメソッドにおけるゼロ除算対策は、例外処理(begin~rescue~end)で行っています。エラーが出たらnilを返します。

たいていのプログラム言語では、整数どうしの割り算の結果は、小数点以下を切り捨てた整数か有限小数で返されます。これだと、切符番号の問題を解くにあたって、式の値が実際には10でないのにプログラム上は10とみなされることがあり、誤判定の原因になります。これを避けるため、数値を分数として扱います。RubyやCommon Lispには、分数(有理数型)が手軽に扱えるという利点があります。

次回へつづく。

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。