再帰中の変数の難しさ値

Question

分割と征服の方法論を使用して配列の逆位を数えようとしています。しかし、逆転の総数を求めることができません。プログラムが完了した後、最後のステップではなく、その前に行われたすべての逆転の合計ではありません。

def mergesort(A): 
if len(A) <2: 
    return A 
mid = len(A)//2 
lefthalf = A[:mid] 
righthalf = A[mid:] 
mergesort(lefthalf) 
mergesort(righthalf) 
Total= merge(lefthalf,righthalf,A) 
return Total 

def merge(left,right,A): 
Total = 0 
i,j,k = 0,0,0 
while i < len(left) and j < len(right): 
    if left[i] <= right[j]: 
     A[k] = left[i] 
     i+=1 
     k+=1 
    else: 
     A[k] = right[j] 
     j+=1 
     k+=1 
     Total+= len(left[i:]) 
while i < len(left): 
     A[k] = left[i] 
     i+=1 
     k+=1 
while j < len(right): 
     A[k] = right[j] 
     j+=1 
     k+=1 
return Total  

印刷（マージソート（[1,5,3,2,4]））

どのようにして合計をmantainことができますか？ 説明付きでコードに必要な変更を提案してください。おかげさまで

Answer 1

これは答えですので、この質問は未回答のセクションには残りません。

合計は、現在のスタックフレームだけでなく、将来の再帰呼び出しのスタックフレームの反転回数を記録する必要があります。このためには、再帰呼び出しの戻り値をTotalに追加するか、現在のようにローカル変数を保持するのではなく、各再帰呼び出し間で共有されるグローバル変数としてTotalを宣言する必要があります。