Skip to main content
 首页 » 编程设计

python之Python 中的欧拉计划 #15

2025年05月04日9shangdawei

我是 Python 新手。我坚持在合理的时间内完成 Project-Euler 中的第 15 题。 memoize 函数中的问题。没有内存所有工作都很好,但只适用于小网格。我已尝试使用记忆化,但此类代码的结果对于所有网格都是“1”。

def memoize(f): #memoization 
    memo = {} 
 
    def helper(x): 
        if x not in memo: 
            memo[x] = f(x) 
        return memo[x] 
    return helper 
 
 
@memoize 
def search(node): 
    global route 
    if node[0] >= k and node[1] >= k: 
        route += 1 
        return route 
    else: 
        if node[0] < k + 1 and node[1] < k + 1: 
            search((node[0] + 1, node[1])) 
            search((node[0], node[1] + 1)) 
    return route 
 
 
k = 2 #grid size 
route = 0 
print(search((0, 0))) 

如果注释掉禁用内存功能的代码:

#@memoize 

一切正常,但对于大网格来说会变慢。我究竟做错了什么?帮忙调试。非常感谢!

更新1:

谢谢你的帮助,我也找到了答案:

def memoize(f): 
    memo = {} 
 
    def helper(x): 
        if x not in memo: 
            memo[x] = f(x) 
        return memo[x] 
    return helper 
 
 
@memoize 
def search(node): 
    n = 0 
    if node[0] == k and node[1] == k: 
        return 1 
    if node[0] < k+1 and node[1] < k+1: 
        n += search((node[0] + 1, node[1])) 
        n += search((node[0], node[1] + 1)) 
    return n 
 
k = 20 
print(search((0, 0))) 

问题并不像我之前想的那样出在 memoize func 中。问题出在“搜索”功能中。没有全局变量,我希望它能正常工作。感谢评论,它们真的很有用。

请您参考如下方法:

你的内存功能很好,至少对于这个问题。对于更一般的情况,我会使用这个:

def memoize(f): 
    f.cache = {}                         # - one cache for each function 
    def _f(*args, **kwargs):             # - works with arbitrary arguments 
        if args not in f.cache:          #   as long as those are hashable 
            f.cache[args] = f(*args, **kwargs) 
        return f.cache[args] 
    return _f 

实际的问题——正如 Kevin 在评论中指出的那样——是只有当函数不能通过副作用起作用时内存才起作用。虽然您的函数确实返回 结果,但您不会在递归计算中使用它,而只是依赖递增全局计数器变量。当您通过内存获得较早的结果时,该计数器不会再增加,您也不会使用返回的值。

改变你的函数来总结递归调用的结果,然后它就可以工作了。

您还可以稍微简化您的代码。特别是,递归调用之前的 if 检查不是必需的,因为无论如何您都会检查 >= k,但是您应该检查 x 组件 或 y 组件是 >= k,而不是两者;一旦其中一个命中k,就只有一条通往目标的路线。此外,您可以尝试倒数到 0 而不是倒数到 k,这样代码就不再需要 k 了。

@memoize 
def search(node): 
    x, y = node 
    if x <= 0 or y <= 0: 
        return 1 
    return search((x - 1, y)) + search((x, y - 1)) 
 
print(search((20, 20)))