如何使用 C++ 示例实现斐波那契数算法

Fibonacci 是一位意大利数学家，他将这门学科引入了欧洲数学，但在他那个时代之前就已经提到了类似的数组。

Fibonacci 数有两种定义，略有变化。两者非常相似，但同时几乎没有什么不同。

第一：
0, 1, 1, 2, 3, 5, 8, ...

第二：
1, 1, 2, 3, 5, 8, ...

如果仔细观察上面的序列，每个数字都被构造为前两个数字的总和。前两个数字是：零和一（或一和一）。

对于本文，我们将使用第一个定义。

Fibonacci(0) = 0,
Fibonacci(1) = 1,
Fibonacci(2) = Fibonacci(0) + Fibonacci(1) = 0 + 1 = 1
Fibonacci(3) = Fibonacci(1) + Fibonacci(2) = 1 + 1 = 2
Fibonacci(4) = Fibonacci(2) + Fibonacci(3) = 1 + 2 = 3
…
Fibonacci(n) = Fibonacci(n-2) + Fibonacci(n-1)。

斐波那契数的实现

有很多方法可以创建斐波那契数组，但我将展示两种最常见的方法。

第一种方法是使用递归实现。为此，您应该发现该模式并将其应用到如下所示的函数中。

long long 
FibonacciElement( long long n)
{
  if (n==0) return 0;
  if (n==1) return 1;
  return FibonacciElement(n-2) + FibonacciElement(n-1);  
}

现在，我强烈建议您采用 Fibonacci 数列的第 8 个元素，并在教科书或适合该任务的某些程序中使用二叉树结构计算它。

当你分析它时，你应该注意到有些元素被计算了几次，这是这种方法会更慢的原因之一，如果你使用内置记忆的编译器可以解决这个问题，有时你需要使用一些调整。

第二种方法不会使用如下所示的函数的自调用：

long long
FibonacciElement2( long long n)
{
   long long Previous   = 0,
             PPrevious  = 1;

long long i=2, Curent;
while( i <= n)
{
	Curent      = PPrevious + Previous;
	PPrevious = Previous;
	Previous   = Curent;
	++i;
}

	return Curent;
}

递归实现通常比那些没有自调用函数的要慢。

#include <iostream>

using namespace std;

long long FibonacciElement1(long long);
long long FibonacciElement2(long long);

int
main(void)
{
	cout<<"Calculate Fibonacci element"<<endl
		<<"enter the n -";
        long long int lliN; cin>>lliN;

	cout<<"With recursion F(n)    ="<<FibonacciElement1(lliN)<<endl
	    <<"Iterative solution F(n)="<<FibonacciElement2(lliN)<<endl;

	int iRespond; cin>>iRespond;

	return EXIT_SUCCESS;
}

long long 
FibonacciElement1( long long n)
{
  if (n==0) return 0;
  if (n==1) return 1;
  return FibonacciElement1(n-2) + FibonacciElement1(n-1);  
}

long long
FibonacciElement2( long long n)
{
   long long Previous   = 0,
             PPrevious  = 1;

if( n==0) return 0;
if( n==1) return 1;

long long i=1, Curent;
while( i <= n)
{
	Curent      = PPrevious + Previous;
	PPrevious   = Previous;
	Previous    = Curent;
++i;
}
return Curent;
}

我们已经讨论了斐波那契数是什么，并且我们已经看到了两种计算它们的方法。

我建议您通过深入研究来进一步研究这个主题。该算法也有一些实际应用。