Fibonacci Seq.奇怪的输出形式(Haskell)

Question

当我在数字的输入中意识到一些"奇怪的"形式时,我正在观察我在Haskell中的Fibobacci序列实现的结果.

首先,这是我提出的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这样的东西,而数字非常大,所有...我看到的是由","形成的一些奇怪的elipses,从列表中的每个Integer之间打印出来,例如:

例1

所以我最大化了输出窗口的大小,看看这个奇怪的模式是否仍会重复,答案是肯定的:

例题

我的问题是:

有人知道为什么在列表中的整数之间的","中出现这种模式？难道不应该更随机而不是像elipses一样吗？

Answer 1

斐波那契数成长为一个指数函数的ñ.

十进制数的长度基本上是其对数基数10.因此,斐波那契的长度增长为n的线性函数,因为对数和指数相互抵消.

因此,如果您将它们打印在一列中,您会看到一条直线.但是你要一个接一个地打印它们,所以这些位置会累积起来.如果您正在获取线性序列的累积和,则会得到二次序列.

在本地,每一行包含大约相同数量的斐波纳契数,我们称之为k.这意味着两件事:

1. 行号随n线性变化.
2. 要计算逗号的实际位置(相对于窗口的左边缘),我们需要将累积"绝对位置"的剩余部分取为行长度的模数.这相当于(平均而言)每n的每个增量减去1/k.此调整是线性的,不会改变位置的二次行为.

所以你所看到的是抛物线 - 二次函数图.