スポンサーサイト

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

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

切符番号の問題を解くRubyのプログラム例。前回のつづき。

今回は、括弧の使用に対応したプログラムの例です。

以下が、実行結果です:

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

[1, 1, 9, 9], option = 1:
( 1 + ( 1 / 9 ) ) * 9 = 10

オプションを指定することで、括弧の使用/不使用の切り替えができます。option = 1のとき、括弧を使用します。

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

#!ruby -Ks

require "rational"  # Ruby 1.9では不要

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

  # 式(をトークン(字句)に分解した配列)の構成
  fms = []  # fms:「式をトークンに分解した配列(fm)」からなる配列
  op = ['+', '-', '*', '/']
  case option
  when 0  # 括弧不使用、数字の並べ替えなし
    nested_each([op, op, op]){ |op1, op2, op3|
      fms << [a[0], op1, a[1], op2, a[2], op3, a[3]]
    }
  when 1  # 括弧使用
    nested_each([op, op, op]){ |op1, op2, op3|
      fms.push(  # 括弧づけは全部で5パターン
        ['(', '(', a[0], op1, a[1], ')', op2, a[2], ')', op3, a[3]],
        ['(', a[0], op1, '(', a[1], op2, a[2], ')', ')', op3, a[3]],
        ['(', a[0], op1, a[1], ')', op2, '(', a[2], op3, a[3], ')'],
        [a[0], op1, '(', '(', a[1], op2, a[2], ')', op3, a[3], ')'],
        [a[0], op1, '(', a[1], op2, '(', a[2], op3, a[3], ')', ')']
      )
    }
  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[0] == '('  # 括弧の処理
      prn_dpt = 1  # 括弧の深さ
      end_idx = 0  # 対応する')'の位置
      1.upto(fm.size) do |i|
        case fm[i]
        when ')'
          prn_dpt -= 1
          next if prn_dpt > 0
          end_idx = i  # 対応する')'の位置をセットして
          break        # ループを抜ける
        when '('
          prn_dpt += 1
          next
        else
          next
        end
      end
      return if end_idx == 0  # 文法エラー:'('に対応する')'がない
      fm_to_val(fm[end_idx+1..-1].unshift(fm_to_val(fm[1..end_idx-1])))
    elsif fm[0] == ')'  # 文法エラー:')'に対応する'('がない
        return
    elsif fm[1] == '+'
      fm[0] + fm_to_val(fm[2..-1])
    elsif fm[1] == '-'  
      if fm[2] == '('
        fm[0] - fm_to_val(fm[2..-1])
      else  
        # a - b を a + (-b) に変形
        fm[0] + fm_to_val(fm[3..-1].unshift(-fm[2]))
      end
    elsif fm[1] == '*'
      if fm[2] == '('
        fm[0] * fm_to_val(fm[2..-1])
      else
        fm_to_val(fm[3..-1].unshift(fm[0] * fm[2]))
      end
    elsif fm[1] == '/'
      if fm[2] == '('
        fm[0] / fm_to_val(fm[2..-1])
      else
        fm_to_val(fm[3..-1].unshift(fm[0] / fm[2]))
      end
    else  # 文法エラー
      return
    end
  rescue
    return
  end
end

# 繰り返しの入れ子を再帰的処理で行う
def nested_each(arys, depth=arys.size, elem_pair=[], &proc)
  if depth == 0
    proc.call(elem_pair)
  else
    arys[depth-1].each{ |elem|
      nested_each(arys, depth - 1, elem_pair + [elem], &proc)
    }
  end
end

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

if __FILE__ == $0

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

end

前回からの主な変更点は、fm_to_valメソッドの丸括弧「(, )」の処理への対応です。あと、ticket_numberメソッドにoptionという引数を一つ増やし、その値を指定することで括弧の使用/不使用を切り替えられるようにしました。

二項演算の順序を指定する括弧を付ける部分について、上のプログラムでは

fms.push(  # 括弧づけは全部で5パターン
  ['(', '(', a[0], op1, a[1], ')', op2, a[2], ')', op3, a[3]],
  ['(', a[0], op1, '(', a[1], op2, a[2], ')', ')', op3, a[3]],
  ['(', a[0], op1, a[1], ')', op2, '(', a[2], op3, a[3], ')'],
  [a[0], op1, '(', '(', a[1], op2, a[2], ')', op3, a[3], ')'],
  [a[0], op1, '(', a[1], op2, '(', a[2], op3, a[3], ')', ')']
)

のように全パターンを書くという方法をとりました。[a[0], op1, a[1], op2, a[2], op3, a[3]]に対して括弧付けの全パターンを返すメソッドについては、以下の記事に書きました:

二項演算の順序を指定する括弧の付け方を列挙するRubyプログラム

次回へつづく。

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

プロフィール

よしいず

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

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

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

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

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

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