Witam,
Potrzebuje koncepcji na wyznaczanie liczby par nieuporzadkowanych w zbiorze, tak ze:
mamy zbior np \(\displaystyle{ 5, 3, 4, 2, 1,6,}\) wiec pary nieuporzadkowane to \(\displaystyle{ (5, 3), (5,4), (5,2), (5,1), (3,2), (3,1), (4,2), (4,1).}\) Musze do tego wykorzystac technike rekurencyjna "dziel i zwyciezaj". Probowalem to zrobic poprostu je sortujac, ale quicksort i megresort nie pokazuja liczby inwersji, to dziala na troche innej zaszadzie jak sie przekonalem...
[Algorytmy] Wypisz liczbe par
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Wypisz liczbe par
napisanie:
słuszna intuicja, jak najbardziej można to zrobić MergeSortem (quicksortem już nie).. wystarczy drobna modyfikacja na etapie scalania dwóch posortowanych tablic.. praca na 5 linijek, aczkolwiek zdaję sobie sprawę, że mogą one sprawiać sporą trudność.. jak już się wpadnie to wydaje się banalne..
polecam prześledzić MergeSort dla małego ciągu na kartce i zobaczyć jak sortuje i gdzie powinien zliczać te inwersje, aby było dobrze i dlaczego to będzie dobrze..
powodzenia
-- 23 paź 2011, o 17:00 --
w wypisanych przez Ciebie parach brakuje jeszcze \(\displaystyle{ \left( 2; 1\right)}\)
jest o tyle niefortunne, że jak zdefiniujesz pary nieuporządkowane w zbiorze? napewno nie będzie to tym o co pytasz, bo w napisanym przez Ciebie "zbiorze" liczy się kolejność.. w ten sposób ciężko jest zrozumieć o co Ci chodzi, ale znam ten problem algorytmiczny, więc skumałem.. ja bym to nazwał ciągiem..paewel pisze:Witam,
mamy zbior np \(\displaystyle{ 5, 3, 4, 2, 1,6,}\)
słuszna intuicja, jak najbardziej można to zrobić MergeSortem (quicksortem już nie).. wystarczy drobna modyfikacja na etapie scalania dwóch posortowanych tablic.. praca na 5 linijek, aczkolwiek zdaję sobie sprawę, że mogą one sprawiać sporą trudność.. jak już się wpadnie to wydaje się banalne..
polecam prześledzić MergeSort dla małego ciągu na kartce i zobaczyć jak sortuje i gdzie powinien zliczać te inwersje, aby było dobrze i dlaczego to będzie dobrze..
powodzenia
-- 23 paź 2011, o 17:00 --
w wypisanych przez Ciebie parach brakuje jeszcze \(\displaystyle{ \left( 2; 1\right)}\)
-
- Użytkownik
- Posty: 38
- Rejestracja: 7 lut 2010, o 11:46
- Płeć: Mężczyzna
- Lokalizacja: Białystok
- Podziękował: 12 razy
[Algorytmy] Wypisz liczbe par
Przepraszam za nieprecyzyjnosc, rzeczywiscie jest to ciag.
Z tym ze nie mam pojecia jak zastosowac ten algorytm, on przeciez porownuje kolejne elementy tablic i nie sposob pokazac ile elementow bylo od niego wiekszych.
Z tym ze nie mam pojecia jak zastosowac ten algorytm, on przeciez porownuje kolejne elementy tablic i nie sposob pokazac ile elementow bylo od niego wiekszych.
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Wypisz liczbe par
ale znasz dobrze MergeSort? bo to będzie tutaj podstawa.. właściwie to drobna jego modyfikacja.. naprawdę spróbuj zobaczyć na kartce w kolejnych krokach jak to by można wpleść w MergeSorta.. posortujmy tym algorytmem dany przez Ciebie ciąg \(\displaystyle{ 5, 3, 4, 2, 1,6}\)..
jak każdy typu "dziel i zwyciężaj" najpierw schodzi do jak najniższego poziomu problemu, czyli w tym przypadku - scalania ze sobą tablic (lewa, prawa) jedno elementowych.. będziemy mieli podczas scalania kolejno takie sytuacje:
1.
2.
3.
postaraj się coś zauważyć.. za każdym razem kiedy scalamy lewą i prawą tablicę w jedną (a więc jest to pewien etap MergeSorta) mamy w lewej tablicy elementy, które w wejściowym ciągu są przed elementami w prawej tablicy.. to, że na danym etapie lewa i prawa tablica są posortowane nic nam nie psuje, a wręcz przeciwnie - ułatwia.. nic nie pomijamy, bo zgodnie z zasadą "dziel i zwyciężaj" zaczynamy od najmniej złożonych tablic z których każda jest jedno elementowa.. pójdź po krokach 1,2,3 które napisałem i zlicz inwersje w parach w których pierwszy element bierzemy z lewej tablicy, a drugi z prawej.. wychodzi 9 inwersji, czyli się zgadza.. ja bym żeby ułatwić sobie życie dał na zliczanie inwersji zmienną globalną, będzie łatwiej na początku..
ale zacznij od napisania dobrego MergeSorta bo bez tego ani rusz.. potem staraj się zmienić etap scalania aby zliczał inwersje tak jak ja wyżej..
powodzenia
jak każdy typu "dziel i zwyciężaj" najpierw schodzi do jak najniższego poziomu problemu, czyli w tym przypadku - scalania ze sobą tablic (lewa, prawa) jedno elementowych.. będziemy mieli podczas scalania kolejno takie sytuacje:
1.
Kod: Zaznacz cały
lewa[]=5; prawa[]=3;
Kod: Zaznacz cały
lewa[]=4; prawa[]=2;
Kod: Zaznacz cały
lewa[]=1; prawa[]=6;
Kod: Zaznacz cały
lewa[]=3,5; prawa[]=2,4;
Kod: Zaznacz cały
lewa[]=2,3,4,5; prawa[]=1,6;
postaraj się coś zauważyć.. za każdym razem kiedy scalamy lewą i prawą tablicę w jedną (a więc jest to pewien etap MergeSorta) mamy w lewej tablicy elementy, które w wejściowym ciągu są przed elementami w prawej tablicy.. to, że na danym etapie lewa i prawa tablica są posortowane nic nam nie psuje, a wręcz przeciwnie - ułatwia.. nic nie pomijamy, bo zgodnie z zasadą "dziel i zwyciężaj" zaczynamy od najmniej złożonych tablic z których każda jest jedno elementowa.. pójdź po krokach 1,2,3 które napisałem i zlicz inwersje w parach w których pierwszy element bierzemy z lewej tablicy, a drugi z prawej.. wychodzi 9 inwersji, czyli się zgadza.. ja bym żeby ułatwić sobie życie dał na zliczanie inwersji zmienną globalną, będzie łatwiej na początku..
ale zacznij od napisania dobrego MergeSorta bo bez tego ani rusz.. potem staraj się zmienić etap scalania aby zliczał inwersje tak jak ja wyżej..
powodzenia
-
- Użytkownik
- Posty: 38
- Rejestracja: 7 lut 2010, o 11:46
- Płeć: Mężczyzna
- Lokalizacja: Białystok
- Podziękował: 12 razy
[Algorytmy] Wypisz liczbe par
Ok, rozumiem juz, bardzo dziekuje za pomoc, bede to robil gdzies w przyszlym tygodniu, ale teraz wiem jak sie za to zabrac. Dzieki jeszcze raz i pozdrowienia