c++实现斐波那契数列

c++实现斐波那契数列斐波那契数列是由莱昂纳多·斐波那契在1202年提出的一种数列，其规律是前两个数之和等于第三个数，以此类推。具体而言，数列的第一个和第二个数为0和1，之后每个数均为前两个数之和。因此，斐波那契数列的前几个数字为0、1、1、2、3、5、8、13、21等。斐波那契数列在数学、计算机科学和自然科学领域都有广泛的应用。

在C++中实现斐波那契数列并不难，可以采用递归或非递归的方式实现。

1.递归

首先，我们可以用递归的方式实现斐波那契数列。具体而言，我们定义一个函数fib(n)，用来计算斐波那契数列的第n个数字。函数的代码如下：

```

intfib(intn)

{

if(n<2)

returnn;

else

returnfib(n-1)+fib(n-2);

}

```

在这段代码中，我们首先判断n是否小于2。如果n小于2，则直接返回n。否则，我们递归调用fib函数，计算斐波那契数列的前两个数之和。由于递归的调用会比较耗时，在计算大数位的斐波那契数列时，会出现运行时间过长的情况。

2.非递归

为了加快计算斐波那契数列的速度，我们可以采用非递归的方式实现。具体而言，我们可以通过for循环或while循环来计算斐波那契数列的第n个数字。这种方式可以大大减少递归的调用次数，从而提高计算速度。

（1）for循环方式

我们可以采用for循环来计算斐波那契数列的第n个数字。具体而言，我们用一个数组来存储计算结果，从而避免重复计算。函数的代码如下：

```

intfib(intn)

{

if(n<2)

returnn;

intf[n+1];

f[0]=0;

f[1]=1;

for(inti=2;i<=n;i++)

f[i]=f[i-1]+f[i-2];

returnf[n];

}

```

在这段代码中，我们首先判断n是否小于2。如果n小于2，则直接返回n。否则，我们定义一个数组f来保存计算结果。数组f的前两个数分别为0和1。然后，我们通过for循环来计算斐波那契数列的第n个数字，将结果存储到数组f中。最后，我们返回数组f的第n个数字。

（2）while循环方式

另一种非递归的方式是采用while循环。具体而言，我们定义三个变量来分别保存前两个数字和当前数字。我们通过while循环来不断计算当前数字，直到计算出第n个数字为止。函数的代码如下：

```

intfib(intn)

{

if(n<2)

returnn;

intf1=0,f2=1,f3;

inti=2;

while(i<=n)

{

f3=f1+f2;

f1=f2;

f2=f3;

i++;

}

returnf3;

}

```

在这段代码中，我们定义了三个变量f1、f2和f3来保存前两个数字和当前数字。我们首先判断n是否小于2。如果n小于2，则直接返回n。否则，我们通过while循环来不断计算当前数字。计算出当前数字之后，我们将f1和f2分别向后移动一个数位，然后将当前数字存储到f3中。最后，我们返回f3。

总结

本文介绍了两种方式来计算斐波那契数列：递归和非递归。递归的方式会比较耗时，在计算大数位的斐波那契数列时会出现运行时间过长的情况。非递归的方式可以避免重复计算，从而提高计算速度