斐波那契数列第n项——C实现

斐波那契数列：第1项为1，第2项为1，其余项均为前两项之和。

这里列举了3种方法：（1）递归法；（2）数组法；（3）迭代法。

如果规定时间限制为1s，采用数组法和迭代法。

1、递归法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int Fibonacci(int n) {
	if (n == 1 || n == 2) {
		return 1;
	}
	else {
		return Fibonacci(n-1)+Fibonacci(n-2);
	}
}

int main() {
	int n;
	printf("请输入n的值：");
	scanf("%d", &n);
	printf("斐波那契数列的第%d项为：%d\n", n, Fibonacci(n));
	return 0;
}
           

2、数组法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int Fibonacci(int n) {
	int arr[40] = { 0，1 };
	for (int i = 2; i <= n; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	return arr[n];
}

int main() {
	int n;
	printf("请输入n的值：");
	scanf("%d", &n);
	printf("斐波那契数列的第%d项为：%d\n", n, Fibonacci(n));
	return 0;
}
           

3、迭代法

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int Fibonacci(int n) {
	if (n == 1 || n == 2) {
		return 1;
	}

	int a = 1, b = 1, result = 0;
	while (n>2) {
		result = a + b;
		a = b;
		b = result;
		n -= 1;
	}
	return result;
}

int main() {
	int n;
	printf("请输入n的值：");
	scanf("%d", &n);
	printf("斐波那契数列的第%d项为：%d\n", n, Fibonacci(n));
	return 0;
}
           

运行结果：