数组求斐波那契数列第n项

Question

如题所述

Answer 1

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

斐波那契数列指的是这样一个数列：

0、1、1、2、3、5、8、13、21、34……

有一组数列，它的第一项为1，第二项为1，从第三项开始，每一项为前两项之和。

斐波那契数列的第n项Fn可以通过如下的递归公式定义：

F(1)=1，F(2)=1,
F(n)=F(n-1)+F(n-2)（n ≥ 3，n ∈ N*）

通项公式


如上，又称为“比内公式”，是用无理数表示有理数的一个范例。

注：此时a1=1，a2=1，a(n)=a(n-1)+a(n-2)，（n ≥ 3，n ∈ N*）

求第n项斐波那契数
现在写一个函数int fib(int n) 返回第n项Fn。例如，若n=0，则函数fib(0)应该返回0，若n=1, 则函数fib(1)应返回1，若 n > 1，返回 F(n-1)+F(n-2)。

若n = 9
输出：34

下面是返回斐波那契数列第n项Fn的不同方法：

方法1 (使用递归)

一个简捷的方法是直接使用递归定义关系式写出递归实现的代码，C/C++代码如下：

//Fibonacci Series using Recursion
#include<stdio.h>
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}

int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}
输出：34
时间复杂度：T(n) = T(n-1) + T(n-2)，该时间复杂度是指数级别的
空间复杂度：如果考虑递归调用时栈的大小，则为O(n) ；如果不考虑调用栈的话，则为O(1)

通过观察，我们可以发现递归求解时做了很多重复的工作(见下面的递归调用树)。因此采用递归方式求解斐波那契数列的第n项Fn不是一种好的方法。

Answer 2

斐波那契数列，又称黄金分割数列、因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。平方与前后项
从第二项开始，每个偶数项的平方都比前后两项之积多1，每个奇数项的平方都比前后两项之积少1。
如：第二项 1 的平方比它的前一项 1 和它的后一项 2 的积 2 少 1，第三项 2 的平方比它的前一项 1 和它的后一项 3 的积 3 多 1。
（注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如从数列第二项 1 开始数，第 4 项 5 是奇数，但它是偶数项，如果认为 5 是奇数项，那就误解题意，怎么都说不通）
证明经计算可得：
与集合子集
斐波那契数列的第n+2项同时也代表了集合
中所有不包含相邻正整数的子集个数。

Answer 3

#include
using namespace std;
int main()
{
int n,i,f[21]={0,0,1},sum=0;
cout<<"请输入一个小于20的数：";
cin>>n;
for(i=3;i<=n;i++)
f[i]=f[i-1]+f[i-2];
for(i=1;i<=n;i++)
sum=sum+f[i];
cout<<"第"<
return 0;
}