題目敘述：https://zerojudge.tw/ShowProblem?problemid=b837
解題想法：
- 題目不保證 A <= B，若A > B，先swap。
- 初始化 a = 0, b = 1。利用 b = a + b, a = b – a，滾動計算費氏數列。
#include <iostream>
using namespace std;
int main() {
int num, n, m;
cin >> num;
for (int iter = 0; iter < num; iter++){
if (iter != 0){
cout << "------\n";
}
cin >> n >> m;
if (n > m){
n = n + m;
m = n - m;
n = n - m;
}
int a = 0, b = 1, count = 0;
while (1){
if (a > m) break;
if (a >= n) {
count ++;
cout << a << "\n";
}
b = a + b;
a = b - a;
}
cout << count << "\n";
}
}
Python 程式碼 (credit: Amy Chou)
- 為例避免反覆計算費氏數列，先建表。依題意，查詢範圍 A, B (0 <= A, B <= 1000000)，計算到 F[31] = 1346269 便已足夠。
- 注意：題目不保證 A <= B。
def findIndex(lst, x):
#找出大於等於 x 的值的index
for i in range(len(lst)):
if lst[i] >= x:
return i
# === main program ===
# F[31] = 1346269 > 1000000
F = [0, 1]
for i in range(2, 35):
F.append(F[-1] + F[-2])
T = int(input())
while (T):
T -= 1;
A, B = map(int, input().split())
if (A > B):
A, B = B, A
idx1 = findIndex(F, A)
idx2 = findIndex(F, B)
if F[idx2] > B:
idx2 -= 1
for i in range(idx1, idx2+1):
print(F[i])
print(max(0, idx2-idx1+1))
if (T > 0):
print("------")