k932 - 00834 - Continued Fractions

🔗 前往 ZeroJudge 原題

題目描述

題目要求將給定的分數表示為連續分數的形式。連續分數的形式為 [b0; b1, b2, ..., bn]，其中 b0 是整數部分，b1, b2, ..., bn 是分數部分的反覆取整數部分。

解題思路

這題的核心是使用歐幾里得演算法（輾轉相除法）來計算連續分數的係數。

1. 首先，計算分數的整數部分 b0 = a / b。
2. 然後，計算餘數 x = a % b。
3. 如果餘數為 0，則表示分數已經被完全表示為整數，結束計算。
4. 如果餘數不為 0，則交換分子和分母，並重複步驟 1 和 2，直到餘數為 0。
5. 每次計算得到的整數部分就是連續分數的一個係數。

複雜度分析

• 時間複雜度: O(log(min(a, b)))，歐幾里得演算法的時間複雜度為對數級別。
• 空間複雜度: O(1)，只需要常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int x,y;
int main(){
	while(cin >> x >> y){
		cout << "[" << x/y << ";"; 
		x%=y;//5 19
		while(x){
			swap(x,y);//19 5
			int tmp=x/y;
			cout << tmp ;
			x=x%y;
			if(x)cout << ",";
		}
		cout << "]\n";
	}
	return 0;
}