網頁

2014年1月25日 星期六

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,停止。
這題和二分搜尋很類似。