Aktuální informace:
Tohle je stranka k cvičení z akademickeho roku 2000/2001. Stránka je
studentům stále k dispozici
jako případný doplňující studijní materiál.
Tady je odkaz na úlohy z programovacích soutěží.
Odkaz na přednášejícího: RNDr.
Tomáš Holan - požadavky ke zkoušce, sylaby, příklady
Odkaz na mou domácí stránku: RNDr.Martin
Čížek, Ph.D. (např. telefony a kde sídlím)
Zde naleznete seznam studentů a informace (patrně již finální) o zápočtech.
Tady je, seznam možných zápočtových úloh.
Některé úlohy, které jsem včas nezařadil:
- integrace + unit
- třídění + unit
- simulace růstu krystalu - nedokončená
Cvičení ze dne 14. 5. 2001:
Úkol: Návrh úlohy s použitím objektů. Navrhněte datové struktury
a abstraktní metody
pro reprezentaci vektorového
prostoru se skalárním součinem a napište programovou
jednotku (UNIT) obsahující
navíc ještě obecnou proceduru pro Gramovu-Schmidtovu
ortonormalizaci. Tuto jednotku
aplikujte na ortonormalizaci vektrů v rovině a na
ortonormalizaci polynomů
(skalární součin = integrál od 0 do 1).
Řešení: Obecná jednotka pro ortogonalizaci může vypadat třeba
takto
a
aplikace na rovinu zase
takhle.
Jednoduchá reprezenatace polynomů je tady.
Také si budeme povídat o diskrétních simulacích (jestli to stihneme).
Cvičení LS-8 ze dne 9. 4. 2001:
1) Dokončení úkolu 2 z minulého cvičení.
Úkol:
Cvičení LS-7 ze dne 2. 4. 2001:
Úkol 1: Průchod obra lesem. Les je zadán jako obdélník o rozměrech
šířka krát délka
a v něm jsou
zadány souřadnice kmenů stromů. Obr je kruh poloměru R. Zjistěte
zda může obr
projít skrz les.
Řešení je tady.
A tady vstupní soubory pro průchozí a neprůchozí
les.
Rozšíření:
řekněte jak by se dalo nejen zjistit, zda lze či nelze projít, ale i vypsat
cestu.
Úkol 2: Navrhněte algoritmus, který pro zadanou rostoucí posloupnost
kladných celých čísel
vytiskne vzestupně
uspořádané prvky množiny součtů dvojic čísel z posloupnosti.
Např.
pro zadanou posloupnost 1, 2, 3, 11 algoritmus vytiskne
2, 3, 4, 5,
6, 12, 13, 14, 22.
Paměťové nároky
musí být nižší než O(N^2).
Řešení:
Na cvičení jsme si vysvětlili, že si stačí pamatovat N součtů a kvůli snadnějšímu
výběru a zařazování nových součtů se hodí mít je uspořádány do haldy.
Program používající haldu reprezentovanou polem indexů je zde.
Cvičení LS-6 ze dne 26. 3. 2001:
Úkol: Projížďka na kole americkým městem: Úkolem je najít
nejkratší cestu
městem se čtvrcovou
sítí ulic v nichž některé jsou jednosměrky a někde
je to moc do
kopce, takže se vám tam nechce. Přesné zadání je tady.
Ukázkové
řešení. Vstupní soubor.
Cvičení LS-5 ze dne 19. 3. 2001:
Úkol: Navrhnout datovou strukturu pro práci s řídkými polynomy
a realizovat:
načtení polynomu
z klávesnice, vypsání polynomu, součet dvou polynomů
a násobení polynomů.
Cvičení LS-4 ze dne 12. 3. 2001:
Na cvičení mne zastupoval Karel Houfek.
Na cvičení se řešilo:
1) Mějme čísla 1 2 3 4 5 6 7 8
9, mezi které můžeme umístit +,-,*,/ (které
znamená
celočíselné dělení) a nebo take nic, tj. např. 5+6 7*8 znamená
5+67*8.
Smyslem úlohy je určit všechny kombinace operací, abychom
dostali
po vyhodnocení výrazu (*,/ mají prioritu pred +,-) dostali
požadované
číslo, které je vstupem daného programu.
2) Procvičit si práci se stromem
uloženém v dynamické datové struktuře.
Úkolem
je ze souboru načíst Morseovku do binárního stromu, který se
větví
podle toho zda následuje tečka nebo čárka a obsahuje význam znaku.
Poté napsat
proceduru, která interpretuje Morseovku v reálném čase.
Úlohu
je možné řešit takto, se vstupním souborem
obsahujícím tabulku znaků.
Cvičení LS-3 ze dne 5. 3. 2001:
Úkol: Procvičit si typ ukazatel a datové struktury.
1) Výpočet posloupnosti dané rekurentně
pomocí k předchozích členů. Použití
cyklyckého seznamu. Ukázkové řešení.
2) Napsat samoučící program, který
hádá zvíře posloupností otázek na něž uživatel
odpovídá
ano či ne. Pokud zvíře nezná, zeptá se na něj a na rozlišovací otázku.
Vše si
pamatuje ve formě binárního stromu. První jednoduchá
verze je zde.
Další
možnosti: ukládat jednou naučené do souboru, možnost rušit podstrom.
Cvičení LS-2 ze dne 26. 2. 2001:
Úkol: Rozbor úloh ze zápočtových testů.
1) Načíst text ze souboru
a vypsat seznam deset nejčastěji se vyskytujících slov.
Řešení
1: Takhle jsme to dělali na cvičení.
Řešení
2: Jiné řešení. Všimněte si použití typu
množiny pro zestručnění testovacích podmínek
a také použití příkazu EXIT, který vyskočí
z právě prováděné procedury či funkce.
A ještě nějaky vstupni text pro testování.
Cvičení LS-1 ze dne 19. 2. 2001:
Úkol: Počítačové řešení hlavolamu "Loydova patnáctka":
1) Navrhnout vhodny
popis.
2) Vygenerovat složitelnou
pozici.
3) Nastínit algoritmus
pro automatické řešení hlavolamu.
Nyní je zde již skutečtě obecně fungující verze.
Pokud máte zájem, můžete si ji ještě sami vylepšit
(Efektivnější řešení, lepší grafika ...)
Několik řešených úloh z minulého semestru:
1) Batoh: Zjištění maximální náplně batohu.
Známe jeho nosnost a máme danou sadu závaží.
Program: Batoh.pas
Vstupní soubor: Zavazi.txt
2) Fibonacci: Výpočet Fibonacciho čísel
různými metodami.
Program: Fib.pas
3) Hlad: Výčetka platidel a McNugget-čísla.
Program: Hlad.pas
4) Klíč: Zjištění počtu klíču, které lze
vyrobit zadaným způsobem.
Program: Klic.pas
5) Mobil: Soustava trámků, špagátů a závaží.
Načtení, zjištění je-li vyvážená a tisk.
Program: Mobil.pas
Vstupní soubor: Mobil1.txt
6) Molekuly: Reprezentace molekuly a výpočet
jejího těžiště.
Program: Molekuly.pas
Vstupní soubor: Mndljv.txt
7) Pauli: Malé cvičení na téma "záznamy".
Program: Pauli.pas
8) Posloupnost: Hledání nejdelší rostoucí
podposloupnosti v náhodně vygenerované posloupnosti.
Program: Posl.pas
9) Úsečky: Určení počtu otvorů, které vzniknou
v papíru po provedení N přímých řezů.
Program: Usecky.pas
Vstupní soubor: Vstup.txt