【題解】ZeroJudge b837: 104北二1費氏數列

• 題目不保證 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("------")
```