0

再帰の学習を始めたばかりで、リストのネストの深さを伝えるプログラムを作成する割り当てがあります。さて、私はブラウジングして、これを行うための作業コードを見つけましたが、それがどのように機能するかを理解するのにまだ問題があります. コードは次のとおりです。

def depth(L) :
    nesting = [] 
    for c in L:
        if type(c)  == type(nesting) :
            nesting.append(depth(c)) 
    if len(nesting)  > 0:
        return 1 + max(nesting)
    return 1

当然のことながら、再帰を呼び出す追加の行で混乱し始めます。ここで何が起こっているのかを簡単に説明できる人はいますか? 実際に何が追加されているのかわからず、頭の中でテストケースを調べても役に立ちません。ありがとう！

編集: 書式設定が不十分な場合は申し訳ありません。携帯電話から入力しました

4

4 に答える 4

2

コードを次のように変更する簡単な方法をお見せしましょう: (### はコードに追加した新しい行なので、そこで何が起こっているかを見ることができます)

def depth(L) :
    nesting = []
    for c in L:
        if type(c)  == type(nesting) :
            print 'nesting before append', nesting ###      
            nesting.append(depth(c))
            print 'nesting after append', nesting ###
    if len(nesting)  > 0:
        return 1 + max(nesting)
    return 1

次に、深さが 3 のリストを作成します。

l=[[1,2,3],[1,2,[4]],'asdfg']

リストに 3 つの要素があることがわかります。1 つはリスト、もう 1 つはそれ自体に別のリストを持つリストで、最後の 1 つは文字列です。このリストの深さが 3 であることは明らかです (つまり、メイン リストの 2 番目の要素にネストされた 2 つのリストがあります)。

このコードを実行してみましょう:

>>> depth(l)
nesting before append []
nesting after append [1]
nesting before append [1]
nesting before append []
nesting after append [1]
nesting after append [1, 2]
3

簡単です！この関数は、ネストに 1 を追加します。次に、要素に別のリストもある場合は、関数自体が呼び出された回数である 1 + ネストの最大数を追加します。要素が文字列の場合はスキップします。

最後に、再帰が発生した最大回数であるネストの最大数を返します。これは、メインリストのリスト内にリストが存在する回数、つまり深さです。この場合、予想どおり、2 番目の要素 + 1=3 に対して再帰が 2 回発生しました。

それでも取得に問題がある場合は、関数にさらにステートメントまたは他の変数を追加してprint、それらを注意深く観察してみてください。最終的には取得できます。

于 2013-04-24T17:47:55.873 に答える
1

つまり、これは、リストを取得して、その入れ子の深さを計算する関数のようです。ネストはリストなので、つまり、if type(c) == type(nesting)リスト内のアイテムがリストの場合L、関数を再度実行して追加し、関数を再度実行すると、リストにネストされたリストがなくなるまで同じテストが行​​われますLすべてのリストの深さは 1 であるため、1 + ネストされたリストの最大数を返します。

この中で不明な点があれば教えてください

于 2013-04-24T17:29:00.557 に答える
0

このアルゴリズムは、ネストされたリストにアクセスし、再帰の各レベルに 1 つ追加します。呼び出しチェーンは次のようになります。

depth([1, 2, [3, [4, 5], 6], 7]) =
    1 + depth([3, [4, 5], 6]) = 3
        1 + depth([4, 5]) = 2
            1

要素がリストではないため、depth([4,5]) はif type(c) == type(nesting)条件に入らないため、基本ケースである外側の戻り値から 1 を返します。

与えられた深さに対して、ネストされたリストが複数ある場合。たとえば[1, [2, 3], [4, [5, 6]]、 と の両方の最大深さが[2,3]深[4, [5, 6]]さ呼び出しに追加され、最大深さは内部の戻り値によって返されます。

于 2013-04-24T17:36:16.930 に答える