c++ - 将浮点十进制值转换为分数

Question

给定一个十进制浮点值，你如何找到它的分数等价/近似值？例如:

as_fraction(0.1) -> 1/10
as_fraction(0.333333) -> 1/3
as_fraction(514.0/37.0) -> 514/37

是否有可以将十进制数转换为小数形式的通用算法？如何在 C++ 中简单有效地实现这一点？

Answer 1

先取小数部分，再取gcd。使用欧几里得算法 http://en.wikipedia.org/wiki/Euclidean_algorithm

void foo(double input)
{
    double integral = std::floor(input);
    double frac = input - integral;

    const long precision = 1000000000; // This is the accuracy.

    long gcd_ = gcd(round(frac * precision), precision);

    long denominator = precision / gcd_;
    long numerator = round(frac * precision) / gcd_;

    std::cout << integral << " + ";
    std::cout << numerator << " / " << denominator << std::endl;
}

long gcd(long a, long b)
{
    if (a == 0)
        return b;
    else if (b == 0)
        return a;

    if (a < b)
        return gcd(a, b % a);
    else
        return gcd(b, a % b);
}