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

題目敘述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("------")
分享本文 Share with friends