递归操作

1
2
3

int Fib(int n){
 return n > 2 ? Fib(n - 1) + Fib(n - 2) : 1;
}

因为使用了递归，所以会出现重复计算。

更高效的方法是递推：

1
2
3
4

int Fib[2333333];
Fib[0] = 0,Fib[1] = 1;
for (int i = 2; i <= 2333333; i++)
Fib[i] = Fib[i - 1] + Fib[i - 2];

当然还有更高效的算法，但是我太弱了还不会。

观察数列的前几项:
1 1 2 3 5 8 13 21 34 55 89...
求相邻两项的商得到
1 0.5 0.67 0.6 0.625 0.61538 0.61904 0.617647 0.618181818 0.61797752808
取极限后相邻两项的商为黄金分割比，这个性质也可以根据通项公式得到
科普通项公式$f(n)=frac{1}{sqrt5}[(frac{1+sqrt5}{2})^n-(frac{1-sqrt5}{2})^n]$

每$3$个连续的斐波那契数有且只有一个被$2$整除，
每$4$个连续的斐波那契数有且只有一个被$3$整除，
每$5$个连续的斐波那契数有且只有一个被$5$整除，
每$6$个连续的斐波那契数有且只有一个被$8$整除，
每$7$个连续的斐波那契数有且只有一个被$13$整除，
……
每$n$个连续的斐波那契数有且只有一个被$f(n)$整除。

如图，每条斜线上的数之和构成了Fibonacci数列。
可以理解为把杨辉三角依次下降，将同一行的数字加起来

1
2
3
4
5
6
7

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

下降->

1
2
3
4
5
6
7
8
9

1           ------1
1           ------1 
1 1         ------2 
1 2         ------3
1 3 1       ------5  
1 4 3       ------8    
1 5 6 1     ------13   
1 6 10 4    ------21 
...................

即有$f(n)=C_{n-1}^0+C_{n-2}^1+…+C_{n-m-1}^m$

求两个数的最大公约数，用辗转相除法

1
2
3

int (int a, int b){
 return b ? gcd(b, a%b) : a;
}

最坏情况下，若$a$较小，需计算$n$次，则$a>f(n-1)$
虽然不怎么懂，但还是很神奇的样子

留给物理竞赛了

科学家发现，一些植物的花瓣、萼片、果实的数目以及排列的方式上，都有一个神奇的规律，它们都非常符合著名的斐波那契数列。例如：蓟，它们的头部几乎呈球状。在下图中，你可以看到两条不同方向的螺旋。我们可以数一下，顺时针旋转的（和左边那条旋转方向相同）螺旋一共有13条，而逆时针旋转的则有21条。此外还有菊花、向日葵、松果、菠萝等都是按这种方式生长的。


还有菠萝、松子等，也都符合这个特点，一般会出现34,55，89和144这几个数字。


Fibonacci Tree

斐波那契螺旋又称黄金螺旋，在自然界中广泛存在。如图是一个边长为斐波那契数列的正方形组成的矩形。
$f(1)^2+f(2)^2+…+f(n)^2=f(n)cdot f(n+1)$
贝壳螺旋轮廓线

是不是很神奇，这应该就是数学之美吧

世事洞明皆数学，留心处处是文章。