🔗 UVA-834 Continued Fractions

tags: `輾轉相除法` `數學(Math)` `遞迴(Recursion)`

範例程式碼已於 UVA、瘋狂程設(CPE) 上皆測試通過。

題意

給定一個有理數 $\frac{x}{y}$ ，將其表示為 連續分數(continued fraction) 的形式。連續分數是由一個整數初始項和一系列正整數係數組成的表示形式。其中，初始項為 $b_0$ ，係數為 $b_1, b_2, \dots, b_n$ ，且每個係數都必須大於 0。連續分數的表示形式為：

$b_0 + \cfrac{1}{b_1 + \cfrac{1}{b_2 + \cfrac{1}{\dots + \cfrac{1}{b_n}}}}$

對於第一個範例 $\frac{43}{19}$ ，其連續分數形式為 $[2; 3, 1, 4]$ ，可以通過計算驗證：

$2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{4}}} = \frac{43}{19}$

LuckyCat 的中文翻譯

思路：輾轉相除法(Euclidean algorithm)

利用輾轉相除法(Euclidean algorithm) 來不斷找出連續分數的係數。每次迭代中，計算當前分數的整數部分作為連續分數的係數，然後取其餘數繼續計算下一個係數，直到餘數為 0 為止。

最後按照題目要求的格式 $[b_0; b_1, b_2, \dots, b_n]$ 輸出每個有理數的連續分數形式。

複雜度分析

時間複雜度： $\mathcal{O}(\log \min(x, y))$ ，取決於輾轉相除的次數。
空間複雜度： $\mathcal{O}(\log \min(x, y))$ ，每次輾轉相除會產生一個新的係數。

while True:
    try:
        x, y = map(int, input().split())
    except EOFError:
        break
    ans = []
    while y:
        ans.append(x // y)
        x, y = y, x % y
    print(f"[{ans[0]}", end = "")
    if len(ans) > 1:
        print(";", end = "")
        print(','.join(map(str, ans[1:])), end = "")
    print("]")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int x, y;
    while (cin >> x >> y) {
        vector<int> ans;
        while (y) {
            ans.push_back(x / y);
            x %= y;
            swap(x, y);
        }
        cout << "[" << ans[0];
        if (ans.size() > 1) {
            cout << ";";
            for (int i = 1; i < ans.size(); ++i) {
                cout << ans[i];
                if (i < ans.size() - 1) cout << ",";
            }
        }
        cout << "]" << endl;
    }
    return 0;
}