Forum 1 Grupy Ćwiczeniowej

fala (aka tomek)

Co do n! i n^n nie będę się kłócił bo nie mam pewności, jednak metodą "na kalkulator" n^n wychodzi znacznie większe niż n! (np dla 8 Razz

)
7. trzeba podać tylko chyba po 1 przykładzie więc aby było Smile

9. algorytm permutujący czyli w sumie chodzi chyba tylko o poprzestawianie kolejności elementów w tablicy, więc wrzucanie na drzewo odpada, chyba wystarczy to jakoś posortować tak żeby A[i]>A[2i] i A[i]<A[2i+1]
10. 2-3 drzewa to są takie drzewa które mogą mieć 2-3 potomków (więcej nic o nich nie wiem Razz

ale przykładowe drzewko i chyba dobre rozwiązanie znajduje się w skanach od Linki)
19. a czy tutaj nie będzie to przypadkiem koszt n? tak jak w skanach? no bo sortowanie leci tylko dla n/2 elementów (n/2 * 2 = n), a potem wyszukiwanie robimy dla n/2 elementów i potem znów dla n/2 elementów. Więc n/2 + 2*(n/2) = n/2 + n = O(n)

Faktycznie BST było na ćwiczeniach po 2gim kole... Ma ktoś może to przepisane? Było by miło jakby ktoś taki się znalazł Smile

Więcej z tych zadań jak narazie nie wykombinowałem... ale i tak jest nieźle Wink

dziemian_rec

a n! rzeczywiście jest mniejsza, choć koszalew w swoim skrypcie dała ją na koniec :/
19. zakres zadania to 2n a nie n
pani Edytka:
ktoś wie jak w zad1. posortować tablicę kolumnami ?

eewkaa

co do 19.
tak dokładnie to koszt wynosi: 3/2n-2
I w tym przypadku nie ma szybszego algorytmu.

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

n! < n^n -> z jakichs notatek;]

fala (aka tomek)

A może ktoś wie co z tymi algorytmami w zadaniach 12, 13, 16, 17 ? Bo ja jakieś tam pomysły do 12 i 16 podałem, ale czy one są prawidłowe to nie mam pojęcia, może ktoś umiał by to zweryfikować?

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

17 zadanie jest z gwiazdka, wiec mnie nie dotyczy;]

PS. Sinus, cosinus.. daj Boże trzy minus.. Wink

To co mowiliscie o zadaniu z kola - kod sprawdzajacy, czy drzewo binarne jest BST.. (odnośnie zad Cool

W notatkach znalazłam tylko to co ponizej, ale nie jestem pewna czy dobrze spisałam i czy wszystko...

fala (aka tomek)

No wszystko ładnie, tylko że to ma być algorytm sprawdzający tablicę a nie drzewo... Więc niestety ale z takiego "gotowca" to się nie uda skorzystać Smile

Na dobrą sprawę dla BST to wystarczy tylko tyle żeby przy przeglądaniu inorder powstawał ciąg rosnący, prawda?

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

masz racje...

dziemian_rec

zadania 16 i 17 można zrobić wykorzystując algorytm magicznych piątek
ale jak to dokładnie działa to nie mam pojęcia Neutral

[link widoczny dla zalogowanych]

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

na wiki jest praktycznie opisane zadanie 16.. a co z 17? magiczne 7 czy co? Very Happy

dziemian_rec

a tak w ogóle to na co Dańko przychylniej patrzy: kod, pseudo czy słownie ???

czart

Właśnie, jak myślicie, algorytmy pisać słownie bardziej ? Czy 101% kodu ?

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

jak juz gdzies wyzej pisalam to dla niego nawet lepiej jak jest opis słowny (ktos chodzil sie pytac o cos do niego i podobno on tak powiedzial) Wink

boro

miła wiadomość :)

Frombehind

W tych skanach sa bledy przy zadaniach z BST. Problem jest identyczny jak na kolokwium, trzeba sprawdzic czy kolejne elementy na drzewie z lewej strony maleja, a z prawej rosnal. Czyli trzeba posortowac tablice na pozycjach niepazystych rosnaca, a na pozycjach pazystych malejaco, wtedy jest 100% pewnosci ze jest to BST. Czyli jak w zadaniu 9 mamy gotowa tablice drzewa binarnego, wystarcza 2 sortowania. Innego pomyslu nie mam.

Zadanie 3 - kazdy robi je sortowaniem przez zliczanie, tlyko ciekawe gdzie jest podany zakres wartosci ?

P.S. Miazga, przy pseudo kodzie albo opisie slownym mozna lac wode i pozniej doszukiwac sie ukrytego sensu juz po sprawdzeniu prac i klucic sie o dodatkowe pkt Very Happy