ASD - Algorytmy i struktury danych

[Izane]

Cześć, nie wiedziałem gdzie się zwrócić z pomocą to może tutaj:


Mam następujące zadania do rozwiązania z ASD i jako tako to rozumie ale chciałbym wiedzieć profesjonalniej jak to wykonać, co musi zawierać... w sensie chce się upewnić czy dobrze to rozumie i czy wszystko co trzeba do zadania umię (a wiem że nie )

zad 1
Napisz funkcję oraz zdefiniuj odpowienie typy, która dla listy elementów typu byte, reprezentowanego poprzez wskaźnik wpocz (parametr funkcji) wyznacz średnią arytmetyczną wartości elementów znajdujących się w liście-wynik funkcji.
Jeżeli lista jest pusta to funkcja zwraca wartość -1.


Zad 2
Dla algorytmu sortowania tablicy n-elementowej (A(n) opisanego poniżej wylicz czasową złożoność obliczeniową:
Begin
for i:=n down to 2 do
w tablicy A[1..i] znajdź pozycję elementu maksymalnego;
Zamień miejscami el. maksymalny z elementem z pozycji i;
end for;
end.

Zad 3
co to jest drzewo BST i ile może mieć najmniej/najwięcej poziomów takowe drzewo n elementowe.

(to raczej pestka gogole wujek )

Zad 4
zdefiniuj typ(y) do obsługi listy dwukierunkowej typu byte



Z góry dzięki za pomoc, najbardziej zależało by mi na zad 2 i 4.

Ale byle jakie zrobione dużo mi pomoże

Pozdrawiam

[kadiii]

Napisz najpierw swoje rozwiązania skoro sam piszesz, że mniej więcej wiesz jak je wykonać. Wykaż sie inicjatywą - na pewno ktoś ci pomoże w razie problemów.

[Izane]

No więc zad 2 należy po pseudo kodzie domyśleć się jakie to jest sortowanie w tym przykładzie jest to sortowanie (no właśnie nie wiem jakie) i trzeba wyliczyć czasową złożoność, niestety znam tylko wzory ogólne a jak je zastosować z danego pseudokodu nie wiem... czy wystarczy użyć ogólny wzór z danego sortowania czy coś jeszcze wyliczać z pseudokodu?


Zad 3 no to wiem że drzewo BST to dynamiczna struktura danych w postaci drzewa binarnego stosowanego do szybkiego wyszukiwania.
Jeśli chodzi o najwięcej i najmniej poziomów to najwięcej może mieć 3? (tutaj nie mam pewności) a najmniej 1? (też nie mam pewności)

zad 4

No właśnie, ogólnie nie umie zrozumieć typu byte na czym on względnie polega?
Wiem co to lista dwukierunkowa, jak po niej się "chodzi" oraz zastosować w pseudokodach np dodawanie elementu do takiej listy lub usuwanie wraz z przepinaniem wskaźników.
Niestety wszystko to co umię nie umię zastosować do tego pytania lub poprostu źle go czytam.

Jedyne co przychodzi mi do głowy na rozwiązanie to następujące typu:

type
w2l=^.e2l;
e2l=record
d: real
n,p: w2l;
end;

Czy to chodzi o to?


No i zadanie 1... niestety kompletnie nie mam pojęcia. Kombinowałem i na myśl przychodzi mi stworzenie pseudokodu który porusza się po "jakieś" liście (i tu problem bo nie wiem czy jedno-dwu kierunkowej czy cyklicznej) która przechodzi całą liste i zlicza sume arytmetyczną



Dziękuje za pomoc i przepraszam za brak inicjatywy ale jak widać cięzko mi idzie rozumienie tego dlatego napisałem ten temat

[kadiii]

Dobrze to po kolei:
1.Dobrze ci się wydaje - nalezy stworzyc kod, który przechodzi po liście i liczy średnią. Typ listy nie ma tu znaczenia - co zmieniłaby informacja o jej typie?
2.NIe ma potrzeby żebyś znał nazwe tego sortowania(znaczy sie na pewno warto, ale to już zostawię tobie jako krótki zadanie). W zadaniu masz pętlę czyli złozoność automatycznie rosnie n razy. Wewnątrz pętli szukasz elementu maksymalnego - jaką złożoność ma szukanie max w ciągu? Ogólnie mówiąc w nieformalnym skócie każda wewnętrzna petla powoduje zwiększenie złożoności n razy. Jaka jest więc złożoność.
3.A czemu nie 17 i 8? Masz drzewo n elementowe, więc odpowiedź musisz uzaleznić od ilości elementów. Jak będzie wyglądało maksymalne drzewo - czy będzie zrównoważone czy może przeciwnie? Jak powinno wyglądać drzewo o minimalnej ilosci poziomów. Do odpowiedzi na to pytania przyda się znajomość tworzenia drzewa BST - jest to rzecz bardzo prosta.
4.Pytanie jest mało precyzyjne - co to znaczy typy do obsługi?

[Izane]

Zad 1:

=pseudokod=
p = początek
b = bierzące wskazanie wskaźnika

Kod: Zaznacz cały

procedure zliczaj ( )

var
 x,i := integer;
 s:=real;
begin
 x:=0
 i:=0
 b:=p;
  if b<>NIL then
   Odczytaj daną liczbe i dodaj do X, i:=i+1;
   przestaw b na następny element w liście[jeśli istnieje];


 s:=x/i;
    else
    x:= -1;
  end if;
end.

(niestety nie wiem jak to zapisać) ponieważ na ćwiczeniach nigdy nie wyciągaliśmy danych z elementu oraz mieliśmy na początku już założone "typy" np dla listy dwukierunkowej następujące:

Kod: Zaznacz cały

type
 w2l=^.e2l;
 e2l=record
d: real 
n,p: w2l;
end;

i wtedy operowaliśmy na zadaniu np gdy było zadanie usuń z listy to:

Kod: Zaznacz cały

function usun2l(var b:w2l; var x:real)
var t:w2l
begin
usun2l=false
 if (b<>NIL) then
 t:=b^.p;
 if (t<>NIL) then 
 t^.n:=b^.n;
 t:=b^.n;
 if (t<>NIL) then 
 t^.p:=b^.p;
 x:=b^.d;
 t:=b;

if (b^.n<>NIL) then b:=b^.n
else b:=b^.p;
dispose(t);
usun2l:=true;
end if;
end.

Jeśli chodzi o informacje o tablicy to chodzi mi o to że pseudokod będzie się różnił dla tablicy jedno/dwu kierunkowej a cyklicznej która nie ma "głowy-ogona" więc ciągle kręci się w koło




Jeśli chodzi o zad 2 to:
jest to sortowanie przez proste wybieranie(wymiane,wole wstawianie) ma kilka różnych nazw? jestem tego prawie pewny tylko robiony od tyłu dlatego miałem problemy ze zgadnięciem

Szukanie elementu MAX ma złożoność hmm... i tak musi sprawdzić każdy element więc złożoność to będzie ilość elementów do sortowania inaczej "n".
Po znalezieniu i szukaniu kolejnego za każdym razem tablica nieposortowana do szukania elementu max będzie zmniejszała się o "n-1".

Przy optymistycznym założeniu będzie to poprostu n. (?) (chociaż w notatkach mam n-1)

Przy pesymistycznym będzie musiał za każdym razem przelecieć liste która będzie się zmniejszała o "n-1" cóż w notatkach mam to ukazane następująco:\(\displaystyle{ (Tpes(n)= 1+2+3...+n-2+n-1= \frac{ n^{2}-n }{2} * n}\)

ale sam niestety nie potrafię zrozumieć dlaczego

jeśli chodzi o złożoność średnią także nie mam pojęcia i nie mam jej w notatkach



Zadanie 3 już staram się bardziej opracować i napisać co się nauczyłem tylko chciałem już napisać aby pokazać co zrobiłem

Zadanie 4 niestety dokładnie takie pytanie przekazała mi osoba która dostała coś takiego na kolokwium z ASD widocznie musiała źle mi przekazać



EDIT:

Zadanie 3: więc troche poczytałem i już znam zasade takiego drzewa, jak się je buduje i kiedy jest zrównoważone a kiedy nie.

Jeśli dobrze zrozumiałem to najmniej poziomów może posiadać dwa i będą one zrównoważone.

Maksymalnie może mieć nieskończenie wiele ale będzie to niezrównoważone drzewo BST.


Czy tak?

[kadiii]

1. Widzę, że to takie tworzenie cudów bez podstaw u was A mi się średnio chce sie uczyć cię programować. Powiem tak - zadanie jest proste i dość standardowe. To jakiej listy użyjesz nie ma znaczenia - uzyjesz jedynie elementów odpowiednich do danej listy. Przeglądsz zawsze tak samo - po razie każdy element. Zobacz tutaj ... kierunkowa są proste operacje dla listy jednokierunkowej. Ostatnia operacja to wyświetlanie - zamiast wyświetlać można oczywiście dodawać wartość i na końcu policzyc średnią. Proste?
2. To nie jest sortowanie przez wstawianie - przez wybór owszem. Nie wiem w jakiej notacji potrzebujesz tę złozoność. Potrafisz wyznaczać złożoności. Żeby cię juz nie męczyć to złożoność to \(\displaystyle{ O(n^{2})}\). Jak ją wyznaczyć, jakim wielomianem przyblizyć?
3.Dobrze, że poczytałeś, na pewno sie przyda(nie zaszkodzi). Spróbuj teraz ułozyć w drzewo BST powiedzmy 15 elementów. A potem 20. Jak dlaej będzie problem to powymyślaj jeszcze inne liczby. Czy twoja odpowiedź była słuszna sam łatwo się przekonasz(no dobrze, podpowiem, że się myliłeś).
4. Może i dobrze powiedział - pewnie na wykładzie czy ćwiczeniach umówiliście się na daną interpretację tej treści.