[TIOJ] 1040. C.連分數

題目連結:http://tioj.infor.org/problems/1040
這題算是數學題吧(?,但也不是什麼難的數學,先說連分數的基本求法就是直接算$\lfloor \frac{a}{b} \rfloor$這東東就會是第一個整數,那顯然的$\frac{a}{b} - \lfloor \frac{a}{b} \rfloor$會是後面那串分數,那就再看$\frac{1}{\frac{a}{b} - \lfloor \frac{a}{b} \rfloor}$(=$\frac{b}{a - b \lfloor \frac{a}{b} \rfloor}$)然後用跟上面同樣的方法算下去,直到$\frac{a}{b} - \lfloor \frac{a}{b} \rfloor = 0$時停止,但是我們在實作時不能真的用double之類的,不然你可能會被浮點數誤差搞死(或許只是我太廢拉XD,所以要做一點基本的數學運算,這邊就不贅述,大概從我的code應該就可看出來在幹嘛了。 溫馨小提示(?有可能一開始b就是0
#include <stdio.h>

void weirdGCD(int,int,bool);

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		int a, b;
		scanf("%d%d",&a,&b);
		printf("%d/%d = %d",a,b,a/b);
		weirdGCD(a,b,0);
		puts("");
	}
}

void weirdGCD(int a,int b,bool tf){
	if(b==0)return;
	int c=a/b;
	if(!tf){
		weirdGCD(b,a-b*c,1);
	}else if(a-b*c == 0){
		printf("+1/%d",c);
		return;
	}else{
		printf("+1/{%d",c);
		weirdGCD(b,a-b*c,1);
		putchar('}');
	}
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology