Cvičení z Programování II (léto 2016/2017, úterý 12:20)

Podmínky zápočtu

  • Aktivní účast na cvičení
  • Alespoň 70% bodů ze zadaných úloh (CodExu, Houbaři, aktuální hranice: 139 * 0.7 = 97 bodů)
  • Splnění zápočtového testu (poslední dvě cvičení)
  • Vypracování zápočtového programu
    • Téma si vybíráte sami, ovšem je třeba si jej nechat schválit
    • Pro inspiraci ohledně témat se můžete podívat sem či sem, popřípadě do archivů libovolné programátorské soutěže
    • Návod k psaní dokumentace jistě znáte ze zimního semestru (R. Kryl)
    • Specifikaci je nutno odevzdat do konce dubna

    23. 5. 2017    Opravný termín zápočtového testu, trénink na zkoušku

    • minimax
    • binární vyhledávací stromy
    • ...

    16. 5. 2017    Zápočtový test


    9. 5. 2017    Trénink na zápočtový test

    • rozprava nad zpracováním aritmetických výrazů rekurzí
    • rozptyl v poli
    • binární vyhledávání
    • souvislý úsek pole délky k s největším součtem (v lineárním čase)

    2. 5. 2017    Algoritmy

    • Union-find
    • Nejmenší kostra (Kruskal)
    • Dijstrův algoritmus

    25. 4. 2017    Algoritmy

    • Převod čísla do binární soustavy
    • Mocnění v logaritmickém čase
    • Eratosthenovo síto
    • Problém batohu

    18. 4. 2017    Dynamické programování, okéknové aplikace


    11. 4. 2017    Vyhlášení výsledků houbařů, dynamické programování

    • Gratulace patří Týmu Zabijáků, kteří přežili v temných lesích windowsové konzole hlad i nápor vlků.
    • Tradiční úlohy pro dynamické programování
      • Optimální uzávorkování násobení matic
      • Nejdelší rostoucí podposloupnost
      • Nejdelší palyndromatická podposloupnost (úložka do tramvaje)
    • Nestihlo se: Jak prohledávat obecné grafy o N vrcholech
      List<List<int>> graph = ...;            // načti graf o N vrcholech
      int source, destination = ...;          // načti počáteční a cílový vrchol
      bool[] visited = new bool[N];           // visited[i] označuje, zda byl vrchol i již navštíven
      Stack<int> found = new Stack<int>();    // alokuj zásobník doposud nalezených vrcholů
      
      found.Push(source);                     // přidej počáteční vrchol do zásobníku
      visited[source] = true;                 // označ počáteční vrchol za navštívený
      
      while (found.Count() > 0) {             // dokud zásobník není prázdný:
          int next = found.Pop();             //     vyndej příští vrchol ze zásobníku
          if (next == destination) break;     //     zkontroluj, zda to není cíl
          foreach (int son in graph[next]) {  //     pro každého syna vyndaného vrcholu:
              if (!visited[son]) {            //         pokud je syn nenavštívený
                  found.Push(son);            //             přidej ho do zásobníku
                  visited[son] = true;        //             označ jej za navštívený
              }
          }
      }
      

    4. 4. 2017    Programování houbařů, detekce ohrožené dámy na šachovnici


    28. 3. 2017    Grafové algoritmy

    • Reprezentace grafu
      • Matice sousednosti
      • Seznam následníků
    • Prohledávání grafu:
      • Prohledávání do hloubky (=DFS, Depth First Search)
        • Pomocí rekurze
        • Pomocí zásobníku
        • Úloha výpis grafu
          • prefixový výpis
          • infixový výpis (pro BST (=Binary Search Tree) vypíše setříděnou posloupnost)
        • Úloha iterace skrz binární strom
          • iterace skrz binární strom má lineární složitost
      • Prohledávání do šířky  (=BFS, Breadth First Search)
        • Podobné jako DFS, jen vyměníme zásobník za frontu
        • Algoritmus pro orientované acyklycké grafy:
        1. Přidej kořen do fronty
        2. Dokud není fronta prázdná:
          1. Vyjmi první prvek z fronty
          2. Přidej jeho syny do fronty
        • Pro obecné grafy je třeba před vložením do zásobníku kontrolovat, zda jsme již vrchol nenavštívili.

    Vytvoření objektu List<List<int>> vhodného pro seznam následníků:

    List<List<int>> graph = new List<List<int>>();
    for (int i = 0; i < N; ++i) {
        graph.Add(new List<int>());
    }
    // nyni muzeme pridavat syny k jednotlivym vrcholum
    graph[2].Add(3);
    graph[1].Add(4);
    

    Pozor, List<int> nemá členskou proměnnou Length, jak tomu bylo u polí, ale Count!


    21. 3. 2017    Objektový návrh

    Navrhovali jsme soutěžní prostředí a simulátor Houbaři.


    14. 3. 2017    CodEx-ový Reader.cs, třídy, polymorfismus

    Použití souboru Reader.cs je popsáno v CodExové dokumentaci.

    Ukázali jsme si rozdíl mezi třídami a objekty, statické funkce, privátní a veřejné funkce, virtuální funkce a polymorfismus. Ukázkový kód na polymorfismus: VirtualniDedeniPsu.cs

    7. 3. 2017    Debugging, slévání setříděných polí, mergesort, 2D pole, transpozice matic


    Vytvoření dvourozměrného pole

    int[,] arr = new int[5, 3];
    arr[0, 2] = 1;

    28. 2. 2017    Rekurzivní Fibonacci, cykly, načítání souborů, zásobník


    Načtení pole ze standardního vstupu

    int[] nums = Console.ReadLine().Trim().Split().Select(w => int.Parse(w)).ToArray();


    Čtení standardního vstupu po řádcích

    string line;
    while ((line = Console.ReadLine()) != null) {
        ...
    }


    Čtení souboru po řádcích

    using System.IO;
    ...
    using (StreamReader sr = new StreamReader(@"soubor.txt")) {
        string line;
        while ((line = sr.ReadLine()) != null) {
            ...
        }
    }

    Předchozí způsob nefunguje ve všech verzích .NET. Vždy můžete použít tento:

    using System.IO;
    ...
    using(var fs = new FileStream(@"soubor.txt", FileMode.Open, FileAccess.Read))
    using(var sr = new StreamReader(fs)) {
        string line;
        while ((line = sr.ReadLine()) != null) {
            ...
        }
    }

    Další funkce System.IO se dají nalézt na stránkách MSDN.


    Iterace skrz pole

    
    int[] arr = new int[...];
    for (int i = 0; i < arr.Length; ++i) {
        ...
    }
    // ekvivalentně
    int i = 0;
    while (i < arr.Length) {
        ...
        ++i;
    }
    

    Setřízení pole

    
    int[] arr = new int[...];
    Array.Sort(arr);
    

    Setřízení pole podle klíčů v jiném poli

    
    string[] items = {"dva", "tri", "jedna"};
    int[] keys = {2, 3, 1};
    Array.Sort(keys, items);
    

    // items == {"jedna", "dva", "tri"}


    Zásobník

    
    using System.Collections.Generic;
    ...
    Stack st = new Stack;
    st.Push("hello");
    st.Push("world");
    Console.WriteLine(st.Peek()); // vypise world
    Console.WriteLine(st.Pop()); // vypise world
    Console.WriteLine(st.Pop()); // vypise hello
    

    Vyhledání v poli

    
    int[] arr = {1, 5, 3, 7};
    Array.IndexOf(3); // == 2
    Array.IndexOf(2); // == -1
    

     

    21. 2. 2017    Základy C#

    Oficiální tutoriály C# a .NET


    Vytvoření řetězcové a číselné proměnné

    string b = "hello";
    int a = 5;


    Načtení řetězce ze standardního vstupu

    string line = Console.ReadLine();


    Načtení jednoho čísla ze standardního vstupu

    int num = int.Parse(Console.ReadLine());


    Vypsání textu a čísel na standartní výstup

    Console.WriteLine($"Vysledek {a} + {b} = {c}");


    Práce s polem

    int[] arr = new int[5];
    arr[0] = 7;


    Načtení více čísel ze standardního vstupu

    string[] words = Console.ReadLine().Trim().Split();
    int a = int.ParseInt(words[0]);
    int b = int.ParseInt(words[1]);

     


    Podmínky

    if (podmínka) {
        tělo
    }
    Např.:
    if (a == 7 || a < 0) {
        Console.WriteLine("A je zaporne nebo rovno 7");
    }

    Základní spojky jsou '&&' (and) a '||' (or). Základní relace jsou '==' (equal), '!=' (not equal), '<' (less), '>' (greater), '<=' (less or equal), '>=' (greater or equal). Negace se provádí operátorem '!', např. 'if (!(a < b))' je to samé jako 'if (a >= b)'.


    Funkce

    static NAVRATOVY_TYP NAZEV_FUNKCE(ARGUMENTY...)
    {
        ...
        return HODNOTA;
    }
    Např.:
    static int add(int a, int b)
    {
        return a + b;
    }
    ...
    int soucet = add(5, 3);


    Komentáře

    // toto je komentar
    /* toto je
       viceradkovy komentar */