斐波那契数列 c语言求N项为(n-1)项加(n+2)项

Question

如题所述

Answer 1

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)

int Fun(int n)

{

    if(n==0)

        {

            return 0;

        }

        else if(n==1) 

        {

            return 1;

        }

        else

        {

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

        }

}

当n不比较大时,此法比较耗时耗内存,而且随n指数上升,当用下法

int Fun(int n)

{

int* arr=(int*)malloc(4*n);

if(n==0)

{

return 0;

}

else if(n==1) 

{

return 1;

}

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

    {

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

}

return arr[n];

}

Answer 2

//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdio.h"
void main(void){
int n,i,k;
unsigned a,b,c;
printf("Shows how many items?\nn=");
scanf("%d",&n);
for(a=b=c=1,k=i=0;i<n;i++){
printf(++k%9 ? "%-11u" : "%-11u\n",a);
c=a+b;
a=b;
b=c;
}
printf("\n");
}

Answer 3

f(0) = 0
f(1) = 1
f(2) = f(0) + f(1)
...
f(n) = f(n-2) + f(n-1)
要求f(n-1) + f(n+2)
首先f(n-1) + f(n+2) = f(n-1) + (f(n+2-2) + f(n+2-1))
然后f(n-1) + f(n+2) = f(n-1) + f(n) + f(n+1)
因为f(n-1) + f(n) = f(n+1)
所以f(n-1) + f(n) + f(n+1) = 2f(n+1)

void main()
{
unsigned int G(unsigned int n);
printf("%d", G(10));

}
unsigned int fib(unsigned int n);
//N项为(n-1)项加(n+2)项记为G（n）
unsigned int G(unsigned int n)
{
return 2*fib(n+1);
//直接来也可以的,下面这个语句有个问题，n-1可能是负数，而上面那个语句n+1不会为负数
//return fib(n-1) + fib(n+2);
}
unsigned int fib(unsigned int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
return fib(n-2) + fib(n-1);

}