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

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。但是可能会有一个更小整数的“更简单”的解决方案。

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

当然，我可以暴力破解小列表/数字和小数点。对于此示例，这将找到83/72, 138/72, 170/72, 189/72, 200/72,226/72和。1731/72

标签： algorithmintegerfractions

Answer 1

假设数字没有太多有效数字并且不是太大，您可以尝试增加分母，直到找到有效的解决方案。这不仅仅是暴力破解。此外，只要没有找到任何内容，以下脚本就会停留在违反约束的数字上，以希望更快地获得更高的分母，而无需计算无问题的数字。

它基于以下公式工作：

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

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

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

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

更好的做法是使用真正的整数计算，例如 Java 中的 long，然后 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])