Forum 1 Grupy Ćwiczeniowej

Frombehind

A moze skrzynke wodki mu kupic ? i zeby zaplacil czekami o nominale 3 Smile

albo in blanco Twisted Evil

czart

można
albo taką dużą rozkladana gazete zeby mial co poczytac na egzaminie

dziemian_rec

hehe czemu nie Smile

i 0.5 za każde pół oceny w górę

a z gazety chyba by się tak nie ucieszył... chyba że taka rozkładana rozkładana ^^

Frombehind

Nigdy nie mialem przyjemnosci byc na wykladzie u niego, ale slyszalem ze gapi sie ciagle w podloge. Ciekawe czy nie zmienia nawykow podczas egzaminu Wink

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

oparte na:
[link widoczny dla zalogowanych]

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).
6. sqrt(n), ln(n!), ln(n^n), n*lg3(n), n*lg2(n), n^2, 2^n, n!, n^n

7. identyczne: sortowanie przez wstawianie (n^2) sort przez zliczanie też ma równe koszty
różne: quicksort (pesymistycznie n^2, średnio n*log(n))

zad. 8 chyba dobrze

int kopiecA(int* TAB, int N, int i){
int k=2*i, l=k+1;

if((k>N)&&(l>N)) return 1;
else if ((k<=N)&&(TAB[i]<TAB[k])) return 0;
else if ((l<=N)&&(TAB[i]<TAB[l])) return 0;

return kopiecA(TAB,N,k)*kopiecA(TAB,N,l);
}

int kopiecB(int* TAB, int N){
int k,l;
for(int i=1;i<=N;i++){
k=2*i , l=k+1;
if(k>N)return 1;
else if(TAB[i]<TAB[k]) return 0;
else if(l>N) return 1;
else if(TAB[i]<TAB[l]) return 0;}
}

9. trzeba taki sam warunek zachować jak w rozwiązaniu 8b ... 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
11. wydaje mi się że dokładniejszym rozwiązaniem będzie podwójne zliczanie, da od razu gotowy wynik, a koszt będzie rzędu n (chyba że się mylę)

12. znaleźć minimum (lub maximum) z Hoare'a i potem sortowanie przez zliczanie dla (max/min + dane m) elementów (nie wiem czy jest to poprawne rozwiązanie)

16. algorytm Hoare'a dla 3ciego w kolejności elementu (?) (w średnim przypadku Hoare ma złożoność O(n) więc zgadzało by się, ale dla pesymistycznego jest (n^2), więc nie jestem pewien)
*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"
14.nie
15.nie : 1,2,3,4,5,6
18.nie
19.tak, koszt 3n. szybciej chyba sie nie da
* 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)
*tak dokładnie to koszt wynosi: 3/2n-2

fala (aka tomek)

NO gazete to można mu jakąś kupić, chociaż słyszałem że na egzaminy to przychodzi ze swoją gazetą ;P
Co do zbierania rozwiązań to może lepiej zebrać je gdzieś oddzielnie, a potem wkleić za jednym zamachem...

Jeśli chodzi o Hoare'a to on ma złożoność dokłądnie taką samą jak QuickSort, w wypadku pesymistycznym jest to n^2, w przypadku średnim jest to n. Ulepszona wersja Hoare'a (ta z 5tkami ma złożoność zawsze n, co jest nawet udowodnione w linku z wikipedii)
[url]http://pl.wikipedia.org/wiki/Algorytm_magicznych_piątek[/url]

Tutaj jest to lepiej rozpisane i jak dla mnie jaśniej to wygląda
[url]http://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Selekcja[/url]

Czy ktoś ma jakieś zastrzeżenia do powyższych rozwiązań? Bo szczerze powiedziawszy ja nie jestem w 100% pewien ich poprawności.

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

ja rowniez nie mam 100% pewnosci;]

vbazyl

7. quicksort średni koszt to n*log(n)

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

zgadza sie:) poprawione juz:)

fala (aka tomek)

Faktycznie, mój błąd. Chociaż gdzieś jak czytałem o tych algorytmach to coś takiego mi wpadło w oko...

Frombehind

Wlasnie przeczytalem o magicznych piatkach (link do wazanika od fali) i jak mozna robic opis slowny to to luzik Smile

bede nawijal makaron na uszy, algorytm latwy w zrozumieniu jak ktos kapuje Hoare i calkiem latwy w opisaniu, troche gorzej z implementacja, ale jako ze nie trzeba jej pisac ...

Roberto

Czyli jak..mozna kartki wyjac u niego na egzaminie jako małą pomoc;P?

dziemian_rec

móc zawsze można, tylko umiejętnie Wink

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

hehe, oby bylo jak na egzaminie z analizy:) ^^ Very Happy

fala (aka tomek)

Jak narazie to ja tylko na równaniach różniczkowych spotkałem się z takim trickiem że można było mieć notatki na kole (na egzaminie u chyba popiołka były to kserówki odpowiedzi ze zbiory zadań, bo książek nie można było mieć Razz

)
A tutaj to różne wersje słyszałem, jedni mówią że można, inni że nie można... ja tam się przygotuje z pomocami, zawsze to coś się zapamięta w trakcie przygotowań