0

これが私の分割統治プログラムですが、エラーが発生します。私は正しい方向に向かっていますか？

public class getSum {
    static int sum = 0;
    public static void main(String[] args) {
            int[] numbers = {2,2,2,2,2,2,2,2};
            int amount = 0;
           amount = sumArray(0,numbers.length,numbers);
           System.out.print(amount);
    }

    public static int sumArray(int first, int last, int[] A){
        int index = last - first;
        if(index == 1){
            return sum;
        }else if(index <= 4 && index > 1){
            for(int i = first; first < last; i++){
                sum += A[i];
            }
            return sum;
        }
        return (sumArray(first, last / 2, A) + sumArray(last / 2, A.length, A));
    }
}

getSum.sumArray（getSum.java:16）のスレッド"main"java.lang.StackOverflowErrorのエラー例外は次のとおりです。

16の配列を取得し、それをベースケース4に分解する簡単な例を探しています。配列を吐き出し、再度分割する方法を完全に理解するのに問題があります。次に、最後にすべての分割を結合します。

4

2 に答える 2

1

配列を吐き出す方法を完全に理解してから、もう一度分割するのに問題があります。

Recursionを使用すると、それを行うことができます。

于 2013-02-19T04:50:54.797 に答える
1

分割統治には再帰を使用できます。一致するものが見つかるまで小さい配列で再帰を続け、次に反省ツリーに登ります。

例：再帰関数isIn（Number x、Array a）を使用して、数値が配列内にあるかどうかを確認します

Boolean isIn(Number x, Array a) {

   n = a.size
   if n==1 then return a[0]==x
   else
      return isIn(x, a[0:n/2]) or isIn(x,a[n/2:n])
}

問題が2つの小さな問題にどのように分割されるかを確認できます。以下同様に、停止条件「n == 1」に達するまで、呼び出しツリーに結果を返し始めます。これは擬似コードです。使用しているプログラミング言語に概念を適合させる必要があります。

于 2013-02-19T04:57:20.200 に答える