≡菜单

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

斐波那契(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;
}

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

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

其他练习:

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

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

  1. 50个Linux Sysadmin教程
  2. 50个最常用的Linux命令(包括示例)
  3. 排名前25位的最佳Linux性能监视和调试工具
  4. 妈妈,我找到了! – 15个实用的Linux Find命令示例
  5. Linux 101 Hacks第二版电子书 Linux 101黑客手册

Bash 101 Hacks书 Sed和Awk 101黑客手册 Nagios Core 3书 Vim 101黑客手册

{ 22 评论 … 加一 }

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

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

    f =- >(x){ x 8

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

  • 赛博纳德 2014年3月7日,上午7:25

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

  • 咯咯笑的 2014年3月7日,上午10:24
  • 丹尼斯·盖兹米斯 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。尝试谷歌它。

发表评论