3

我有一个任务要编写一个方法来确定一个数字是否是斐波那契数列的一部分。

配合公式：

正整数 z 是斐波那契数当且仅当 5z^2 + 4 或 5z^2 - 4 之一是完美平方

我定义了以下适用于小数和大斐波那契数的方法，但是，无论出于何种原因，我的分配规范在处理大的非斐波那契数时会抛出错误，特别是在运行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

8

如其他地方所述，问题在于浮点数的精度。 BigDecimal提供任意精度的算术：

require 'bigdecimal'

def is_fibonacci?(i)
  i = BigDecimal.new(i)
  bigNumber1 = (5*(i**2)+4).sqrt(0)
  bigNumber2 = (5*(i**2)-4).sqrt(0)
  return (bigNumber1 == bigNumber1.round || bigNumber2 == bigNumber2.round)
end

is_fibonacci? 927372692193078999171 # => false
is_fibonacci? 927372692193078999176 # => true
于 2013-05-14T18:03:23.643 回答
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

比奈公式需要计算平方根。这是我使用内置 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

此外，还有一种方法可以在不使用 Binet 的情况下进行计算，如Kenneth's memoization by Hash所示。所以你可以通过 has_value?(number) 的内置方法来检查一个数字。

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 回答