Zadání projektů

Obecné zásady

TYTO POZNÁMKY SI OPRAVDU PŘEČTĚTE!

U všech projektů se hodnotí zejména:

Forma výsledného programu:

V řešení se nesmí vyskytnout zejména:

Seznam úloh

  1. Rotace matice po spirále
  2. Enigma rotace
  3. Řešení soustavy rovnic
  4. Řazení lineárního seznamu
  5. Analýza barev
  6. Body na přímce
  7. Středy kružnic
  8. Obvod mnohouhelnika
  9. Obsah mnohouhelnika
  10. Čtyři roviny
  11. Test obecného sudoku
  12. Vigenerova šifra
  13. Steganografie
  14. Množiny

Vstupní data pro maticové operace

Vytvořte program, který ze souboru zadaného prostřednictvím parametru příkazového řádku přečte matici celých čísel ve formátu:

R S
a11 a12 .... a1S
a21 a22 .... a2S
 .            .
 .            .
aR1 aR2 .... aRS

Na prvním řádku jsou rozměry matice (R - řádky, S - sloupce) a na dalších řádcích se nachází prvky matice oddělené bílými znaky. Detekujte případné chyby ve vstupním souboru (neúplná matice, chybný formát čísel).

Zpět na seznam úloh

Rotace matice po spirále

Vytvořte program pro zpracování matic. Specifikace vstupních hodnot viz Vstupní data pro maticové operace.

Proveďte rotaci prvků v matici podle křivky naznačené na obrázku. Rohový prvek matice označený tečkou udává počet, o kolik pozic se po zadané křivce posune každý prvek v matici. Kladný směr rotace je naznačen na obrázku, záporný směr jde opačně. Prvek, který při rotaci vypadne na konci křivky, se přesouvá na začátek křivky (tedy do výchozího bodu). Výsledkem operace je tedy matice stejných rozměrů, v níž budou jednotlivé prvky posunuty vůči své původní pozici po zadané křivce.

Výslednou matici vytiskněte na standardní výstup ve stejném formátu, jako vstup (tedy včetě rozměrů).

Spirála

Zpět na seznam úloh

Enigma rotace

Vytvořte program pro zpracování matic. Specifikace vstupních hodnot viz Vstupní data pro maticové operace.

Kromě jména souboru bude program rozumět dvěma dalším parametrům: -vertical a -horizontal. Při zadání parametru -vertical, bude program rotovat jednotlivé sloupce zadané matice o tolik pozic, kolik udává prvek na indexu 0 v tomto sloupci. Prvky, které při rotaci ze sloupce na jedné straně vypadnou, se objeví na druhé straně. Rotace kladným směrem znamená rotaci ve směru shora dolů, rotace v záporném směru znamená rotaci zdola nahoru. Při zadání parametru -horizontal bude program fungovat podobně, ale pro řádky. Kladný směr znamená rotaci zleva doprava, záporný směr rotaci zprava doleva.

Výslednou matici vytiskněte na standardní výstup ve stejném formátu, jako vstup (tedy včetně rozměrů).

Zpět na seznam úloh

Řešení soustavy rovnic

Vytvořte program pro zpracování matic. Specifikace vstupních hodnot viz Vstupní data pro maticové operace.

Načtenou matici považujte za matici koeficientů soustavy rovnic. Vyřešte tuto soustavu a vypíšte na výstup vektor řešení (nebo hlášení o tom, že soustava nemá řešení, či jich má nekonečně mnoho, ...). Implemntujte alespoň dvě různé metody řešení soustav rovnic. Každá z metod se bude zapínat jiným parametrem z příkazové řádky.

Zpět na seznam úloh

Seřazení lineárního seznamu

Načtěte ze souboru libovolně dlouhou posloupnost anglických slov oddělených bílými znaky (nemusíte uvažovat diakritiku) do lineárního seznamu. Vyberte si libovolnou metodu řazení a seznamte se s ní. Seřaďte načtená data a výsledek uložte do výstupního souboru tak, že každé slovo bude ležet na samostatném řádku. Zvolenou metodu řazení musíte dokonale pochopit, protože ji posléze budete prezentovat ostatním studentům.

Vstupní i výstupní soubor si uživatel bude volit pomocí parametru příkazového řádku.

Zpět na seznam úloh

Analýza barev

Napište program, který bude ze souboru (zadán parametrem příkazového řádku) číst údaje o barvách ve formátech RGB a HSV (bude se přepínat pomocí parametru příkazového řádku), co řádek to jedna barva:

128 128 128
0 50 0
255 128 0
200 200 200
...

Hodnoty jednotlivých barevných složek budou v intervalu 0 až 255 (nutno otestovat při čtení). Po přečtení údaje o jedné barvě, program vypíše do výstupního souboru (zadán parametrem příkazového řádku) slovní popis této barvy. Například takto:

Šedá
Tmavě zelená
Oranžová
Světle šedá
...

Program musí zohlednit citlivost lidského oka na jednotlivé složky barevného spektra.

Pojmy RGB, HSV a vysvětlení citlivosti lidského oka na barvy lze najít např. na Wikipedii.

Zpět na seznam úloh

Geometrie - body na přímce

Napište program, který bude číst ze souboru po trojicích souřadnice bodů v prostoru (jeden řádek - devět čísel - 3x3 souřadnice) a do výstupního souboru bude zapisovat na odpovídající řádky slova "ANO" a "NE" v závislosti na tom, zda všechny tři body leží nebo neleží na stejné přímce. Pracujte s datovým typem double.

Formát vstupního souboru:

0 0 0 1 1 1 20.3 20.3 20.3
0.4 0.6 0.1 1.1 0.6 1.7 3.1 7.2 10.6
...

Formát výstupního souboru:

ANO
NE
...
Zpět na seznam úloh

Středy kružnice

Napište program, který bude číst ze souboru po trojicích souřadnice bodů na ploše (jeden řádek - šest čísel - 3x2 souřadnice) a do výstupního souboru bude zapisovat na odpovídající řádky souřadnice středu kružnice, která je určena třemi vstupními souřadnicemi. Pokud tři vstupní body neleží na kružnici, vypište na výstupní řádek hodnotu konstanty NAN (not a number). Pracujte s hodnotami typu double.

Formát vstupního souboru:

0 0  1 1  20.3 20.3
0 1  1 0  0 -1
...

Formát výstupního souboru:

#
0.00000000e00
...
Zpět na seznam úloh

Obvod mnohoúhelníka

Napište program, který bude číst ze souboru souřadnice bodů na ploše a na standardní výstup zapíše obvod obrazce, který je vymezen těmito body. Předpokládejte, že jsou propojeny vždy následující body a také první a poslední - tímto je vytvořen uzavřený obrazec. Zjistěte, zda jde opravdu o mnohoúhelník, tj. jestli se některé hrany zadané cesty nekříží. Pokud nepůjde o mnohoúhelník, vytiskněte na chybový výstup chybové hlášení (jinak ne). Pracujte s datovým typem double.

Formát vstupního souboru:

0 0  1 1  20.3 20.3 0 1  1 0  0 -1
...

Formát výstupního souboru:

123.567
V zadané cestě se kříží hrany, nejde tudíž o mnohoúhelník.
Zpět na seznam úloh

Obsah konvexního trojúhelníka pomocí triangulace

Vytvořte program, který bude mít stejný vstup, jako předchozí úloha. Program ověří, že zadaný mnohoúhelník je konvexní a pokud ano, provede triangulaci (není potřeba hledat minimální triangulaci) a vypočte obsah zadaného útvaru. Výsledek vypište na standardní výstup. Pracujte s datovým typem double.

Nápověda

Diagonálou konvexního N-úhelníku nazveme každou úsečku spojující dva jeho různé vrcholy, které spolu nesousedí na obvodu

Triangulací konvexního N-úhelníku označujeme takovou množinu jeho neprotínajících se diagonál, které rozdělují plochu N-úhelníku na samé trojúhelníky.

Zpět na seznam úloh

Čtyři roviny

Mějme čtyři roviny v prostoru. Každá rovina je zadána třemi body. Zjistěte, zda se všechny tři roviny navzájem protínají a v případě, že ano, vypište souřadnice bodů, kde se tři roviny protínají a vypočtěte povrch (případně i objem) takto vymezeného tělesa. Body budou zadávány ze vstupního souboru (nebo stdin) pomocí 3D souřadnic:

x1r1 y1r1 z1r1
x2r1 y2r1 z2r1
x3r1 y3r1 z3r1
x1r2 y1r2 z1r2
x2r2 y2r2 z2r2
x3r2 y3r2 z3r2
x1r3 y1r3 z1r3
x2r3 y2r3 z2r3
x3r3 y3r3 z3r3
x1r4 y1r4 z1r4
x2r4 y2r4 z2r4
x3r4 y3r4 z3r4

Výsledek vypisujte na standardní výstup. Pracujte s datovým typem double.

Zpět na seznam úloh

Test řešení obecného sudoku

Vytvořte program, který ověří, jestli je zadaná matice řešením obecného sudoku. Specifikace vstupních hodnot viz Vstupní data pro maticové operace. Výsledek zapište na standardní výstup.

Klasické sudoku je tvořeno maticí rozměru 9x9, která je rozdělena na 9 submatic o rozměrech 3x3. Řešením klasického sudoku je taková matice, ve které se mohou vyskytovat hodnoty 1 až 9 a to tak, že se každá číslice vyskytuje právě jednou ve svém řádku, ve svém sloupci i ve své submatici.

Hru sudoku lze zobecnit tak, že prohlásíme klasické sudoku za sudoku řádu 3. Obecné sudoku řádu N (N je přirozené číslo > 0) je tvořeno maticí N2xN2, která je rozdělena na N2 submatic o rozměrech NxN, a ve které se mohou vyskytovat pouze hodnoty z intervalu 1 až N2.

Zpět na seznam úloh

Kryptografie - Viegenerova šifra

Vytvořte program, který zašifruje vstupní soubor tímto způsobem:

Každý znak vstupního souboru se sloučí pomocí operace XOR se znakem klíče na odpovídající pozici. Následně se v celém tomto souboru provede kruhový posuv o N bitů doprava tak, že bity ze znaku vlevo přetečou do znaku vpravo a bity z posledního znaku přetečou do prvního znaku v souboru.

Program si načte z příkazového řádku název souboru, který má zašifrovat, název souboru, do kterého se má uložit výsledek a heslo(klíč). Hodnota N se vypočítá z klíče jako součet všech znaků klíče modulo 11. Šifrování se bude zapínat přepínačem -s a dešifrování se bude zapínat přepínačem -d. Zamyslete se nad silou tohoto způsobu šifrování dat. Jakým způsobem by šlo tuto šifru zdolat? (Můžete naprogramovat.)

Zpět na seznam úloh

Kryptografie - Steganografie

Vytvořte program, který provede zašifrování vstupního souboru pomocí steganografie do bitmapového obrázku. Klíčem bude samotný bitmapový obrázek.

Jméno šifrovaného souboru a obrázek zadávejte pomocí parametrů příkazové řádky. Šifrování se bude zapínat přepínačem -s a dešifrování se bude zapínat přepínačem -d. Zamyslete se nad silou tohoto způsobu šifrování dat.

Zpět na seznam úloh

Množiny - bitové operace - opakující se znaky

V jazyce C neexistuje datový typ množina jako v Pascalu. Úkolem je implementace abtraktního datového typu množina podle Pascalovského vzoru (využití všech bitů proměnné/pole). Tento abstraktní datový typ použijte pro řešení následující úlohy:

Ve vstupním textovém souboru zjistěte, které znaky jsou společné pro N-tice po sobě jdoucích řádků. Parametr N zadávejte z příkazové řádky programu. Znaky společné pro každou N-tici vypisujte do výstupního souboru na zvláštní řádek (pokud N=5 a soubor má 18 řádků, pak ve výstupním souboru budou 4 řádky, odpovídající každé z N-tic, kde poslední N-tice bude neúplná).

Zpět na seznam úloh


Poslední modifikace: 15. December 2008. Pokud v tomto dokumentu narazíte na chybu, dejte mi prosím vědět.