[Algorytmy] Czy relacja jest przechodnia

adambak · Post autor: **adambak** » 27 lis 2011, o 17:40

Mam ciekawe zadanko.. Otóż na wejście podawane są uporządkowane pary liczb oznaczające elementy w relacji, a ja muszę stwierdzić jaka ta relacja jest: zwrotna, przeciwzwrotna, symetryczna, antysymetryczna, przechodnia, spójna.. na koniec podsumować czy będzie to relacja równoważności, częściowego porządku czy liniowego porządku, czy oczywiście żadna z nich.. mam problem z przechodniością i domyślam się, że trzeba to zrobić jakoś grafowo, jednak od już długiego czasu nie wiem jak to ugryźć.. elementów będzie napewno mało(i będą to małe liczby), więc jeśli to pomoże to macierz sąsiedztwa spokojnie zmieści się w pamięci, a kwadratówka wystarczy.. jakieś pomysły?

Zordon · Post autor: **Zordon** » 27 lis 2011, o 20:16

Kod: Zaznacz cały

FOR(i,n) FOR(j,n) FOR(k,n) if (r[i][j] && r[j][k] && !r[i][k]) return false;
return true;

edit: to co tu było wcześniej może być fałszywe ;d

adambak · Post autor: **adambak** » 27 lis 2011, o 20:22

Powaga? a ja tyle się nasiedziałem głowiąc się nad tym jak zejśc niżej, bo przecież nie przepchnę tego widać, źle że nie spróbowałem.. kwadratówka (jeśli jest, bo nie wiem) chyba nie jest trywialna.. nie widzę sposobu jak obejść sprawdzanie wszystkich trójek..

PS gratuluję super wyniku na PA!

Zordon · Post autor: **Zordon** » 27 lis 2011, o 20:38

Nie da się jednak w \(\displaystyle{ O(n^2)}\), przynajmniej ja nie umiem ;d.

PS gratuluję super wyniku na PA!

dzięki, miejsce niby wysokie, ale zadań to powinienem był więcej zrobić

abc666 · Post autor: **abc666** » 27 lis 2011, o 21:14

Taki luźny pomysł.

Mamy 3 mapy setów. Dla każdej pary \(\displaystyle{ (a,b)}\) do pierwszej mapy pod kluczem \(\displaystyle{ a}\) dodajemy do setu \(\displaystyle{ b}\), w drugiej pod kluczem \(\displaystyle{ b}\) dodajemy \(\displaystyle{ a}\), w trzeciej pod kluczem \(\displaystyle{ a}\) dodajemy \(\displaystyle{ b}\) oraz elementy z drugiej mapy spod klucza \(\displaystyle{ b}\) pomijając \(\displaystyle{ a}\). Po przetworzeniu tak wszystkich par sprawdzamy czy pierwsza mapa jest taka sama jak trzecia.

Chociaż w sumie nie wiem czy to jest poprawne.

Zordon · Post autor: **Zordon** » 27 lis 2011, o 21:59

Domyślam się mniej więcej jak to ma działać, ale to wygląda na \(\displaystyle{ O(n^3\cdot log(n))}\).

adambak · Post autor: **adambak** » 27 lis 2011, o 22:21

ja tak średnio kumam.. czy chodzi o to, że w tym algo składasz tą relację samą ze sobą? bo też mi to chodziło po głowie.. z tym, że boję się w takim podejściu o poprawność bo z tego co wiem to:

\(\displaystyle{ r \text{ jest przechodnia } \Leftrightarrow r\cdot r \subseteq r}\)

a więc będzie trzeba sprawdzać nie do końca równość, ale zawieranie.. choć to mała zmiana, do przeżycia..

jeśli w ogóle o to chodzi, bo jak mówię średnio skumałem

abc666 · Post autor: **abc666** » 28 lis 2011, o 01:35

W sumie nieważne bo to nie działa w ogóle ;p Raczej dam sobie spokój z tym bo Zordon ma racje chyba z tym, że się nie da kwadratowo zrobić.