suma kombinacji tablicy jednowymiarowej z równoważnikiem

Witam serdecznie,

mam jedno pytanko, nie potrafię za implementować algorytmu do takiej postaci zadanka :

Jest tablica, która ma losowane za pomocą Random ilość indexów i wartości w tablicy. Należy znaleźć wartość równoważnika. Dla przykładu:
1)Dla takiej postaci
tab[i] 5
tab[i] 0
tab[i] 4
tab[i] 4
tab[i] 2
tab[i] 8
tab[i] 2
tab[i] 3

wynik:
prawa część tablicy:
tab[i] 5
tab[i] 0
tab[i] 4
tab[i] 4

tab[i] 2 ---to będzie równoważnik

lewa część tablicy:
tab[i] 8
tab[i] 2
tab[i] 3

2. Dla takiej postaci
   tab[i] 3
   tab[i] 1
   tab[i] 6
   tab[i] 8
   tab[i] 8

wynik:
prawa część tablicy:
tab[i] 3
tab[i] 6

tab[i] 8 --- to będzie równoważnik

lewa część tablicy:
tab[i] 1
tab[i] 8

Roumiem , że mam wykonać kombinację sumy wszystkich elementów tab, ale nie do końca wiem jak to robić...

Zaczęłam tak:

  public int obliczTablice_rownowagi(int[] tab, int n) {

        Random generator = new Random();
        n = generator.nextInt(10);
        tab = new int[n];
        int n_tab = generator.nextInt(10);
        for (n_tab = 0; n_tab < tab.length; n_tab++) {
            tab[n_tab] = generator.nextInt(10) + generator.nextInt(10) * (-1);
            System.out.println(" tab[i] " + tab[n_tab]);

            suma = suma + tab[n_tab];
            int[] t2 = Arrays.copyOfRange(tab, 1, tab.length);
        }
  }

hmmm, nie wiem jak kombinację uzyskać...?
skopiować tabele następnie wykonać rekurencje...?

Może zamiast mało zrozumiałych przykładów podaj definicje równoważnika tablicy.

tablica ma random ilości indexów oraz random wartości. Należy podzielić tak tablicę , aby suma po prawej stronie i po lewej była identyczna. Jedna wartość nie może należeć do żadnej ze stron .

tak jak tu:

tab[1] 3
tab[2] 1
tab[3] 6
tab[4] 8
tab[5] 8

wynik:
prawa część tablicy:
tab[1] 3
tab[3] 6 : suma będzie 9

tab[5] 8 --- to będzie równoważnik

lewa część tablicy:
tab[2] 1
tab[4] 8 : suma będzie 9

metoda powinna zwrócić wartość 8 lub index czyli 5 lub 4

  public int obliczTablice_rownowagi(int[] tab, int n) {
 
        Random generator = new Random();
        n = generator.nextInt(10);
        tab = new int[n];
        int n_tab = generator.nextInt(10);
        for (n_tab = 0; n_tab < tab.length; n_tab++) {
            tab[n_tab] = generator.nextInt(10) + generator.nextInt(10) * (-1);
            System.out.println(" tab[i] " + tab[n_tab]);
 
            suma = suma + tab[n_tab];
            int[] t2 = Arrays.copyOfRange(tab, 1, tab.length);
        }
   return 1;
  }

Jaka powinna być odpowiedź dla tablicy dwuelementowej {3,4}?

czy mamy znaleźć element taki, że suma leżących na lewo równa jest sumie leżących na prawo?, to można zrobić O(n)
czy też znaleźć element taki że resztę da się podzielić na dwie grupy o identycznej sumie?

Zajrzyj może tu: http://en.wikipedia.org/wiki/Partition_problem.

Czy mnie się wydaje, czy założenia zadania są sprzeczne? Jeżeli przestawienia będą dopuszczalne to złożoność obliczeniowa nie będzie O(n) tylko O(n!*n) przynajmniej przy łopatologicznym algorytmie sumującym elementy i sprawdzający czy któryś nie spełnia warunków

z pomocą braciszka , kod przedstawia się następująco:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package zadanie;

import java.util.Random;

/**
 *
 * @author Ola
 */
public class Tab_row {

    /**
     * @param args the command line arguments
     */
    private int[] A;
    private int N;

    public Tab_row() {
    }


    public int Tab_rownowagi(int[] A) {
        Random generator = new Random();
        int wynik = 0;
        N = generator.nextInt(10);
        System.out.println("N:" + N);
        A = new int[N];
        int suma = 0;
        int sumaLewa = 0;
        int sumaPrawa = 0;
        for (int i = 0; i < N; i++) {
            A[i] = generator.nextInt(10) - 5;
            System.out.println("tab[" + i + "]:" + A[i]);
            suma += A[i];
        }
        System.out.println("suma:" + suma);
        System.out.println("Algorytm 1");

        for (int P = 0; P < N; P++) {
            sumaLewa = 0;
            sumaPrawa = 0;
            for (int j = 0; j < N; j++) {
                if (j < P) {
                    sumaLewa += A[j];
                }
                if (j > P) {
                    sumaPrawa += A[j];
                }
            }
            if (sumaLewa == sumaPrawa) {
                System.out.println("sumaLewa:" + sumaLewa);
                System.out.println("sumaPrawa:" + sumaPrawa);
                wynik = 0;
                System.out.println("P:" + P);
            }
        }

        sumaLewa = 0;
        sumaPrawa = suma;
        int tmp;
        System.out.println("Algorytm 2");
        // start = System.nanoTime();
        for (int P = 0; P < N; P++) {
            tmp = A[P];
            if (sumaLewa == sumaPrawa - tmp) {
                System.out.println("P:" + P);
                wynik = 0;
            } else {
                sumaLewa += tmp;
                sumaPrawa -= tmp;
                wynik = -1;
            }
        }
        return wynik;
    }

    public static void main(String[] args) {
        // TODO code application logic here
        Random generator = new Random();
        int n = generator.nextInt(10);
        int[] tab = new int[n];
        Tab_row d = new Tab_row();
        d.Tab_rownowagi(tab);

    }
}

:) :) :) :)

kasiaKasia napisał(a):

z pomocą braciszka , kod przedstawia się następująco:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
    }
}

:) :) :) :)

And now - follow the white rabbit!