UVa10077 - The Stern-Brocot Number System (二分搜尋)

題目大意：

The Stern-Brocot tree 能夠完美的建構出沒有任何一個負分數，且 n 與 m 絕對互質，也就表示產生的值絕對不會有重複。

現在給你 The Stern-Brocot tree 其中一個值，我們想詢問透過 The Stern-Brocot tree 的方式，那它的位置在哪裡？透過 R and F 描述

舉例： 找出 \(\frac{3}{1}\)，那就是 RR 。

分析：

這題考的是腦筋急轉彎，問你會不會運用自身所學的知識。

其實這題就是二分搜尋，只是他將規則稍微改變。
但如果你可以從中得出結論你可以發現，數字的左邊值一定比中間的數字小，反之，右邊則會比中間數字大。

只要透過此規則進入左邊輸入 L、右邊輸入 R 就是答案了。

圖示：

重點觀念：

• 在判斷的時候因為有分子與分母要判斷，必須兩個都同時等於才跳出迴圈，因此 (b1 != d1 && b1 != d2) 這邏輯是錯誤的，錯誤舉例：b1 = 1 , b2 = 2 , d1 = 1 , d2 = 3。因此要改變下，變成 !(b1 == d1 && b2 == d2) 即可。
• int 在相除時出來的數字還是 int，因此需要將兩個數字都先轉成 float 再進行除法才會得出小數。
  舉例：double r = (float)b1 / (float)b2
• 不要強轉型態，會很花時間，向第二個重點的寫法，就會導致超時，因此要將這兩個額外拉出宣告兩個小數點變數。

變數命名

• int
  • a1 , a2
    左邊的值
  • b1 , b2
    中間的值
  • c1 , c2
    右邊的值
  • d1 , d2
    題目需要找到的值
• double
  • compute_b , compute_d
    計算大小用
  • d_b1 , d_b2 , d_d1 , d_d2
    計算 b and d 的值，強轉型態會浪費時間因此拉出 double 宣告

參考來源

Programming學習筆記 - UVa 10077 The Stern-Brocot Number System

心得

這題目真的好棒啊，我被她考到我卻一點怨言都沒有，出這題目的人是天才八，把我玩弄得心服口服，可惡，我學起來了，下次不會再犯了。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
int a1=0 , a2=1 , b1=1 , b2=1 , c1=1 , c2=0 ;
int d1 , d2 , t1 , t2 ;
double compute_b , compute_d , d_b1 , d_b2 , d_d1 , d_d2 ;
void bs(){ //binary search
    a1 = 0 ; a2 = 1 ;
    b1 = 1 ; b2 = 1 ;
    c1 = 1 ; c2 = 0 ;
    while(!(b1 == d1 && b2 == d2)){
        d_b1 = b1 ; d_b2 = b2 ;
        d_d1 = d1 ; d_d2 = d2 ;
        compute_b = d_b1 / d_b2 ;
        compute_d = d_d1 / d_d2 ;
        //cout << compute_b << ' ' << compute_d << '\n' ;
        if(compute_d > compute_b ){ //great than
            a1 = b1 ; a2 = b2 ;
            cout << "R" ;
        }
        else{ //less than
            c1 = b1 ; c2 = b2 ;
            cout << "L" ;
        }
        b1 = a1 + c1 ;
        b2 = a2 + c2 ;
        //cout << "a is " << a1 << '/' << a2 << '\n' ;
        //cout << "b is " << b1 << '/' << b2 << '\n' ;
        //cout << "c is " << c1 << '/' << c2 << '\n' ;
    }
    cout << '\n' ;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout);
#endif // LOCAL

    while(cin >> d1 >> d2 && d1 + d2 != 2 ){
        //cout << d1 << ' ' << d2 << '\n' ;
        bs();
    }
    return 0;
}