UVa 10077 The Stern-Brocot Number System

題目連結

想法：
　　初始化三個數L=0/1, M=1/1, R=1/0，設輸入的分數為a：

• 如果a<M，那麼要往左邊走，
      R = M;
      M = (L分子+M分子)/(L分母+M分母);
• 如果a>M，往右邊走，
      L = M;
      M = (R分子+M分子)/(R分母+M分母);
• 如果a==M，停止。

這題和二分搜尋很類似。

	#include <cstdio>
	using namespace std;
	struct fraction{
	int M; //Molecular 分子
	int D; //Denominator 分母
	};
	int main()
	{
	int m,n;
	while (scanf("%d%d",&m,&n))
	{
	if (m==1 && n==1) break;
	fraction L={0,1},M={1,1},R={1,0};
	while (1){
	long double t1 = (long double)m/n, t2 = (long double)M.M/M.D;
	if (t1 < t2){
	printf("L");
	R = M;
	M.M += L.M;
	M.D += L.D;
	}
	else if (t1 > t2){
	printf("R");
	L = M;
	M.M += R.M;
	M.D += R.D;
	}
	else{
	printf("\n");
	break;
	}
	}
	}
	return 0;
	}

view raw [UVa] 10077 The Stern-Brocot Number System.cpp hosted with ❤ by GitHub