Algorytm tablica jednowymiarowa

0

witam

http://4programmers.net/Forum/Algorytmy/136541-algorytm_tablica_jednowymiarowa

był już taki temat jednak po przeanalizowaniu ostatniego postu od Shalom'a próbowałem sam zapisać ten algorytm i okazuje się, że on zakłada, że punkt podziału wypada w środku tablicy a może się okazać, że punkt podziału jest gdzie indziej
czy może ktoś już próbował rozwiązać to inaczej?
z programowaniem dopiero zaczynam więc proszę o pseudokody

dzięki za pomoc

0

Bzdury gadasz. Punkt podziału może być i taki że masz 1 liczbę z jednej strony z całą resztę tablicy z drugiej. Nie umiesz czytać ze zrozumieniem.

0

hehe :) spoko jeszcze raz no to spojrze

0

Przykład:
tablica = {10,1,3,3,3}
suma = 0
lewy_index = 0
prawy_index = 4
Zaczynamy iść od lewej, dodajemy od sumy aktualną wartość z lewej strony więc suma jest 10, przesuwamy sobie lewy index w prawo. Suma jest większa od 0 więc idziemy z prawej i odejmujemy kolejne liczby, przesuwając się w lewo aż suma nie spadnie do 0. Odejmujemy kolejno 3, 3, 3 i wreszcie 1 i suma spadła do 0. Jednocześnie index prawy oraz lewy się "zeszły" więc algorytm się zakończył. Suma wynosi 0 więc punkt podziału istnieje i jest nim index 1.

0

ok dzięki
to już zamyka temat

0

witam

niestety temat wraca

algorytm nie działa dla liczb ujemnych
np. dla tablicy [-1 -1 -1 -1] widać, że punkt podziału jest po drugim elemencie a algorytm tego podziału nie znajdzie

proszę o pomoc bo może znowu coś źle zrozumiałem

0

o_O Przecież z opisu tego algorytmu od razu widać że nie będzie on działał w sytuacji kiedy sumarycznie liczby w tablicy sumują się do ujemnej wartości. Ale tak na oko, to możesz sobie to sprawdzić na początku sumując wszystko i jak wyjdzie ci liczba ujemna to możesz sobie zmienić wszystkie znaki przy liczbach na przeciwne ;]

0

Tylko ze mam stworzyc prosty algorytm w pseudokodzie wiec dodawanie takich warunkow strasznie utrudni sprawe. Moze jakies inne rozwiazanie?

1

Zsumuj wszystkie liczby. Potem licz sumy częściowe (pierwsza liczba, pierwsze dwie,...). Jeżeli pewna suma częściowa jest równa połowie sumy całkowitej to masz rozwiązanie.

0

Ale w takim razie nie szukasz algorytmu optymalnego? No to co za problem ->

  • sumujesz wszystkie liczby w tablicy
  • dzielisz tą sumę na pół
  • lecisz od jednego końca i sumujesz kolejne liczby aż suma wyniesie tyle ile pół sumy całej tablicy -> to będzie punkt podziału
    Jak dojdziesz do końca tablicy to znaczy że się nie da.

Taki algorytm działa dla dowolnych danych wejściowych, ale jest 2x wolniejszy niż ten o którym rozmawialiśmy wcześniej.

0

Wlasnie ma dzialac dla dowolnych liczb calkowitych. Spojrze jeszcze na to wieczorem bo na razie to wykladowca mnie sprowadzil na ziemie z tym rozwiazaniem.

1 użytkowników online, w tym zalogowanych: 0, gości: 1