Search
Naším úkolem je rozluštit zprávu zakódovanou Caesarovou šifrou, která funguje na principu záměny písmene z abecedy za písmeno posunuté o pevně určený počet míst. V našem případě máme k dispozici nejen zašifrovaný text, ale také nespolehlivě odposlechnuté originální znění zprávy, tj. některé znaky originální zprávy jsou chybně zapsány. Řešení tak můžeme založit na testování všech možností kódování Caesarovou šifrou a porovnání s odposlechnutým textem. Posun s největší shodou dekódovaného textu s odposlechnutou zprávu budeme považovat za správný a takto dekódovaný text je náš požadovaný výstup. Obecně nemusí tento postup vést na unikátní správné řešení, nicméně v testovaných případech vždy existuje unikátní řešení.
Jedním z cílů tohoto domácího úkolu je procvičení dynamické alokace paměti na základě velikosti vstupu. Proto délka vstupního textu není dopředu známa a je nutné v případě vyčerpání počáteční velikost (např. 10-100 znaků) dynamicky alokovat prostor větší, např. funkcí realloc() pro dvojnásobnou délku. V programu používejte pouze množství paměti, které řádově odpovídá zadanému vstupu. Odevzdávací systém kontroluje velikost dynamicky alokované paměti.
realloc
Použitá abeceda se skládá pouze z malých a velkých písmen bez diakritiky, tj. znaky v rozsahu [a-zA-Z].
getchar()
scanf(“%c”,…)
Použití metody dynamického načítání textového řetězce prostřednictvím rozšíření scanf(“%ms”) nebo scanf(“%as”) není z tohoto důvodu povoleno.
Na standardním vstupu očekávejte dvě posloupnosti znaků (texty) na samostatných řádcích. První text je zakódovaná zpráva a druhý text je nespolehlivě odposlechnutý text.
Error: Chybny vstup!
100
stderr
Error: Chybna delka vstupu!
101
Na standardní výstup vypište dekódovanou zprávu jako posloupnost znaků zakončenou znakem konce řádku. Program končí s návratovou hodnotou 0.
0
Program vhodně dekomponujte na jednotlivé funkce, např. funkce pro dekódování textu o definovaný posun a výpočet vzdálenosti dvou textových řetězců:
void shift(const char *src, char *dst, int offset); int compare(const char *str1, const char *str2);
Dále může být vhodné napsat funkci pro šifrování jednoho písmene, která bude respektovat zadanou abecedu [a-zA-Z]. Například:
char rotate(char original, int offset);
V prvním příkladu je zašifrován text “Helloworld”. Posun je zde o 42 písmen. (16 míst je mezi 'h' a 'x'; 26 pak mezi malými a velkými písmeny). Zašifrovaný text je tedy “xUbbemehbT”.
Helloworld
xUbbemehbT
Odposlechnutý text může být například “??lloworld”, kde písmena na místě otazníku špatně odposlechneme a dostaneme jiné náhodné písmeno, například “XYlloworld”.
??lloworld
XYlloworld
xUbbemehbT XYlloworld
Příklad vyhodnocení. Největší počet shodných písmen (8/10) má posun o 10, proto jej vyhodnotíme jako správný výsledek.
00: xUbbemehbT ~ XYlloworld > correct letters: 0 01: yVccfnficU ~ XYlloworld > correct letters: 0 02: zWddgogjdV ~ XYlloworld > correct letters: 0 03: AXeehphkeW ~ XYlloworld > correct letters: 0 04: BYffiqilfX ~ XYlloworld > correct letters: 1 05: CZggjrjmgY ~ XYlloworld > correct letters: 0 06: DahhksknhZ ~ XYlloworld > correct letters: 0 07: Ebiiltloia ~ XYlloworld > correct letters: 0 08: Fcjjmumpjb ~ XYlloworld > correct letters: 0 09: Gdkknvnqkc ~ XYlloworld > correct letters: 0 10: Helloworld ~ XYlloworld > correct letters: 8 -- result 11: Ifmmpxpsme ~ XYlloworld > correct letters: 0 12: Jgnnqyqtnf ~ XYlloworld > correct letters: 0 ... 50: vSZZckcfZR ~ XYlloworld > correct letters: 0 51: wTaadldgaS ~ XYlloworld > correct letters: 0 52: xUbbemehbT ~ XYlloworld > correct letters: 0
mnoXYhnJLA JCudvgtXRi
studentPRG
fghQRa-CEC scbdeMKARZ
fghQRa scbdeMK
for (int i = 0; i < strlen(text); i++) { ... }
U bonusové části úlohu rozšiřujeme o možnost úplné ztráty písmene nebo naopak odposlechnutí písmene, které nebylo vůbec vysláno. Vstupní texty tak mohou mít různou délku. V tomto případě věrohodný text určíme na základě Levenštejnovy vzdálenosti vypočtené pomocí Wagner-Fisher algoritmu. Vstup pro volitelné zadání může obsahovat dva texty různé délky. Proto nevypisujeme chybu 101. Použití Levenštejnovy vzdálenosti by fungovalo i pro povinné zadání, ale bylo by výrazně pomalejší, používalo více paměti a odevzdávací systém by ho neakceptoval. Používejte proto prosím Levenštejnovu vzdálenost výhradně pro testovací vstupy z volitelného zadání. Používejte dynamickou alokaci paměti.
xUbbemehbT Hellwooorld
Příklad vzdálenostní macite při výpočtu vzdálenosti pomocí Wagner-Fisher algoritmu. Matice je vyplňována postupně po řádcích s využitím předchozích hodnot (dynamické programování).
Levenštejnova vzdálenost je zde rovna jedné, protože stačí pouze jedna operace odebrání písmena.