POJ

POJ1650 OpenJ_Bailian1650 ZOJ1601 Integer Approximation

題目連結 POJ
題目連結 OpenJ_Bailian
題目連結 ZOJ

  • 題意：給定一浮點數 $A$，求一個最靠近 $A$ 的分數(分子 $N$ 和分母 $D$ 皆 $\leq L$ 的正整數)。
  • 題解：先讓 $N=D=1$，如果 $N/D>A$，讓 $D+=1$，反之讓 $N+=1$。
  • 備註：ZOJ1601 是 EOF 版
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <map>
    #include <string>
    #include <vector>

    using namespace std;
    typedef long long LL;
    const int INF = 1e9;
    const int MXN = 1e5 + 5;
    const int MXV = 3e5 + 5;
    const LL MOD = 10009;
    const LL seed = 31;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                             \
        cout.tie(NULL);                                                            \
        ios_base::sync_with_stdio(false);

    double A, L;
    double x, y;
    double ansx = 1, ansy = 1;

    void update()
    {
        if (abs(x / y - A) < abs(ansx / ansy - A))
        {
            ansx = x;
            ansy = y;
        }
    }

    int main()
    {
        IOS;
        cin >> A >> L;
        x = y = 1;
        update();
        while (x < L && y < L)
        {
            // cout << x << ' ' << y << '\n';
            if (x / y > A)
            {
                y += 1.0;
            }
            else
            {
                x += 1.0;
            }
            update();
        }
        cout << fixed << setprecision(0) << ansx << ' ' << ansy << '\n';
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts