Haskell 检查数字是否来自斐波那契数列

Question

我是 Haskell 初学者。上次我学习了斐波那契数列，所以我可以创建斐波那契数列。现在我想知道如何编写一个函数来检查数字是否属于 Fib 序列。

我的意思是功能:

belongToFib :: Int -> Bool

我真的不需要代码。一些如何处理这个问题的提示就足够了。提前致谢。

Answer 1

我将为您提供一些涉及惰性求值的解决方案的提示:

1. 定义所有斐波那契数列。
2. 检查您输入的数字是否属于该序列。

这些是您需要定义的两件事的签名:

fib :: [Int]
belongToFib :: Int -> Bool

当然，您需要一些技巧才能完成这项工作。即使你的列表有一个(理论上)无限的数字序列，如果你确保只需要处理有限的子序列，由于它的惰性，Haskell 将只生成严格需要的部分，并且你的函数不会永远循环。因此，在检查您的号码的 fib 成员资格时，请确保在某个时刻返回 False。

另一种可能的解决方案是尝试找出您的数字是否在斐波那契数列中，而不实际将其生成到输入，而是仅依靠算术。作为对此的提示，请查看 this thread .

关于Wikipedia您会发现许多其他方法来检查斐波那契数列的成员资格。

编辑:顺便说一句，请注意 Int 的溢出。您可能希望切换到Integer。