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

有用な手法は、「利用可能な解決策がない」値を選択して、それが解決策を表しているかのように処理しても「利用できる解決策がない」値を生成するようにすることです。たとえば、低い数値が最適解を表す場合、対象となる有効な解よりも大きい値を選択できます。整数型を使用している場合は、有効な解であるかのように操作しても数値オーバーフローが発生しないように、「使用可能な解がありません」の値が十分に小さいことを確認する必要があります [たとえば、再帰呼び出しが常に次のコストを想定している場合ある位置からの解は、再帰呼び出しによって生成された解のコストよりも 1 大きくなります。その場合、999,999,999 より大きい値を使用して「利用可能な解がない」ことを表すことができます。ただし、コードがソリューションのコストを他の 2 つのソリューションの合計と見なす可能性がある場合は、より小さい値を選択する必要があるかもしれません]。あるいは、「正の無限大」の値は他の値よりも大きくなり、それに正または有限の量を追加してもそれは変わらないため、浮動小数点型を使用することでメリットが得られる場合があります。

于 2013-03-06T17:56:13.147 に答える