1

私のプログラムは、このコードでは機能しないようです。Python は初めてなので、これが言語関連のエラーかどうかはわかりません。現在、Python 2.7.8 を使用しています。

    A = [-1, -2, 3, 4, -5, 6]

    def main():
        a,b,c = find_maximum_subarray_recursive(A)                                                   
        print a,b,c

    def find_maximum_crossing_subarray(A, low, mid,  high):

        #mid = math.floor((low + high)//2)
        left_sum = float("-inf")
        sum = 0
        i = mid
        max_left = 0
        for i in range (mid, low, -1):
            sum = sum + A[i]
            if sum > left_sum:
                 left_sum = sum
                 max_left = i

        right_sum = float("-inf")
        sum = 0
        j = mid + 1
        max_right = 0
        for j in range (mid + 1, high):
            sum = sum + A[j]
            if sum > right_sum:
                 right_sum = sum
                 max_right = j
        return (max_left, max_right, left_sum + right_sum)


    def find_maximum_subarray_recursive(A, low = 0, high = -1):
        high = len(A)
        if high == low:
            return (low, high, A[low])
        else:
            mid = math.floor((low + high) // 2)
            left_low, left_high, left_sum = find_maximum_subarray_recursive(A, low, mid)
            right_low, right_high, right_sum = find_maximum_subarray_recursive(A, mid + 1, high)
            cross_low, cross_high, cross_sum = find_maximum_crossing_subarray(A, low, mid,  high)
            if left_sum >= right_sum & left_sum >= cross_sum:
                return (left_low, left_high, left_sum)
            elif right_sum >= left_sum & right_sum >= cross_sum:
                return (right_low, right_high, right_sum)
            else:
                return (cross_low, cross_high, cross_sum)

    if __name__ == '__main__':main()

関数 find_maximum_crossing_subarray(A, low, mid, high) は正常に動作していますが、私の人生では関数 find_maximum_subarray_recursive(A, low, high) でエラーを見つけることができないようです。プログラムがオーバーフローする原因となります。ロジックに問題があるのか​​構文に問題があるのか​​わかりません。誰かが私にこれを説明してくれれば、本当に感謝しています。どうもありがとう！

4

1 に答える 1

2 
def find_maximum_subarray_recursive(A, low = 0, high = -1):
    high = len(A)

このhigh = len(A)行は、私には論理エラーのように見えます。あなたの元の推論は、「ユーザーがパラメーターの値を指定しない場合、受け入れることができるhigh最高のインデックスとしてそれを指定する」というものだったと思います。Aそれがあなたの意図である場合、2 つの問題があります。

  1. ユーザーが自分で値を指定したかどうかに関係なく、値を設定します。
  2. A受け入れることができる最高のインデックスはlen(A)-1、ではありませんlen(A)。

ユーザーが指定した値を無視するhighと、無限ループが発生します。たとえば、 は 3find_maximum_subarray_recursive(A, 0, 6)の a を計算し、を見つけるためにmid呼び出します。しかし、その 3 の値は破棄され、6 に置き換えられます。したがって、次の関数は 3 の a を計算して呼び出します ... というように、永遠に続きます。find_maximum_subarray_recursive(A, 0, 3)left_summidfind_maximum_subarray_recursive(A, 0, 3)

したがって、関数の先頭は次のようにする必要があると思います。

def find_maximum_subarray_recursive(A, low = 0, high = -1):
    if high == -1: high = len(A)-1

そして別のこと：

    else:
        mid = math.floor((low + high) // 2)

これは私には型エラーのように見えます。math.floor浮動小数点値を返しますmidが、整数である必要があります (将来リストのインデックスに使用する予定であり、リストは整数のみを受け入れるため)。電話をかける必要はまったくありませんmath.floor。演算子は//すでに整数を返しています。この行は次のようになるはずです。

mid = (low + high) // 2

これらの変更によってプログラムが完全に修正されるわけではありません。の結果が得られますが2 3 7、7 は の部分配列の合計の最大値ではありませんA。サブ配列 [3, 4, -5, 6] の最大合計は 8 です。

しかし、少なくともあなたはもう溢れていません！

于 2014-09-10T18:28:29.790 に答える