/ ALGORITHM

初识连分数

Description

  • 连分数形式通常为 :

  • 连分数常用于无理数的逼近,例如:

  • 连分数表示的算法:

    • 考虑实数 $r$,每次从中分离出它的整数部分,然后对于小数部分取倒数,继续重复这个过程。如果 $r$ 为有理数,那么当小数部分为 $0$ 时,过程中止。
    • 连分数一般简写作: $ x = [a_0;a_1,a_2,a_3]$
    • For example :
      $3.245 = 3 + 0.245, \frac{1}{0.245} = 4.082 $
      $4.082 = 4 + 0.082, \frac{1}{0.082} = 12.250$
      $12.250= 12 + 0.250, \frac{1}{0.250} = 4.000$
      $4.000 = 4 + 0, stop $
      $3.245 = 3 + \frac{1}{4 + \frac{1}{12 + \frac{1}{4}}} $

Problems

  • ECOJ 3305
    • Question : 要求用一个分母不超过 $10^9$ 的分数逼近给定的小数
    • Solution : 模拟连分数计算过程,直至超过限制
    • Code :
        double tar;
        vector<LL> ans;
        LL limit = 1000000000;
        void find( double now)
        {
        LL cnt = (LL)now;
        if(cnt>limit || ans.size()>100 ) return;
        ans.pb(cnt);
        if( now-1.0*cnt>eps ) find( 1.0/(now-1.0*cnt) );
        }
        void solve()
        {
        ans.clear();
        find( 1.0/tar );
        int loc = ans.size(); 
        LL p,q;
        while(loc)
        {
            loc--;
            p=1,q=0;
            for(int i=loc;i>=0;i--)
            {
                LL tp = p*ans[i]+q, tq = p;
                LL g = __gcd(tp, tq);
                p = tp/g;
                q = tq/g;
                if(p > limit || q > limit) break;
            }
            if(p<=limit) break;
        }
        cout << q << " " << p << endl;
        }
        int main()
        {
        while(cin >> tar)
        {
            if(fabs(tar)<eps) cout << "0 1\n";
            else if(fabs(tar-1.0)<eps) cout << "1 1\n"; 
            else solve();
        }
        }
      
  • HDU 6209
    • Question : 给定整数 $k$,要求用分母不超过 $10^5$ 的分数逼近 $k^{\frac{2}{3}}$
    • Solution : 暂时没用连分数的做法通过,因为分母限制比较小,那么可以考虑二分逼近的做法。
    • Code :
        int cbrt3(int x){
        return (int)cbrt(x + 0.5);
        }
        int k;
        void solve()
        {
        int limit = 100000;
        LD tar = cbrt(1.0l*k*k);
        int base = (int)tar;
        tar -= base;
        int x1 = 0, y1 = 1, x2 = 1, y2 = 1;
        while(true){
            if(y1+y2 > limit) break;
            int up = x1 + x2, down = y1 + y2;
            LD tmp = 1.0*up/down;
            if(tmp<tar)
                x1 = up, y1 = down;
            else
                x2 = up, y2 = down;
        }
        LD tmp1 = 1.0*x1/y1, tmp2 = 1.0*x2/y2;
        if( tar - tmp1 > tmp2 - tar )
            printf("%d/%d\n", x2+y2*base, y2);
        else 
            printf("%d/%d\n", x1+y1*base, y1);
        }
        int main()
        {
        int T;
        scanf("%d", &T);
        while(T--)
        {
            read(k);
            int x = cbrt3(k);
            if( k==x*x*x ) printf("%d/1\n", x*x);
            else solve();
        }
        }