Back to School

Jednorozmerné pole, frekvenčná tabuľka, algoritmizácia, ladenie programov, štandardný vstup, používanie polí ako parametre funkcií.

Motivácia

Vašou úlohou bude dnes rozlúštiť zašifrovaný text. Na šifrovanie bola použitá jednoduchá substitučná šifra, kde dochádzalo k nahrádzaniu písmen 'a''z' (napr. písmeno 'a' bolo všade v texte nahradené písmenom 'f'). V texte zostali zachované interpunkčné znamienka (t.j. čiarky, bodky, výkričníky, otázniky a pod.), nezáleží na veľkosti znakov (to znamená, že ak sa písmeno 'b' nahrádza písmenom 'k', bude sa aj písmeno 'B' nahrádzať písmenom 'K') a mäkčene a dĺžne neboli vzaté do úvahy vôbec (samotny text nebude zapisany s diakritickymi znakmi).

Ciele

  1. Práca s jednorozmerným poľom.
  2. Tvorba vlastných funkcií vracajúcich hodnotu.
  3. Tvorba algoritmov v jazyku C.
  4. Práca s funkciami knižnice stdlib.h.
  5. Presmerovanie štandardného vstupu.
  6. Ladenie programu pomocou cgdb.

Postup

Krok #1: Bootstrap

V tomto kroku sa budeme venovať výlučne vytvoreniu potrebných funkcií pre rozšifrovanie zadaného textu.

Úloha 1.1

Vytvorte funkciu build_ftable(), pomocou ktorej vytvoríte tzv. frekvenčnú tabuľku.

Frekvenčná tabuľka predstavuje výskyt písmen v danom texte. Ak by bol v našom prípade vstupným textom text:

Ahoj jano!
počet výskytov písmena 'a' v texte by bol 2 a písmena 'b' by bol 0.

Deklarácia funkcie je nasledovná:

void build_ftable(int ftable[]);
kde:
  • ftable reprezentuje vstupno-výstupný parameter funkcie, ktorým je frekvenčná tabuľka. Toto pole bude mať toľko prvkov, koľko je písmen abecedy, pričom na prvej pozícii sa bude nachádzať frekvencia používania písmena 'a' v texte a na poslednom zasa frekvencia používania písmena 'z' v texte.

Keďže zatiaľ nevieme pracovať so súbormi, text, z ktorého frekvenčnú tabuľku zostavíte, načítate priamo zo štandardného vstupu. Keďže ale načítavaný text bude dlhší, presmerujte štandardný vstup zo súboru, v ktorom budete mať vstupný text uložený.

Úloha 1.2

Overte správnosť svojho programu.
Ak ste postupovali správne, tak frekvenčná tabuľka pre vstupný text uložený v súbore laktibrada.txt bude vyzerať nasledovne:
$ ./table < laktibrada.txt
A - 847
B - 109
C - 206
D - 285
E - 537
F - 1
G - 2
H - 117
I - 365
J - 142
K - 226
L - 294
M - 188
N - 287
O - 486
P - 155
Q - 0
R - 239
S - 286
T - 319
U - 215
V - 228
W - 0
X - 0
Y - 127
Z - 179

Úloha 1.3

Vytvorte funkciu build_ttable(), pomocou ktorej vytvoríte prekladovú tabuľku (translation table).

Prekladová tabuľka bude slúžiť práve na mapovanie písmen - originálne písmeno abecedy za nahradzujúce písmeno. Táto tabuľka však bude stále reprezentovaná jednorozmerným poľom, takže mapovanie bude nasledovné: index položky bude reprezentovať písmeno originálnej abecedy, pričom obsah položky bude reprezentovať index kódovaného písmena. Ak sa napr. na indexe 5 bude nachádzať hodnota 0, budeme písmeno 'f' kódovať písmenom 'a'.

Deklarácia funkcie vyzerá nasledovne:

void build_ttable(const int ftable[], int ttable[]);
, kde
  • ftable predstavuje frekvenčnú tabuľku (zostavenú pomocou funkcie build_ftable()),
  • ttable predstavuje vstupno-výstupný parameter, v ktorom sa bude nachádzať výsledná prekladová tabuľka

Prekladovú tabuľku zostavíte tak, že obsah frekvenčnej tabuľky usporiadate vzostupne (od najmenšej hodnoty po najväčšiu).

Poznámka:  Pre vyriešenie tejto úlohy môžete využiť aj funkcie qsort() a bsearch() z knižnice stdlib.h.

Úloha 1.4

Overte správnosť svojej implementácie.
Ak ste postupovali správne, tak pre frekvenčnú tabuľku vytvorenú z textu laktibrada.txt bude prekladová tabuľka vyzerať nasledovne:
A - 25
B - 5
C - 12
D - 17
E - 24
F - 3
G - 4
H - 6
I - 22
J - 8
K - 14
L - 20
M - 11
N - 19
O - 23
P - 9
Q - 0
R - 16
S - 18
T - 21
U - 13
V - 15
W - 1
X - 2
Y - 7
Z - 10
pričom vzostupne usporiadaný výstup frekvenčnej tabuľky pre tento súbor vyzerá nasledovne:
A - 0
B - 0
C - 0
D - 1
E - 2
F - 109
G - 117
H - 127
I - 142
J - 155
K - 179
L - 188
M - 206
N - 215
O - 226
P - 228
Q - 239
R - 285
S - 286
T - 287
U - 294
V - 319
W - 365
X - 486
Y - 537
Z - 847

Krok #2: Encryption and Decryption

V predchádzajúcom kroku sme vytvorili prekladovú tabuľku s pomocou frekvenčnej tabuľky. Máme teda všetko pripravené pre to, aby sme mohli zakódovať a rozkódovať ľubovoľný text.

Úloha 2.1

Vytvorte funkciu decrypt(), pomocou ktorej budete vedieť rozšifrovať zadaný text.

Deklarácia tejto funkcie je nasledovná:

void decrypt(const int ttable[], char text[]);
kde:
  • ttable - prekladová tabuľka
  • text - vstupno-výstupná premenná, ktorá pri zavolaní funkcie bude obsahovať text na rozšifrovanie a po ukončení funkcie sa v nej bude nachádzať rozšifrovaný text.

Úloha 2.2

Overte správnosť svojej implementácie.

Úloha 2.3

Vytvorte funkciu encrypt(), pomocou ktorej budete vedieť zašifrovať zadaný text.

Deklarácia tejto funkcie je nasledovná:

void encrypt(const int ttable[], char text[]);
kde:
  • ttable - prekladová tabuľka
  • text - vstupno-výstupná premenná, ktorá pri zavolaní funkcie bude obsahovať text na zašifrovanie a po ukončení funkcie sa v nej bude nachádzať zašifrovaný text.

Úloha 2.4

Overte správnosť svojej implementácie.
Ak použijete vytvorenú prekladovú tabuľku spolu s nasledujúcim kódom:
char message[512];
sprintf(message, "Jeden chudobny clovek mal od svojej prvej zeny jednu dceru.");
encrypt(ttable, message);
printf("%s", message);
bude preklad prvej vety zo súboru laktibrada.txt nasledovný:
IYRYT MGNRXFTH MUXPYO LZU XR SPXIYI JQPYI KYTH IYRTN RMYQN.

Diskusia

Upozornenie: Do svojich príspevkov nevkladajte správne riešenia úloh a ani ich od ostatných nežiadajte! Nepoužívajte sprosté slová! Takéto príspevky budú zmazané! Riaďte sa podľa pravidiel etického kódexu.