POJ 1079 Ratio

PKU 実装問題

問題

A/Bという分数が与えられる。
この分数に対して、次のような分数列を求めよ。

  • 分母が前の分数より常に大きい
  • 前の分数よりもA/Bに対する良い近似を与える
  • 項数が最大
  • 近似が同じ分子が二通りある場合、分子の大きいほうを採用する


例えばA=5, B=4の場合、
1/1
4/3
5/4
のような列である。

制約条件

A,B≦5000

方針

分母を1からBまで動かし、それぞれの分母について最良の近似を与える分子を探し、
それが今までの最良の近似より良くなっているなら出力する。


分子を見つける部分は、しゃくとり法っぽく1ずつ増やしていくことができる。

ソースコード

int a,b;

int main()
{
	while(~scanf("%d%d",&a,&b)){
		double mn=INF;
		for(int d=1, n=0;d<=b;d++){
			while(abs((n+1.0)/d-a*1.0/b)<abs(n*1.0/d-a*1.0/b)+EPS)n++;
			if(mn>abs(n*1.0/d-a*1.0/b)+EPS){
				printf("%d/%d\n",n,d);
				mn=abs(n*1.0/d-a*1.0/b);
			}
		}
		puts("");
	}
	return 0;
}