3 
def abc(s):
    filter = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    for i in range(len(filter) - 1):
        if filter[i] > filter[i+1]:
            return print(s, "is not abcdearian")
    return print(s,  "is abcdearian")


while True:
    try:
        s = input("String? ")
abc(s)

abc(s) の再帰バージョンを作成するのに問題があります。何か案は？

4

3 に答える 3

3

非再帰的ソリューション：

def issorted(L):
    return all(x <= y for x, y in zip(L, L[1:]))

再帰関数を作成するには、同じ方法で解決できる、問題をより小さく、および/またはより単純なサブ問題に分割する方法を見つける必要があります。

#!/usr/bin/env python3
from string import ascii_lowercase

def abcdearian(s):
    return issorted_recursive([c for c in s.lower() if c in ascii_lowercase])

def issorted_recursive(L):
    return L[0] <= L[1] and issorted_recursive(L[1:]) if len(L) > 1 else True

これissorted_recursive()が再帰関数です。基本ケースは次のとおりですlen(L) <= 1（要素が0または1のリストは常にソートされるためTrue、この場合は戻ります）。再帰的な場合（len(L) > 1）ではL、最初の項目がソートされた順序（L[0] <= L[1]）であり、残りのリスト（L[1:]）もソートされている場合、リストはソートされていると見なされます。L[0] > L[1]順序が正しくない要素が見つかるまで（ ）、または基本ケースが検出されて関数が終了するまで、関数はますます小さな入力を受け取るたびに。

例

while True:
    s = input("String? ")
    if not s:
        break
    print("{} is {}abcdearian".format(s, "" if abcdearian(s) else "not "))

入力

    abc
    bac

出力

String? abc is abcdearian
String? bac is not abcdearian
String?
于 2012-11-30T02:34:31.077 に答える
0

このコードを試してください。質問に投稿されたものと同等ですが、再帰的なスタイルで書かれています:

from string import ascii_lowercase

def abc(s):
    f = [c for c in s.lower() if c in ascii_lowercase]
    if aux(f, 0):
        return s + " is abcdearian"
    else:
        return s + " is not abcdearian"

def aux(s, i):
    if i >= len(s)-1:
        return True
    elif s[i] > s[i+1]:
        return False
    else:
        return aux(s, i+1)

次のように使用します。

while True:
    s = input("String? ")
    if not s:
        break
    print(abc(s))

問題を 2 つに分割していることに注意してください。まず、「メイン」関数abc()が文字列のフィルタリングを処理し、正しい初期値でプロシージャを呼び出し、aux最後に結果文字列を返します (または、ブール値を返して、結果の文字列は別の場所にあります)。

実際の作業はヘルパーaux関数で行われ、文字列内の連続する文字のすべてのペアについて「abcdearian」条件が真であるかどうかをチェックする文字列を再帰的に走査します。文字列を反復処理する方法auxは効率的です (再帰を使用しているという事実は別として) s[1:]。これは末尾再帰アルゴリズムの例でもあり、反復解の構造をよく反映しています。

于 2012-11-30T01:12:52.950 に答える
0

受け入れられた回答が最初に書かれた方法は、過度に複雑に見えました。うまくいけばそれを修正する編集を送信しました。しかし、私がそれに気づいた時には、私はすでに以下の答えと説明を書いていました. 説明が誰かに役立つ場合に備えて、それを保管してください：

def abc(s):
    filtered = [i for i in s.lower() if i in 'abcdefghijklmnopqrstuvwxyz']
    optionalNotString = ('' if _abc(filtered) else ' not')
    print( '{0} is{1} abcdearian'.format( repr(s), optionalNotString ) )

# Recursively process the "rest" (remainder) of the string.
# At each step, examine the first two characters.
def _abc(rest):
    if len(rest) < 2:
        # We've successfully compared all successive pairs, so return True.
        return True
    if (rest[0] > rest[1]):
        return False
    return _abc(rest[1:])

使用中 (文字列が短すぎる、文字列 'acb' の末尾と文字列 'bac' の先頭で False 条件を検出するなど、テストする最も重要なケース。最初に書いた方法でバグが発生しました。それは、「bac」を False としてキャッチできませんでした!):

abc( '' )
abc( 'a' )
abc( 'ac' )
abc( 'abc' )
abc( 'acb' )
abc( 'bac' )

出力：

'' is abcdearian
'a' is abcdearian
'ac' is abcdearian
'abc' is abcdearian
'acb' is not abcdearian
'bac' is not abcdearian

説明：

  1. フィルタリングは一度だけ実行する必要があるため、再帰的な「_abc」関数ではなく、メインの「abc」関数で実行してください。

  2. 各ステップで、アルゴリズムは隣接する 2 つの文字を調べる必要があります。「_abc」を呼び出すたびに、これらは最初の 2 文字になります。

  3. "_abc" は、次の 2 つのケースを処理する必要があります。

    • ケース 1: 文字列が短すぎて比較を実行できません。例: '' または 'a'。このような文字列は abcderian 基準を満たすため、True を返します。

    • ケース 2: 文字列は 2 文字以上です。最初の 2 つのアブクデリアン計算を実行します。それが失敗した場合、答えは False です。それ以外の場合は、最初の文字を除くすべてで再帰します。

  4. 「repr(s)」は、「s」をその周囲の引用符で印刷する簡単な方法です。

  5. "optionalNotString ": True/False の場合の望ましい回答文字列は、'not' の有無によってのみ異なります。そのため、「if .. else ..」式を使用して、フォーマットされた出力に「not」を含めるかどうかを制御します。不要な場合は、空の文字列 '' に置き換えてください。

于 2013-12-12T21:12:19.467 に答える