0

リストがソートされているかどうかをブールチェックする再帰関数を作成しようとしています。リストがソートされている場合は true を返し、ソートされていない場合は false を返します。これまでのところ、「基本ケース」が正しいかどうかを理解しようとしています(つまり、最初の「if」ステートメント):

def isSorted(L, i=[]):
    if L[i] > L[i + 1]:
         return false
    else:
         return true

if "L[i] > L[i + 1]:"再帰の基本ケースとして私のイニシャルで正しいですか?

私の「基本ケース」が正しいと仮定すると、リストが非降順でソートされているかどうかを再帰的に判断する方法がわかりません。

4

4 に答える 4

1

これが私が思いついたものです。デフォルトのリストを に指定します0。最初のアイテムが最後のアイテムかどうかを確認します。そうでない場合は、リストの最後に到達するまで各項目をチェックする必要があります。

def isSorted(L):
    # Base case
    if len(L) == 1:
        return True

return L[0] <= L[1] and isSorted(L[1:])
于 2012-07-24T21:40:29.000 に答える
0

いいえ、基本ケースはリストの最後に到達したときであり、その場合は true を返します。

そうではなく、見ている 2 つの要素が順不同である場合は、false を返します。

それ以外の場合は、リストの下の次の要素に対する再帰呼び出しの結果を返します。

于 2012-07-23T21:58:52.430 に答える
0

これが私が始める方法です。次のシグネチャを使用して関数を記述します。

function isSorted(currentIndex, collection)

currentIndex関数内で、 がコレクションの最後にあるかどうかを確認します。そうであれば、true を返します。

collection[index]次に、とcollection[index+1]が正しくソートされている かどうかを確認します。


そうでない場合はfalse を返します。isSorted(currentIndex+1, collection)

警告: これは再帰の恐ろしい使い方です

于 2012-07-23T21:29:35.840 に答える
0

@MStodd に同意します。再帰は Python でこの問題を解決する方法ではありません。非常に長いリストの場合、Python はそのスタックをオーバーフローする可能性があります! しかし、短いリストの場合は問題ありません。教師がこの問題を出したら、このようにする必要があります。

ここでは、この問題についてどのように考える必要があります。再帰呼び出しごとに、次の 3 つのいずれかを実行する必要があります。0)Falseリストがソートされていないことが判明したため、戻ります。1)True基本ケースに達したため、戻ります。2) 基本ケースに到達するまで、作業を分解し、残りの問題を何とか小さくします。基本ケースは、作業をこれ以上分解できないケースです。

大まかな概要は次のとおりです。

def recursive_check(lst, i):
    # check at the current position "i" in list
    # if check at current position fails, return False
    # update current position i
    # if i is at the end of the string, and we cannot move it any more, we are done checking; return true
    # else, if i is not at the end of the string yet, return the value returned by a recursive call to this function

たとえば'@'、文字列に文字があるかどうかを確認する関数を次に示します。文字列のどこにもTrueない場合は返されます。@

def at_check(s, i):
    if s[i] == '@':
        return False
    i += 1
    if i >= len(s):
        return True
    else:
        return at_check(s, i)

上記のアウトラインとまったく同じように上記を書きました。これは、同じことを行うわずかに短いバージョンですが、まったく同じ順序ではありません。

def at_check(s, i=0):
    if i >= len(s):
        return True
    if s[i] == '@':
        return False
    return at_check(s, i+1)

i=0編集:に引数を入れたことに注意してくださいat_check()。これは、 の「デフォルト」値iが 0 になることを意味します。この関数を呼び出す人at_check(some_string)は、最初の呼び出しで明示的に 0 を渡さなくても呼び出すことができます。デフォルトの引数は、最初の 0 引数を提供します。

本当に追加する必要があるiのは、関数を再帰的に呼び出すときだけです。1を足す部分が重要な「仕事を分解する」部分です。まだチェックしていない文字列の部分は の後の部分でi、その部分は呼び出すたびに小さくなります。「スライス」についてまだ学んでいるかどうかはわかりませんが、「スライス」を使用して、呼び出しごとに文字列を実際に小さくすることができます。そのように動作するバージョンを次に示します。スライスについてまだ知らない場合は無視してください。

def at_check(s):
    if s == '':  # empty string
        return True
    if s[-1] == '@':  # is last character '@'?
        return False
    return at_check(s[:-1]) # recursive call with string shortened by 1

このバージョンでは、空の文字列が基本ケースです。空の文字列には が含まれない@ため、 を返しTrueます。次に、最後の文字が; の場合は;@を返すことができます。Falseそれ以外の場合は、最後の文字を切り捨てて、関数を再帰的に呼び出します。ここでは、完了するまで文字列を文字通り短くすることで、作業を分解します。しかし、インデックス変数に 1 を追加することと、文字列内でインデックスを移動することは同じことです。

再帰を使用して作業を分解し、各再帰呼び出しである程度の進歩を遂げるというアイデアが得られるまで、これらの例を調べてください。次に、リストがソートされているかどうかを調べる問題にこのアイデアを適用する方法を理解できるかどうかを確認してください。

幸運を！

于 2012-07-24T00:37:28.750 に答える