b837 - 104北二1費氏數列

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算指定範圍內費氏數列的數量，並輸出符合範圍內的費氏數。輸入包含多組測試資料，每組資料包含一個範圍 [A, B]，輸出範圍內的所有費氏數以及數量。

解題思路

程式首先預先計算出前 32 個費氏數列的數值，並儲存在 a 陣列中。對於每組測試資料，程式會比較輸入的 b 和 c 的大小，如果 c 小於 b，則交換它們的值。然後，程式遍歷預先計算的費氏數列，檢查每個費氏數是否在範圍 [b, c] 內。如果在範圍內，則輸出該費氏數，並增加計數器 ans。最後，程式輸出計數器 ans 的值，並根據是否還有其他測試資料，輸出分隔符號 "------"。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是測試資料組數，M 是預先計算的費氏數列的長度 (在本例中為 32)。
• 空間複雜度: O(1)，因為程式只使用固定大小的陣列 a 來儲存費氏數列，空間使用量不隨輸入大小而變化。

程式碼

#include <stdio.h>
int main(){
	int i=1,ans,d;
	long long int b=1,c=0,a[32];
	a[0]=0;
	for(;i<32;i++){
		a[i]=b;
		b+=c;
		c=b-c;
	}
	scanf("%d",&d);
	while(scanf("%lld%lld",&b,&c)>0&&d>0){
		if(c<b){
			b=c^b;
			c=c^b;
			b=c^b;
		}	
		for(i=0,ans=0;a[i]<=c;i++){
			if(a[i]>=b){
				printf("%d\n",a[i]);
				ans++; 
			}
		}
		d--;
		if(d!=0)
			printf("%d\n------\n",ans);
		else
			printf("%d\n",ans);	
	}
}