每日一算法:Fibonacci数列

Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。

如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89......

/*递归算法一*/

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int Fibonacci(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (n == 1 || n == 2)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return 1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return Fibonacci(n-1) + Fibonacci(n-2);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

     
	printf("%d\n",Fibonacci(n));
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

/*递归算法二*/

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define N 40
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int Fib[N] = {0};
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     

      	Fib[0] = Fib[1] = 1;
     
    
   

    

     

    
    

     
	for (i=2; i<N; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for (i=0; i<N; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("%d\t",Fib[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\n");
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

/*迭代算法*/

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     
	int Fib1 = 1;
     
    
   

    

     

    
    

     
	int Fib2 = 1;
     
    
   

    

     

    
    

     
	int Fib = 1;
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

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

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		Fib  = Fib1 + Fib2;
     
    
   

    

     

    
    

     

      		Fib1 = Fib2;
     
    
   

    

     

    
    

     

      		Fib2 = Fib;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("%d\n",Fib);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/14522279