Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 16: Rozdiel medzi revíziami
(Vytvorená stránka „== Oznamy == * Dnes budú zverejnené úlohy na cvičenia č. 9 (menej, než obvykle). * V úvode piatkových doplnkových cvičení bude krátka písomka zameraná pre…“) |
|||
Riadok 44: | Riadok 44: | ||
#include <cstdio> | #include <cstdio> | ||
#include <cassert> | #include <cassert> | ||
+ | using namespace std; | ||
int main(void) { | int main(void) { | ||
Riadok 103: | Riadok 104: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdio> | #include <cstdio> | ||
+ | using namespace std; | ||
int main(void) { | int main(void) { | ||
Riadok 136: | Riadok 138: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdio> | #include <cstdio> | ||
+ | using namespace std; | ||
int main(void) { | int main(void) { | ||
Riadok 178: | Riadok 181: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdio> | #include <cstdio> | ||
+ | using namespace std; | ||
int main(void) { | int main(void) { | ||
Riadok 213: | Riadok 217: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdio> | #include <cstdio> | ||
+ | using namespace std; | ||
const int maxN = 101; | const int maxN = 101; | ||
Riadok 255: | Riadok 260: | ||
#include <cstdio> | #include <cstdio> | ||
#include <cstring> | #include <cstring> | ||
+ | using namespace std; | ||
const int maxN = 100; | const int maxN = 100; | ||
Riadok 276: | Riadok 282: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdio> | #include <cstdio> | ||
+ | using namespace std; | ||
int main(void) { | int main(void) { | ||
Riadok 311: | Riadok 318: | ||
#include <cstdio> | #include <cstdio> | ||
#include <cctype> | #include <cctype> | ||
+ | using namespace std; | ||
int main(void) { | int main(void) { | ||
Riadok 351: | Riadok 359: | ||
#include <cstdio> | #include <cstdio> | ||
#include <cassert> | #include <cassert> | ||
+ | using namespace std; | ||
void encryptCaesar(FILE *fr, FILE *fw, int shift) { | void encryptCaesar(FILE *fr, FILE *fw, int shift) { | ||
Riadok 392: | Riadok 401: | ||
#include <cstdio> | #include <cstdio> | ||
#include <cassert> | #include <cassert> | ||
+ | using namespace std; | ||
void decryptCaesar(FILE *fr, FILE *fw, int shift) { | void decryptCaesar(FILE *fr, FILE *fw, int shift) { | ||
Riadok 438: | Riadok 448: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
#include <cstdio> | #include <cstdio> | ||
+ | using namespace std; | ||
const int maxKeyLength = 100; | const int maxKeyLength = 100; | ||
Riadok 486: | Riadok 497: | ||
#include <cstdio> | #include <cstdio> | ||
#include <cassert> | #include <cassert> | ||
+ | using namespace std; | ||
const int maxKeyLength = 100; | const int maxKeyLength = 100; |
Verzia zo dňa a času 15:17, 15. november 2020
Obsah
Oznamy
- Dnes budú zverejnené úlohy na cvičenia č. 9 (menej, než obvykle).
- V úvode piatkových doplnkových cvičení bude krátka písomka zameraná predovšetkým na rekurziu a smerníky. Riešenia budete písať priamo do editovateľných zadaní vo formáte pdf a body za písomku budú riadnou súčasťou hodnotenia tohtotýždňových cvičení. Bližšie informácie k technickej relizácii písomky v stredu.
Príklad na prácu s textovými súbormi
Na minulej prednáške sme sa zaoberali základnými technikami práce s textovými súbormi s využitím knižnice cstdio. V rámci ich opakovania uvažujme nasledujúci problém: máme daných niekoľko „čiastkových” textových súborov, z ktorých každý obsahuje postupnosť niekoľkých celých čísel. Hlavný vstupný súbor vstup.txt potom pozostáva z:
- Prvého riadku obsahujúceho názov výstupného súboru.
- Niekoľkých ďalších riadkov zakaždým obsahujúcich názov niektorého „čiastkového” súboru nasledovaný celým číslom.
Úlohou je pre každú dvojicu tvorenú názvom „čiastkového” súboru a číslom N, uvedenú v súbore vstup.txt, prekopírovať z daného „čiastkového” súboru do výstupného súboru prvých N čísel.
Napríklad pre „čiastkový” súbor a.txt pozostávajúci z čísel
1 2 3 4 5 6 7 8 9
a „čiastkový” súbor b.txt pozostávajúci z čísel
10 20 30 40 50 60 70 80 90
sa pre hlavný vstupný súbor vstup.txt daný ako
vystup.txt a.txt 2 b.txt 1 a.txt 3
majú do výstupného súboru vystup.txt nakopírovať hodnoty
1 2 10 1 2 3
Túto úlohu realizuje program uvedený nižšie, ktorý pracuje v nasledujúcich krokoch:
- Otvorí hlavný vstupný súbor vstup.txt a prečíta z neho názov výstupného súboru.
- Otvorí výstupný súbor.
- Následne, až kým nenarazí na koniec hlavného vstupného súboru, opakuje nasledujúce:
- Z hlavného vstupného súboru prečíta názov „čiastkového” súboru a prirodzené číslo N.
- Otvorí „čiastkový” súbor s práve načítaným názvom, prekopíruje z neho N čísel do výstupného súboru a následne tento „čiastkový” súbor zatvorí.
- Zatvorí hlavný vstupný súbor aj výstupný súbor.
Dĺžka načítavaných reťazcov bude vo volaniach funkcie fscanf obmedzená na 19 znakov (to teda bude maximálna dĺžka názvu súboru, s ktorou bude program vedieť pracovať).
#include <cstdio>
#include <cassert>
using namespace std;
int main(void) {
FILE *fr_main, *fr_part, *fw;
int N,r,num;
fr_main = fopen("vstup.txt", "r");
assert(fr_main != NULL);
char filename[20];
r = fscanf(fr_main,"%19s",filename);
assert(r == 1);
fw = fopen(filename, "w");
assert(fw != NULL);
while (!feof(fr_main)) {
r = fscanf(fr_main,"%19s %d ",filename,&N);
assert(r == 2);
fr_part = fopen(filename, "r");
assert(fr_part != NULL);
for (int i = 0; i <= N-1; i++) {
r = fscanf(fr_part, "%d ", &num);
assert(r == 1);
fprintf(fw, "%d ", num);
}
fclose(fr_part);
}
fclose(fw);
fclose(fr_main);
return 0;
}
Čítanie a zapisovanie po znakoch
Knižnica cstdio obsahuje funkciu
int getc(FILE *f);
ktorá načíta jeden znak zo súboru, na ktorý odkazuje smerník f. V prípade, že načítanie prebehne úspešne, je výstupom funkcie getc kód tohto znaku. V opačnom prípade je výstupom špeciálna konštanta EOF, ktorá je vždy rôzna od ľubovoľnej hodnoty typu char; to je aj dôvod, prečo funkcia getc nevracia hodnotu typu char, ale hodnotu typu int. Je preto dôležité vyvarovať sa ukladania výstupnej hodnoty funkcie getc do premennej typu char – v takom prípade nie je možné rozoznať koniec súboru. Funkcia
int getchar(void);
je skratkou pre getc s parametrom stdin; načíta tak jeden znak z konzoly (rovnako ako napríklad pri scanf sa však vstup začne spracovávať až potom, ako používateľ stlačí Enter – nie je takto možné reagovať priamo na stlačenie nejakej klávesy).
Výstupným náprotivkom k funkcii getc je funkcia
int putc(int c, FILE *f);
Tá zapíše znak c do súboru, na ktorý odkazuje smerník f. Funkcia
int putchar(int c);
je skratkou pre putc s parametrami c a stdout; vypíše teda daný znak na konzolu.
Príklad: kopírovanie súboru
Nasledujúci program skopíruje obsah súboru original.txt do súboru kopia.txt.
#include <cstdio>
using namespace std;
int main(void) {
FILE *fr = fopen("original.txt", "r");
FILE *fw = fopen("kopia.txt", "w");
int c = getc(fr);
while (c != EOF) {
putc(c, fw);
c = getc(fr);
}
fclose(fr);
fclose(fw);
return 0;
}
Načítavanie pritom možno realizovať aj priamo v podmienke cyklu while – výstupom priradenia c = getc(fr) je nová hodnota premennej c, ktorú možno hneď porovnať s EOF. Kľúčová časť horeuvedeného programu sa tak dá kratšie, hoci menej čitateľne, prepísať takto:
int c;
while ((c = getc(fr)) != EOF) {
putc(c, fw);
}
Konce riadkov
Koniec riadku je reprezentovaný znakom '\n'. Pri čítaní alebo zápise sa môže prekladať na jeden alebo dva znaky v závislosti od operačného systému (<LF>, <CR><LF>, alebo <CR>).
Cvičenie: čo robí nasledujúci program?
#include <cstdio>
using namespace std;
int main(void) {
FILE *fr;
int c;
fr = fopen("vstup.txt", "r");
while ((c = getc(fr)) != '\n') {
putchar(c);
}
putchar(c); // vypis \n
fclose(fr);
return 0;
}
Funkcia ungetc
Signálom na ukončenie načítavania znakov často býva až „náraz” na znak, ktorý už nie je žiadúce prečítať. V takom prípade je užitočné „posunúť sa v načítavaní o jeden krok nazad”. Túto úlohu realizuje funkcia
int ungetc(int c, FILE * f);
Ak bol posledným načítaným znakom (zo súboru, na ktorý odkazuje smerník f) znak c, volanie ungetc(c,f) má skutočne efekt „kroku nazad”. Ako parameter funkcie ungetc však možno okrem naposledy prečítaného znaku použiť aj ľubovoľný iný znak c – funkcia ungetc potom tento znak „virtuálne” pridá na začiatok neprečítanej časti súboru. Súbor sa teda reálne nemení, ale pri nasledujúcom čítaní z neho sa ako prvý prečíta znak c. V prípade úspechu sa po volaní ungetc(c,f) vráti hodnota c; v prípade neúspechu je výstupom konštanta EOF.
Takéto správanie funkcie ungetc je však garantované len v prípade, že sa táto funkcia nevolá viackrát za sebou.
Príklad č. 1: Nasledujúci kus programu skonvertuje reťazec pozostávajúci zo znakov '0' až '9' na zodpovedajúcu číselnú hodnotu. Keď narazí na prvý znak, ktorý nie je cifra, vráti ho, aby sa dal použiť pri ďalšom spracovávaní.
int hodnota = 0;
int c = getchar();
while (c >= '0' && c <= '9') {
hodnota = hodnota * 10 + (c - '0');
c = getchar();
}
ungetc(c, stdin);
Príklad č. 2: Nasledujúci program prečíta číslo pomocou funkcie fscanf, predtým však musí prečítať neznámy počet znakov '$'.
#include <cstdio>
using namespace std;
int main(void) {
FILE *fr = fopen("vstup.txt", "r");
int c = getc(fr);
while (c == '$') {
c = getc(fr);
}
ungetc(c, fr);
int hodnota;
fscanf(fr, "%d", &hodnota);
printf("%d\n", hodnota);
fclose(fr);
return 0;
}
Čítanie a zapisovanie po riadkoch
V knižnici cstdio je definovaná funkcia
char *fgets(char *str, int n, FILE * f);
pomocou ktorej možno načítať zo súboru, na ktorý ukazuje smerník f, práve jeden riadok (alebo nejakú jeho časť, ak je tento riadok príliš dlhý). Vstupnými argumentmi funkcie fgets sú:
- Pole znakov str, do ktorého sa v prípade úspechu riadok načíta.
- Číslo n určujúce maximálny počet znakov skopírovaných do poľa str. Presnejšie: do poľa str sa z daného riadku súboru skopíruje najviac n-1 znakov a reťazec str sa následne ukončí znakom \0. Pri typickom volaní funkcie fgets je teda n rovné dĺžke poľa str.
- Smerník f na súbor, z ktorého sa má riadok prečítať.
Funkcia fgets na týchto argumentoch postupne načítava znaky zo súboru, na ktorý ukazuje smerník f, pričom ich ukladá do str. To robí až dovtedy, kým narazí na koniec riadku (\n) alebo koniec súboru, prípadne kým sa zo súboru neprečíta n-1 znakov. Prípadný znak \n na konci riadku sa (pokiaľ nebolo načítaných príliš veľa znakov) nezahodí, ale pridá sa na koniec reťazca str. Výstupom funkcie fgets je v prípade načítania aspoň jedného znaku načítaný reťazec str; v prípade „nárazu” na koniec súboru je výstupom NULL a reťazec str ostáva nezmenený.
Príklad: nasledujúci program spočíta počet riadkov v súbore vstup.txt (za predpokladu, že žiaden z týchto riadkov nie je dlhší ako 100 znakov vrátane znaku \n na konci riadku):
#include <cstdio>
using namespace std;
const int maxN = 101;
int main(void) {
char str[maxN];
int num = 0;
FILE *fr = fopen("vstup.txt", "r");
while (fgets(str, maxN, fr) != NULL) {
num++;
}
fclose(fr);
printf("%d\n",num);
return 0;
}
Cvičenie: Zistite, ako sa správa uvedený program, keď posledným znakom v súbore je resp. nie je znak \n. Zistite, čo program vypíše na výstup pre súbor, ktorý obsahuje jediný riadok o 200 znakoch.
Výstupným náprotivkom funkcie fgets je funkcia
int fputs(const char *str, FILE *f);
ktorá do súboru, na ktorý ukazuje smerník f, vypíše reťazec str. Vypisovaný reťazec str pritom môže obsahovať ľubovoľný (aj nulový) počet výskytov symbolu \n pre koniec riadku. V prípade úspechu vráti funkcia fputs nezáporné celé číslo; v prípade neúspechu vráti konštantu EOF.
Prístupy k spracovaniu textového vstupu
Vstup môže byť v textovom súbore zadaný v rôznych formátoch. V závislosti od formátu potom môžu byť výhodnými rôzne spôsoby jeho spracovania. Často používanými prístupmi k spracovaniu textového vstupu sú napríklad nasledujúce:
- Pomocou funkcie fscanf postupne načítať jednotlivé čísla, slová, a podobne. Tento prístup býva zvyčajne výhodný vtedy, keď sa všetky biele znaky považujú za ekvivalentné oddeľovače.
- Pomocou funkcie getc spracovať vstupný súbor po znakoch. Tu ide o relatívne univerzálny spôsob spracovania vstupu, ktorý je však v niektorých situáciách pomerne prácny.
- Pomocou funkcie fgets postupne prečítať jednotlivé riadky do reťazca a tento reťazec následne spracovať. Tento prístup je výhodný najmä vtedy, keď má koniec riadku funkciu prirodzeného oddeľovača vstupov a keď je dĺžka riadku predom obmedzená.
Často môže byť užitočné horeuvedené prístupy aj navzájom kombinovať.
Príklad č. 1: predpokladajme, že potrebujeme nájsť dĺžku najdlhšieho riadku v súbore (vrátane symbolu \n, ktorý sa môže vyskytovať na jeho konci). Nasledujúce dva programy túto úlohu riešia dvoma odlišnými spôsobmi:
- Prvý program postupne načítava riadky do reťazca, ktorý následne spracúva (problém, ak je riadok príliš dlhý).
- Druhý program číta súbor po znakoch, pričom si udržiava premennú pocet uchovávajúcu informáciu o tom, koľko písmen sa už v momentálne spracovávanom riadku načítalo.
#include <cstdio>
#include <cstring>
using namespace std;
const int maxN = 100;
int main(void) {
FILE *fr = fopen("vstup.txt", "r");
int maxDlzka = 0;
char str[maxN];
while (fgets(str, maxN, fr) != NULL) {
int dlzka = strlen(str);
if (dlzka > maxDlzka) {
maxDlzka = dlzka;
}
}
fclose(fr);
printf("Najdlhsi riadok ma dlzku %d\n", maxDlzka);
return 0;
}
#include <cstdio>
using namespace std;
int main(void) {
FILE *fr = fopen("vstup.txt", "r");
int maxDlzka = 0;
int dlzka = 0;
int c = getc(fr);
while (c != EOF) {
dlzka++;
if (c == '\n') {
if (dlzka > maxDlzka) {
maxDlzka = dlzka;
}
dlzka = 0;
}
c = getc(fr);
}
if (dlzka > maxDlzka) { // Posledny riadok nemusi koncit symbolom \n.
maxDlzka = dlzka;
}
fclose(fr);
printf("Najdlhsi riadok ma dlzku %d\n", maxDlzka);
return 0;
}
Príklad č. 2: nasledujúci program spracúva vstupný súbor obsahujúci čísla oddelené bielymi znakmi (medzery, tabulátory, konce riadkov,...), pričom medzi dvoma číslami môže byť aj viac ako jeden oddeľovač. Pre každý riadok program vypíše súčet čísel, ktoré sa v tomto riadku vyskytujú (predpokladá pritom, že každý – t. j. aj posledný – riadok vstupného súboru je ukončený symbolom \n).
Vzhľadom na to, že tu ide o pomerne nepríjemnú kombináciu rozlišovania koncov riadku od iných bielych znakov a čítania formátovaných hodnôt (čísel), kombinuje nasledujúci program čítanie po znakoch s využívaním funkcie fscanf. Pracuje pritom nasledovne:
- Kým sú na vstupe biele znaky, spracúva ich pomocou funkcie getc. Ak je niektorý z týchto znakov koncom riadku, vypíše zistený súčet čísel.
- Po „náraze” na prvý nebiely znak použije funkciu ungetc na jeho vrátenie do vstupného prúdu. Následne prečíta číslo pomocou funkcie fscanf a na základe prečítanej hodnoty aktualizuje súčet.
- Na zistenie, či je prečítaný znak biely, využíva nasledujúci program funkciu isspace z knižnice cctype.
#include <cstdio>
#include <cctype>
using namespace std;
int main(void) {
FILE *fr = fopen("vstup.txt", "r");
int sucet = 0;
int hodnota;
while (!feof(fr)) {
int c = getc(fr);
while (c != EOF && isspace(c)) { // Precitaj biele znaky po najblizsi nebiely.
if (c == '\n') { // Na konci riadku vypis sucet.
printf("Sucet %d\n", sucet);
sucet = 0;
}
c = getc(fr);
}
if (c == EOF) { // Pri naraze na koniec suboru nepokracuj dalej.
break;
}
ungetc(c, fr); // Posledny precitany znak nebol biely; vrat ho do vstupneho prudu.
fscanf(fr, "%d", &hodnota); // Precitaj cislo a pripocitaj ho k suctu.
sucet += hodnota;
}
fclose(fr);
return 0;
}
Cvičenie: upravte program tak, aby pracoval správne aj v prípade, že posledný riadok nie je ukončený symbolom \n.
Jednoduché šifrovanie
Prácu so súbormi si v nasledujúcom precvičíme na dvoch jednoduchých šifrách.
Cézarova šifra
Cézarova šifra je šifra, pri ktorej sa každé písmeno vstupného reťazca posunie cyklicky o K miest v abecednom poradí, kde K je zadaný parameter šifry (tzv. posun).
- Napríklad pre K=2 sa písmeno A zmení na C, písmeno b sa zmení na d a písmeno Z sa zmení na B.
- Ukážeme si jej použitie pre anglickú abecedu (t. j. znaky 'a' až 'z' a 'A' až 'Z' bez diakritiky); je ju ale možné upraviť napríklad aj tak, aby pracovala s ASCII kódmi.
Zašifrovanie súboru realizuje nasledujúci program:
#include <cstdio>
#include <cassert>
using namespace std;
void encryptCaesar(FILE *fr, FILE *fw, int shift) {
assert(shift >= 0 && shift <= 25);
int c;
while ((c = getc(fr)) != EOF) {
if ((c >= 'A') && (c <= 'Z')) {
c = c + shift;
if (c > 'Z') {
c -= 26;
}
} else if ((c >= 'a') && (c <= 'z')) {
c = c + shift;
if (c > 'z') {
c -= 26;
}
}
putc(c, fw);
}
}
int main(void) {
int shift;
scanf("%d", &shift);
FILE *fr = fopen("plaintext.txt", "r");
FILE *fw = fopen("ciphertext.txt", "w");
encryptCaesar(fr, fw, shift);
fclose(fr);
fclose(fw);
return 0;
}
Dešifrovanie súboru zašifrovaného Cézarovou šifrou realizuje tento program:
#include <cstdio>
#include <cassert>
using namespace std;
void decryptCaesar(FILE *fr, FILE *fw, int shift) {
assert(shift >= 0 && shift <= 25);
int c;
while ((c = getc(fr)) != EOF) {
if ((c >= 'A') && (c <= 'Z')) {
c = c - shift;
if (c < 'A') {
c += 26;
}
} else if ((c >= 'a') && (c <= 'z')) {
c = c - shift;
if (c < 'a') {
c += 26;
}
}
putc(c, fw);
}
}
int main(void) {
int shift;
scanf("%d", &shift);
FILE *fr = fopen("ciphertext.txt", "r");
FILE *fw = fopen("plaintext2.txt", "w");
decryptCaesar(fr, fw, shift);
fclose(fr);
fclose(fw);
return 0;
}
Vigenèrova šifra
Vigenèrova šifra je veľmi podobná Cézarovej; posun už ale nie je konštantný a realizuje sa podľa kľúča.
- Kľúčom je reťazec zložený z písmen A až Z, pričom tieto predstavujú posuny o 0 až 25 pozícií v abecede.
- Pri šifrovaní aj dešifrovaní sa jednotlivé abecedné posuny realizujú podľa kľúča. Prvý symbol otvoreného textu je tak zašifrovaný podľa prvého symbolu kľúča, druhý symbol podľa druhého symbolu kľúča, atď. Po vyčerpaní celého kľúča sa pokračuje cyklicky, opäť od jeho začiatku.
Zašifrovanie súboru realizuje nasledujúci program:
#include <cstdio>
using namespace std;
const int maxKeyLength = 100;
void encryptVigenere(FILE *fr, FILE *fw, char *key) {
int c;
int i = 0;
while ((c = getc(fr)) != EOF) {
if ((c >= 'A') && (c <= 'Z')) {
c = c + (key[i] - 'A');
if (c > 'Z') {
c -= 26;
}
i++;
} else if ((c >= 'a') && (c <= 'z')) {
c = c + (key[i] - 'A');
if (c > 'z') {
c -= 26;
}
i++;
}
if (key[i] == 0) {
i = 0;
}
putc(c, fw);
}
}
int main(void) {
char key[maxKeyLength];
scanf("%s", key);
FILE *fr = fopen("plaintext.txt", "r");
FILE *fw = fopen("ciphertext.txt", "w");
encryptVigenere(fr, fw, key);
fclose(fr);
fclose(fw);
return 0;
}
Dešifrovanie súboru zašifrovaného Vigenèrovou šifrou realizuje tento program:
#include <cstdio>
#include <cassert>
using namespace std;
const int maxKeyLength = 100;
void decryptVigenere(FILE *fr, FILE *fw, char *key) {
int c;
int i = 0;
while ((c = getc(fr)) != EOF) {
if ((c >= 'A') && (c <= 'Z')) {
c = c - (key[i] - 'A');
if (c < 'A') {
c += 26;
}
i++;
} else if ((c >= 'a') && (c <= 'z')) {
c = c - (key[i] - 'A');
if (c < 'a') {
c += 26;
}
i++;
}
if (key[i] == 0) {
i = 0;
}
putc(c, fw);
}
}
int main(void) {
char key[maxKeyLength];
scanf("%s", key);
FILE *fr = fopen("ciphertext.txt", "r");
FILE *fw = fopen("plaintext2.txt", "w");
decryptVigenere(fr, fw, key);
fclose(fr);
fclose(fw);
return 0;
}