Fifnmar edited 4 年，6 月前
我还没学编译原理，听说那里有很多相关的知识；所以现在我就用笨方法解这种题了。这也是我现在不太爱做这种题的原因……
我的想法是这样的：可以把各种小数抽象为一类：
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 是有点冗余了。
总体的步骤如下：
CyclicNum。CyclicNum 翻译为分数。这里不考虑输入不合法的问题。
CyclicNum一个小数可能由如下几部分构成：
integral part.，如果没有小数点就结束。non-cyclic fractional part[，如果没有方括号就结束。cyclic part]，必然存在一个右方括号和左方括号对称。所以，可以一步步写。这里使用了一个辅助函数 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;
}
}
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';
}
}