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

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

问题是 n 是一个 Int 而 fibList 是一个 [Int]，你不能检查 Int 和 [Int] 是否相同，因为它们具有不同的类型。

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

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

isFib :: Int -> [Int] -> Bool
isFib _ [] = False
isFib n (x:xs)
    | x >= n = -- ...  🖘 to implement
    | otherwise = isFib n xs

我将填写 ... 部分作为练习。

您的 fib 函数效率不高:需要指数时间来确定第 n 个元素。您可以通过递归生成斐波那契数列，并检查我们生成的其中一项是否确实是斐波那契数列:

isFib :: Int -> Bool
isFib n = go 0 1
  where go f1 f2
          | f1 >= n = …
          | otherwise = go f2 (f1 + f2)