3

数値がフィボナッチ数列の一部であるかどうかを判断するメソッドを作成する割り当てがあります。

式に従ってください：

5z^2 + 4 または 5z^2 − 4 のいずれかが完全平方である場合に限り、正の整数 z はフィボナッチ数です。

小さい数と大きいフィボナッチ数で機能する次のメソッドを定義しましたが、なんらかの理由で、大きな非フィボナッチ数を処理するとき、特にis_fibonacci?(927372692193078999171). どうやらメソッドはtrueの代わりに戻りますfalse。他のすべては正しいように見えるので、なぜこれがうまくいかないのか、ちょっと頭を悩ませています。助言がありますか？

def is_fibonacci?(i)
  bigNumber1 = Math.sqrt((5*(i**2)+4))
  bigNumber2 = Math.sqrt((5*(i**2)-4))
  if bigNumber1 == bigNumber1.round || bigNumber2 == bigNumber2.round
    return true
  else 
    return false
  end
end
4

4 に答える 4

3

問題は、Math.sqrt通常は実際の平方根の推定にすぎない浮動小数点値を返すことです。大きな数の場合、コードでは常に整数と見なされる 1234567600000.0 のようなものを取得します。

独自の任意精度の整数平方根関数を実装します。単純なアプローチは次のようになります。

def is_fibonacci?(i)
  n1 = 5 * i**2 + 4
  n2 = n1 - 8
  is_square?(n1) or is_square?(n2)
end

# find floor(sqrt(i)) by nesting intervals
def sqrt(i)
  a, b = 0, i
  while a + 1 < b
    m = (a + b) / 2
    if m**2 > i
      b = m
    else
      a = m
    end
  end
  a
end

def is_square?(i)
  s = sqrt(i)
  s ** 2 == i
end
于 2013-05-14T17:33:08.087 に答える
0

Binet の式は平方根の計算が必要です。これは、平方根をチェックするための組み込みの Bignum および Newton のメソッドを使用した私のソリューションです。

def isSQRT(x)
  return true if [0,1,4,9,16,25,36,49,64,81,100].include?x
  z = x / 10  #first guess
  z=z-(z*z-x)/(2*z) while (z-1)**2 > x
  return true if (z-1)**2 == x
  false
end

def is_fibonacci?(num)
  isSQRT(5*num**2+4) || isSQRT(5*num**2-4)
end

また、ケネスの Hash によるメモ化法で示されているように、Binet を使用せずに把握する方法もあります。したがって、組み込みメソッドの has_value?(数値) で数値を確認できます。

fibo = Hash.new{ |h,k| h[k] = ( k<=2 ? 1 : h[k-2] + h[k-1] ) }
fibo[500] #=> instant result of Fibonacci!
于 2015-01-24T21:01:36.447 に答える
0

これは、Ruby のコア API メソッドのみで問題なく動作するものです。ブール値を返します

def fibonacci?(number_sought)
  num = 2
  result = [1, 1]  until num >= number_sought
    result << result[-1] + result[-2]
    if result.include?(number_sought) then break 
    elsif result[-1] > number_sought then return false
    else next
    end
    num += 1
  end
  !!result
end

p fibonacci?(10946)
p fibonacci?(927372692193078999176)

配列を返したい場合：

def fibonacci(number_sought)
  num = 2
  result = [1, 1]  until num >= number_sought
    result << result[-1] + result[-2]
    if result.include?(number_sought) then break 
    elsif result[-1] > number_sought then return result
    else next
    end
    num += 1
  end
  result
end
于 2021-04-22T15:09:43.270 に答える