Различные результаты для одного и того же решения проблемы в node.js и python - PullRequest
Новая
       98

Различные результаты для одного и того же решения проблемы в node.js и python

3 голосов
/ 05 февраля 2020

Я решил следующую проблему leetCode с некоторым кодом:

У вас есть d игральные кости, и каждый d ie имеет f граней с номерами 1, 2, ..., f .

Вернуть число возможных способов по модулю 10 ^ 9 + 7 бросить кости, чтобы сумма чисел лицом вверх равнялась t.

Я сделал две версии код решения, один в node.js с использованием математика js и один в python с использованием математического модуля.

In node.js

const { combinations: comb, bignumber: Big } = require("mathjs");

function dice(d, f, t) {
    if (t > d * f || t < d) return 0;

    var result = Big(0);
    var i = 0;
    var sign = 1;
    var n = t - 1;
    var k = t - d;

    while (k >= 0 && i <= d) {
        result = result.add(
            comb(Big(d), Big(i))
                .times(comb(Big(n), Big(k)))
                .times(sign)
        );

        i++;
        n -= f;
        k -= f;
        sign *= -1;
    }

    return result;
}

console.log(
    dice(30, 30, 500).mod(
        Big(10)
            .pow(9)
            .add(7)
    )
);

В python: 

import math


def dice(d, f, t):
    if t > d * f or t < d:
        return 0

    result = 0
    i = 0
    sign = 1
    n = t - 1
    k = t - d

    while k >= 0 and i <= d:
        result += math.comb(d, i) * math.comb(n, k) * sign
        i += 1
        n -= f
        k -= f
        sign *= -1

    return result


print(dice(30, 30, 500) % (math.pow(10, 9) + 7))

Теперь, когда я запускаю код со следующими параметрами: d = 30 f = 30 t = 500 (последняя строка каждой версии кода), я ожидаю, что результат будет 222616187.

В версии node.js это именно то, что я получаю.

Но в версии python я Я получаю 811448245.0 Я не могу понять, почему это происходит.

Так почему же разница в результатах?

Ответы [ 2 ]

5 голосов
/ 05 февраля 2020

Модуль math использует float, не произвольную точность int.

математика - Математические функции

[...]

Следующие функции предоставляются этим модулем. За исключением случаев, когда явно указано иное, все возвращаемые значения являются числами с плавающей запятой.

Поскольку math.pow возвращает float, ведущий аргумент % также преобразуется в float. Результат dice(30, 30, 500) слишком велик, чтобы его можно было точно представить как float. Его представление float отключено -14999044413600247749080617.

Оператор ** и его версия функции operator.pow не вызывают преобразование float и предоставляют целое число, если все параметры являются целыми числами. 

>>> print(dice(30, 30, 500) % (10 ** 9 + 7))
222616187
2 голосов
/ 05 февраля 2020

Решено, странным образом. Оказывается, math.pow возвращает float вместо int и как-то прослушивается. Я думаю, что int% float имеет другую операцию приведения и обрабатывается компилятором по-разному. Это можно исследовать дальше. Если вы приведете его к int, это будет ваш ответ. 

import math


def dice(d, f, t):
    if t > d * f or t < d:
        return 0

    result = 0
    i = 0
    sign = 1
    n = t - 1
    k = t - d

    while k >= 0 and i <= d:
        result += math.comb(d, i) * math.comb(n, k) * sign
        i += 1
        n -= f
        k -= f
        sign *= -1

    return result


print(dice(30, 30, 500) % int((math.pow(10, 9) + 7)))
...