斐波那契数列（Fibonacci sequence）
前言： 斐波那契数列是最基础最常见的了，但是隔很久不仅是对语言，对这个也开始生疏了。这里做一次复习并用几种常用语言来实现。
又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1,F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。——摘自《百度百科》
第一种方法使用的是经典的递归算法
最后的结果为：
1 1 2 3 5 8 13 21 34
go 实现
package main
import . "fmt"
func fibonacci(n int) int {
if n < 2 {
return n
}
return fibonacci(n-2) + fibonacci(n-1)
}
func main() {
var i int
for i = 0; i < 10; i++ {
Printf("%d\t", fibonacci(i))
}
}
使用闭包，匿名函数作为返回值的算法实现。
package main
import . "log"
func main() {
f := fibonacci()
var i int
for i = 1; i < 10; i++ {
Printf("NO.%d = %d\t", i, f())
}
}
func fibonacci() func() int {
x, y := 0, 1
return func() int {
y = x + y
return y
}
}
python 实现
递推法：
def fibonacci(i):
if i == 1 or i == 2:
return 1
return fibonacci(i-2) + fibonacci(i-1)
for i in range(1, 10):
print(fibonacci(i), end=' ')
下面利用闭包，但这种方法每次都需要计算一项斐波那契数列的值，所以他的时间复杂度是 O(n)。
def fibonacci():
x, y = 0, 1
def sum():
nonlocal x, y
temp = x + y
x, y = y, temp
return temp
return sum
fib = fibonacci()
for i in range(1, 10):
print(fib(), end=' ')
学习一下：矩阵乘法是一种预处理斐波那契数列的方法，它可以在 O(log n) 的时间内计算任意项的值。
def matrix_multiply(a, b):
c = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
for k in range(2):
c[i][j] += a[i][k] * b[k][j]
return c
def matrix_power(matrix, n):
if n == 1:
return matrix
elif n % 2 == 0:
return matrix_power(matrix_multiply(matrix, matrix), n//2)
else:
return matrix_multiply(matrix, matrix_power(matrix, n-1))
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
matrix = [[1, 1], [1, 0]]
result = matrix_power(matrix, n-1)
return result[0][0]
for i in range(10):
print(fibonacci(i), end=' ')
解释：
首先定义了一个函数 matrix_multiply接受两个 2x2 的矩阵作为参数，并返回它们的乘积。定义了一个 2x2 的矩阵 c，值初始化为 0。然后使用三层循环来遍历每一个元素。其中，第一层循环遍历矩阵 a 和 c 的行，第二层循环遍历矩阵 b 的列，第三层循环遍历矩阵 a 的列和矩阵 b 的行。每次循环将矩阵 a 和 b 的对应元素相乘，并将结果累加到矩阵 c 的对应元素上。最后，返回矩阵 c。
还定义了一个函数 matrix_power，它接受一个 2x2 的矩阵和一个整数 n 作为参数，并返回矩阵的 n 次方。
其他语言的基本实现：
Java 实现
package com.study.bk;
public class Fibonacci {
public static int fibonacci(int i) {
if (i == 1 || i == 2) {
return 1;
}
return fibonacci(i-2) + fibonacci(i-1);
}
public static void main(String[] args) {
for (int i = 1; i < 10; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}
C 实现
#include "stdio.h"
int fibonacci(int i){
if (i == 1 || i == 2)
return 1;
return fibonacci(i-2) + fibonacci(i-1);
}
int main(){
for (int i = 1; i < 10; i++){
printf("%d ", fibonacci(i));
}
return 0;
}