e523 - 106 彰雲嘉區複賽 - Q3 費波南希數列

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷一個給定的正整數是否為費波那契數列中的一項，如果是，則輸出該數在數列中的位置（從 1 開始計數），否則輸出 -1。如果輸入為 1，則輸出 1。

解題思路

由於題目限制輸入數值小於 1000000，且測資為官方測資，因此可以直接預先計算出小於 1000000 的所有費波那契數列，並將其儲存在一個陣列中。然後，對於每個輸入的數字，在陣列中進行線性搜尋，如果找到該數字，則輸出其在陣列中的索引加 1（因為索引從 0 開始，而題目要求從 1 開始計數）。如果搜尋到陣列中的數字大於輸入數字，則表示輸入數字不在費波那契數列中，輸出 -1。

複雜度分析

• 時間複雜度: O(n*m)，其中 n 是測試資料組數，m 是費波那契數列陣列的長度。在最壞的情況下，需要遍歷整個陣列才能確定輸入數字是否在數列中。
• 空間複雜度: O(m)，其中 m 是費波那契數列陣列的長度。需要儲存小於 1000000 的所有費波那契數列。

程式碼

#include <stdio.h>
int main(){
	int b=0,c=1;
	int a[30]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040};
	scanf("%d",&b);
	while(scanf("%d",&b)>0){
		c=0;
		while(1){
			if(a[c]==b){
				printf("%d\n",c+1);break;
			}
			else if(a[c]>b){
				printf("-1\n");break;
			}
			c++;
		}
	}
}