如何判断一个数字是否在斐波那契数列中

Question

我创建了一个函数，可以给出给定输入的斐波那契数列。我现在想创建一个函数来检查给定的数字是否在斐波那契数列中。

这是我到目前为止所做的：

-- Basic Fib Function 
fib :: Int -> Int 
fib x =
  if x < 1
    then 0
    else if x < 2
           then 1
           else fib (x - 1) + fib (x - 2)

-- Outputs list of all the functions 
fibList :: [Int]
fibList  = map fib [1..]
--  function that takes an Integer, and returns True if the argument is a Fibonacci number and False otherwise
isFib :: Int -> [Int] -> Bool
isFib n fibList
    |n `elem` fibList = True
    |otherwise = False

fibList有效，但计算需要很长时间。另外，我已经这样做了：

fibList' :: [Int]
fibList'  = map fib [1..100]

isFib' :: Int -> [Int] -> Bool
isFib' n fibList'
    |n `elem` fibList' = True
    |otherwise = False

数字较小时，计算时间仍然较长

GHCI

Answer 1

问题是nis anInt和fibListis an [Int]，您无法检查 anInt和[Int]是否相同，因为它们具有不同的类型。

\n

elem如果给定的数字不是斐波那契数，则使用也会失败，因为 Haskell 将继续枚举列表以查找下一个候选者，并且仅False在到达列表末尾时才返回，但如果生成无限列表，则这永远不会结束。

\n

您可以实现isFib检查列表的第一项是否大于的函数n。如果是这种情况，我们知道所有剩余元素都会更大，因此我们可以停止搜索：

\n

isFib :: Int -> [Int] -> Bool\nisFib _ [] = False\nisFib n (x:xs)\n    | x >= n = -- ...