Zárthelyi feladatok, és megoldásaik

1.      Zárthelyi feladat: 2002.02.18 12.00 óra  

A csoport:  Egész (típusú) tömbben a hárommal osztható elemek átlagának meghatározása. (Amennyiben nincs ilyen elem a tömbben, akkor 0-t adjon vissza a függvény. Megoldásra szánt idő: 2 perc)

Megoldás: ZH01A.Cpp

B csoport:  Valós (típusú) tömbben a pozitív elemek közül a legkisebb érték meghatározása. (Amennyiben nincs pozitív elem a tömbben, akkor a függvény -1-el térjen vissza. Megoldásra szánt idő: 3 perc)

Megoldás: ZH01B.Cpp

2.      Zárthelyi feladat: 2002.02.25 12.00 óra

A csoport:  Valós (típusú) tömb elemeinek varianciájának meghatározása (Megoldásra szánt idő: 3 perc)

Megoldás: ZH02A.Cpp

B csoport:  Egész (típusú) tömb elemeinek egymáshoz képesti távolságának meghatározása (Megoldásra szánt idő: 2 perc.)

Megoldás: ZH02B.Cpp

3.    Zárthelyi feladat: 2002.03.04 12.00 óra

      A csoport: Rendezzen növekvő sorrendben egy egész (típusú) tömböt a maximum kiválasztás módszerével. (Megoldásra szánt idő: 3 perc.)

      Megoldás: ZH03A.Cpp

B csoport:  Rendezzen csökkenő sorrendben egy valós (típusú) tömböt a buborék rendezés módszerével. (Megoldásra szánt idő: 2 perc.)

Megoldás: ZH03B.Cpp

4.      Zárthelyi feladat: 2002.03.11 12.00 óra

A csoport:  Készítsen egy olyan logikai függvényt, mely egy paraméterül kapott pozitív egész számról eldönti, hogy prímszám vagy sem. (Megoldásra szánt idő: 2 perc.)

Megoldás: ZH04A.Cpp

B csoport:  Valós típusú tömb átlagtól való abszolút eltérésének meghatározása (Megoldásra szánt idő: 3 perc.)

Megoldás: ZH04B.Cpp

5.      Zárthelyi feladat: 2002.03.18 12.00 óra

A csoport:  Kérje be egy adott intervallumba eső valós tömb értékeit. Írja le a teljes programot. (Megoldásra szánt idő: 8 perc.)

Megoldás: ZH05A.Cpp

B csoport:  Verem megvalósítása dinamikusan láncolt kétirányú listával. (Megoldásra szánt idő: 7 perc.)

Megoldás: ZH05B.Cpp

6.      Zárthelyi feladat: 2002.03.25 12.00 óra

      A csoport:  FIFO megvalósítása dinamikusan láncolt kétirányú listával. (Megoldásra szánt idő: 15 perc.)

Megoldás: ZH06A.Cpp

      B csoport:  Kétféle területszámoló eljárás azonos őssel és módosított virtuális metódussal. Az egyik metódus egy kör, még a másik egy négyzet területét számítja ki. Írja le a teljes programot. (Megoldásra szánt idő: 16 perc.)

Megoldás: ZH06B.Cpp

7.      Zárthelyi feladat: 2002.04.08 12.00 óra

      A csoport:  Rendezzen csökkenő sorrendbe egy valós tömböt a bináris keresőfa segítségével. Írja le a teljes programot. (Megoldásra szánt idő: 16 perc.)

Megoldás: ZH07A.Cpp

      B csoport:  Írjon olyan függvényt, mely egy valós tömb második legnagyobb elemét adja vissza. Írja le a teljes programot. (Megoldásra szánt idő: 15 perc.)

Megoldás: ZH07B.Cpp

8.      Zárthelyi feladat: 2002.04.15 12.00 óra

A csoport:  Készítse el a string osztály != összehasonlító operátorát. (Megoldásra szánt idő: 3 perc.)

Megoldás: ZH08A.Cpp

      B csoport:  Készítse el a string osztály <= összehasonlító operátorát. (Megoldásra szánt idő: 4 perc.)

Megoldás: ZH08B.Cpp

9.      Zárthelyi feladat: 2001.04.22 12.00 óra

      A csoport:  Készítse el a string osztály két konverziós konstruktorát, melyek közül az egyik konstruktor paramétere egy karakter, a másik konstruktor paramétere egy char* karakter tömb. (Megoldásra szánt idő: 3 perc.)

      B csoport:  Készítse el a string osztály = operátor felüldefiniálásait. (Megoldásra szánt idő: 4 perc.)

Megoldás: ZH09.Cpp

10.      Zárthelyi feladat: 2001.04.29 12.00 óra

        A csoport:  Készítse el a string osztály [] operátor felüldefiniálását. (Megoldásra szánt idő: 2 perc.)

        B csoport:  Készítse el a string osztály + operátor felüldefiniálását. (Megoldásra szánt idő: 3 perc.)

  Megoldás: ZH10.Cpp

Gyakorlati órákon tárgyalt feladatok, és megoldásaik

1. Gyakorlat: A C++ nyelvi elemeinek gyakorlása feladatokkal.

1. Valós (dinamikusan lefoglalt) tömb adatainak bekérése, összeg/átlag meghatározása.
   Összeg:      ,Átlag:          .
   
2. Helyzeti mutatók, középértékek, szóródási mutatók meghatározása:
   a.) Harmonikus átlag:
   b.) Mértani átlag:
   c.) Négyzetes átlag:
   d.) r-ed rendű momentum: , ahol
   e.) Terjedelem:
   f.) Átlagos (abszolút) eltérés:
   g.) Variancia:
   h.) Szórás:
   i.) Realtív szórás:
   j.)  Átlagos (abszolút) különbség:

A gyakorlati feladat megoldása:

Orai01.Cpp

1. Gyakorlat (Házi feladat): További helyzeti és alakmutatók.

1.,    Helyzeti mutatók: Módusz, medián, kvantilisek (kvintilisek, kvartilisek, decilisek, percentilisek) meghatározása
2.,   Alak mutatók: Ferdeségi mutatók: Pearson, F-mutatók, a₃-mutató. Csúcsossági mutatók  K-mutató, a₄-mutató

Megjegyzés: ahhoz, hogy a kvantililseket ki tudjuk számolni, vagy osztályokat kell képezni, vagy rendezni kell az elemeket.

A házi feladat megoldása:

HF01.Cpp

2. Gyakorlat: A C++ nyelvi elemeinek gyakorlása feladatokkal. II

1., Egész típusú (dinamikusan lefoglalt) tömb véletlen adatokkal való feltöltése, átmásolása egy másik tömbbe. A tömbök rendezése         minimum-kiválasztásos, és buborékrendezés segítségével. A futásidők összehasonlítása.

2.,  A sin(x²) a és b közötti határozott integráljának meghatározása az alábbi numerikus integrál közelítő módszerekkel. Készítsen olyan függvényt, amely fokból radiánba, radiánból fokba számít.

      §         Téglalap formula: h(y₀+y₁+y₂+..+y_n-1), vagy h(y₁+y₂+..+y_n-1+y_n)
§         Trapéz formula: h(y₀/2+ y₁+y₂+..+y_n-1+ y_n/2)
§         Simpson formula: h(y₀+ 4y₁+2y₂+4y₃+..+2y_n-2+4y_n-1+ y_n)/3 (ha n=2k)

Orai02-1.Cpp, Orai02-2.Cpp

2. Gyakorlat (Házi feladat): Tetszőleges függvény határozott integráljának meghatározása a három integrálközelítő módszer segítségével. A függvény értelmezését végezze el a lengyel formula segítségével!

Integral.Cpp, Integral.Doc (Bocska István)

3-4. Gyakorlat: Feladatok osztályokkal.

1. Készítse el a következő osztálydefiníciót, és hozza létre az osztály egy statikus példányát.
   • Osztály neve:

   CString;

   Adattagok:

   Buffer //Ez tartalmazza a stringet.
   WordCount //A stringben szereplő szavak számát tartalmazza.
   Length //A string hosszát tartalmazza.
   Fügvénytagok: (saját függvények)
   SetSeparator //Az elválasztó jelet állítja be.
   SetCount //A szavak számát állítja be.
   (nyilvános függvények)
   SetString //Új stringet definiál.
   GetString //Visszaadja a jelenleg tárolt stringet.
   GetWordCount //A szavak számát adja vissza.
   GetLength //A string hosszát adja vissza.
   Készítsen két konstruktort. Egy alapértelmezettet, mely a Buffer-nek egy üres stringet ad át, és egy olyat, melynek át lehet adni egy stringet, valamint készítsen destruktort is.
   

2. Készítsen egy CVertex osztályt, mely tartalmazza, a valós típusú vektort, a szükséges bekérő, módosító, lekérdező függvényeket. Készítsen olyan CVertexes objektumot, melynek VCount db. vektortagja van, tartalmazza az osztály olyan függvényt, mely visszaadja a vektorok összegét, és skaláris szorzatát.

Orai03-1.Cpp, Orai03-2.Cpp

3-4. Gyakorlat (házi feladat) (1):Langrange interpoláció: adottak x_i (i=0,1,..,n) alappontok, y_i (i=0,1,..,n) függvényértékek, n az alappontok száma -1. Keresendő egy olyan g függvény melyre y_i=g(x_i). Tegyük fel, hogy g(x) legfeljebb n-ed fokú polinom. Ekkor g felírható: g(x)=c₀+c₁x+c₂x²+..+c_nxⁿ. (Bizonyítható, hogy egyértelműen található ilyen legfeljebb n-ed fokú polinom, adott x_i,y_i esetén.). Az együtthatók megtalálását két lépésben végezzük.

Először meghatározzuk, az un. Newton együtthatókat: a_i (i=0,1,..,n), ahol g(x)=a₀+a₁*(x-x₀)+a₂*(x-x₀)*(x-x₁)+a₃*(x-x₀)*(x-x₁)*(x-x₂)+..+a_n*(x-x₀)*..*(x-x_n-1)

Az algoritmus formális leírása: Harung Ferenc Bevezetés a Numerikus Analízisbe c. könyve alapján (185. oldal)

INPUT:    n-az alappontok száma-1
                x_i (i=0,1,..,n) alappontok
                y_i (i=0,1,..,n) függvényértékek
OUTPUT: a_i (i=0,1,..,n) Newton polinom együtthatói.

for i=0,1,..,n do
    a_i¬y_i
end do
for j=1,2,..,n do
    for i=n,n-1,..,j do
        a_i¬(a_i-a_i-1)/(x_i-x_i-j)
    end do
end do
output (a₀,a₁,..,a_n,)

Newton polinom kiértékelése:

INPUT:    n-az alappontok száma-1
                a_i (i=0,1,..,n) Newton polinom együtthatói
                y_i (i=0,1,..,n) függvényértékek
                x - a pont ahol kiértékeljük a polinomot
OUTPUT: y a Newton polinom értéke x-ben.

y¬a_n
for i=n-1,n-2,..,0 do
     y¬y*(x-x_i)+a_i
end do
output y

A Newton polinom együtthatóiból c_k (k=0,1,...,n) már könnyen számítható.

pl. 

xi	-1	1	2	3
yi	-2	0	-2	2

Ekkor a Newton polinom együtthatói a_i= -2 1 -1 1. Ebből g(x)=-2+1*(x+1)-1*(x+1)*(x-1)+1*(x+1)*(x-1)*(x-2) = x³-3x²+2

3-4. Gyakorlat (házi feladat) (2): Bezier görbék, Bernstein együtthatók segítségével. 

Definíció: Legyen az i-edik n-ed rendű Bernstein polinom a következő: , ahol , .

Példa: 4 pont által meghatározott Bezier görbe.

A Bernstein együtthetók ebben az esetben:

b₀³(u)=(1-u)³
b₁³(u)=3u*(1-u)²
b₂³(u)=3u²*(1-u)
b₃³(u)=u³
Ebből P pont koordinátája: P=r(u)=b₀³(u)*r₀+b₁³(u)*r₁+b₂³(u)*r₂+b₃³(u)*r₃ Tehát pl. ez a görbe a térben:

. Általánosságban egy n csúcshoz tartozó Bezier görbén lévő pont egyenlete:

Felület esetén a Bezier felületet szintén ki lehet számolni az alábbi összeföggés alapján: 

Egy pont a Bezier felületen:: 

, ahol

5. Gyakorlat: Feladatok osztályokkal II – FIFO megvalósítása, öröklődés

1.,  Készítsen olyan osztály, mely egy dinamikusan lefoglalt FIFO tárat valósít meg kétirányú láncolt lista segítségével! Származtasson le az ős osztályból egy újabb adv_fifo osztályt, amely rendelkezik, Top és Bottom tagfüggvényekkel is.

2.,  Származtasson le az adv_fifo osztályból, CList osztályt, mely egy kétirányú láncolt listát valósít meg. A láncolt listába, lehessen egy tetszőleges pozícióba új elemet beszúrni. Lehessen tetszőleges pozícióból elemet törölni. Legyen olyan tagfüggvénye, amely a top/bottom mutatótól kezdve kiírja az elemeket.

Orai05-1.Cpp, Orai05-2.Cpp

6.      Gyakorlat: Feladatok osztályokkal III – Lista megvalósítása, öröklődés, virtuális függvények

Készítsen olyan listát, mely adott alakzatoknak (háromszög, négyszög, kör) az adatait tárolja, valamint kiszámolja az egyes alakzatok területét, és kerületét.

Orai06.Cpp

6. Gyakorlat (házi feladatok): Feladatok osztályokkal IV - Gráfelméleti algoritmusok

BFS (Breadth First Search) algoritmus

DFS (Depth First Search) algoritmus

7.      Gyakorlat: Feladatok osztályokkal IV – Bináris fák

Készítsen olyan osztályt, mely egy adott számú (tetszőleges típusú) elemet tart nyílván. Rendezze az elemeket a HeapSort algoritmus segítségével.

Orai07.Cpp, Orai07.H

7. Gyakorlat (házi feladatok): Feladatok osztályokkal IV - Gráfelméleti algoritmusok II
Kruskal, Prim, Sollin algoritmus megvalósítása kétirányú láncolt listával.

Kruskal algoritmus:

Prim algoritmus:

algorithm heap-Prim;
begin
create-heap(H);
        for each jÎN-{1} do d(j):=C+1;
set d(1):=0; and pred(1):=0;
for each jÎN-{1} do insert(j,H);
T*:=0;
while |T*|<(n-1) do
begin
        find-min(I,H);
        delete-min(i,H);
        T*:=T*E(pred(i),i);
        for each (i,j)ÎA(i) with jÎH do
            if d(j)>cij then
            begin
                    d(j):=cij;
                    pred(j):=i;
                    decrease-key(j,cij,H);
            end;
    end;
end;
T* is a minimum spanning tree
end;

Sollin algoritmus:

algorithm Sollin;
begin
        for each iÎN do Ni:={i};
        T*:=A;
        while |T*|<(n-1) do
        begin
                for each tree Nk do nearest-neighbour(Nk,ik,jk);
                for each tree Nk do
                    if nodes ik and jk belong to different trees then
                        merge (ik,jk) and update T*:=T*E{(ik,jk)};
        end;
end;

8.   Gyakorlat: Feladatok osztályokkal V – Operátorok túlterhelése

Készítsen olyan osztályt, mely egy halmaz elemeit tartalmazza. Értelmezze az osztályon két (vagy több) halmaz unióját (+), különbségét (-), metszetét (*) az operátorok túlterhelésének segítségével. Majd készítsen olyan osztályt amely egy vektor adatai tartja nyilván és értelmezze rajta a +,-,* műveleteket!

Orai08-1.Cpp, Orai08-2.Cpp

8.   Gyakorlat (házi feladat): Feladatok osztályokkal V - Gráfelméleti algoritmusok III
Dijkstra algoritmus megvalósítása kétirányú láncolt listával.

9.      Gyakorlat: Feladatok osztályokkal VI – Operátorok túlterhelése

Készítsen olyan osztályt, mely egy mátrix adatait tartja nyilván. Értelmezze az osztályon két (vagy több) mátrix összeadását, kivonását, szorzását az operátorok túlterhelésének segítségével.

Orai09.Cpp

9. Gyakorlat (házi feladat): Feladatok osztályokkal VI - Gráfelméleti algoritmusok
CPM (Critical Path Method) algoritmus megvalósítása kétirányú láncolt listával.

Tevékenységlista

Eseménylista

,

Kritikus út: 1-2-3-4-5-6
A kritikus út hossza: 31

CPM-Hálótervezés - fogalmak, feladatok, megoldások

10. Gyakorlat: Feladatok osztályokkal VII, template-ek I

     Készítsen olyan osztályt, mely egy adott számú (tetszőleges típusú) elemet tart nyílván. Rendezze az elemeket a HeapSort algoritmus segítségével.

Orai10.Cpp, Orai10.H

10. Gyakorlat (házi feladat): Feladatok osztályokkal VIII - Gráfelméleti algoritmusok

Tartalékidők számítása:

1., Tevékenység tartalékidők

a., teljes tartalékidő = LST(i,j)-EST(i,j)=LFT(i,j)-EFT(i,j)

b., szabad tartalékidő = EETj-EETi-d(i,j)

c., feltételes tartalékidő = teljes tartalékidő - szabad tartalékidő

d., független tartalékidő = EETj-LETi-d(i,j)

2., Esemény tartalékidő = LETi-EETj

11. Gyakorlat: Feladatok osztályokkal VIII – template-ek  II

Készítsen olyan osztályt, mely egy adott számú (tetszőleges típusú) elemet tart nyílván. Rendezze az elemeket a QuickSort algoritmus segítségével.

procedure quicksort(p,q)
begin
        i=p,j=q,k=Buffer[((p+q) div 2)];
        repeat
                while (Buffer[i]<k) do i:=i+1;
                while (k<Buffer[j]) do j:=j-1;
                if (i<=j) then
                begin
                        Swap(i,j);
                        i:=i+1;
                        j:=j-1;
                end;
        until (i>j);
        if (p<j) then quicksort(p,j);
        if (i<q) then quicksort(i,q);
end;

Orai11.Cpp, Orai11.H

11. Gyakorlat: Feladatok osztályokkal, gráfelméleti algoritmusok

Feladatok osztályokkal X - Gráfelméleti algoritmusok

Valósítsa meg a CPM/COST algoritmust

A kritikus út hossza: 22
A kritikus út elemei: 1-2-4-5

12. Gyakorlat: Feladatok osztályokkal IX

Valósítsa meg a BucketSort algoritmust

i=1,2,..,n, 0<=A[i]<=1
B[0..n-1]

procedure Bucket_sort(A)
begin
n:=length(A);
for i:=1 to n do
    insert A[i] into list B[ënA[i]û];
for i:=1 to n-1 do sort B[i] with insertion_sort;
concate B[0]..B[n-1];
end;

Példa:

 Összes eddigi gyakorlati feladat / házi feladat megoldása:

GYAK.Exe, HF.Exe

További letölthető file-ok

Beadandó feladatok:

Bead.Doc

Beadott prezentációk:

Alapértelmezett, és paraméterezett konstruktorok

Sablonok

Segítség a beadandó feladatokhoz:

Calc.Cpp, Calc.Doc, Beker.Cpp

Kapcsolódó oldalak:

A honlapot készítette Kosztyán Zsolt Tibor