斐波那契數列第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;
}
           

運作結果：