一、斐波那契数列
斐波那契数列（Fibonacci Sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例而引入的。它指的是这样一个数列
如果设an为该数列的第n项（n∈N*），那么上面数列可以归结为：an=an-1+an-2显然这是一个线性递推数列。
二、代码实现
问题：现在要求输入一个整数n，如何获取斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
C
int Fibonacci(int n ) { // write code here
if(n <= 1) return n;
int i = 2, a = 0, b = 1, c;
while(i++ <= n){ c = a+b; a = b; b = c; }
return c;
}
C++
class Solution {
public:
int Fib(vector<int> &dp,int n){
if(n<2) return n;
else if(dp[n]!=-1) return dp[n];
return dp[n]=Fib(dp,n-1)+Fib(dp,n-2);
}
int Fibonacci(int n) {
vector<int> dp(n+1,-1);
return Fib(dp,n);
}
};
Java
public class Solution {
public int Fibonacci(int n) {
int a=1;
int b=1;
int c=1;
if(n==0){
return 0;
}
if(n<3){
return 1;
}
for(int i=2;i<=n;i++){
b=c;
a=c-a;
c=a+b;
}
return c;
}
}
Python
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.listArray = [0,1]
def Fibonacci(self, n):
# write code here
if n <= 1:
return self.listArray[n]
for i in range(2,n+1):
self.listArray.append(self.listArray[i-1]+self.listArray[i-2])
return self.listArray[n]
PHP
<?php
function Fibonacci($n)
{
// write code here
$dp[0] = 0;
$dp[1] = 1;
for ($i=2;$i<=$n;$i++) {
$dp[$i] = $dp[$i-1]+$dp[$i-2];
}
return $dp[$n];
}
JS
function Fibonacci(n)
{
// write code here
if(n<=1){
return n;
}
let pre1=0;
let pre2=1;
let temp;
for(let i=2;i<n;i++){
temp=pre2;
pre2=pre2+pre1;
pre1=temp;
}
return pre1+pre2;
}
module.exports = {
Fibonacci : Fibonacci
};
GO
package main
/**
*
* @param n int整型
* @return int整型
*/
func Fibonacci( n int ) int {
// write code here
a, b := 0, 1
for i := 0; i < n; i++ {
a, b = b, a + b
}
return a
}
三、斐波那契数列的应用
1、斐波那契堆
斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质，可以进行插入、查找、合并和删除等操作。
插入：创建一个仅包含一个节点的新的斐波纳契堆，然后执行堆合并。
查找：由于用指针指向了具有最小值的节点，因此查找最小值的节点时间复杂度为O(1)。
合并：合并两个斐波纳契堆的根表。即把两个斐波纳契堆的所有树的根首尾相接。
删除：（释放）最小节点。
2、氢原子能级问题
假设有一些氢气原子，每个电子最初所处位置为稳定态（0能级），电子每获得1个能量可以使它上升1个能级，每释放1个能量可以下降1个能级。假设电子最初在第2能级，它释放能量后可以到第1能级或第0能级。那么，电子现在所处的能级可能情形是：1、2、3、5、8、13、21…种。这是斐波那契数列的一部分。
3、植物的生长
科学家发现，一些植物的花瓣、叶片、果实的数目以及排列的方式上，都有一个神奇的规律，它们都非常符合著名的斐波那契数列。比如百合花和蝴蝶花是3个花瓣;梅花、山桃花、苹果花、山茶花、木槿花都是5个花瓣;翠雀花8个花瓣;金盏、玫瑰13个花瓣;而紫宛有21个花瓣。如下图是木槿花，有5个花瓣，末端的花蕊也是5个。
xDroid——让安卓应用运行在Linux平台上
转载：https://blog.csdn.net/xDroid_linzhuo/article/details/115503664