Algorytm tablica jednowymiarowa

Odpowiedz Nowy wątek
2014-12-12 13:58
Maciek_P
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

Pozostało 580 znaków

2014-12-12 15:06
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.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2014-12-12 15:12
Maciek_P
0

hehe :) spoko jeszcze raz no to spojrze

Pozostało 580 znaków

2014-12-12 15:20
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.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2014-12-12 15:23
Maciek_P
0

ok dzięki
to już zamyka temat

Pozostało 580 znaków

2014-12-20 13:21
Maciek_P
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

Pozostało 580 znaków

2014-12-20 13:26
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 ;]


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2014-12-20 13:39
Maciek_P
0

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

Pozostało 580 znaków

2014-12-20 14:10
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.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2014-12-20 14:10
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.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

2014-12-20 14:21
Maciek_P
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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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