Python: gọi đệ quy đếm cách đi bộ sản lượng lưới câu trả lời không chính xác khi kích thước lưới là quá lớn

Question

Vấn đề:

Hãy tưởng tượng bạn bắt đầu ở góc của một X bằng lưới Y. Bạn chỉ có thể di chuyển theo hai hướng: phải và xuống. Có bao nhiêu đường dẫn có thể có để bạn đi từ (0, 0) đến (X, Y)

Tôi có hai cách tiếp cận cho điều này, trước tiên là sử dụng thuật toán đệ quy được tăng cường bằng ghi nhớ, và thuật toán thứ hai là sử dụng chiến lược đếm nhị thức

Recursive Way

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)] 

đếm nhị thức

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

hai wa ys cung cấp cho các câu trả lời tương tự khi x và y là tương đối nhỏ

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

Khi x và y là lớn

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

lời giải thích cho điều này là gì. Stack tràn của một số loại? Tuy nhiên, nó không ném bất kỳ ngoại lệ. Có cách nào để khắc phục điều này cho cuộc gọi đệ quy không?

Answer 1

Vấn đề ở đây là một hạn chế của điểm số học và sự khác biệt giữa python2 và python3 liên quan đến các nhà điều hành phận nổi.

Trong python 2 toán tử phân chia trả về tầng của kết quả của bộ phận nếu đối số là ints hoặc longs (như trong trường hợp này) hoặc xấp xỉ hợp lý nếu đối số là phao hoặc phức tạp. Mặt khác, Python 3 trả về một phép tính xấp xỉ hợp lý của phân chia độc lập với kiểu đối số.

Với số lượng đủ nhỏ, xấp xỉ này đủ gần để đưa trở lại số nguyên kết thúc bằng kết quả tương tự như phiên bản python 2. Tuy nhiên khi kết quả đủ lớn, biểu diễn dấu phẩy động không đủ gần đúng để kết thúc với kết quả chính xác khi truyền trở lại một int.

Trong python2.2 các sàn bộ phận điều hành đã được giới thiệu // và trong python3 đúng bộ phận thay phân chia cổ điển (xem nguồn gốc của thuật ngữ ở đây: 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 

Bản cập nhật của tất cả những điều này là dành cho hàm nhị thức của bạn, bạn có thể xóa bỏ phép cast thành int và chúng ta e toán tử chia tầng rõ ràng để nhận được kết quả chính xác được trả về.

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

Answer 2

Tôi đang bối rối trong thời gian này, nhưng tôi có một số tiến bộ tốt đẹp. Tôi đã thử một vài điều để theo dõi này:

1. tôi đã thay đổi chìa khóa từ điển của bạn từ một chuỗi đến một tuple (x, y), chỉ để làm cho đoạn code dễ đọc hơn.
2. Tôi đã thêm các biến kết quả ở một vài nơi để giúp theo dõi các giá trị trả lại.
3. Tôi đã thêm một số câu lệnh in. Các giá trị này theo dõi các giá trị góc cuối cùng của bộ đệm, kết quả được tính toán trong các hàm và kết quả nhận được.

Mã mới bên dưới, là đầu ra. Bạn có thể thấy vấn đề quan trọng trong đầu ra: hàm thực hiện tính giá trị thích hợp và trả về giá trị đó cho chương trình gọi. Tuy nhiên, chương trình gọi sẽ nhận được một giá trị lớn hơn. Điều này xảy ra trong Python 3.5.2, nhưng 2.6.6 tính toán đúng. Ngoài ra còn có một sự khác biệt ký hiệu: 2.6.6 giá trị lớn có dấu "L" trên giá trị được hiển thị.

Code:

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)]) 

Output:

$ 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 

Sự khác biệt là 8736902458008; trong hex, đây là 0x7f237f7aa98 - tức là không có gì đặc biệt thú vị trong cơ sở 2. Nó không phải là một giá trị bất cứ nơi nào trong bộ nhớ cache.

Tôi biết đây không phải là câu trả lời hoàn chỉnh, nhưng tôi hy vọng nó sẽ thu hẹp phạm vi vấn đề đối với nội dung mà một công cụ SO khác nhận ra.

BTW, tôi đã phân biệt các tệp bộ nhớ cache; chúng giống hệt nhau, ngoại trừ dấu 'L' trên mỗi số nguyên dài trong 2.6.6