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 */