[Algorytmy] Wypisz liczbe par

paewel · Post autor: **paewel** » 23 paź 2011, o 15:31

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...

adambak · Post autor: **adambak** » 23 paź 2011, o 15:53

napisanie:

paewel pisze:Witam,
mamy zbior np \(\displaystyle{ 5, 3, 4, 2, 1,6,}\)

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..

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)}\)

paewel · Post autor: **paewel** » 23 paź 2011, o 16:51

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.

adambak · Post autor: **adambak** » 23 paź 2011, o 17:16

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.

Kod: Zaznacz cały

lewa[]=5; prawa[]=3;

Kod: Zaznacz cały

lewa[]=4; prawa[]=2;

Kod: Zaznacz cały

lewa[]=1; prawa[]=6;

2.

Kod: Zaznacz cały

lewa[]=3,5; prawa[]=2,4;

3.

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

paewel · Post autor: **paewel** » 23 paź 2011, o 17:31

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