スポンサーサイト

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

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

切符番号の問題を解くRubyのプログラム例。前回のつづき。繰り返し(eachメソッド)の入れ子を再帰的処理で実現する方法について。

前回のプログラムにおける、eachメソッドによる繰り返しの入れ子の部分:

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

と同等の処理を、以下のようにして再帰的処理に置き換えます。そうすると、ソースコードがスッキリします。

#!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 = ['+', '-', '*', '/']
  nested_each([op, op, op]){ |op1, op2, op3|
    fms << [a[0], op1, a[1], op2, a[2], op3, a[3]]
  }
  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

# eachメソッドの入れ子を再帰的処理で行う
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

end

新たに導入したnested_eachメソッドによって、 eachメソッドによる繰り返しの入れ子を再帰的処理で実現しています。nested_eachメソッドは、入れ子の深さに関して再帰的に定義されています。

注意点として、メソッドの再帰呼び出しを行う際、引数elem_pairに渡すものに対して非破壊的メソッドを用いるべきだということがあります。具体的にいうと、「elem_pair + [elem]」のところを、例えば「elem_pair.concat([elem])」や「elem_pair.push(elem)」に置き換えると、再帰的処理がうまくいきません。

次回へつづく。

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

プロフィール

よしいず

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

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

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

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

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

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