Python: подсчет Рекурсивный вызов пути ходьба выход сетки неправильный ответ, когда размер сетки слишком большой

Question

Проблема:

Представьте, что вы начинаете на углу Х по Y сетки. Вы можете двигаться только в двух направлениях: вправо и вниз. Сколько возможных путей есть для вас, чтобы перейти от (0, 0) до (X, Y)

У меня есть два подхода к этому, первый заключается в использовании рекурсивного алгоритма усиливается запоминанием, а второй заключается в использовании биномиального СТРАТЕГИЯ подсчета

рекурсивного образом

def gridMovingCount(x, y, cache): 
    if x == 0 or y == 0: 
     return 1 
    elif str(x)+":"+str(y) in cache: 
     return cache[str(x)+":"+str(y)] 
    else: 
     cache[str(x)+":"+str(y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache) 
     return cache[str(x)+":"+str(y)] 

биномиальный подсчет

def gridMovingCountByBinomial(x, y): 
    return int(math.factorial(x + y)/(math.factorial(x) * math.factorial(y))) 

этих два в YS дают те же ответы, когда х и у сравнительно небольшой

#the same result 
print(gridMovingCount(20, 20, cache)) #137846528820 
print(gridMovingCountByBinomial(20, 20)) #137846528820 

Когда х и у больших

# gave different result 
print(gridMovingCount(50, 50, cache)) #100891344545564193334812497256 
print(gridMovingCountByBinomial(50, 50)) #100891344545564202071714955264 

Что такое объяснение. Переполнение стека? Однако это не исключает. Есть ли способ преодолеть это для рекурсивного вызова?

Answer 1

Проблема здесь является ограничением арифметики с плавающей точкой и различия между python2 и Python3 относительно оператора деления.

В python 2 оператор деления возвращает пол результата деления, если аргументы являются ints или longs (как в данном случае) или разумным приближением, если аргументы являются float или сложными. С другой стороны, Python 3 возвращает разумную аппроксимацию деления, не зависящего от типа аргумента.

При достаточно малых количествах это приближение достаточно близко, что возврат обратно в целое число заканчивается тем же результатом, что и версия python 2. Однако по мере того, как результат становится достаточно большим, представление с плавающей запятой не является достаточным приближением, чтобы привести к правильному результату при возврате в int.

В python2.2 пол подразделение оператор был введен // и в Python3 истинное деление заменить классическое разделение (см происхождение терминологии здесь: https://www.python.org/dev/peps/pep-0238/)

#python2 
from math import factorial 
print(int(factorial(23)/2)) # 12926008369442488320000 
print(int(factorial(23)//2)) # 12926008369442488320000 

---

#python3 
from math import factorial 
print(int(factorial(23)/2)) # 12926008369442489106432 
print(int(factorial(23)//2)) # 12926008369442488320000 

Результат всего этого заключается в том, что для вашей биномиальной функции вы можете удалить бросок в int и нас e явный оператор разделения полов, чтобы получить верные результаты.

def gridMovingCountByBinomial(x, y): 
    return math.factorial(x + y) // (math.factorial(x) * math.factorial(y)) 

Answer 2

На данный момент я в тупике, но у меня есть хороший прогресс. Я попробовал несколько вещей, чтобы отслеживать это:

1. Я изменил свой словарь ключ из строки в кортеж (х, у), просто чтобы сделать код более читаемым.
2. Я добавил переменные результата в несколько мест, чтобы отслеживать возвращаемые значения.
3. Я добавил несколько заявлений на печать. Они отслеживают последние угловые значения кеша, результаты, вычисленные в функциях, и полученные результаты.

Новый код ниже, как и выход. Вы можете увидеть критическую проблему в выходе: функция делает вычисляет правильное значение и возвращает его вызывающей программе. Однако вызывающая программа получает значение, которое больше. Это происходит в Python 3.5.2, но 2.6.6 правильно вычисляется. Существует также разница в обозначениях: 2.6.6 большие значения имеют конечный «L» для отображаемого значения.

Код:

import math 

def gridMovingCount(x, y, cache): 
    if x == 0 or y == 0: 
     return 1 
    elif (x,y) in cache: 
     if x+y > 98: 
      print ("returning cached", x, y, result) 
     return cache[(x,y)] 
    else: 
     cache[(x,y)] = gridMovingCount(x-1, y, cache) + gridMovingCount(x, y-1, cache) # stack will overflow 
     result = cache[(x,y)] 
     if x+y > 98: 
      print ("returning binomial", x, y, result) 
     return result 

def gridMovingCountByBinomial(x, y): 
    return int(math.factorial(x + y)/(math.factorial(x) * math.factorial(y))) 


cache={} 
#the same result 
print(gridMovingCount(20, 20, cache)) #137846528820 
print(gridMovingCountByBinomial(20, 20)) #137846528820 

# gave different result 
print() 
print("50x50 summed ", gridMovingCount(50, 50, cache)) #100891344545564193334812497256 
with open("p3.4_out", 'w') as fp: 
    lout = sorted(list(cache.items())) 
    for line in lout: 
     fp.write(str(line) + '\n') 

result = gridMovingCountByBinomial(50, 50) 
print() 
print("50x50 binomial", result) #100891344545564202071714955264 
print("50x50 cached ", cache[(50,50)]) 

Выход:

$ python3 so.py 
137846528820 
137846528820 

returning binomial 49 50 50445672272782096667406248628 
returning binomial 50 49 50445672272782096667406248628 
returning binomial 50 50 100891344545564193334812497256 
50x50 summed 100891344545564193334812497256 

50x50 binomial 100891344545564202071714955264 
50x50 cached 100891344545564193334812497256 

Разница заключается в том 8736902458008; в шестнадцатеричном виде это 0x7f237f7aa98 - то есть ничего особенно интересного в базе 2. Это не значение в любом месте кеша.

Я знаю, что это не полный ответ, но я надеюсь, что он сужает область проблемы до того, что распознает другой SO denizen.

BTW, я различал файлы кеша; они идентичны, за исключением конечного «L» для каждого длинного целого числа в 2.6.6