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
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
- Nejdelší palyndromatická podposloupnost
- Okénková aplikace: Klikací hra dolévání vody
- Windows Forms na stránkách MSDN
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:
- Přidej kořen do fronty
- Dokud není fronta prázdná:
- Vyjmi první prvek z fronty
- 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.
- Prohledávání do hloubky (=DFS, Depth First Search)
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 */