TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Rozhodl jsem se vytvořit tento článek, protože jsem se setkal se spoustou lidí, kteří si neuvědomují, co všechno se dá vytvořit pouze pomocí základních příkazů programovacího jazyka. Já si zvolím pro naši ukázku jazyk C++ a v některých příkladech uvedu i řešení v Pascalu.
Jak již bylo řečeno v úvodu, budu zde chtít ukázat řešení několika příkladů. Některé se objevily ve zkoušce pro fyziky na MFF UK (konkrétně hned první tři).
Co bude třeba znát? Přiřazovací příkaz, podmíněný příkaz if, příkaz for (popř. while apod.) a tím bychom zřejmě skončili. V jednom příkladu použijme i funkci pro spočtení délky řetězce sizeof/length.
Je také třeba znát druhy proměnných. Před přečtením tohoto článku by měly být známy pojmy proměnné boolean, integer, double/real, string/char[]. Zmíněné funkce length a sizeof vysvětlím v textu.
Funkce "jePalindrom?"
V této části budeme chtít ukázat, jak zjistit, zda je daná věta palindromem či není.
Palindrom jest slovem, resp. větou v tom smyslu, že přečteme-li jej odzadu, přečteme to samé jako od předu. Programátorsky řečeno, na i-té pozici nalezneme stejný znak jako na pozici n-i-té, kdy n je celková délka řetězce (toto není až tak přesné).
Nyní již začněme se samotnou funkcí, která by měla toto vyhodnotit.
První krok - vymazání mezer a interpunkce z řetězce
Čteme-li něco pozpátku, může to být rozdílné z důvodu mezer, avšak přečetli bychom to stejně. Příkladem jest palindrom "Kuna nese nanuk". Musíme tedy z textu vymazat všechny mezery, čárky, tečky atd.
První částí tohoto kroku bude tedy uvědomit si, jak udělat pomocnou funkci, která nám ověří, zda nějaký znak na i-té pozici není jedním z nepovolených výrazů. Základní úvahou - nejdelší, ale nejjednodušší - by zřejmě bylo udělat si dlouhý podmiňovací příkaz if:
if( pal[i] == " " || pal[i] == "," || pal[i] == "." || pal[i] == "!" ... // C/C++
if (pal[i] = ' ') or (pal[i] = ',') or ... {Pascal}
Asi chápete, že tento přístup by byl zdlouhavý pro psaní. Můžeme si však udělat pole znaků, do kterého si uložíme všechny nepovolené znaky, následně toto pole projedeme od začátku a zjistíme, zda se námi zpracovávaný znak v tomto poli nevyskytuje. Uveďme již celou funkci, kterou později využijeme.
bool jePovolen( char c ){
char znaky[] = {" ", ",", ".", "!", "?", "'"}; // a další dle uvážení
int delka_pole = sizeof(znaky)/sizeof(znaky[0]);
for( int i = 0; i < delka_pole; i++ ){
if( c == znak[i] ) return false;
}
return true;
}
function jePovolen( c: char ):boolean;
begin
znaky[1] := ' ';
znaky[2] := ','; {a další dle uvážení}
delka_pole := const.; { určujeme nějakou konstantu,
která je daná v Pascalu při deklaraci }
for i := 1 to delka_pole do begin
if znaky[i] = c then jePovolen := false;
end;
jePovolen := true;
end;
Vyloučíme-li všechny nepovolené znaky, můžeme přejít k hlavnímu problému - řešení čtení odpředu a odzadu. Nejdříve jsem však slíbil vysvětlení funkce sizeof().
Funkce sizeof() funguje tak, že vezme argument a sdělí nám jeho velikost. Takovou velikostí tedy bude číslo. My chceme zjistit, kolik prvků obsahuje pole - velikost není obecně počet prvků pole! Máme-li tedy velikost pole sizeof(znaky), tak si určíme velikost jednoho prvku - velikost prvků bude stejná, jelikož prvky jsou stejného datového typu, tedy určeme tuto velikost jako sizeof(znaky[0]). Jsme si jisti, že alespoň jeden znak pole mít bude - proč jinak ho vytvářet, že... Počet prvků tedy bude odpovídat {velikosti-pole}/{velikosti-prvku-pole}, v C zapsáno jako sizeof(znaky)/sizeof(znaky[0]).
Pro ty, kteří znají v C funkci strlen(), nechť klidně užijí tu.
V Pascalu je toto daleko snazší, avšak dost neproměnné. V C můžeme jen tak přidávat znaky do pole a vše bude fungovat i dále.
Druhý krok - převedení řetězce na řetězec bez nepovolených znaků a na "stejnou velikost písmen"
Vrhněme se tedy již na celkové řešení úlohy. Máme-li hotovou funkci jePovolen, udělejme nyní funkci, která převede daný řetězec do tvaru, kde nejsou nepovolené znaky - jsou přeskočeny!
Dle mého je nejsnazším způsobem udělat si dvě indexové proměnné i a j. Poté budeme mít dvě pole znaků - dva řetězce - a budeme na j-tou pozici řetězce výsledného ukládat i-tý znak pole původního, bude-li povolený, poté provedeme i++, j++. Pokud nebude znak povolený, nezapíšeme ho, index j zůstane stejný, ale index i zvedneme o jedničku.
Co jsem to teď tak nepřehleně napsal? Následující systém:
1) i = 0; j = 0; Znak na puvodni[0] je povolený, takže přiřadíme vysledny[0] = puvodni[0]
2) i = 1; j = 1; Znak na puvodni[1] je povolený, takže přiřadíme vysledny[1] = puvodni[1]
3) i = 2; j = 2, Znak na puvodni[2] je zakázaný, takže nepřiřadíme nic a nezvedneme j o jedna
4) i = 3; j = 2; Znak na původni[3] je povolený, takže přiřadíme vysledny[2] = puvodni[3]
A takto stále dokola, dokud neprojedeme celý řetězec. Nyní se tedy pojďme podívat, jak toto zaručíme:
int j = 0;
// budeme zacházet s řetězcem jako s polem znaků
int delka = sizeof(palindrom)/sizeof(palindrom[0]);
for( int i = 0; i < delka; i++ ){
if( jePovolen(palindrom[i]) ) vysledek[j++] = palindrom[i];
}
j := 1;
delka := legth( palindrom ); { funkce v Pascalu pro počet znaků
řetězce - délku řetězce }
for i := 1 to delka do begin
if jePovolen( palindrom[i] ) = true then begin
vysledek[j] := palindrom[i];
j := j + 1;
end;
end;
Kód, který jsme doteď napsali, udělá z libovolného řetězce řetězec bez povolených znaků. Dám příklad skutečného palindromu, který byl uveden i jako příklad v zadání zkoušky na MFF UK:
Právě jsme z "Kuna nese nanuk" udělali řetězec "Kunanesenanuk".
Je to všechno? Zapřemýšlejme... náš řetězec vysledek, ve kterém máme "Kunanesenanuk", palindromem je, avšak první a poslední písmena stejná nejsou, tedy tento řetězec je stále nedokonalý. Převeďme nyní všechna písmena v řetězci na velká.
Funkcí, kterou využijeme, bude funkce pro převod písmena z malého na velké. Taková funkce se v jazyce Pascal jmenuje UpCase a je definována jako UpCase( c: char): char. Přijímá tedy znak a vrací znak - to je přesně to, co chceme. Funkci pro převod celého řetězce na velká písmena obecně nemáme, ale můžeme si ji snadno udělat. Abychom dodrželi soudržnost jazyka Pascal a C v tomto článku, budeme i v jazyce C používat funkci pro převod jednoho znaku na velké písmeno. V jazyce C je touto funkcí toupper(), která vrátí velké písmeno, je-li vstupní hodnota písmeno malé, jinak vrátí ten samý znak, který byl vložen.
Udělejme tedy další část kódu pro převod řetězce z malých písmen na velká:
// předpokládejme, že máme řetězec vysledek
for( int i = 0; i < delka; i++ ){
vysledek[i] = toupper(vysledek[i]);
}
{i pro Pascal máme stejný přepoklad řetězce vysledek}
for i := 1 to length(vysledek) do begin
vysledek[i] = UpCase( vysledek[i] );
end;
Třetí krok - dokončení
Není to tedy nic těžkého. Nyní již můžeme začít porovnávat znaky mezi sebou. Námi hledaný algoritmus pro řešení, zda něco je či není palindromem, spočívá v tom, že porovnáme znak první a poslední, poté druhý a předposlední atd. K tomu nám postačí obyčejný cyklus:
// předpokládáme řetězec vysledek, který obsahuje všechna písmena
// stejné velikosti
bool zaver = true;
// náhradou za sizeof(vysledek)/sizeof(vysledek[0]) užijme funkci strlen();
int delka = strlen( vysledek );
for( int i = 0; i < delka; i++ ){
if( i > (delka - i) ) break;
if( vysledek[i] != vysledek[delka-i] ){
zaver = false;
break;
}
}
{stejný předpoklad jako pro C}
zaver := true;
delka := length( vysledek );
for i := to delka do begin
if i > (delka - 1) then break;
if( vysledek[i] <> vysledek[delka-i] ) then begin
zaver := false;
break;
end;
end;
Nyní už můžeme tedy napsat dohromady celou funkci jePalindrom. Opět dodržím to, že první kód je v jazyce C a druhý v jazyce Pascal.
Zdrojový kód pro C/C++
bool jePovolen( char c ){
char znaky[] = {" ", ",", ".", "!", "?", "'"}; // a další dle uvážení
int delka_pole = sizeof(znaky)/sizeof(znaky[0]);
for( int i = 0; i < delka_pole; i++ ){
if( c == znak[i] ) return false;
}
return true;
}
bool jePalindrom( char palindrom[] ){
int j = 0;
int delka = sizeof(palindrom)/sizeof(palindrom[0]);
for( int i = 0; i < delka; i++ ){
if( jePovolen(palindrom[i]) ) vysledek[j++] = palindrom[i];
}
for( int i = 0; i < delka; i++ ){
vysledek[i] = toupper(vysledek[i]);
}
bool zaver = true;
delka = strlen( vysledek );
for( int i = 0; i < delka; i++ ){
if( i > (delka - i) ) break;
if( vysledek[i] != vysledek[delka-i] ){
zaver = false;
break;
}
}
return zaver;
}
Zdrojový kód pro Pascal
function jePovolen( c: char ):boolean;
begin
znaky[1] := ' ';
znaky[2] := ','; {a další dle uvážení}
delka_pole := const.; { určujeme nějakou konstantu,
která je daná v Pascalu při deklaraci }
for i := 1 to delka_pole do begin
if znaky[i] = c then jePovolen := false;
end;
jePovolen := true;
end;
function jePailndrom( palindrom :string );
begin
j := 0;
delka := length( palindrom );
for i := 1 to delka do begin
if jePovolen( palindrom[i] ) = true then begin
vysledek[j] := palindrom[i];
j := j + 1;
end;
end;
for i := 1 to length(vysledek) do begin
vysledek[i] = UpCase( vysledek[i] );
end;
zaver := true;
delka := length( vysledek );
for i := 1 to delka - 1 do begin
if i > (delka - 1) then break;
if( vysledek[i] <> vysledek[delka-i] ) then begin
zaver := false;
break;
end;
end;
jePalindrom := zaver;
end;
A náš úkol byl napsat právě takovou funkci!
Alternativní způsob přistupování k povoleným znakům (návrh spoluautora)
Hledáme-li nějakou větu, jsme si jisti, že v ní nalezneme pouze písmena latinské abecedy. Náš předešlý způsob by jako palindrom určil i řetězec "Kuna 3 nese 3. nanuk", pokud bychom dali 3 jako povolený i nepovolený znak. Otázkou, zda se jedná o palindrom, či nejedná, se zabývat nebudeme, avšak ukážeme si ještě, jak napsat funkci pro určení palindromu z řetězce, který se skládá pouze z čísel. Jsme si však jisti, že ve větě "Bitva proběhla roku 1346" má číslo svůj platný význam. Kdyby věta před číslem byla palindromem a my jsme nechali pouze písmena, tak řekneme, že tento řetězec palindromem je, i když ve skutečnosti není!
Budeme uvažovat, že nemáme nepovolené znaky, ale pouze povolené znaky. Budou jimi 'A' až 'Ž'. V Pascalu přistoupíme k následujícímu řešení:
{po transformaci celého textu na velká písmena}
j := 0;
delka := legth( palindrom ); { funkce v Pascalu pro počet znaků řetězce -
délku řetězce }
for i := 1 to delka do begin
if ('A' <= palindrom[i]) and (palindrom[i] <= 'Z') then begin
vysledek[j] := palindrom[i];
j := j + 1;
end;
end;
Zjistíme vlastně, zda se znak nachází mezi 'A' a 'Z'. Určitě by se zároveň hodilo, vyskytne-li se v textu písmeno 'Ž', aby se přepsalo na 'Z', avšak opět bude nastávat problém kupříkladu ve slově "Želez".
Pro věty složené pouze z písmen bez písmena 'Ž' je však tento způsob jednodušší a časově efektivnější.
V jazyce C bude kód obdobný. Uvádět ho již nebudu, věřím, že čtenář již přišel dle návodu na to, jak si svůj kód upravit. Ti, kdož programují v Pascalu, mají aktuálně výhodu, jelikož je zde uveden jejich kód, v příštím díle však budou mít nevýhodu, tam bude kód především v jazyce C. Ve skutečnosti nám přece vůbec o jazyk nejde, jde nám o přístup k problému, o přemýšlení.
Snad vám, jenž s programováním začínáte a zajímalo by vás, co lze udělat pouze pomocí základních příkazů, byl tento článek k užitku.
Příště bych rád v jazyce C++ rozvedl, jak vyřadit nejvíce nesymetrický vektor z množiny vektorů. V čem úloha spočívá a jak na ni, to se dozvíte příště. Naučíme se zároveň v C definovat vlastní datové typy pomocí typedef struct{ parts } name;
Poznámka na konec:
U data 1346, které mi vyskočilo hlavou při psaní, by mě zajímalo, kdo je schopen bez Googlu přijít na to, o kterou bitvu se jedná. Napovím, že v ní zemřel někdo významný. Je mi jasné, že v takové komunitě programátorů, která je zde, nebude příliš historiků, ani to nechci jako nějakou otázku, na kterou byste mi měli odpovídat, ale zkuste se zamyslet, jestli na to přijdete. Kdo na to přijde, určitě bude rád, že na to přišel. A kdo ne, ať si to na tom Googlu najde a obohatí se o české a evropské dějiny. :)
