Forum 1 Grupy Ćwiczeniowej

dziemian_rec

eee nie wiem czy dobrze łapie ...
tzn jak mamy np taką tablicę:

8| 5|12| 4| 9| 7|11| 2| 6
-1--2--3--4--5--6--7--8--9

to mam posortować rosnąco pozycje: 1,3,5,7,9
a malejąco 2,4,6,8 ??

albo nie zrozumiałem albo to kiepski pomysł bo po tych operacjach tablica będzie wyglądała tak:
6 |7 | 8| 5 |9 |4 |11 | 2 |12 czyli źle :/

fala (aka tomek)

W zadaniu 3 podane jest że jest to tablica INTEGERów, a więc zakresem wartości jest INTEGER.
Po zliczeniu wystarczy sprawdzić czy jakaś wartość w tablicy się powtarza i jesli tak to mamy 1 (TRUE), a jeśli nie to 0 (FALSE).

Zad 16 równie dobrze można zrobić z algorytmem Hoare'a. Tylko teraz pytanie czy trzeba dla niego opisywać co ten algorytm robi, czy wystarczy opisać swoje rozwiązanie na zasadzie "do znalezienia największej wartości wykorzystyjemy algorytm Hoare'a" Razz

Jeśli chodzi o sprawdzenie czy to jest BST to faktycznie jest to bardziej złożony problem. Co do tego pomysłu z posortowaniem parzystych i nieparzystych pozycji to dziwnie to wygląda Razz

Ale zaraz sprawdzę czy to faktycznie tak działa.
Dziemian, czy jesteś pewien że ta tablica jest zła? Bo na mój pierwszy rzut oka to chyba właśnie jest dobrze... Ale zaraz jeszcze sam to będę sprawdzał.
EDIT: Faktycznie ta tablica "dziemianowa" wygląda nie za bardzo... Frombehind, może dasz jakiś przykład tak coby to zobrazować dokładniej?

Frombehind

Nie zrozumiales mnie do konca. Wejsciowa tablica jest zla. Wejsciowa tablica ma byc juz ustawiona T[i]> T[2*i] i T[i]<T[2*i+1]. Dopiero pozniej sortujesz.

dziemian_rec

heh jakby wejściowa tablica spełniała warunek T[i]> T[2*i] i T[i]<T[2*i+1]
to nie byłoby co robić Smile

problem właśnie jak ją do takiego stanu doprowadzić ...

Linka · Dołączył: 13 Mar 2007 Posty: 98 Przeczytał: 0 tematów Ostrzeżeń: 0/5

co do zad 16 i propozycji do rozwiazania algorytmem magicznych piatek..

z WIKI:
Algorytm magicznych piątek to algorytm rozwiązujący problem selekcji, czyli znalezienia k-tej co do wielkości spośród n liczb. Jest on oparty na prostszym algorytmie rozwiązującym ten sam problem, algorytmie Hoare'a.

czyli hoare'em;]

fala (aka tomek)

Ok, tylko zauważ że w zadaniu nie ma podanego tego warunku że tablica jest ustawiona zgodnie z warunkiem T[i] > T[2i] & T[i] < T[2i+1], tam jest podane tylko że jest to drzewo binarne, a w zwykłym drzewie binarnym przecież nie musi być spełniona taka nierówność że L < K < P
[link widoczny dla zalogowanych]
Więc niestety ale Twoje rozwiązanie zakłada duże uproszczenie zadania...

Ten algorytm z piątkami to jest nadal Hoare, tylko lekko zmodowany Wink

Frombehind

Qrde a jednak to sortowanie nie idzie.
Chodzi o to ze sam warunek T[i]> T[2*i] i T[i]<T[2*i+1] nie wystarczy. Bo przeslizgna sie bledy. Przyklad:
20 10 30 5 15 17 35
I to jest wlasnie problem z kolokwium.

Ustawienie elementow wedlug tego wzoru to zaden problem, gorzej jest sprawdzic czy elementy sa ulozone rosnaca i malejaco wzgledem korzenia.

fala (aka tomek)

Mając drzewo w postaci "drzewa właściwego" a nie jakiejś tablicy, problem jest w sumie prosty bo wystarczy przejrzeć in_order i jak jest ciąg rosnący i już sprawdzone jest, a jak zrobić to z tablicą to w sumie nie wiem...
Tutaj jest jakieś rozwiązanie tego problemu (na samym dole), tyle tylko że jest to rozwiązanie dla takiego "drzewa właściwego"
[link widoczny dla zalogowanych]

Linka - ja wiem że to tak troche chyba nie wypada prosić o to.. ale może mogła byś jakoś te rozwiązane do tej pory zadania co do których nie ma większych wątpliwości ogarnąć? Bo zrobił się już z lekka bałagan, a jako że jesteś z płci tej co to jakoś staranniej notatki ogarnia, to sądze że zrobisz to najlepiej Smile

Z góry dziękuję w imieniu wszystkich udzielających się i piszących jutrzejszy egzamin Smile

Frombehind

Hmm to zadanie 16 mi cos przypomina. Jak sie nie myle to szczuroskoczek(czyt. Borowska) mowila cos o tym na cwiczeniach z ASD. Jak mnie pamiec nie myli to trzeba uzyc zmodyfikowanego quicksorta, ktory nie sortuje, a tylko sprawdza. Zaraz sprobuje czegos poszukac o tym.

Edit:
Bladz, znalazlem to ale to algorytm Hoare.

dziemian_rec

to może łatwiejsze pytanie:
jak sprawdzić 8.b) B) ??

Linka, Linka, Linka Wink

mały doping zawsze się przyda

Frombehind

Identyczny problem jak z 9 .....

dziemian_rec

w 9 trzeba zaimplementować poprawne tworzenie, a tu tylko sprawdzić nierekurencyjnie więc może będzie łatwiej ...

fala (aka tomek)

Co do zadania z wyszukiwaniem elementów to ja mam wrażenie że już na 1szej stronie pisałem że do tego służy algorytm Hoare'a, i w międzyczasie się to kilka razy powtarzało (chociażby przy tej metodzie z "5tkami" która jest zmodyfikowanym Hoare'm)
A zadanie faktycznie było identyczne u szczuroskoczka, tyle tylko że trzeba było znaleźć element bodajrze 4-ty największy.
Moge przepisać zaraz kod który skoczek dawał na swoich kartkach bo mam to pod ręką jeśli ktoś byłby zainteresowany.

dziemian_rec

tylko że z tego co tu wyczytałem horae ma złożoność pesymistyczną n^2 ... czyli buba

Linka · Dołączył: 13 Mar 2007 Posty: 98 Przeczytał: 0 tematów Ostrzeżeń: 0/5

co mam zrobic? Very Happy

w jeden post wszystko co dotychcasz ustalone zostalo? Smile