求Fibonacci数列前20项：利用数组

引例：求Fibonacci数列前20项

1，1，2，3，5，8，13……

所谓递推就是指，在初始条件下，可以由前面一项或者多项推出后面的项。

在Fibonacci数列中，已知f1=1,f2=1,可得f3=f1+f2=3，f4=f2+f3=5,f5=f3+f4=8……依次类推，可以求得f19，f20。但是如果是这样一项一项求的话，程序过于繁杂。如果求前100项呢？

所以，对于递推问题，应该利用循环。要求某一项，已知前两项就可以。

程序设计

定义f1，f2，f且f1=1，f2=1；输出f1，f2.。

设计循环，循环体中，次数是一定的。即从i=3到i=20。循环体中f=f1+f2，输出f。再为下一次循环做准备。t=f2，f2=f，f1=f2，（需要定义中间变量t）

故需要定义f1，f2，f，i（计数器），t（中间变量）

代码实现

#include <stdio.h>
int main (void)
{
  int f1,f2,f,i,t;
  f1=1;f2=1;
  printf("%d\t%d\t",f1,f2);
  for (i=3;i<=20;i++)
  {
    f=f1+f2;
    printf("%d\t",f);
    if (i%5==0)
      printf("\n");
    t=f2;
    f2=f;
    f1=t;
  }
  return 0;
}

思考：若是要求只是输出Fibonacci数列的某一项呢？

在上面的代码中，只是对于每一项进行了输出，而其实际的数据并没有在内存中保存。

如果要求输出某一项，就要求我们把Fibonacci数列的每一项数据都存在内存中。这时，可以考虑数组。

利用数组：

将数列的第一项，赋值给a[0],第二项赋值给a[1],第三项赋值给a[3]

定义一维数组，a[20];方法分析如上。

代码实现

#include <stdio.h>
int main (void)
{
  int a[20],i;
  a[0]=1;a[1]=1;
  for (i=2;i<20;i++)
    a[i]=a[i-1]+a[i-2];
  for (i=0;i<20;i++)
  {
    printf("%d\t",a[i]);
    if ((i+1)%5==0)
      printf("\n");
  }
  printf("%d",a[10]);
  return 0;
}

这时，利用数组能将每一项都保存下来，若要输出某一项时，也可以直接输出。