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

通过科西卡·杜斯科（Koscica Dusko）上 2014年3月6日

斐波那契（Fibonacci）是一位意大利数学家，他将这一学科介绍给了欧洲数学，但是甚至在他上任之前就提到过类似的系列。

斐波那契数有两个定义，但有微小的变化。两者非常相似，但几乎没有什么不同。

第一：
0、1、1、2、3、5、8…

第二：
1，1，2，3，5，8，…

如果您仔细查看上述序列，则每个数字都将被构造为前两个数字的总和。前两个数字为：零和一（或一和一）。

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

斐波那契（0）= 0，
斐波那契（1）= 1
斐波那契（2）=斐波那契（0）+斐波那契（1）= 0 +1 = 1
斐波那契（3）=斐波那契（1）+斐波那契（2）= 1 +1 = 2
斐波那契（4）=斐波那契（2）+斐波那契（3）= 1 + 2 = 3
…
斐波那契（n）=斐波那契（n-2）+斐波那契（n-1）。

斐波那契数的实现

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

第一种方法是使用递归实现。为此，您应该发现图案并将其应用于功能，如下所示。

long long 
FibonacciElement( long long n)
{
  如果（n == 0）返回0;
  如果（n == 1）返回1;
  return FibonacciElement(n-2) + FibonacciElement(n-1);  
}

现在，我强烈建议您采用斐波那契数列的第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)
{
  如果（n == 0）返回0;
  如果（n == 1）返回1;
  返回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;
}

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

我建议您通过更深入地研究对该主题进行进一步研究。该算法也有实际应用。

其他练习：

创建并显示前n个斐波那契数，分别使用第一个和第二个定义。
显示第n个斐波那契数：以二进制形式，十六进制形式和八进制形式显示。
用n个斐波那契数创建向量。
构造类似于Fibonacci数组的数组，但使用：a和b作为前两个数字。
形成类似于Fibonacci数组的序列，其中树的第一个元素等于：1、1和1。
具有一些近似公式的第n个斐波那契数，如果您可以自己创建一个，那会更好。
查找前n个斐波纳契数的总和。

> 添加您的评论

如果您喜欢这篇文章，您可能还会喜欢..

标记为：斐波那契C代码, 斐波那契C递归, 斐波那契数列算法, 斐波那契序列C程序

{ 22 评论 … 加一 }

基芬 2014年3月7日，上午4:48

哇，肯定有很多这样简单的算法代码。例如，在Ruby中，可以将以下相同的代码替换为上面相同的代码：

f =- >(x){ x 8

所以我’d说，尽管C / C ++对很多事情都有好处，但这绝对不是其中之一。

链接
赛博纳德 2014年3月7日，上午7:25

问题不在于如何实施它，而是它提供了哪些实际和/或有用的现实生活收益？似乎是在浪费时间。

链接
咯咯笑的 2014年3月7日，上午10:24

@cybernard

看到这里 ’ll

http://en.wikipedia.org/wiki/Fibonacci_number#Applications

链接
丹尼斯·盖兹米斯 2014年3月7日，上午10:44

赛博纳德你对主题太错了。只是谷歌“自然界中的斐波那契数”看看它在您旁边有什么好处，以及您有多错误。

链接
西雅图C ++ 2014年3月7日，上午11:43

斐波那契数列的增长速度约为n平方，但它却没有’不需要任何乘法来计算。它’因此，s在加法为fas且乘法速度较慢的小型或低功耗处理器中很有用。它的许多事情之一’有助于在通信中实现指数退避和重试。在正常使用中，您已经知道fibonacci（n-1）和fibonacci（n-2），就可以计算出fibonacci（n）。该计算仅需要一次加法。

斐波那契数列是数学中那些晦涩难懂的角落之一，您可以一生都不知道，但一旦知道，便会一遍又一遍地使用它。

C ++样式说明

The Fibonacci sequence is 上 ly defined over positive integers. The argument to FibonacciElement1() should be 未签名. As coded, FobonacciElement1() will run away dangerously for any negative value of n.

您的计算机不足以针对n的较大值递归计算斐波那契数列，因为堆栈上将具有n个堆栈帧。对于较大的n值，即使迭代计算也将花费很长时间。我建议使用类型为参数的FibonacciElement1（）进行编码“unsigned”, which is “unsigned int”。由于fibonacci（n）大约等于n的平方，因此您必须决定是否要对大n运行此代码。如果这样做，则结果类型的位数必须约为参数类型的两倍。如上所述，由于这是不可行的，因此’合理的返回“unsigned” as well.

这里’是更安全的修订版本。请注意，递归版本仍然效率低下。您可以将FibonacciElement2（）重新编码为练习:-)。

未签名
FibonacciElement1a（无符号n）
{
如果（n == 0）返回0;
如果（n == 1）返回1;
返回FibonacciElement1（n-2）+ FibonacciElement1（n-1）;
}

链接
黄昏科西嘉 2014年3月7日，下午1:29

@cybernard ，恩，您的发言非常含糊，我只是不知道’没有足够的信息可以得出任何结论。当你说“waist of time”这就像让我感到奇怪的事情！

@Deniz Gezmis，您真的很明白这件事，只需阅读文章，然后进行练习，如果您想与他人进行一些有趣的交流。

@Seattle C ++，您有很多知识，并且对细节了解敏锐。辛苦了还有一件事，如果您需要的话，可以将Fibbonachi数组的第n个元素近似化，但是可以通过更仔细的搜索在Internet上找到。快乐的黑客人！！！

链接
黄昏科西嘉 2014年3月7日，下午2:32

有人知道第n个Fibbonachi密码的估算公式！尝试谷歌和其他一些，但只是不会显示它。

链接
黄昏科西嘉 2014年3月7日，下午11:14

@Kiffin好吧，如果您说类似f =->{x8是不是已经准备好了，所以您只需调用某些东西，或者您早就添加了一些库，现在您已经放弃了它或类似的东西。嗯，那么您可以说，如果有人用C ++开发数值算法，这是很费时间的，因为那是Matlab等程序。更加详细一些！

链接
黄昏科西嘉 2014年3月7日，晚上11:27

@Kiffin好吧，我从未遇到过Kiffins，但我注意到您在您的站点上提到了复制析构函数。请您对此做进一步的阐述，因为我从来没有见过那种东西，有复制构造函数，但我从未听说过复制析构函数，也没有听说过虚拟的。有趣的题材不死！

链接
基芬 2014年3月8日，上午8:42

Sorry, but the code I added in my comment got botched because of the special characters. Does code work?

链接
基芬 2014年3月8日，上午8:44

f =- >(x){ x < 2 ? x : f[x-1] + f[x-2] }
puts f[5]

链接
黄昏科西嘉 2014年3月8日，上午9:46

从您的观点出发，您冷漠地创建了更快的代码，我不同意！近似算法更易于实现，更快，节省内存等。您可能会注意到，这是更加锻炼的事情。

This is 上 e array of cyphers it has something to do with Fibonachi array to, it is for execize>0112358314593471897639213… 上 e more thing to do with it is to check is it periodicall or not. Have funn!

好吧，贴近任何时间，任何速度或任何时间都会咬住那条线！

链接
匿名 2014年3月9日，晚上10:16

模板结构斐波那契
{
枚举{value =（Fibonacci :: value + Fibonacci :: value）};
};

模板结构斐波那契
{
枚举{value = 1};
};

模板结构斐波那契
{
枚举{value = 1};
};

模板结构斐波那契
{
枚举{value = 1};
};

int main（）
{
整数x = Fibonacci :: value;
out << x << endl;
整数x
}

链接
黄昏科西嘉 2014年3月11日，上午6:54

好啦 >

链接

OK 2014年3月11日，上午9:58

对于诸如计算斐波那契数之类的任务，您仍然可以使用递归算法而无需计算爆炸。您需要的是能够返回多个值。在C ++中，您可以使用向量之类的结构。

请参阅以下代码的重做，这些代码可以递归计算斐波那契数，而没有本文所述的问题。此版本与迭代版本一样快。

#include <iostream>
#include <vector>

using namespace std;

vector<long long> FibonacciElement(long long);

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

    cout<<"With recursion F(n)    ="<<FibonacciElement(lliN)[1]<<endl;

    int iRespond; cin>>iRespond;

    return 0;
}

vector<long long>
FibonacciElement( long long n)
{

  if (n==0) return vector<long long> { 0, 0  }; 
  if (n==1) return vector<long long> { 0, 1  }; 
  vector<long long> fib = FibonacciElement(n-1);
  long long tmp = fib[0];
  fib[0] = fib[1];
  fib[1] = fib[0] + tmp;
  return fib;
}

链接

黄昏科西嘉 2014年3月11日，上午11:40

好东西！

THX很多！

即使这样做，也不会改善文章！

链接
黄昏科西嘉 2014年3月12日，上午12:49

再说一遍，当我想到递归时，我喜欢考虑树的不同观点，是的，还有其他观点，但是它们并不那么重要>递归的数学定义是什么，如果您对n进行分析，您将看到差异！定义，第二个是程序员如何编写代码，您很好地提出了另一种方法来生成计算量更少的代码，第三种方法可能是最重要的方法，它是如何通过一些优化将其转换为可执行bfile的。速度很快，但如果未执行此硫磺处理，则可以在该字段上执行更多操作接下来的大事是多线程，但这是另一个大话题。

链接
黄昏科西嘉 2014年3月12日，上午1:34

而且，如果没有这样说，当您应用selfcaled函数时，该函数有很多副本，则堆栈会被过度使用，这是传统观点，如果可以避免这种情况，那么您可以编写出不错的代码并获得非常快的结果…无尽的故事不死。分两步扩展递归>1.查看第二步以了解什么是递归。 2.如果尚未收到，请返回第一步。这有点可笑。对真实的东西有正式的材料定义！

链接
黄昏科西嘉 2014年3月13日，下午12:05

One more coment 上 this subject, it has a lot of applications in real life, but there is 上 e more thing to go with this article, and this way it would not be said. Well, you could array-s for big numbers, then you could calculate the Fibonacci elemente even beyond the limits of the long long int, the 未签名上 e, or any data type that would be provided to you 通过 defaults…

链接
OK 2014年3月14日，下午3:21

@duskoKoscica是的，您是对的，因为这样的计算可能是重新发现算法上的问题。太深的递归总是问题，并且可能引起麻烦。与递归相比，我更喜欢您的迭代版本。
我想在代码中显示的是某些任务需要返回多个值。对于这种情况，使用复杂的数据类型很有用。
在某些语言中，例如perl，可以仅返回数据数组。
我已经读过一些函数式编程语言可以进行函数调用结果缓存。所以如果你调用fib（5），然后在调用fib（6）时将只计算fib（5）和fib（4）的两个缓存值之和。我认为这个问题非常适合此类功能。

链接
黄昏科西嘉 2014年3月15日，上午1:13

@Fok非常感谢您提供的信息，以您所显示的方式来计算Fib的方法很棒。递归很棒。但是，从速度的角度来看，有一些解决方案是好的，有些仅仅是智能化的预告片，您应该了解它们的功能。在我的下一篇有关质数的文章中，这只是人们寻找其他方式的途径。这样，这只是每个读者应达到的目标的一小步。因为我们不一样，而且我们有一些偏好，所以结果应该有所不同，但这是工作的方式！

链接
黄昏科西嘉 2014年4月5日，上午12:04

还有关于Fib nums的另一件事。有一种非常简单的方法来检查给定的数字是否为Fib num。尝试谷歌它。

链接

下一篇：如何将MS SQL Server存储过程查询转换为MySQL

上一篇：分支和中继的7个Subversion SVN合并命令示例

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

斐波那契数的实现

其他练习：

如果您喜欢这篇文章，您可能还会喜欢..

关于极客的东西

联系我们

支持我们