13

当我在数字的 optput 中意识到一些“奇怪”的形式时，我正在观看我在 Haskell 中的斐波巴契序列实现的结果。

首先，这是我想出的 Haskell 代码： 

fib :: Integer -> [Integer]
fib 0 = [0]
fib 1 = [0, 1]
fib a = (fib' 0 1 [0,1] 1 a)

fib' :: Integer -> Integer -> [Integer] -> Integer -> Integer -> [Integer]
fib' n1 n2 l cont n 
        | cont == n = l
        | otherwise = (fib' n2 n3 (l++[n3]) (cont+1) n)
             where n3 = n2 + n1

对于像 fib 10 这样的输出将是：[0,1,1,2,3,5,8,13,21,34,55] 然后我想尝试像 fib 1000 这样的数字，而数字非常大而且所有...我看到的是由“，”形成的一些奇怪的省略号，这些省略号在列表中的每个整数之间打印出来，例如：

示例1

所以我已经最大化了输出窗口的大小，看看这个奇怪的模式是否还会重复，答案是肯定的：

示例2

我的问题是：

有谁知道为什么在列表中的整数之间的“，”中出现这种模式？它不应该更随机，更不像省略号吗？

4

2 回答 2

21

斐波那契数作为n的指数函数增长。

十进制数的长度本质上是它的以 10 为底的对数。因此，斐波那契的长度像n的线性函数一样增长，因为对数和指数相互抵消。

因此，如果您将它们打印在一列中，您会看到一条直线。但是您一个接一个地打印它们，因此位置会累积。如果您正在获取线性序列的累积和，则会得到一个二次序列。

在本地，每一行都包含大约相同数量的斐波那契数，我们称之为k。这意味着两件事：

  1. 行号随n线性变化。
  2. 为了计算逗号的实际位置（相对于窗口的左边缘），我们需要将累积的“绝对位置”的余数取模行长度。这相当于（平均）每增加一次n减去1/k。这种调整是线性的，不会改变位置的二次行为。

所以你看到的是抛物线——二次函数的图形。

于 2013-05-26T18:12:53.147 回答
3

当你想到它时，没有什么奇怪的。相邻的斐波那契数具有相似的长度，并且长度随着序列的增加而增加。因此，假设您的屏幕大小为 30 个字符，并且当前F(n)有 29 个数字，那么对于接下来的几个数字，长度可能是：

29, 29, 29, 30, 30, 30, 31, 31, 31

这给了你左 -> 稳定 -> 右运动。

于 2013-05-26T18:05:09.667 回答