分数の発見 in Ruby DouKaku?

schemeにはrationalizeという手続きがありますが、これは結果を一つしか返しません。そして、複数の結果が欲しい場合も稀にあります。

そこで、非負の実数aが一つ与えられたときに、以下の条件を満たす分数b/cをaに近い順に全て表示する手続きを考えてみてください。条件は、 1. 分数b/cよりaに近い分数d/cは存在しない 2. 分数b/cは既約 3. cは1桁の整数です。

例をいくつかあげます(あってると思うけど...)。

a = 1.732051 12/7 7/4 16/9 5/3 9/5 3/2 2/1

a = 3.141593 22/7 25/8 19/6 28/9 16/5 13/4 3/1

a = 1920 / 1080 16/9 9/5 7/4 11/6 12/7 5/3 2/1

同じ値の分数かどうかを「入力との差が等しいかどうか」で判定しているので、入力の値によっては誤差が出るかも……

def rationalizes value
  # [入力との差, [分母, 分子]]からなる配列を作成する
  candidates = (1..9).map do |moderator|
    numerator  = (value*moderator).round
    difference = (value-numerator.quo(moderator)).abs
    [difference, [moderator, numerator]]
  end
  
  # 入力との差、分母の順に比較してソートすることで、
  # 入力との差が等しい場合には分母の小さい分数が先に並ぶ
  # その上で、差が等しい場合は最初の分数のみを選択することで、
  # 既約分数のみが返却される
  latest_difference = nil
  candidates.sort.inject([]) do |result, (difference, (moderator, numerator))|
    unless difference == latest_difference
      latest_difference = difference
      result << "#{numerator}/#{moderator}"
    end
    result
  end
end

p rationalizes(1.732051)      #=> ["12/7", "7/4", "16/9", "5/3", "9/5", "3/2", "2/1"]
p rationalizes(3.141593)      #=> ["22/7", "25/8", "19/6", "28/9", "16/5", "13/4", "3/1"]
p rationalizes(1920 / 1080.0) #=> ["16/9", "9/5", "7/4", "11/6", "12/7", "5/3", "2/1"]

「差が等しい」だと符号が違う値を同じ分数だとみなしてしまうので、値自体を比較に使用するように修正しました。

また、条件1には抵触しませんが「近い順に全て」という問いなので、「差が等しく」「分母が同じで」「分子が異なる」分数が検知できないのは間違いだと考えて修正しました。

※例えば0.7を入力した場合、分母が5の分数は4/5しか見つけられないが、3/5も4/5と同じだけ近いので検出されるべきではないか？　という話

def rationalizes value
  # [浮動小数点数, [分母, 分子]]からなる配列を作成する
  candidates = (1..9).inject([]) do |result, moderator|
    # 四捨五入すれば分母の近似値が求められるが、
    # .5の場合は両方を使用する
    numerator = value * moderator
    if numerator%1.0 == 0.5
      numerators = [numerator.floor, numerator.ceil]
    else
      numerators = [numerator.round]
    end
    
    numerators.each do |numerator|
      float = numerator.quo(moderator)
      result << [float, [moderator, numerator]]
    end
    result
  end
  
  # 入力との差、分母、分子の順に比較してソートすることで、
  # 入力との差が等しい場合には分母、分子の小さい分数が先に並ぶ
  candidates = candidates.sort_by do |float, fraction|
    [(value-float).abs, fraction]
  end
  
  # 浮動小数点数が等しい場合は最初の分数のみを選択することで、
  # 既約分数のみが返却される
  latest_float = nil
  candidates.inject([]) do |result, (float, (moderator, numerator))|
    unless float == latest_float
      latest_float = float
      result << "#{numerator}/#{moderator}"
    end
    result
  end
end

p rationalizes(1.732051)      #=> ["12/7", "7/4", "16/9", "5/3", "9/5", "3/2", "2/1"]
p rationalizes(3.141593)      #=> ["22/7", "25/8", "19/6", "28/9", "16/5", "13/4", "3/1"]
p rationalizes(1920 / 1080.0) #=> ["16/9", "9/5", "7/4", "11/6", "12/7", "5/3", "2/1"]

p rationalizes(0.7)           #=> ["5/7", "2/3", "3/4", "3/5", "4/5", "1/2", "1/1"]

DouKaku?

[topic] 分数の発見

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq