Fibonacci数列基础

163 阅读 0 评论 108 点赞

我是靠谱客的博主火星上镜子，这篇文章主要介绍Fibonacci数列基础，现在分享给大家，希望可以做个参考。

问题描述

主要讲一下fibonacci数列的基础。

思路

斐波那契数列（Fibonacci sequence），又称黄金分割数列。指的是这样的一个数列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*）

显然，这是一个线性递推数列。可以用递推或者递归的办法解决。
看下面两道例题：

问题一： [ jobdu-1092 ]

题目描述：
The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55…} are defined by the recurrence:
F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
Write a program to calculate the Fibonacci Numbers.
输入：
Each case contains a number n and you are expected to calculate Fn.(0<=n<=30) 。
输出：
For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.
样例输入：
1
样例输出：
1

代码(1)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
long fib( int n ); // 递推
long fib1( int n ); // 递归
int main( void )
{
int n = 0;
while( std::cin >> n )
{
std::cout << fib( n ) << std::endl;
}
return 0;
}
long fib( int n )
{
if( n < 0 )
return -1;
else if(
!n )
return 0;
else if( 1==n )
return 1;
else
{
long f1 = 0;
long f2 = 1;
for( int i = 2; i <= n; ++i )
{
long t = f1 + f2;
f1 = f2;
f2 = t;
}
return f2;
}
}
long fib1( int n )
{
if( n < 0 )
return -1;
else if(
!n )
return 0;
else if( 1==n )
return 1;
else
return fib1( n - 2 ) + fib1( n - 1 );
}

再看一道比较基础的题目：
问题二：[jobdu-1075]

题目描述：
编写一个求斐波那契数列的递归函数，输入n值，使用该递归函数，输出如样例输出的斐波那契数列。
输入：
一个整型数n
输出：
题目可能有多组不同的测试数据，对于每组输入数据，
按题目的要求输出相应的斐波那契图形。
样例输入：
6
样例输出：
0
0 1 1
0 1 1 2 3
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34 55

代码(2)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
这个题的话，其实就是打印六行fib数列的值。
发现每一行打印 前2*i - 1项fib数列。
input:
输入n，行数
process:
1.循环：循环n次
1.1.打印前 2* i- 1项的fib数列
output:
*/
#include <iostream>
void print_fib( int n );
long fib( int n );
void print_fib1( int n );
int main()
{
int n = 0;
while( std::cin >> n )
{
for( int i = 1; i <= n; ++i )
{
print_fib( 2*i - 1 );
std::cout << std::endl;
}
}
return 0;
}
void print_fib( int n )
{
long f1 = 1;
long f2 = 1;
for( int i = 1; i <= n; ++i )
{
if(1 == i)
{
if( i != n )
std::cout << 0 << " ";
else
std::cout << 0;
}
else if( 2 == i || 3 == i )
{
if( i != n )
std::cout << 1 << " ";
else
std::cout << 1;
}
else
{
long t = f1 + f2;
f1 = f2;
f2 = t;
if( i != n )
std::cout << t << " " ;
else
std::cout << t;
}
}
}
long fib( int n )
{
if( n < 1 )
return -1;
else if( 1 == n )
return 0;
else if( 2 == n || 3 == n )
return 1;
else
return fib( n - 1 ) + fib( n - 2 );
}
void print_fib1( int n )
{
for( int i = 1; i <= n; ++i )
{
if( i != n )
std::cout << fib(i) << " ";
else
std::cout << fib(i);
}
}