Простой пример "разделяй и властвуй"

Вот моя тестовая программа «разделяй и властвуй», но она дает мне ошибку. Я иду в правильном направлении?

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));
    }
}

Вот исключение ошибки в потоке "main" java.lang.StackOverflowError в getSum.sumArray (getSum.java:16)

Я ищу простой пример того, как взять массив из 16 и разбить его на базовый случай 4. У меня возникли проблемы с пониманием того, как разбить массив, а затем снова разделить его. затем объедините все расколы в конце.


divide-and-conquer
person shinjuo    schedule 19.02.2013    source источник
comment
какой-то конкретный язык?   -  person    schedule 19.02.2013
comment
c ++, java или что-то в этом роде. Мне просто нужно понимание   -  person shinjuo    schedule 19.02.2013

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете использовать рекурсию для разделения и властвования. Вы продолжаете рекурсию на меньших массивах, пока не найдете совпадение, а затем поднимаетесь вверх по дереву повторения.

Например: найдите, есть ли число в массиве, используя рекурсивную функцию 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])
}

Вы можете видеть, как проблема разделяется на две более мелкие проблемы и так далее, пока она не достигнет условия остановки «n == 1», после чего она начнет возвращать результаты вверх по дереву вызовов. Это псевдокод, вам придется адаптировать концепцию к языку программирования, который вы используете.

person ilomambo    schedule 19.02.2013

arrow_upward
1
arrow_downward

Возникли проблемы с пониманием того, как плюнуть массив, а затем снова разделить его.

Это можно сделать с помощью рекурсии.

person Bhushan Firake    schedule 19.02.2013
comment
Это то, что я не знаю, как это сделать. - person shinjuo; 19.02.2013
comment
@Bhusha_Firake Я добавил тест «разделяй и властвуй» выше. Похоже, я на правильном пути? - person shinjuo; 19.02.2013