三种方法求第n个斐波那契数:递归,数组,循环

斐波那契数列:

1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,418…

第一第二项是1,第三项是前两项的和1+1=2,第四项是第二第三项的和1+2=3,所以第n项是第n-1项与n-2项的和。


1.用递归求第n个斐波那契数

我们先写代码主要框架,输入一个数n,创建中间变量i,我们要一直重复 n-1项 + n-2项,直到n被求出来为止。我们可以运用for循环,循环内部调用实现相加的函数,最后将第n个数打印出来。

for(i=1;i<n;i++) { fun(i)); } printf("%d",fun(n));

接下来需要将调用函数实现写出来

int fun(int n) { if (n == 1 || n == 2) { return 1; } else { return fun(n - 1) + fun(n - 2); } }
#include<stdio.h>
int fun(int n)
{
	if (n == 1 || n == 2)//通过数列的规律发现,前两项都为1,作为递归的终止条件
	{
		return 1;
	}
	else
	{
		return fun(n - 1) + fun(n - 2);//要求第n项,就是求n-1项和n-2项的和
	}
}
int main()
{
	int i, n;
	printf("请输入你要打印第n个斐波那契数:");
	scanf("%d", &n);//n为打印的项数
	printf("第n个斐波那契数:");
	for (i = 1; i <= n; i++)
	{
		fun(i);//fun函数返回的是第i项,所以用for循环打印每一项
	}
	printf("%d", fun(n));
	return 0;
}

2.用数组求第n个斐波那契数

由于数组下标从0开始,所以第n个数的下标是n-1

#include<stdio.h>
int main()
{
	printf("求第n个斐波那契数:");
	int i = 0;
	int sz = 0;
	int n = 0;
	scanf("%d", &n);
	int a[20] = { 1,1 };
	sz = sizeof(a) / sizeof a[0];
	for (i = 2; i < sz; i++)
	{
		a[i] = a[i - 1] + a[i - 2];
	}
	printf("第n个斐波那契数是:");
	printf("%d", a[n-1]);
	return 0;
}

3.用循环求第n个斐波那契数

创建一个中间变量count

n<2时,返回1,此时count为1,n==3时,count++,count为2

#include<stdio.h>
int count = 0;
int fib(int n)
{
	if (n == 3)
		count++;
	if (n <= 2)
		return 1;
	else
		return fib(n - 1) + fib(n - 2);
}
int main()
{
	printf("求第n个斐波那契数:n=");
	int n = 0;
	scanf("%d", &n);
	int ret = fib(n);
	printf("第n个斐波那契数:");
	printf("%d
", ret);
	return 0;
}
经验分享 程序员 微信小程序 职场和发展