当前位置：首页 > article >正文

Fibonacci数列（斐波那契数列或兔子数列）

article 2024/11/23 8:00:47

一、斐波那契数列介绍

二、三种处理方法

1.递归处理

2.迭代处理

3.数组处理

总结

一、斐波那契数列介绍

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

那么如何使用C语言程序来输出斐波那契数列呢？下面给出了三种解决方案。

二、三种处理方法

三种处理方法均只给出了Fibonacci数列处理的函数，主函数都是一样的，要输出每一项则使用循环，只输出某一项，则直接打印返回值即可。

#include <stdio.h>

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		printf("%d ", Fib1(i));
	return 0;
}

1.递归处理

//递归方法
int Fib1(int n)
{
	if (n <= 2) 
		return 1;
	else
		return Fib1(n - 1) + Fib1(n - 2);
}

2.迭代处理

//迭代方法
int Fib2(int n)
{
	int f1 = 1, f2 = 1, f3=1;
	while (n > 2)
	{
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;
		n--;
	}
	return f3;
}

3.数组处理

#include<stdlib.h>

//数组方法
int Fib3(int n)
{
	if (n == 1 || n == 2)return 1;
	int* ints = (int*)malloc(n * sizeof(int));
	ints[0] = 1;
	ints[1] = 1;
	for (int i = 2; i < n; i++)
	{
		ints[i] = ints[i - 1] + ints[i - 2];
	}
	return ints[n-1];
}