[EOJ 2980] 小数转化分数

Deuchie edited 9 月,2 周前

我还没学编译原理,听说那里有很多相关的知识;所以现在我就用笨方法解这种题了。这也是我现在不太爱做这种题的原因……

我的想法是这样的:可以把各种小数抽象为一类:

struct NumSection {
    u64 val = 0;
    u64 len = 0;
};

struct CyclicNum {
    NumSection front_part;
    NumSection cyclic_part;
    i64 offset = 0; // offset by order of magnitude.
};

这里 front_part 用来记录循环节之前的数字,以一个整数看待。用 offset 标记小数点的位置(一开始写的是 offset_by_order_of_magnitude ,但觉得这个名字有点太长了,我想可以用注释而不是写这么长的名字)。由于循环节可能以 0 开头所以我使用了 NumSection 来同时记录下这段数字的长度。front_part 也使用了 NumSection 是有点冗余了。

总体的步骤如下:

  1. 把字符串翻译为 CyclicNum
  2. CyclicNum 翻译为分数。
  3. 输出分数。

细化

这里不考虑输入不合法的问题。

Parse String to CyclicNum

一个小数可能由如下几部分构成:

所以,可以一步步写。这里使用了一个辅助函数 NumberSection::parse

struct NumSection {
    u64 val = 0;
    u64 len = 0;

    // Parse a string to a number, including the length(count) of digits.
    // Second of ret value points to the first non-digit char.
    template <typename Iter> static tuple<NumSection, Iter> parse(Iter iter) {
        NumSection ret;
        for (; '0' <= *iter && *iter <= '9'; ++iter) {
            ret.val = ret.val * 10 + *iter - '0';
            ++ret.len;
        }
        return {ret, iter};
    }
};

struct CyclicNum {
    // ...
    CyclicNum static parse(string_view str) {
        CyclicNum ret;
        auto iter = str.begin();
        tie(ret.front_part, iter) = NumSection::parse(iter);
        if (iter == str.end()) {
            return ret;
        }
        // now iter points to '.', if input is correct.
        ++iter;
        NumSection temp;
        tie(temp, iter) = NumSection::parse(iter);
        ret.front_part.val = ret.front_part.val * pow10(temp.len) + temp.val;
        ret.front_part.len += temp.len;
        ret.offset = -static_cast<i64>(temp.len);
        if (iter == str.end()) {
            return ret;
        }
        // now iter points to '['
        ++iter;
        tie(ret.cyclic_part, iter) = NumSection::parse(iter);
        return ret;
    }
}
Parse CyclicNum to Fraction

要把一个小数 $n$ 转成分数,如果 $n$ 是无限循环小数,设它的不循环部分忽略小数点后的值为 $x$,循环节的值为 $y$,循环节的长度为 $a$,由于小数点移位产生的修正为 $10^z$,显然有 $z\le 0$。此时下面的公式:
$$
n = \frac{(10^a-1)x+y}{10^a-1}\times 10^z
$$
如果不存在循环节,则
$$
n = \frac{x}{10^{-z}}
$$
用代码实现如下,使用了辅助函数 pow10

// kOrderOfMagnitude must be positive.
inline u64 pow10(u64 const kOrderOfMagnitude) {
    u64 ret = 1;
    for (u64 i = 0; i < kOrderOfMagnitude; ++i) {
        ret *= 10;
    }
    return ret;
}

struct CyclicNum {
    // ...
    bool is_cyclic() const {
        return cyclic_part.len != 0;
    }

    Fraction to_frac() const {
        Fraction ret;
        if (this->is_cyclic() == false) {
            ret.numerator = front_part.val;
            if (offset >= 0) {
                ret.numerator *= pow10(offset);
                ret.denominator = 1;
            } else {
                ret.denominator = pow10(-offset);
                ret.simplify();
            }
            return ret;
        }
        ret.denominator = pow10(cyclic_part.len) - 1;
        ret.numerator = front_part.val * ret.denominator + cyclic_part.val;
        if (offset >= 0) {
            ret.numerator *= pow10(offset);
        } else {
            ret.denominator *= pow10(-offset);
        }
        ret.simplify();
        return ret;
    }
};

这两步完成以后就可以输出了。由于它很简单我没有单独写一个函数而在 main 中直接写了。

int main() {
    u64 t;
    cin >> t;
    for (u64 query = 0; query < t; ++query) {
        cout << "case #" << query << ":\n";
        string num_str;
        cin >> num_str;
        Fraction frac = CyclicNum::parse(num_str).to_frac();
        cout << frac.numerator << '/' << frac.denominator << '\n';
    }
}

Comments

你当前正在回复 博客/题目
存在问题!