1

我有一个具有特殊情况的递归算法，例如一个路径算法，如果路径良好，我想将距离加 1，但如果它遇到死胡同，则返回 -1。当使用一堆递归调用解决最大化问题时，这是有问题的。

有没有更好的方法来编写以下代码：

def rec(n):
  if n == 1:
    return -1
  if n == 0:
    return 1
  val = rec(n - 2)
  if val == -1:
    return -1
  else:
    return val + 1

因此rec(4) = 2，rec(3) = -1

4

2 回答 2

2

在 Python 中，并非如此。None您可以通过返回而不是 -1在 Python 中使其更清晰；这样做的好处是错误地添加到无效值会引发异常。

具有更严格的类型系统和“可能”或可选值的良好概念的语言使其变得轻而易举。说，哈斯克尔：

rec 1 = Nothing
rec 0 = Just 1
rec n = map ((+) 1) $ rec (n - 2)

map调用意味着它将添加框中的任何内容（如果是），Just x并返回无效值（Nothing）不变。当然，您可以设计自己的更复杂的类型，允许多种错误条件或其他任何情况，并且仍然获得类似的简单结果。这在 OCaml、F#、Standard ML 和 Scala 中几乎一样简单。

None您可以通过定义一个辅助函数在 Python中模拟这种方法：

def mapMaybe(obj, f):
    if obj is None:
        return None
    else:
        return f(obj)

然后你可以这样做：

return mapMaybe(val, lambda x: x + 1)

但我不知道我是否真的建议这样做。

模拟 Scala 书中的一个技巧，也可以将所有这些都包含在生成器理解中（未经测试）：

def maybe(x):
    if x is not None:
        yield x

def firstMaybe(it):
    try:
        return it.next()
    except StopIteration:
        return None

然后：

return firstMaybe(x + 1 for x in maybe(val))

但这确实是非标准、非惯用的 Python。

于 2013-03-06T17:37:07.960 回答
1

一个有用的技术是选择一个“没有可用的解决方案”值，这样处理它就好像它代表一个解决方案一样仍然会产生一个“没有可用的解决方案”值。例如，如果低数字代表最佳解决方案，则可以选择一个大于任何感兴趣的有效解决方案的值。如果使用整数类型，则必须确保“没有可用的解决方案”值足够小，以至于对其进行操作就好像它是一个有效的解决方案不会导致数值溢出[例如，如果递归调用总是假设某个位置的解决方案将比递归调用生成的解决方案的成本大一，然后使用大于 999,999,999 的值来表示“没有可用的解决方案”应该有效；但是，如果代码可能将解决方案的成本视为其他两个解决方案的总和，则可能需要选择较小的值]。或者，一个人可能会从使用浮点类型中受益，因为“正无穷大”的值将比任何其他值都大，并且向它添加任何正数或有限量都不会改变这一点。

于 2013-03-06T17:56:13.147 回答