Учитывая округленные числа, как найти исходную дробь? - PullRequest
Новая
       116

Учитывая округленные числа, как найти исходную дробь?

2 голосов
/ 06 августа 2020

Задав этот вопрос на 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.

1 Ответ

1 голос
/ 07 августа 2020

Предполагая, что числа не содержат слишком много значащих цифр и не слишком велики, вы можете попробовать увеличивать знаменатель, пока не найдете верное решение. Это не просто брутфорс. Кроме того, следующий сценарий остается на числе, нарушающем ограничения, до тех пор, пока ничего не найдено, в надежде получить знаменатель выше быстрее, без необходимости вычислять числа c без проблем.

Он работает на основе следующей формулы: 

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

Это означает, что знаменатель d действителен, если: 

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

Часть ceil (...) вычисляет наименьший возможный числитель удовлетворяет ограничению нижней границы, а остальное проверяет, удовлетворяет ли она также верхней границе.

Лучше было бы работать с реальными целочисленными вычислениями, например, просто long в 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])
...