Matematyka.pl

Czyżby to zadanie: ? W opracowaniu XVIII Olimpiady Informatycznej (tzw. "niebieskiej książeczce"), dostępnym na stronie Olimpiady, jest to dość dobrze przedyskutowane.

Pana źródło przestrzeliło o 3 punkty Wygrał Karol Farbiś z Radomia, Świstak jest drugi i oczywiście jedzie na IOI. Może powinien sobie odpuścić IMO

Poeksperymentuj z potęgami. Na przykład wartość = stały współczynnik * (umiejętność)^2. Albo do trzeciej potęgi.

Będziesz musiała w Eli zaimplementować rekurencję - wiesz, jak? Bo ja nie
Trzeba również dokładniej zapisać, w jaki sposób przestawiasz mniejsze elementy na lewo, większe na prawo - to jest dobrze zapisane np. na Wikipedii.

Mniej-więcej dobrze. Tylko jeszcze dwie rzeczy: trzeba zapisać algorytm przestawiania elementów, oraz zrozumieć, co to jest rekurencja

Ha, tu jest pewne zderzenie poważnej algorytmiki (QuickSort) z niepoważnym ujęciem (Eli). Mało kto tłumaczy algorytmy w ten sposób. Spróbowałbym z książką "Algorytmy" - Dasgupta, Papadimitriou, Vazirani. Nie jest aż tak prosto, żeby były schematy blokowe, ale jest po amerykańsku łopatologi...

Algorytm działa dla dowolnego ciągu. Z przeniesieniem nie powinno być problemu. Tak naprawdę procedurę "mieszającą" możesz przepisać wprost bez dokładnego zastanawiania się - to jest jedna pętla. Ale musisz dokładnie zrozumieć kiedy, dlaczego i na czym wywołuje się rekursję.

Oj, nie tak. Nic nie ma o tym, że dzielimy na pół. Dzielimy na dwie części, na ogół zupełnie nierówne. To, jakie te części będą, okazuje się - uwaga - dopiero na końcu! Zależy to od wyboru elementu dzielącego. A ten z kolei wybieramy na ogół przypadkowo - w niektórych implementacjach jest to element...

Uwaga na kolejność! Najpierw wybieramy element dzielący, potem mieszamy tablicą (małe na lewo, duże na prawo), a na końcu zastanawiamy się, jak ją podzielić (na ogół nierówno). Na przykład Twoja tablica: 7 5 8 10 1 15 12 4 11 19 1 Wybieramy element dzielący, niech to będzie pierwszy od lewej (7). Mi...

Tak, po podziale tablica będzie wyglądała jakoś tak:

7 5 8 10 1 1 12 4 19 15

i podzieli się nierówno (lewa tablica 7 ... 4, prawa: 19 15) . Taki urok tego algorytmu

Tak, dobrze. Tylko jeszcze istotna kwestia: quicksort musi bardzo odpowiednio podzielić ten ciąg na dwa. Wybiera sobie jakiś element X (na przykład pierwszy od lewej), po czym tak "miesza" tablicą, żeby elementy mniejsze od X znalazły się po lewej stronie tablicy, a elementy większe po pra...

No to od początku: czy wiesz, co to jest QuickSort, do czego służy i jak działa?

Nie znam środowiska Eli (i uważam je za skrajnie pokopany pomysł dla jakichkolwiek ludzi starszych niż gimnazjum), ale chyba umiem zdiagnozować problem: nie możesz "znaleźć w internecie i przenieść". Konieczne jest zrozumienie, jak działa quicksort: wybór elementu dzielącego, przestawienie...

Hm. A nie jest bardzo łatwo zrobić funkcję niewielomianową, dla której \(\displaystyle{ f(x) = f(x+1)}\)? Jakiś sinus czy coś?

Rekursja. Pierwszy element musi być korzeniem (w końcu to preorder), a po nim musi nastąpić najpierw lewe podrzewo, a potem prawe. Na obu należy osobno wywołać rekursję, tylko jak odróżnić, gdzie kończy się lewe, a zaczyna prawe? Pomyśleć o własności BST Uwaga do mojego poprzednika: Twój post wygląd...