UVa 834 Continued Fraction

本題題目連結

想法：
　　這題可以自己舉幾個例子算出分數，找出規則，解法如下，由題目Example，從(43,19)逆推回去

1. 首先2的話就是43/19=2,43%19=5，那麼現在[2;] & (5,19)
2. 19/5=3,19%5=4，得到[2;3] & (5,4)
3. 倒數的緣故，交換兩數，現在[2;3] & (4,5)
4. 重複2~3步驟，直到第一個數為1

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	int a,b;
	while (scanf("%d%d",&a,&b)!=EOF){ // 43,19
	printf("[%d;",a/b); // [2;
	a %= b; // 5,19
	while(a!=1){
	printf("%d,",b/a); // [2;3, / [2;3,1,
	b %= a; // 5,4 / 4,1
	swap (a,b); // 4,5 / 1,4
	}
	printf("%d]\n",b); // [2;3,4,1]
	}
	return 0;
	}

view raw [UVa] 834 Continued Fraction.cpp hosted with ❤ by GitHub