Programovanie (1) v C/C++
1-INF-127, ZS 2017/18

Úvod · Pravidlá · Prednášky · Odovzdávanie
Stránku pre školský rok 2017/18 pripravujeme. Materiály z minulého roku nájdete v archíve.
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Prosíme študentov, aby si pravidelne čítali e-maily na @uniba.sk adrese alebo aby si tieto emaily presmerovali na adresu, ktorú pravidelne čítajú, viď návod tu: [1]


Zimný semester, test a skúška

Z Programovanie
Prejsť na: navigácia, hľadanie

Na tejto stránke budú postupne pribúdať informácie týkajúce sa záverečného písomného testu a praktickej skúšky pri počítači v zimnom semestri. Odporúčame tiež si preštudovať pravidlá predmetu.

Termíny

Písomný test

  • Riadny termín piatok 16.12. o 11:30 v posluchárni A
  • Opravný termín štvrtok 26.1. o 13:00 v posluchárni B

Predbežné termíny skúšok

  • utorok 20.12. 9:00 H6 riadny termín
    • osobné stretnutia v stredu doobeda 10:00-11:30 v M163
  • štvrtok 12.1. 13:00 H6 riadny termín
    • osobné stretnutia piatok 13.1. 10:00-11:30 v M163, prípadne 8:30-9:00 v M263
  • piatok 27.1. 9:00 H6 1. opravný termín
    • osobné stretnutia piatok poobede, čas upresníme na skúške
  • 2. opravný termín vo februári (presný dátum neskôr)

K zapisovaniu na skúšky

  • Na termín skúšky sa zapisujte v systéme AIS.
    • Prihlasovanie/odhlasovanie na skúšku do 14:00 deň pred skúškou.
  • Na skúšku môžete ísť, aj keď ešte nemáte úspešne absolvovaný test (ale kým nespravíte test, nezapíšeme vám známku).
  • Ak na prvom riadnom termíne skúšku nespravíte, môžete použiť druhý riadny termín ako váš prvý opravný atď. Okrem týchto štyroch už však neplánujeme ďalšie termíny a každý sa môže zúčastniť na najviac troch termínoch.
  • Po skúške poobede alebo na ďalší deň budú určené časy na osobné stretnutie, diskusiu k vašim riešeniam, reklamácie bodov, zapisovanie známok do indexov.
    • Ak máte ku skúške akékoľvek otázky (čo som mal zle, ako sa to dalo robiť lepšie atď), príďte na osobné stretnutie.
    • Príďte na stretnutie, aj ak ste skúšku nespravili. Môžeme vám poradiť, čo robiť inak na opravnom termíne.
    • Ak spravíte skúšku v riadnom termíne, stretnutie je nepovinné. Známku do indexu si môžete zapísať aj na inom termíne skúšky alebo poslať index po spolužiakovi (zapisovať známky ale budeme len v určené časy, nie keď zrovna idete okolo...).
    • Prípadné otázky k bodovaniu riešte na osobnom stretnutí po skúške, alebo emailom najneskôr deň po skúške, nie neskôr.
    • Ak ste písali opravný termín, osobné stretnutie je povinné.

Záverečná písomka

  • 90 minút
  • Aby ste mali šancu úspešne ukončiť predmet, musíte získať aspoň polovicu bodov.
  • Jeden opravný termín

Čo musíte, môžete a nemôžete

Musíte:

  • index/ISIC
  • perá (pre istotu aj viac)

Môžete:

  • ťahák veľkosti A4

Nemôžete:

  • žiadne elektronické pomôcky (vypnúť mobily)
  • opisovať
  • iné materiály na stole (čisté papiere dostanete od nás)

Príklady

  • Bude zhruba 6 príkladov
    • Príklad môže mať niekoľko podpríkladov, ktoré sú zároveň odporúčaným postupom krokov
  • Náročnosť zhruba ako rozcvičky
  • Dobre si rozvrhnite čas, niektoré úlohy sú ťažšie, iné ľahšie.

Typy príkladov:

  • napíšte funkciu, ktorá... (napr. na prácu so spájanými zoznamami, súbormi, stromami, rekurzia)
  • do funkcie nižšie doplňte chýbajúce časti tak, aby robila ... (dopĺňanie správnych typov, podmienok v cykloch a pod.)
  • zistite, čo vypíše funkcia pre nasledujúce vstupy...
  • čo spraví algoritmus z prednášky na danom vstupe, na akom vstupe sa bude správať takto a pod.
  • príklady na výrazy v postfixovej, prefixovej a infixovej forme, binárne vyhľadávacie stromy, zásobník a rad, ...

Skúška pri počítači

  • Termíny vypísané v AIS
  • Prineste si ISIC a index, písacie potreby na písanie pracovných poznámok, ťahák v rozsahu jedného listu A4. Žiadne ďalšie pomôcky nie sú povolené, nebude k dispozícii ani internet.
  • Stretávame sa vždy desať minút pred začiatkom skúšky pred počítačovou miestnosťou, kde sa dozviete pokyny a rozsadenie do miestností
  • Skúška: 2 hodiny práca pri počítačoch.
    • Prostredie ako na cvičeniach (Linux, Netbeans, ale môžete používať aj iné nainštalované editory, valgrind a pod.)
    • Budete používať špeciálne skúškové konto, takže nebudete mať k dispozícii žiadne svoje súbory alebo nastavenia.
    • Odovzdávanie prostredníctvom špeciálnej verzie testovača, slúži súčasne ako záloha.
  • Poobede alebo ďalší deň: vyhodnotenie u prednášajúcich, zapisovanie známok, viď vyššie.

Príklady

  • Na skúške budete riešiť dva príklady za rovnaký počet bodov
    • Nie sú rovnako ťažké, preto si dobre premyslite, ako si rozdelíte čas.
  • V prvom príklade budete mať za úlohu samostatne napísať celý program, ktorý rieši zadanú úlohu. Typicky bude treba načítať dáta, spracovať ich a vypísať výsledok.
    • V tomto príklade môžete použiť ľubovoľný postup.
    • Predtým ako začnete programovať, si poriadne rozmyslite, aké dátové štruktúry (polia, matice, struct-y a pod.) chcete v programe použiť.
  • V druhom príklade dostanete kostru programu, pričom vašou úlohou bude doprogramovať niektoré funkcie.
    • V tomto príklade môžete mať v zadaní predpísaný spôsob, ako máte niektoré časti naprogramovať.
    • Budú sa vyžadovať aj zložitejšie časti učiva, ako napríklad zoznamy, stromy a rekurzia.
  • Nebudeme používať SVGdraw.
  • Môžete používať aj črty C/C++, ktoré sme nebrali. Používajte len štandardné súčasti jazyka. Vaše programy by mali fungovať v prostredí používanom v učebni resp. na testovači bez zvláštnych nastavení kompilátora a pod.

Hodnotenie

  • V prvom rade budeme hodnotiť správnosť myšlienky vášho programu. Predtým, ako začnete programovať, si dobre rozmyslite, ako budete úlohu riešiť.
  • Ďalej je veľmi dôležité, aby sa program dal skompilovať (v štandardnom prostredí) a aby správne fungoval na všetkých vstupoch spĺňajúcich podmienky v zadaní.
  • V druhej úlohe budeme jednotlivé funkcie hodnotiť zvlášť, takže môžete získať čiastočné body, ak ste niekoľko funkcií napísali správne.
  • Na hodnotenie môže mať menší vplyv aj úprava a štýl programu (komentáre, mená premenných, odsadzovanie, členenie dlhšieho programu na funkcie,...)
  • Na tejto skúške nezáleží na rýchlosti vášho programu. Radšej napíšte jednoduchý, prehľadný a hlavne správny pomalší program, než rýchlejší, ale zbytočne zložitý, či nesprávny.
  • Aby ste mali šancu úspešne ukončiť predmet, aspoň jeden z príkladov vám musí prejsť všetky testy na testovači
    • Túto podmienku nebudeme považovať za splnenú, ak váš program nerieši zadanú úlohu (t.j. jeho myšlienka nie je v zásade správna)
    • Podmienku však považujeme za splnenú, ak váš program prejde všetky vstupy, má v zásade správnu myšlienku, ale nedostane plný počet bodov napríklad kvôli chýbajúcemu uvoľneniu pamäte, menšej chybe, ktorá sa neprejavila na daných vstupoch a pod.

Opravné termíny

  • Záverečný test má jeden opravný termín (je súčasťou priebežného hodnotenia)
    • Ak sa zúčastníte opravného termínu, strácate body z predchádzajúceho termínu, aj keby ste na opravnom získali menej bodov.
    • Rozhodnúť o účasti sa musíte predtým, ako rozdáme zadania
    • Toto platí aj pre študentov, ktorí získali aspoň polovicu bodov na teste pre pokročilých a rozhodujú sa, či prísť na riadny termín testu
  • Opakovanie skúšky sa riadi študijným poriadkom fakulty. Máte nárok na dva opravné termíny (ale len v rámci termínov, ktoré sme určili).
  • Ak po skúške pri počítači máte nárok na známku E alebo lepšiu, ale chceli by ste si známku ešte opraviť, musíte sa dohodnúť so skúšajúcimi pred zapísaním známky do indexu.
  • Ak po skúške pri počítači píšete opravnú písomku, je potrebné prísť uzavrieť a zapísať známku v termíne určenom vyučujúcimi.
  • Ak sa zo závažných dôvodov (napr. zdravotných, alebo konflikt s inou skúškou) nemôžete zúčastniť termínu skúšky alebo písomky, dajte o tom vyučujúcim vedieť čím skôr.

Ukážkové príklady na písomný test

V texte nižšie je niekoľko príkladov, ktoré sa svojim charakterom a obtiažnosťou podobajú na príklady, aké budú na záverečnej písomke. Tieto ukážkové príklady sú prevažne vybrané z cvičení a prednášok, na skutočnej písomke však budú nové, zatiaľ nepoužité príklady. Svoje odpovede si môžete skontrolovať nižšie.

  • Príklad 1: Zistite, čo vypíše nasledujúca funkcia, ak ju spustíme ako generuj(a, pocet, 0, 2, 3), pričom polia a a pocet majú dĺžku n=3 a obe sú naplnené nulami. Funkcia vypis(a,n) vypíše prvky poľa a.
    • Ako musíme funkciu opraviť, aby vypisovala všetky usporiadané n-tice čísel z množiny {0,...,n-1}, v ktorých sa každé číslo opakuje najviac k krát?
void generuj(int a[], int pocet[], int i, int k, int n) {
    if (i == n) {
        vypis(a, n);
    } else {
        for (int x = 0; x < n; x++) {
            if (pocet[x]<k) {
                a[i] = x;
                pocet[x]++;
                generuj(a, pocet, i + 1, k, n);
            }
        }
    }
}
  • Príklad 2: Prepíšte výraz 8 3 4 * + 2 3 + / z postfixovej notácie do bežnej infixovej notácie
  • Príklad 3: Prepíšte výraz ((2+4)/(3*5))/(1-2) do postfixovej a prefixovej notácie
  • Príklad 4: Vyhodnocujeme výraz 8 3 4 * + 2 3 - / v postfixovej notácii algoritmom z prednášky. Aký bude obsah zásobníka v čase, keď začneme spracovávať znamienko +?
  • Príklad 5: Máme zásobník s a rad q, pričom obidve štruktúry uchovávajú dáta typu char. Aký bude ich obsah po nasledujúcej postupnosti príkazov?
init(s);
init(q);
push(s, 'A');
push(s, 'B');
push(s, 'C');
enqueue(q, pop(s));
enqueue(q, pop(s));
push(s, 'D');
push(s, dequeue(q));
  • Príklad 6: Máme binárny strom, v ktorom má každý vrchol buď dve deti a v dátovom poli uložený znak '#' alebo nemá žiadne deti a v dátovom poli má uložený znak '*'. Keď tento strom vypíšeme v preorder poradí, dostaneme postupnosť ##*#*** Nakreslite, ako vyzerá tento strom.
  • Príklad 7: Nakreslite binárny vyhľadávací strom, ktorý dostaneme, ak do prázdneho stromu postupne vkladáme záznamy s kľúčami 3, 4, 1, 2, 5, 6 (v tomto poradí).
  • Príklad 8: Nakreslite lexikografický strom s abecedou {a,b}, do ktorého sme vložili reťazce aba, aaab, baa, bab, ba. Vrcholy, ktoré zodpovedajú niektorému reťazcu zo vstupu, zvýraznite dvojitým krúžkom.
  • Príklad 9: Uvažujme nasledujúcu rekurzívnu funkciu na vyfarbovanie. Predpokladajme, že a je matica s troma riadkami a troma stĺpcami vyplnená nulami, pričom funkciu spustíme na stredné políčko, t.j. stlpec=riadok=1 a nová farba je tiež 1. V akom poradí vyfarbí políčka matice novou farbou?
void vyfarbi(int **a, int n, int m, int riadok, int stlpec, int farba) {
    /* prefarbi suvislu jednofarebnu oblast obsahujucu 
     * a[riadok][stlpec] na farbu farba */

    if (a[riadok][stlpec] != farba) {
        int stara_farba = a[riadok][stlpec];
        a[riadok][stlpec] = farba;
        if (riadok > 0 && a[riadok - 1][stlpec] == stara_farba) {
            vyfarbi(a, n, m, riadok - 1, stlpec, farba);
        }
        if (riadok + 1 < n && a[riadok + 1][stlpec] == stara_farba) {
            vyfarbi(a, n, m, riadok + 1, stlpec, farba);
        }
        if (stlpec > 0 && a[riadok][stlpec - 1] == stara_farba) {
            vyfarbi(a, n, m, riadok, stlpec - 1, farba);
        }
        if (stlpec + 1 < m && a[riadok][stlpec + 1] == stara_farba) {
            vyfarbi(a, n, m, riadok, stlpec + 1, farba);
        }
    }
}
  • Príklad 10: Napíšte funkciu vyhod(linkedList &z), ktorá z jednosmerného spájaného zoznamu vyhodí všetky záznamy, v ktorých má položka data nulovú hodnotu. Pozor, takéto záznamy sa môžu vyskytovať aj na začiatku zoznamu. Vyhodené položky zoznamu treba odalokovať.
  • Príklad 11: Napíšte funkciu dvojicky(node *root), ktorá spočíta počet všetkých vnútorných vrcholov v strome s koreňom root takých, že ich ľavé aj pravé dieťa majú v svojom dátovom poli uloženú tú istú hodnotu.
  • Príklad 12: Nasledujúci program načíta od užívateľa počet kruhov, zoznam údajov pre jednotlivé kruhy (celočíselné súradnice a polomer), posunie každý kruh o 10 nižšie a zase kruhy vypíše. Doplňte do programu chýbajúce časti vyznačené čiarami (typy premenných, parametre a návratové typy funkcií).
#include <iostream>
using namespace std;

struct kruh {
   ________________
};

_______ posunKruh(__________) {
  k.y-=10;
}

_______ nacitajKruhy(__________) {
  _________ a;
  a = new kruh[n];
  for(int i=0; i<n; i++) {
    cin >> a[i].x >> a[i].y >> a[i].r;
  }
  return a;
}

______ vypisKruhy(________________) {
  for(int i=0; i<n; i++) {
    cout << " " << a[i].x << " " << a[i].y << " " << a[i].r << endl;
  }  
}

int main(void) {
  _______ n;
  _______ a;
  cin >> n;
  a = nacitajKruhy(n);
  for(int i=0; i<n; i++) {
    posunKruh(a[i]);
  }
  vypisKruhy(a, n);
  delete[] a;
}
  • Príklad 13: Funkcia jeRastuci kontroluje, či sa hodnoty v spájanom jednosmernom zozname zvyšujú v smere od začiatku ku koncu zoznamu, t.j. či každý prvok je väčší ako jeho predchodca. Ak áno, vráti true, inak vráti false. Doplňte podmienky na podčiarknuté miesta tak, aby funkcia správne fungovala. V prípade, že zoznam je prázdny alebo obsahuje jeden prvok, odpoveď má byť true.
struct item {
    int data;
    item* next;
};

struct zoznam {
    item* zaciatok;
};

bool jeRastuci(zoznam &z) {
  item *v = z.zaciatok;
  while(____________) {
    if(_____________) {
      return false;
    }
    v = v->next;
  }
  return true;
}
  • Príklad 14: Uvažujme funkciu na triedenie vkladaním uvedenú nižšie.
    • Koľkokrát sa vykoná riadok označený (**) na vstupnom poli (5,2,3,4,1)?
    • Koľkokrát sa vykoná riadok označený (**) na vstupnom poli dĺžky n, ktoré je celé utriedené okrem toho, že najmenší a najväčší prvok sú vymenené teda (n,2,3,4,...,n-2,n-1,1)? Počet vykonaní zapíšte ako funkciu od dĺžky poľa n.
void insertionSort(int a[], int n) {
    /* usporiadaj prvky v poli a od najmenšieho po najväčší */

    for (int i = 1; i < n; i++) {
        int prvok = a[i];
        int kam = i;
        while (kam > 0 && a[kam - 1] > prvok) {
            a[kam] = a[kam - 1];  // (**) 
            kam--;
        }
        a[kam] = prvok;
    }
}

Vzorové riešenia ukážkových príkladov na písomný test

  • Príklad 1: funkcia vypíše tri trojice: 0 0 1, 0 0 2, 0 1 2. Nevypisuje to čo má, lebo po vynorení z rekurzie nezníži od pocet[x], aj keď hodnota a[i] bude zmenená z x na x+1. Tu je funkcia po oprave:
void generuj(int a[], int pocet[], int i, int k, int n) {
    if (i == n) {
        vypis(a, n);
    } else {
        for (int x = 0; x < n; x++) {
            if (pocet[x]<k) {
                a[i] = x;
                pocet[x]++;
                generuj(a, pocet, i + 1, k, n);
                pocet[x]--; /* pridany prikaz */
            }
        }
    }
}
  • Príklad 2: (8+3*4)/(2+3)
  • Príklad 3: postfix 2 4 + 3 5 * / 1 2 - / prefix: / / + 2 4 * 3 5 - 1 2
  • Príklad 4: na zásobníku budú čísla 8 a 12 (8 je na spodku zásobníka). Číslo 12 vzniklo vynásobením 3 a 4.
  • Príklad 5: na zásobníku budú znaky A, D, C (A na spodku zásobníka), v rade bude písmeno B
  • Príklad 6:
        #
       / \
      #   *
     /\
    *  #
      /\
     *  *
  • Príklad 7:
        3
       / \
      1   4
      \    \
       2    5
             \
              6
  • Príklad 8: (namiesto dvojiteho krúžku používame *)
          .
         / \
        /   \
       /     \ 
      a       b
     / \     /
    a   b   a*
   /   /   / \
  a   a*  a*  b*
 /
b*
  • Príklad 9: do každého políčka sme vpísali poradové číslo, kedy bude vyfarbené:
3 2 9
4 1 8
5 6 7
  • Príklad 10: Jedna možnosť je použiť dvojitý smerník, ktorý môže ukazovať buď na premennú zaciatok v zozname alebo na premennú next v niektorom jeho prvku.
void vyhod(zoznam &z) {
  /* vytvorime si smernik na miesto,
   * kde je ulozeny smenrik na dalsi prvok*/
  item **smernik = &(z.zaciatok);
  /* kym nie sme na konci zoznamu */
  while((*smernik)!=NULL) {
      /* dalsi prvok je nula, zmazeme ju a prevesime zvysok zoznamu */
      if((*smernik)->data==0) {
          item *remove = *smernik;
          (*smernik) = (*smernik)->next;
          delete remove;
      }
      /* dalsi prvok nie je nula, posunieme smernik */
      else {
          smernik = &((*smernik)->next);
      }
  }
}

Druhá možnosť je použiť dva cykly: jedným mažeme nuly na začiaktu a druhým mažeme nuly vo zvyšku zoznamu.

void vyhod(zoznam &z) {
    /* vyhadzujeme nuly na zaciatku */
    while (z.zaciatok != NULL && z.zaciatok->data == 0) {
        item * remove = z.zaciatok;
        z.zaciatok = remove->next;
        delete remove;
    }
    /* node bude ukazovat vzdy na nenulovy prvok,
     * kontrolujeme prvok za nim */
    item * node = z.zaciatok;
    while (node != NULL && node->next != NULL) {
        if (node->next->data == 0) {
            item * remove = node->next;
            node->next = remove->next;
            delete remove;
        }
        else {
            node = node->next;
        }
    }
}
  • Príklad 11:
int dvojicky(node *root) {
    /* prazdny strom neobsahuje dvojicky */
    if(root == NULL) return 0;
    
    int result = 0;
    /* ak su deti korena dvojicky, pricitaj 1*/
    if(root->left != NULL && root->right != NULL
            && root->left->data == root->right->data) {
        result++;
    }
    /* spocitaj dvojicky v lavom a pravom podstrome */
    result += dvojicky(root->left);
    result += dvojicky(root->right);
    return result;
}
  • Príklad 12:
#include <iostream>
using namespace std;

struct kruh {
    int x, y, r;
};

void posunKruh(kruh &k) {
  k.y-=10;
}

kruh * nacitajKruhy(int n) {
  kruh * a;
  a = new kruh[n];
  for(int i=0; i<n; i++) {
    cin >> a[i].x >> a[i].y >> a[i].r;
  }
  return a;
}

void vypisKruhy(kruh *a, int n) {
  for(int i=0; i<n; i++) {
    cout << " " << a[i].x << " " << a[i].y << " " << a[i].r << endl;
  }
}

int main(void) {
  int n;
  kruh * a;
  cin >> n;
  a = nacitajKruhy(n);
  for(int i=0; i<n; i++) {
    posunKruh(a[i]);
  }
  vypisKruhy(a, n);
  delete[] a;
}
  • Príklad 13:
bool jeRastuci(zoznam &z) {
    item *v = z.zaciatok;
    while (v != NULL && v->next != NULL) {
        if (v->data >= v->next->data) {
            return false;
        }
        v = v->next;
    }
    return true;
}
  • Príklad 14:
    • Čísla 2,3,4 musia preskočiť číslo 5, riadok sa teda pre každé z nich vykoná raz a pre číslo 1 sa vykoná 4 krát, spolu teda 7 krát.
    • Čísla 2,3,4,...,n-2,n-1 musia preskočiť číslo n, riadok sa teda pre každé z nich vykoná raz a pre číslo 1 sa vykoná n-1 krát. Spolu sa teda riadok vykoná n-2+n-1=2n-3 krát.


Ukážkové príklady na skúšku pri počítači

Niektoré ukážkové príklady na skúšku sú k dispozícii na testovači, môžete si ich v rámci tréningu vyriešiť a odovzdať. Pre realistickejší tréning si vždy prečítajte zadanie tesne predtým, ako príklad začnete riešiť, aby ste odhadli, koľko času vám príklad zaberie vrátane čítania zadania a rozmýšľania nad riešením.

Prvý príklad

Druhý príklad