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

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会继续枚举列表寻找下一个候选人，只有 return 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)

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

How to find out if a number is in the Fibonacci Sequence

haskell

list

fibonacci