C语言实现斐波拉契数列

C语言实现斐波拉契数列教程

怎么使用 C 语言 实现计算斐波拉契数列的第 N 项的值？

C语言实现斐波拉契数列详解

背景知识

斐波那契数列是一组第一位和第二位为 1，从第三位开始，后一位是前两位和的一组递增数列，像这样的：1、1、2、3、5、8、13、21、34、55 …。

我们可以看到，此数列的第一位和第二位都是 1，第三位的值是第一位和第二位的和、第四位的值是第二位和第三位的和、第无位的值是第三位和第四位的和、依次类推。

解题思路一

看到此类问题，我们最优先想到的就是使用 递归 来实现该算法，递归的出口条件是第一项或者第二项值都是 1，否则，第 N 项的值是第 N - 1 项的值加上第 N - 2 项的值。

解题思路二

我们可以使用 for 循环，从第一项和第二项开始计算，一直计算到我们需要求的第 N 项的值。每次计算的值使用变量进行临时保存即可。

C语言实现斐波拉契数列实现

递归实现

使用递归实现求解斐波拉契数列的值

#include <stdio.h>
int Fibonacci(int n)
{
	if (n == 1 || n == 2)
	{
		//如果是第一项或者是第二项，值都是 1 
		return 1;
	}
	else
	{
		//开始递归，n 项的值就是 n-1 项的值和 n-2 项的值 
		return Fibonacci(n - 1) + Fibonacci(n - 2); 
	}
}
int main()
{
	printf("嗨客网(www.haicoder.net)\n");
	int n = 0;
	printf("请输入要求的项：");
	scanf("%d", &n);
	int result = Fibonacci(n);
	printf("result = %d\n", result);
	return 0;
}

程序运行后，控制台输出如下：

我们单独定义了一个函数 Fibonacci，在该函数里面，我们使用 if 判断如果 n 的值为 1 或者 2 则直接返回 1，这就是递归的出口。

否则，我们则继续调用 Fibonacci 函数，返回第 N - 1 项和第 N - 2 项的和，这里就是递归的开始。最后，我们输入了 10，返回了 55。

for循环实现

使用 for 循环加上临时变量实现求解斐波拉契数列的值

#include <stdio.h>
int Fibonacci(int n)
{
	int num1 = 1, num2 = 1, temp = 0, i = 0;
	if (n == 1 || n == 2)
	{
		return 1;
	}
	else
	{
		for (i = 0; i < n-2; i++)
		{
			temp = num1 + num2;
			num1 = num2;
			num2 = temp;
		}
		return temp;
	} 
}
int main()
{
	printf("嗨客网(www.haicoder.net)\n");
	int n = 0;
	printf("请输入要求的项：");
	scanf("%d", &n);
	int result = Fibonacci(n);
	printf("result = %d\n", result);
	return 0;
}

程序运行后，控制台输出如下：

我们单独定义了一个函数 Fibonacci，在该函数里面，我们使用 if 判断如果 n 的值为 1 或者 2 则直接返回 1。

否则，我们则使用 for 循环计算 n - 2 次，同时，将每次的计算结果保存在临时变量 temp 中，一轮计算结束，将变量 num2 赋给 num1，将临时变量 temp 赋值给 num2。最后，我们输入了 10，返回了 55。

C语言实现斐波拉契数列总结

使用 C 语言实现计算斐波拉契数列的第 N 项的值有两种方法，第一种就是使用递归实现，第二种则是使用 for 循环按个计算。