DokuWiki - zalg

avl_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-04-08T13:15:25+00:00

Vyvážené stromy #include #include using namespace std; struct Item { int key; int height; Item * left; Item * right; Item () { key = 0; height = 1; left = nullptr; right = nullptr; } // Item () : key (0), height (1), left (nullptr), right (nullptr) { } }; inline int h (Item * p) { if (p == nullptr) return 0; else return p->height; } inline void update (Item * p) { int L = h (p->left); int R = h (p->right); if (L…

avl_st

Anonymous (anonymous@undisclosed.example.com) — 2021-04-08T13:14:32+00:00

Vyvážené stromy #include using namespace std; struct Item { int key; int height; Item* left; Item* right; Item () { key = 0; height = 1; left = nullptr; right = nullptr; } }; Item* root = nullptr; inline int h (Item* p) { if (p == nullptr) return 0; else return p->height; } inline void update (Item* p) { int L = h (p->left); int R = h (p->right); if (L > R) p->height = L+1; else p->height = R+1; } void…

avl

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:06:38+00:00

Vyvážené stromy Kapitola 6.1 ve skriptech Niklaus Wirth: Algoritmy + datové struktury = programy Binární ohodnocené stromy. Pro všechny uzly stromu musí platit, že výšky podstromů se liší nejvýše o 1. Animace:

btree_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-04-29T12:24:06+00:00

B-tree #include // #include #include using namespace std; const int Max = 4; // max. pocet klicu v jednom uzlu const int Min = Max / 2; struct Item { int cnt; // 1 <= cnt <= Max, cnt == Max+1 pri preplneni int key [Max+1]; // o jeden klic navic pri preplneni Item * ref [Max+2]; // vyuzivame key [0] , ... , key [cnt-1] // vyuzivame ref [0] , ... , ref [cnt-1], ref [cnt] Item (); }; Item::Item () { cnt = 0; for (int k = 0; k < Max+…

btree_st

Anonymous (anonymous@undisclosed.example.com) — 2021-04-28T12:00:20+00:00

B-tree #include using namespace std; const int Max = 4; const int Min = Max / 2; struct Item { int cnt; // pocet klicu, nejvise Max, docasne Max+1 int key [Max+1]; // cnt klicu Item * ref [Max+2]; // cnt+1 ukazatelu Item (); }; Item::Item () { cnt = 0; for (int i = 0; i < Max+1; i++) key [i] = 0; for (int i = 0; i < Max+2; i++) ref [i] = nullptr; } void shift (Item* p, int i, int new_key, Item* new_ref) { for (int k = p->cnt-1; k >= i; k--) p->key…

btree

Anonymous (anonymous@undisclosed.example.com) — 2023-05-11T10:28:26+00:00

B-stromy Skripta 2.3.1 nebo * B-stromy jsou vyvažované stromy se stejnou délkou cesty od kořene ke všem listům. * Každý uzel obsahuje několik hodnot a několik ukazatelů na podstromy (zobecnění binárních stromů). * Každý uzel, který není listem, má alespoň dva podstromy (důležité pro efektivní vyhledávání)

dama_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-03-17T14:11:23+00:00

Osm dam, prozatím osm věží #include using namespace std; const int N = 8; int a [N+1]; int cnt = 0; void tisk () { for (int i = 1; i <= N; i++) { cout << a [i]; } cout << endl; } void umisti (int k) { for (int i = 1; i <= N; i++) { bool ok = true; for (int t = 1; t <= k; t++) if (a [t] == i) ok = false; if (ok) { a [k] = i; if (k == N) { …

dama_src

Anonymous (anonymous@undisclosed.example.com) — 2020-04-07T08:09:40+00:00

#include using namespace std; const int N = 8; int p [N]; int cnt = 0; void place (int s) { for (int r = 0; r < N; r++) { bool ok = true; for (int v = 1; v <= s && ok; v++) { int d = p[s - v]; if (d == r || d == r-v || d == r+v) ok = false; } if (ok) { p[s] = r; if (s < N - 1) place(s + 1); else { cnt++; …

dama_st

Anonymous (anonymous@undisclosed.example.com) — 2021-03-17T14:12:16+00:00

Osm dam #include using namespace std; const int N = 8; int a [N+1]; // a[0] nepouzivam int cnt = 0; void tisk () { cnt ++; if (1) { for (int s = 1; s <= N; s++) cout << a [s] << ' '; cout << endl; } if (0) { for (int r = 1; r <= N; r++) { for (int s = 1; s <= N; s++) if (a[s] == r) cout << "* "; else cout << ". "; cout…

dama

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:03:44+00:00

Osm dam Metoda hledání s návratem, problém osmi dam (skripta 3.4) Zadání úlohy: Zdrojový text Pocet sloupcu const int N = 8; Jednorozmerne pole pro evidenci dam int p [N]; Prvek pole p [i] obsahuje informaci o dame v i-tem slopci: obsahuje cislo radky, kde se nachazi dama.

git

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:00:38+00:00

Přístup k GIT z Linuxu git clone http://gitlab.fjfi.cvut.cz/culikzde/zalg.git A později v adresáři “zalg” stažení nových verzí: git pull Přístup k GIT z Windows Windows Git: a užitečný doplněk Windows Tortoise Git: Zkopírování příkladů

heapsort_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-03-25T14:42:06+00:00

Heap sort (indexovani od 0) #include #include using namespace std; const int N = 1000; int a [N]; inline void swap (int i, int k) { int t = a[i]; a[i] = a[k]; a[k] = t; } void heapify (int i, int k) // vytvorit haldu s indexy i, ..., k // za predpokladu, ze indexy i+1, ..., k jiz haldu tvori { while (2*i+1 <= k) // levy existuje { int v = 2*i+1; // index leveho if (v+1 <= k) // pravy existuje if (a [v+1] > a [v]) // pr…

heapsort_st

Anonymous (anonymous@undisclosed.example.com) — 2021-03-31T13:53:28+00:00

Heap sort (indexovani od 1) #include #include using namespace std; const int N = 1000; // int a [N+1] = { 0 /* a[0] nepouzivam */, 10, 4, 8, 20, 7, 5, 1 }; int a [N+1]; /* a[0] nepouzivam */ inline void swap (int i, int k) { int t = a [i]; a [i] = a [k]; a [k] = t; } void heapify (int i, int k) { while (2*i <= k) // dokud existuje levy { int v = 2*i; // index leveho if (v+1 <= k) // pokud pravy existuje { if (a [v+…

heapsort

Anonymous (anonymous@undisclosed.example.com) — 2020-04-07T11:29:44+00:00

Heap sort Třídění haldou, skripta 5.1.6 Heap sort má složitost O(n log n), kde n je počet tříděných prvků Formální rozložení prvků ve stromu Je zadáno pole N hodnot a[0], ... a[N-1]. Hodnoty boudou stále uloženy v poli, ale představíme si je ve stromu.

ide

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:01:55+00:00

Vývojová prostředí Dev C++ Pro naše cvičení stačí Dev-C++ 5.0 beta 9.2 (4.9.9.2) (9.0 MB) with Mingw/GCC Code Blocks Balíček s překladačem GCC codeblocks-17.12mingw-setup.exe Qt Creator Windows: Novější: Arch Linux: pacman -S qtcreator

jezdec_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-03-18T14:16:56+00:00

Hledání nejkratší cesty jezdcem #include using namespace std; const int N = 8; int p [N+1] [N+1]; void tisk () { for (int r = 1; r <= N; r++) { for (int s = 1; s <= N; s++) { if (p [r][s] == -1) cout << ' '; else cout << p [r][s]; cout << ' '; } cout << endl; } cout << endl; } void jump (int r, int s, int v = 0) { if (r >= 1 && r <= N && s >= 1 && s <= N) …

jezdec_st

Anonymous (anonymous@undisclosed.example.com) — 2021-03-24T14:15:14+00:00

Hledání nejkratší cesty jezdcem Mapa vzdáleností #include using namespace std; const int N = 8; int p [N+1] [N+1]; // mapa vzdalenosti, radek a sloupec 0 nepouzivame void tisk () { for (int i = 1; i <= N; i++) { for (int k = 1; k <= N; k++) { int v = p[i][k]; if (v >= 0) cout << v; else cout << "."; cout << " "; } …

jezdec

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:04:58+00:00

Hledání nejkratší cesty jezdcem Hledání nejmenšího počtu tahů/skoků koněm mezi dvěma zadanými políčky. Vyvoříme si “mapu” vzdáleností. Výchozí políčko ohodotíme čislem 0. Okolní políčka do kterých se dostaneme jedním skokem číslem

lexi_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-05-06T12:54:15+00:00

Lexikografické třídění #include using namespace std; const int D = 20; // delka retezce const int K = 256; // pocet prihradek struct Item { char key [D+1]; // retezce ukoncene 0 Item* next; }; struct List // prihradka { Item * first; Item * last; }; void clear (List & p) { p.first = nullptr; p.last = nullptr; } void insertLast (List & p, Item * t) { if (p.first == nullptr) p.first = t; else p.last->next = t; p.last = t; t…

lexi

Anonymous (anonymous@undisclosed.example.com) — 2020-05-11T16:28:24+00:00

Lexikografické třídění Příhrádkové třídění - skripta 5.4.1 Lexikografické třídění - skripta 5.4.2 * Budeme třídit řetězce dlouhé D znaků * Každý znak může nabývat K hodnot, vytvoříme K příhrádek * V našem programu budeme třídit jen řetězce složené z číslic, stačilo by 10 příhrádek

mult

Anonymous (anonymous@undisclosed.example.com) — 2021-05-12T14:54:27+00:00

Násobení čísel typu float #include #include using namespace std; const int bias = 127; const int emax = 255; const int emin = 0; struct Number { unsigned int m : 23; // 23 bitu 1 . m1 m2 m3 m23 unsigned int e : 8; // exponent 8 bitu, e = 0 ... 255, 2^(e-127) unsigned int s : 1; // znamenko, s = 0 nebo 1, (-1)^s }; void mul (Number & z, Number x, Number y) // z = x*y { int xm = x.m | 1 << 23; int ym = y.…

nakresli_strom

Anonymous (anonymous@undisclosed.example.com) — 2021-03-15T16:57:55+00:00

Nakresli strom mxGraph #include #include using namespace std; struct Item { int key; Item* left; Item* right; // Item () { key = 0; left = nullptr; right = nullptr; } Item () : key (0), left (nullptr), right (nullptr) { } }; Item* root = nullptr; Item* search (Item* p, int value) { while (p != nullptr && p->key != value) { if (value < p->key) p = p->left; else p = …

quicksort_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-04-01T13:10:10+00:00

Quick Sort #include #include using namespace std; const int N = 1000000; int a [N]; inline void swap (int i, int k) { int t = a [i]; a [i] = a [k]; a [k] = t; } void quickSort (int r, int s) // setridit a[r], ..., a[s] { int i = r; int k = s; int h = a [ (r+s)/2 ]; while (i <= k) { while (a[i] < h) i++; while (a[k] > h) k--; if (i <= k) { swap (i, k); // prohodit a[i] <-> a[k] …

quicksort_st

Anonymous (anonymous@undisclosed.example.com) — 2021-04-07T13:19:26+00:00

Quick Sort #include #include using namespace std; // const int N = 7; // int a [N] = { 10, 4, 8, 20, 7, 5, 1 }; const int N = 1000000; int a [N]; inline void swap (int i, int k) { int t = a [i]; a [i] = a [k]; a [k] = t; } void quickSort (int r, int s) { // cout << r << ", " << s << endl; int h = a [ (r+s)/2 ]; int i = r; int k = s; while (i <= k) { while (a[i] < h) i++; while (a[k] > h) k--; if (i <= k) …

quicksort

Anonymous (anonymous@undisclosed.example.com) — 2021-04-01T12:19:18+00:00

Quicksort Funkce quicksort (int r, int s) Funkce quicksort sparametry (r, s) má setřídit část globálního pole a. Třídí prvky a[r], ..., a[s]. Výběr pivotu Vybereme si jednu hodnotu z této části, nazveme ji pivot a uložíme do proměnné

strom_add

Anonymous (anonymous@undisclosed.example.com) — 2023-05-11T10:38:06+00:00

Hledání prvku ve stromu zdrojový text Funkce search je vlastne cyklus jdouci od korene dolu k listum. Pokud najde hledany klic, vrati ukazatel na cely uzel stromu. Pokud nenajde, vraci nullptr. Parametrem je ukazatel na koren stomu a hodnota hledaneho klice.

strom_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-03-04T14:28:21+00:00

Jednosměrný seznam #include using namespace std; struct Item { string name; int r, g, b; Item* next; }; Item* first = nullptr; // prazdny seznam void print(Item* t) { cout << t->name << " " << t->r << "," << t->g << "," << t->b << endl; } Item * find (string name0) { Item * p = first; while (p != nullptr && p->name != name0) { p = p->next; } return p; } int main() { Item* c = new Item; c->name = "cervena"; c->r = 255; …

strom_del

Anonymous (anonymous@undisclosed.example.com) — 2020-04-07T08:11:01+00:00

Odpojení jednoho prvku ze stromu zdrojový text Skripta, příklad 2.4, odstavec: Zrušení vrcholu Item * remove (Item * & p, int k) Funkce remove ma ve stromu s korenem p najit a odpjit prvek s klicem k. Funkce remove vraci ukazatel na odpojeny prvek.

strom_src

Anonymous (anonymous@undisclosed.example.com) — 2020-04-20T14:02:45+00:00

#include using namespace std; struct Item { int key; Item * left; Item * right; Item () : key (0), left (nullptr), right (nullptr) { } }; Item * root = nullptr; Item * search(Item* p, int k) { while (p != nullptr && p->key != k) { if (k < p->key) p = p->left; else p = p->right; } return p; } Item* find(Item* p, int k) { if (p == NULL || p->key == k) { return p; } …

strom_st

Anonymous (anonymous@undisclosed.example.com) — 2021-03-10T14:24:12+00:00

veze_ct

Anonymous (anonymous@undisclosed.example.com) — 2021-04-29T13:13:58+00:00

Hanojské věže #include #include using namespace std; const int N = 5; struct Vez { int v; // vyska int p [N+1]; // p[0] nepouzivame, p[1] velikost spodniho disku, ... p[v] velikost horniho disku }; void napln (Vez& X) { X.v = N; X.p [0] = 0; for (int i = 1; i <= N; i++) X.p [i] = N + 1 - i; } void nuluj (Vez& X) { X.v = 0; for (int i = 0; i <= N; i++) X.p[i] = 0; } /* void krok (Vez & X, Vez & Z) { int d = X.p [X.v]; X.v --; Z.v…

veze_st

Anonymous (anonymous@undisclosed.example.com) — 2021-04-28T13:14:50+00:00

Hanojské věže #include using namespace std; const int Max = 4; struct Vez { int v; // vyska, pocet disku int p [Max+1]; // p[1] velikost spodniho disku, ..., p[v] horniho horniho disku, p[0] nepouzivame }; void nuluj (Vez & X) { X.v = 0; for (int i = 0; i < Max+1; i++) X.p [i] = 0; } void napln (Vez & X) { X.v = Max; for (int i = 1; i <= Max; i++) X.p[i] = Max + 1 - i; } void krok (Vez & X, Vez & Z) { int d = X.p [X.v]; // horni hisk X.v --; …

veze

Anonymous (anonymous@undisclosed.example.com) — 2020-09-30T09:10:59+00:00

Hanojské věže * Máme N disků na první věži * V jednotlivých krocích přenášíme jeden disk z vrcholu některé věže na vrchol jiné věže * Nesmíme položit větší disk na menší * Cílem je přemístit všechny disky na třetí věž

video

Anonymous (anonymous@undisclosed.example.com) — 2020-04-20T19:21:14+00:00

Algoritmy Data Structures and Algorithms Heap sort Heap sort Quick sort quick sort Abdul Bari, QuickSort Abdul Bari, QuickSort Analysis Jenny's lectures, QuickSort Vyvážené stromy AVL tree Abdul Bari, AVL tree

zalg

Anonymous (anonymous@undisclosed.example.com) — 2023-07-12T10:08:25+00:00

Příklady Příklady naleznete v GIT repository Letošní cvičení ve úterý Letošní cvičení ve čtvtek Nejjednodušší přístup k zdrojovým souborům na zmíněné webové stránce je tlačítko “Download”, schované vedle tlačítka