Question

使用递归算法求Fibonacci数列的第n项，第一项是1，第二项是1，第n项是前两项之和

#include "stdafx.h"
#include <stdio.h>
int F(int n)
{
if(n=0) return 1;
else if(n=1) return 1;
else return (F(n-1)+F(n-2));
}
int main(int argc, char* argv[])
{
int n;
scanf("%d",&n);
printf("%d",F(n));
return 0;
}
哪里错了？，我输n多少，都显示1

Answer 1

int F(int n)

{
if(n==1||!n)

return 1;

else

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

}
比较大小是用==，,n=1是先将n赋值为1再判断n是否不为0
n==0可简写为!n，||是逻辑运算符“或”
其实上面的程序是指数时间复杂度，下面程序则是线性时间复杂度的：
int F(int n)
{
int a=1,b=1;

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

{

int c=a+b;

a=b;

b=c;

}

return b;

}
其实还有一种方法，是利用二维矩阵{1 1}{1 0}的幂实现的，对数时间复杂度。如果感兴趣可以查一下，网上资料很多的。由于代码太长，我这里就不写出来了

Answer 2

int F(int n)
{
	if(n==0) //比较用==
		return 1;
    else if(n==1) //比较用==
		return 1;
	else
		return (F(n-1)+F(n-2));
}

Answer 3

#include <stdio.h>
int sum(int j);
int j;
int main()
{
printf("请输入斐波那契数列的项数(最大为第57项):\n");
scanf_s("%d", &j);
if (j == 1 || j == 2)
{
printf("第%d项的值为1",j);
}
else
{
sum(j);
}
return 0;
}
int sum(int j)
{
int i,a=1,b=1;
for (i = 3; i <= j; i++)
{
if (i % 2 == 1)
{
a = a + b;
}
else if (i % 2 == 0)
{
b = a + b;
}
}
if (j % 2 == 1)
{
printf("第%d项的值为%d", j, a);
}
else if (j % 2 == 0)
{
printf("第%d项的值为%d", j, b);
}
}