Целочисленное переполнение встречается в сумме - PullRequest
Новая
       53

Целочисленное переполнение встречается в сумме

0 голосов
/ 24 сентября 2019

У меня сложилось впечатление, что целые числа Python имеют произвольную точность.Но сегодня, решая проблему leetCode и несколько заявок с неправильным ответом, я наконец добавил mod в свое решение, и оно сработало.Я не понимаю, почему это произошло, вот мой код: 

import math

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        if target>d*f or target<d:
            return 0
        memo = {}
        return int(self.recurse(d,f,target,memo)%(math.pow(10,9) + 7))

    # def recurse(self,d,f,target,memo):

    def recurse(self,d,f,target,memo):
        key = "%d %d"%(d,target)
        if key in memo:
            return memo[key]
        if d*f<target or target<d:
            return 0
        elif d==1:
            return 1
        else:
            ways = 0
            for i in range(1,f+1):
                # following line uncommented, and the next one commented, gives correct answer
                #ways = (ways+self.recurse(d-1,f,target-i,memo))%(math.pow(10,9) + 7)
                ways += self.recurse(d-1,f,target-i,memo)

            memo[key] = ways
            return memo[key]

Я предполагаю, что переполнение приводит к неверному результату, модифицируя частичный результат каждый раз, пока суммирование решает проблему.Или мне чего-то не хватает?

1 Ответ

1 голос
/ 26 сентября 2019

Вы вычисляете с помощью чисел с плавающей запятой: 

return int(self.recurse(d,f,target,memo)%(math.pow(10,9) + 7))

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

Давайте сделаем d, f, target = 30, 30, 500.Затем int(self.recurse(d, f, target, memo) возвращает 1319186227454333254490768998141738589030871, int, в то время как math.pow(10, 9) + 7 равно 1000000007.0, float.

Итак, вот что вы делаете: 

print(1319186227454333254490768998141738589030871 % 1000000007.0)  # wrong
811448245.0

Если вы вместо этого убедитесь, что дивиденд также является целым числом (10 ** 9 + 7 или 1000000007): 

print(1319186227454333254490768998141738589030871 % 1000000007)  # right   
222616187
...