给定一些四舍五入的数字，如何找到原始分数？

Question

在 math.stackexchange.com 上问了这个问题后，我认为这毕竟是一个更好的地方...

我有一小部分正数四舍五入到（比如说）两位小数：

 1.15  (can be  1.145 -  1.154999...)
 1.92  (can be  1.915 -  1.924999...)
 2.36  (can be  2.355 -  2.364999...)
 2.63  (can be  2.625 -  2.634999...)
 2.78  (can be  2.775 -  2.784999...)
 3.14  (can be  3.135 -  3.144999...)
24.04  (can be 24.035 - 24.044999...)

我怀疑这些数字是整数的分数，并且所有分子或所有分母都相等。在这种情况下，选择 100 作为公分母是可行的，这会将最后一个值保留为 2404/100。但是可能会有 'simpler' 整数更小的解决方案。

如何有效地找到最小公分子 and/or 分母？或者（如果不同的话）会导致最小最大分母的那个。分子？

当然，我可以对小 lists/numbers 和小数点进行暴力破解。对于这个例子，这会找到 83/72、138/72、170/72、189/72、200/72、226/72 和 1731/72。

Answer 1

假设数字没有太多有效数字并且不太大，您可以尝试增加分母，直到找到有效的解决方案。不只是 brute-forcing。此外，只要没有发现任何内容，以下脚本就会停留在违反约束的数字上，希望能更快地提高分母，而不必计算 non-problematic 个数字。

它基于以下公式工作：

x / y < a / b   if   x * b < a * y

这意味着分母 d 在以下情况下有效：

ceil(loNum * d / loDen) * hiDen < hiNum * d

ceil(...) 部分计算满足下边界约束的最小可能分子，其余部分检查它是否也满足上边界。

更好的方法是使用实整数计算，例如只做多 Java，然后 ceil 部分变成：

(loNum * d + loDen - 1) / loDen

function findRatios(arr) {
    let lo = [], hi = [], consecutive = 0, d = 1
    for (let i = 0; i < arr.length; i++) {
        let x = '' + arr[i], len = x.length, dot = x.indexOf('.'),
            num = parseInt(x.substr(0, dot) + x.substr(dot + 1)) * 10,
            den = Math.pow(10, len - dot),
            loGcd = gcd(num - 5, den), hiGcd = gcd(num + 5, den)
        lo[i] = {num: (num - 5) / loGcd, den: den / loGcd}
        hi[i] = {num: (num + 5) / hiGcd, den: den / hiGcd}
    }
    for (let index = 0; consecutive < arr.length; index = (index + 1) % arr.length) {
        if (!valid(d, lo[index], hi[index])) {
            consecutive = 1
            d++
            while (!valid(d, lo[index], hi[index]))
                d++
        } else {
            consecutive++
        }
    }
    for (let i = 0; i < arr.length; i++)
        console.log(Math.ceil(lo[i].num * d / lo[i].den) + ' / ' + d)
}

function gcd(x, y) {
    while(y) {
        let t = y
        y = x % y
        x = t
    }
    return x
}

function valid(d, lo, hi) {
    let n = Math.ceil(lo.num * d / lo.den)
    return n * hi.den < hi.num * d
}

findRatios([1.15, 1.92, 2.36, 2.63, 2.78, 3.14, 24.04])

给定一些四舍五入的数字，如何找到原始分数？

Given some rounded numbers, how to find the original fraction?

algorithm

integer

fractions