斐波那契数列

✍ dations ◷ 2024-09-20 09:46:05 #整数数列

斐波那契数列（意大利语：Successione di Fibonacci），又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列。

在数学上，斐波那契数列是以递归的方法来定义：

用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……（OEIS中的数列A000045）

特别指出：0不是第一项，而是第零项。

根据高德纳（Donald Ervin Knuth）的《计算机程序设计艺术》（），1150年印度数学家Gopala和金月在研究箱子包装对象长宽刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥那多（意大利人斐波那契Leonardo Fibonacci），他描述兔子生长的数目时用上了这数列:

假设在n月有兔子总共a对，n+1月总共有b对。在n+2月必定总共有a+b对：因为在n+2月的时候，前一月（n+1月）的b对兔子可以存留至第n+2月（在当月属于新诞生的兔子尚不能生育）。而新生育出的兔子对数等于所有在n月就已存在的a对

斐波纳契数也是帕斯卡三角形的每一条红色对角线上数字的和。

为求得斐波那契数列的一般表达式，可以借助线性代数的方法。高中的初等数学知识也能求出。

已知

设 $a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})$ = 时，

费波那西数列是费波那西n步数列步数为2的特殊情况，也和卢卡斯数列有关。

反费波那西数列的递归公式如下：

如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...

即是 $F_{2n+1}=G_{2n+1},F_{2n}=-G_{2n}$ $F_{{2n+1}}=G_{{2n+1}},F_{{2n}}=-G_{{2n}}$ 。

反费波那西数列两项之间的比会趋近 $-{\frac {1}{\varphi }}=-0.618$ $-{\frac {1}{\varphi }}=-0.618$ 。

费波那西数列可以用一个接一个的正方形来表现，巴都万数列则是用一个接一个的等边三角形来表现，它有 $P_{n}=P_{n-2}+P_{n-3}$ $P_{{n}}=P_{{n-2}}+P_{{n-3}}$ 的关系。

佩尔数列的递归公式为 $P_{n}=2P_{n-1}+P_{n-2}$ $P_{n}=2P_{n-1}+P_{n-2}$ ，前几项为0,1,2,5,12,29,70,169,408,...

1970年，尤里·马季亚谢维奇指出了偶角标的斐波那契函数

正是满足Julia Robison假设的丢番图函数，因而证明了希尔伯特第十问题是不可解的。

斐波那契数列中是否存在无穷多个素数？

在斐波那契数列中，有素数：2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……目前已知最大素数是第81839个斐波那契数，一共有17103位数。

JavaScript迭代版

function fib(n) {    var fib_n = function(curr, next, n) {        if (n == 0) {            return curr;        }        else {            return fib_n(next, curr+next, n-1);        }    }    return fib_n(0, 1, n);}alert(fib(40));

C语言通项公式版

#include <stdio.h>#include <math.h>int main(){    int n;    double constant_a = (1 + sqrt(5)) / 2;    double constant_b = (1 - sqrt(5)) / 2;    double constant_c = sqrt(5) / 5;    double value_1 = 0;    int value_2 = 0;    scanf("%d", &n);    if(n > 0)    {        for (int i = 0; i < n; i++)        {             value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));             value_2 = (int)value_1;             printf("%d\n", value_2);        }        return 0;    }    else    {        return -1;    }}

c++通项公式版

#include <iostream>#include <cmath>using namespace std;int main(){    unsigned long long n;    double ca = (1 + sqrt(5)) / 2;    double cb = (1 - sqrt(5)) / 2;    double cc = sqrt(5) / 5;    double v1 = 0;    double v2 = 0;    cout <<" ";    cin>>n;    if(n > 0)    {        for (unsigned long long i = 0; i < n; i++)    {            v1 = cc * (pow(ca, i) - pow(cb, i));        v2 = (int)v1;        cout <<v2<<endl;    }    return 0;    }    else    {        return -1;    }        cout <<'/b';}

# Fibonacci numbers moduledef fib(n): # write Fibonacci series up to n a, b = 0, 1 while b < n: print(b, end=' ') a, b = b, a+b print()def fib2(n): # return Fibonacci series up to n result = a, b = 0, 1 while b < n: result.append(b) a, b = b, a+b return result

(defun fibs (x) (cond ((equal x 0) 1) ((equal x 1) 1) (t (+ (fibs (- x 1)) (fibs (- x 2))))))(defun fibs (x) (do ((n 0 (+ n 1)) (i 1 j) (j 1 (+ i j))) ((equal n x) i)))

public int fibonacci(int n){ if(n<2){ return n; }else { int ans = new int; ans = 1; ans = 2; for(int i=2;i<n;i++) { ans=ans+ans; } return ans; }}

#include <stdio.h>#include <stdlib.h> int main(){ int n,s,L; printf("輸入長度"); scanf("%d",&L); while(L<0) { printf("錯誤"); return 0; } int a; int x=1,y=2; a=x; a=x; a=y; for(n=3;n<L;n++) { a=a+a; } for(n=0;n<L;n++) { printf("%d ",a); } system("pause"); return 0;}

斐波那契数列

相关