Kiwiki - Príspevky používateľa [sk]

Rekurzia (riešené príklady)

2023-05-16T12:40:56Z

PiknaR:

{{Draft}}
{{Skripta programovanie (zbierka úloh)}}
__TOC__

==Najväčší spoločný deliteľ==
'''Zadanie'''
Nájdite rekurzívny vzťah v Euklidovom algoritme pre výpočet najväčšieho spoločného deliteľa a využite ho vo funkcii, ktorá bude počítať najväčší spoločný deliteľ dvoch čísel, uvedených ako jej parametre. Funkciu použite v programe, ktorý načíta dve čísla a napíše hodnotu ich najväčšieho spoločného deliteľa.

Poznámka:
V Euklidovom algoritme môžete namiesto klasického odpočítavania využiť zvyšok po delení, čo zníži počet krokov výpočtu a nebude potrebné sa zaoberať problémom „nesprávneho poradia“ čísel pri odpočítavaní.

'''Vzorové príklady'''
{|
|-
!vstup
!
!výstup
|-
|36 48
| ->
|12
|-
|576 284
| ->
|4
|-
|2553 7215
| ->
|111
|}

'''Analýza riešenia'''

Hľadaný rekurzívny vzťah je vidieť v postupe prevodu čísel postupným „modulovaním“ (operáciou modulo) – delenec a je nahradený deliteľom b, deliteľ b zase výsledkom a%b, ukončenie je pri nulovom b:
* NSD(a, b) = NSD(b, a%b) pre b>0,
* NSD(a, 0) = a

'''Možné riešenie:'''
<source lang="c" line>
#include <iostream.h>

int NSD(int a, int b)
{
if (b == 0) return a;
return NSD(b, a%b);
}

int main()
{
int a, b;
cin >> a >> b;
cout << NSD(a, b);
return 0;
}
</source>
==Fibonacciho postupnosť==
'''Zadanie'''
Pre Fibonacciho postupnosť platí, že hodnota ďalšieho jeho prvku je súčtom dvoch predchádzajúcich. Zostavte program, ktorý bude z klávesnice čítať čísla n, kým nenačíta nulu a pre každé číslo n vypíše n-té Fibonacciho číslo v poradí, za predpokladu, že Fib(0) = 0 a Fib(1) = 1.

'''Vzorové príklady'''
{|
|-
!vstup
!
!výstup
|-
|4
| ->
|3
|-
|9
| ->
|34
|-
|20
| ->
|6765
|-
|40
| ->
|102334155
|-
|0
| ->
|
|}

'''Analýza riešenia'''

Fibonacciho postupnosť je rekurzívne definovaná ako:
* fib(0)=0
* fib(1)=1
* fib(i)=fib(i-1)+fib(i-2), pre i<nowiki>></nowiki>1

Na tomto príklade je vhodné demonštrovať, čo sa stane, ak zabudneme v rekurzívnej funkcii uviesť podmienku pre ukončenie rekurzie – program havaruje kvôli pretečeniu zásobníka.

'''Možné riešenie:'''
<source lang="c" line>
#include <iostream.h>
long fib(int n)
{
if (n < 2) return n;
else return fib(n-1) + fib(n-2);
}
int main()
{
int n;
cin >> n;
while (n)
{
cout << fib(n) << endl;
cin >> n;
}
return 0;
}
</source>
==Prevod čísel z 10-vej sústavy==
'''Zadanie'''

Zostavte program, ktorý bude prevádzať prirodzené čísla do ľubovoľných číselných sústav so základom Z<10, využitím rekurzívnej funkcie. Túto funkciu postupne zdokonaľujte:
#Funkciu vylepšite, aby vedela prevádzať aj do sústav so základom Z<=16.
#Upravte funkciu tak, aby vedela prevádzať všetky celé čísla (čiže aj záporné a nulu).
#Pokúste sa funkciu obohatiť o prevod reálnych čísel (čiže aj desatinných).
V programe načítajte 2 vstupné údaje: číslo N v 10-vej sústave a základ novej sústavy z.

'''Vzorové príklady'''
{|class=wikitable
|-
!vstup
!výstup
|-
|80 2
|1010000
|-
|93 16
|5D
|-
|0 8
|0
|-
| -74 4
| -1022
|-
|3.141592654 16
|3.243F6A8A48AA
|-
| -0.1 2
| -0.0001100110011001100
|}

Je vhodné začať jednoduchou funkciou na prevod prirodzeného čísla. Ak máme základ cieľovej sústavy z<10, môžeme problém vyjadriť aj rekurentným vzťahom v matematickom tvare: P(n, z) = P(n/z, z) * 10 + n%z (pre n > 0), a teda by bolo možné vytvoriť funkciu, ktorej návratovou hodnotou by bolo celé číslo.

V prípade, že uvažujeme o vyššom základe, vo výsledku sa objavia aj symboly A, B, C, ... funkcia by už musela výsledok vracať vo forme reťazca. Pre zjednodušenie nám stačí funkcia, ktorá bude výsledok priamo vypisovať. Je treba si uvedomiť, ako sa počíta prevod čísla – číslo vydelíme základom sústavy, tento podiel prevedieme a za ním bude nasledovať zvyšok po pôvodnom delení.

Na vypísanie zvyšku pre vyššie sústavy by sme mohli pre zvyšky väčšie ako 9 použiť aj inkrementáciu znakového typu:
<source lang="c">
cout << char (‘A’ + n%z – 10);
</source>

Keďže základ sústavy sa počas celého prevodu samozrejme nemení, nemá význam v každom volaní funkcie vytvárať jeho kópiu v podobe vstupnej premennej, ale stačí nám referencia (ušetrí sa pár bajtíkov pri každom vnorení).

Ak chceme, aby funkcia dokázala prevádzať aj nulu a záporné čísla, musíme si pridať akúsi „úvodnú“ funkciu, ktorá ošetrí problematické situácie a až potom zavolá hlavnú rekurzívnu funkciu prevodu.

'''Možné riešenie:'''

<source lang="c">
#include <iostream.h>

const char znaky[] = "0123456789ABCDEF";
void PrevodCele(int n, int &zaklad)
{
if (n == 0) return;
PrevodCele(n/zaklad, zaklad); // prevedie celu cast podielu
cout << znaky[n%zaklad]; // za tym napise zvysok
}

void PrevodReal(double r, int &zaklad, int presnost)
{
if (r == 0) return;
r *= zaklad; // posunie o jeden rad vlavo
cout << znaky[int(r)]; // celu cast vypise
PrevodReal(r - int(r), zaklad, presnost - 1); // zvysok prevedie
}

// uvodna funkcia na specialne pripady
void Prevod(double r, int zaklad, int presnost)
{
// ak je zaporne
if (r < 0)
{
r = -r; cout << '-';
}
// cela cast
int n = int(r);
if (n)
PrevodCele(n, zaklad);
else
cout << 0; // ak je nula, vypise ju

// desatinna cast (ak je)
if (r -= n)
{
cout << '.';
PrevodReal(r, zaklad, presnost);
}
}

int main()
{
double r;
int sustava;
cout << "cislo v 10-kovej sustave: "; cin >> r;
cout << "cielova sustava: "; cin >> sustava;
cout << "prevedene: ";
Prevod(r, sustava, 6);
return 0;
}
</source>

==Prvočísla==

'''Zadanie:'''

Pomocou rekurzívneho riešenia vytvorte funkciu, ktorá otestuje, či je dané číslo prvočíslo.
===Prvé riešenie - neoptimalizované===

'''Analýza riešenia:'''

Testujeme číslo n na prvočíselnosť. Číslo n budeme postupne deliť číslami od 2 až po (n-1) aby sme zistili zvyšok po delení. Pri prvom zvyšku, ktorý je rovný 0 (teda číslo z delí číslo n bezo zvyšku) funkciu ukončíme a vrátime hodnotu 0 (n nie je prvočíslo). Ak je z<(n-1) tak funkciu is_prime1 voláme rekurzívne a v tomto volaní zvýšime parameter z o 1. (riadok č. 8). V prípade, že neplatí rovnosť z<(n-1) a ani jedno číslo z intervalu <2,n-1> nedelí číslo n bezo zvyšku, vrátime hodnotu 1 (n je prvočíslo).

'''Možné riešenie:'''

<source lang="c" line >
int is_prime1(int n, int z=2)
{
if((n%z)==0)
return 0;
else
{
if(z<(n-1))
return is_prime1(n,z+1);
else
return 1;
}
}
</source>
===Druhé riešenie - čiastočne optimalizované===
Optimalizácia v tomto prípade znamená eliminovať počet delení modulo. Myšlienka nájdenia hornej hranice hodnoty premennej ''z'' z predchádzajúceho príkladu:
*Číslo n delíme modulo hodnotou 2. (výsledok je rôzny od 0)
** nemá zmysel deliť číslom ''z'' väčším ako je n/2, pretože už nám nemôže vyjsť celočíselný podiel. Výsledok takéhoto delenia bude v intervale (0,1)
*Číslo n delíme modulo hodnotou 3. (výsledok je rôzny od 0)
** nemá zmysel deliť číslom ''z'' väčším ako je n/3, pretože už nám nemôže vyjsť celočíselný podiel. Výsledok takéhoto delenia bude v intervale <math>(1,2) \cup (2,3)</math>. Podiel nebude mať hodnotu 2, pretože v tom prípade by bolo číslo n delitelné číslom 3 bezo zvyšku.
*Delitel n budeme zväčšovať až pokiaľ platí <math>\frac {n}{d}>d</math>

Horná hranica hodnoty d sa dá určiť nasledovne: <math>d=\sqrt{n}</math>

'''Možné riešenie:'''

<source lang="c" line >
int is_prime2(int n, int z=2)
{
if((n%z)==0)
return 0;
else
{
if(z<sqrt(n))
return is_prime2(n,z+1);
else
return 1;
}
}
</source>

===Tretie riešenie - viac optimalizované===
V predchádzajúcom príklade sme delili číslo n hodnotami premennej d. Premenná d mala prvú hodnotu 2 a potom sa k nej vždy pripočítala hodnota 1. Teda, číslo n sme postupne delili hodnotami
2, 3, 4, 5, 6, 7, 8, ... <math>d=\sqrt{n}</math>.

Všimnime si, že niektoré delenia sú opäť zbytočné:
*ak delíme číslom 2, potom nemá zmysel deliť žiadnym jeho násobkom
*vo všeobecnosti platí: ak delíme číslom ''j'', potom nemá zmysel deliť žiadnym násobkom čísla ''j''.

Inak povedané, netreba deliť žiadnom zloženým číslom. Stačí deliť prvočíslami. A tu sa dostávame k rekurzívnej definícii prvočísel:

'''Rekurzívna definícia prvočísla''':
* Číslo 2 je najmenšie prvočíslo.
* Prvočíslo je každé celé kladné číslo, ktoré nie je deliteľné žiadnym iným menším prvočíslom ako je toto číslo samotné.

Pri takto stanovenej podmienke je komplikovanejšie vytvoriť podmienku, ktoré by toto spĺňala. Preto skúsme napísať program, ktorý by zbytočne nedelil násobkami čísel 2 a 3.
Ak nechceme deliť násobkami čísla 2, tak potom budeme postupne deliť premennú n hodnotami 3,5,7,9,11,...

Ak nechceme deliť násobkami čísla 3, tak potom budeme postupne deliť premennú n hodnotami 4,5,7,8,10,11,13,14,...

Prienikom týchto dvoch podmienok je, že nám zostava deliť číslami 5,7,11,13,17,19,23, ...

V tejto postupnosti je jednoduché pravidlo: striedavé pripočítavanie hodnoty 2 a 4. Vyjadrené aritmetickou postupnosťou:
*<math>d_0=2</math>
*<math>d_1=3</math>
*<math>d_2=5</math>
*<math>d_n=d_{n-1} + 3-(-1)^{i+1}</math>

'''Možné riešenie:'''

<source lang="c" line >
int is_prime3(int n, int z,int krok)
{
int d=z+3+krok;
if((n%d)==0)
return 0;
else
{
if(d<sqrt(n))
return is_prime3(n,d,-krok);
else
return 1;
}
}

int is_prime(int n)
{
if((n%2)==0) return 0;
if((n%3)==0) return 0;
if((n%5)==0) return 0;
return is_prime3(n,5,-1);
}
</source>

'''Rozbor zdrojového kódu:'''

Pre hľadanie prvočísel použijeme funkciu is_prime, ktorá otestuje číslo n na deliteľnosť číslami 2, 3 a 5. Potom zavoláme pomocnú rekurzívnu funkciu is_prime3(int n, int z,int krok) ktorá bude testovať deliteľnosť čísla n prvkami postupnosti <math>\big\{d_n\big\}</math>. Aby sme sa vyhli zbytočným podmienkam, ktoré môžu celý algoritmus spomaliť, definujeme tretí parameter funkcie is_prime3 ''krok''. Parameter krok je v našej postupnosti výraz <math> 3-(-1)^{i+1}</math>, avšak tu nepočítame hodnotu mocniny <math>(-1)^{i+1}</math> ale využívame skutočnosť že tento výraz nadobúda hodnoty -1,1,-1,1, ... .

V premennej d je vypočítaná hodnota aktuálneho deliteľa podľa vzťahu: <math>d_n=d_{n-1} + 3-(-1)^{i+1}</math>.

===Riešenie s globálnym poľom===
Pre zjednodušenie tvorby programu si vytvorme globálne pole do ktorého uložíme prvých n prvočísel. Potom najväčšie číslo, ktoré môžeme testovať na prvočíselnosť je <math>N=n^2</math>.

'''Analýza riešenia:'''

Testujeme číslo n na prvočíselnosť. Ako prvé vypočítame zvyšok po delení prvým prvočíslom v poli ''pcisla'' (delíme číslom pcisla[0]=2). V prípade, ak je výsledok 0, tak výpočet ukončíme a vrátime hodnotu (0 - nie je prvočíslo). V opačnom prípade rekurzívne zavoláme funkciu jePrvocislo, kde druhý parameter (má význam indexu v poli ''pcisla'') zvýšime o 1. Teda v ďalšom volaní funkcie jePrvocislo už budeme deliť číslom pcisla[1]=3. Musíme však zabezpečiť, aby hodnota pcisla[i] v riadku č. 5 existovala. To zabezpečíme tak, že rekurzívne volanie dovolíme len ak je hodnota indexu i menšia ako počet hodnôt v pole pcisla.

'''Možné riešenie:'''

<source lang="c" line >
int prvocisla[]={2,3,5,7,11,13,17,19,23,29,31,37};

int is_prime4(int n, int i=0)
{
if(n%prvocisla[i]==0)
return 0;
if(i<223 && n>pow(prvocisla[i],2))
return is_prime4(n,i+1);
else
return 1;
}
</source>

'''Vzorové riešenie'''

Uvádzame postupnosť volaní funkcie '''is_prime4(31)'''

{| class=wikitable
|+
!Vnorenie
!Volaná funkcia
!prvocisla[i]
!n%prvocisla[i]
!rekurzívne volanie
|-
|0
|is_prime(31,0)
|2
|31%2=1
|is_prime(31,1)
|-
|1
|is_prime(31,1)
|3
|31%3=1
|is_prime(31,2)
|-
|2
|is_prime(31,2)
|5
|31%5=1
|is_prime(31,3)
|-
|3
|is_prime(31,3)
|7
|31%7=3
|is_prime(31,4)
|-
| 4
| is_prime(31,4)
| 11
| n.a.
| neplatí podmienka n>prvocisla[i]^2<br/>n=31, i=4, prvocisla[i]=11<br/>funkcia vracia hodnotu '''1'''
|-
| 3
| návrat na is_prime(31,3)
| 7
| n.a.
| spätný rekurzívny chod
|-
| 2
| návrat na is_prime(31,2)
| 5
| n.a.
| spätný rekurzívny chod
|-
| 1
| návrat na is_prime(31,1)
| 3
| n.a.
| spätný rekurzívny chod
|-
| 0
| návrat na is_prime(31,0)
| 2
| n.a.
| spätný rekurzívny chod
|}
====Porovnanie efektivity navrhovaných algoritmov====
Skôr ako budeme porovnávať ukázané algoritmy, poznamenajme, že tento spôsob zisťovania prvočíselnosti je pre veľké čísla veľmi neefektívny. Pri 8-cifernom čísle trvá výpočet funkcie is_prime približne 230 s. Pre zisťovanie prvočíselnosti existujú špeciálne algoritmy, napr. [http://en.wikipedia.org/wiki/AKS_primality_test ASK test], [http://en.wikipedia.org/wiki/Solovay%E2%80%93Strassen_primality_test Test Solovay-Strassena], [http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Test Millera-Rabina] a iné.
V nasledujúcej tabuľke a na obrázku sú výsledky porovnania efektívnosti týchto algoritmov pri hľadaní prvočísel na intervale (100,n) kde n sme menili od 50 000 do 2 000 000. V tabuľke ani v grafe nie je zahrnutá funkcia is_prime1, pretože pri n=100 000 pri rekurzívnom volaní funkcia neočakávane skončila.
Aby sme mohli porovnávať aj funkciu is_prime4, musíme do poľa ''prvocisla'' pridať všetky prvočísla, ktoré sú menšie ako <math>\sqrt{n_{max}}</math>, kde n_max je v našom prípade 2 000 000. Pole ''prvocisla'' obsahuje prvých 233 prvočísel:
<source lang="c">
int prvocisla[]={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,
191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,
397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,
617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,
1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,
1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423};
</source>
Naprogramované funkcie sme testovali nasledovne:

<source lang="c">
#include <iostream.h>
#include <time.h>

int main()
{
clock_t start, end;
double elapsed;
int n;
n=50000; //100000, 200000, ... 2000000
start = clock();
for(int i=100;i<n;i++)
is_prime(i);
end = clock();
elapsed = ((double) (end - start)) / CLOCKS_PER_SEC;
cout<<elapsed<<endl;
}
</source>
{| class=datatable
|+Tabuľka nameraných časov behu funkcií
|-
!n [tisíc]
!is_prime_2 t[s]
!is_prime t[s]
!is_prime4 t[s]
|-
|50
|0,16
|0,086
|0,061
|-
|100
|0,398
|0,134
|0,126
|-
|200
|1,034
|0,345
|0,304
|-
|500
|1,245
|1,237
|0,958
|-
|1000
|3,275
|3,264
|2,349
|-
|1500
|17,203
|5,831
|3,9
|-
|2000
|26
|8,6
|5,82
|}

<pLines ymin=0 ymax=27 colors=FF0000,00FF00,0000FF size=600x250 plots legend>
,is_prime2, is_prime, is_prime4
50 tis, 0.16, 0.08, 0.061
100 tis, 0.398, 0.134, 0.126
200 tis, 1.034, 0.345, 0.304
500 tis, 1.245, 1.237, 0.958
1 mil, 3.275, 3.264, 2.349
1.5 mil, 17.203, 5.831, 3.9
2 mil, 26, 8.6, 5.82
</pLines>

Podobné časy pri nižších hodnotách n sú dané tým, že vzdialenosť susedných prvočísel je väčšia pri vyšších prvočíslach. Z grafu taktiež vidieť účinok optimalizácie algoritmu.

==Odkazy==
*http://sk.wikipedia.org/wiki/Zoznam_prvo%C4%8D%C3%ADsiel
*http://www.prime-numbers.org/

Štruktúry (riešené príklady)

2023-05-16T12:38:04Z

PiknaR:

{{Draft}}
{{Skripta programovanie (zbierka úloh)}}
__TOC__

==Štruktúra Zlomok==
'''Úloha:'''

Zostavte program, ktorý pomôže pri práci so zlomkami – bude vedieť zlomok skrátiť a vypísať ho v čo najvhodnejšom tvare. Program načíta dva zlomky, každý hneď po načítaní upravene vypíše, ďalej vypíše ich súčin, súčet a podiel:
#Zostavte funkciu na načítanie zlomku z klávesnice a funkciu, ktorá vypíše zlomok na obrazovku v tvare „a/b“, napr. „3/4“. Postupne ju zdokonaľujte:
##V prípade, že zlomok má celú časť, vypíše ho v tvare „a b/c“, napr. namiesto „9/4“ bude písať „2 1/4“.
##V prípade, že jeho zvyšná časť je nulová, nebude ju vypisovať, napr. namiesto „6/2“ nebude písať „3 0/2“, ale iba „3“ a podobne, namiesto „0/2“ iba „0“.
#Vytvorte si pomocnú funkciu, ktorá zjednoduší (skráti) zlomok, napr. „36/48“ prevedie na „3/4“ a obohaťte ňou funkciu pre vypísanie zlomku (aby sa zlomok vypisoval už v zjednodušenom tvare).
#Zostavte funkcie, ktoré vypočítajú súčin, súčet a podiel dvoch zlomkov a použite ich v hlavnom programe.

'''Vzorový vstup:'''
5 4
1 1/4
6 8
3/4

'''Vzorový výstup:'''
sucin: 15/16
sucet: 2
podiel: 1 2/3

Cieľom je precvičiť si prácu so štruktúrou – bolo by vhodné ju v programe využiť.
Funkcia na načítanie zlomku môže využiť referenciu alebo štruktúru ako návratovú hodnotu. Pre krátenie zlomku môžeme využiť referenciu a pre matematické operácie so zlomkami zase návratovú hodnotu.

Pre krátenie zlomku treba funkciu na najväčší spoločný deliteľ – použijeme Euklidov algoritmus postupného odpočítavania menšieho čísla od väčšieho a jeho zdokonalenie cez operáciu modulo.
Pri matematických funkciách môžeme využiť akýsi „akoby konštruktor“ na vytvorenie zlomku, no nie je to nutné.

'''Možné riešenie:'''
<source lang="c" line>
#include <iostream.h>

using namespace std;

struct TZlomok { int citatel, menovatel; };
void CitajZlomok(TZlomok &z)
{
cin >> z.citatel;
cin >> z.menovatel;
}

int NSD(int a, int b)
{
while (b)
{
int c = a % b;
a = b;
b = c;
}
return a;
}

void SkratZlomok(TZlomok &z)
{
int nsd = NSD(z.citatel, z.menovatel);
z.citatel /= nsd;
z.menovatel /= nsd;
}

void VypisZlomok(TZlomok z)
{
SkratZlomok(z);
int cela_cast = z.citatel / z.menovatel;
if (cela_cast)
{
cout << cela_cast;
int zvysok = z.citatel % z.menovatel;
if (zvysok) cout << " " << zvysok << "/" << z.menovatel;
}
else
{
cout << z.citatel;
if (z.citatel) // ak je nula, napise len ju a nie napr. 0/1
cout << "/" << z.menovatel;
}
cout << endl;
}

TZlomok Zlomok(int cit, int men)
{
TZlomok z;
z.citatel = cit;
z.menovatel = men;
SkratZlomok(z);
return z;
}

TZlomok SucinZlomkov(TZlomok z1, TZlomok z2)
{
return Zlomok(z1.citatel * z2.citatel, z1.menovatel * z2.menovatel);
}

TZlomok SucetZlomkov(TZlomok z1, TZlomok z2)
{
return Zlomok(z1.citatel * z2.menovatel + z2.citatel * z1.menovatel,
z1.menovatel * z2.menovatel);
}

TZlomok PodielZlomkov(TZlomok z1, TZlomok z2)
{
return Zlomok(z1.citatel * z2.menovatel, z1.menovatel * z2.citatel);
}

int main()
{
TZlomok z1, z2;
CitajZlomok(z1); VypisZlomok(z1);
CitajZlomok(z2); VypisZlomok(z2);
cout << "sucin: "; VypisZlomok(SucinZlomkov(z1, z2));
cout << "sucet: "; VypisZlomok(SucetZlomkov(z1, z2));
cout << "podiel: "; VypisZlomok(PodielZlomkov(z1, z2));
return 0;
}
</source>

==Zásobník - pamäť typu LIFO==
===Intepreter postfixových aritmetických výrazov===
'''Zadanie:'''

Vytvorte program v jazyku C, ktorý po spustení načíta od používateľa postfixový aritmetický výraz, vyhodnotí ho, vypíše jeho hodnotu do konzoly (na monitor) a skončí.

'''Analýza:'''

V postfixovom aritmetickom výraze sa operátor zapisuje vždy po svojich dvoch operandoch, ako to môžeme vidieť v nasledujúcom takomto výraze
5 9 8 + 4 6 * * 7 + *
ktorý má hodnotu 2075.
Každý infixový aritmetický výraz, môže byť prepísaný na postfixový. Infixová verzia uvedeného postfixového výrazu je nasledovná:
5 * ( ( (9 + 8) * (4 * 6) ) + 7)
a tá má samozrejme po vyhodnotení rovnakú hodnotu 2075.

Pomocou abstraktného dátového typu (ADT) zásobníka sa dajú veľmi dobre vyhodnocovať práve postfixové aritmetické výrazy. Každý operátor si z vrcholu zásobníka načíta svoje dva operandy a po vykonaní operácie na nich vráti jej výsledok namiesto týchto dvoch operandov na vrchol zásobníka (využitie princípu dátovej štruktúry typu LIFO). Nasledujúci obrázok demonštruje tento jednoduchý princíp na vyhodnocovaní vyššie uvedeného postfixového aritmetického výrazu.

{| border="1" class=wikitable
|+ Spracovanie postfixového výrazu 5 9 8 + 4 6 * * 7 + *
|-
!index v pamati zásobníka<hr/>číslo kroku
! 0
! 1
! 2
! 3
! 4
! operácia
|-
| 1
| 5
|
|
|
|
|
|-
| 2
| 5
| 9
|
|
|
|
|-
| 3
| 5
| 9
| 8
|
|
|
|-
| 4
| 5
|
|
|
|
| 8+9
|-
| 5
| 5
| 17
|
|
|
|
|-
| 6
| 5
| 17
| 4
|
|
|
|-
| 7
| 5
| 17
| 4
| 6
|
|
|-
| 8
| 5
| 17
|
|
|
| 6 * 4
|-
| 9
| 5
| 17
| 24
|
|
|
|-
| 10
| 5
|
|
|
|
| 24*17
|-
| 11
| 5
| 408
|
|
|
|
|-
| 12
| 5
| 408
| 7
|
|
|
|-
| 13
| 5
|
|
|
|
| 408 + 7
|-
| 14
| 5
| 415
|
|
|
|
|-
| 15
|
|
|
|
|
| 415 * 5
|-
| 16
| 2075
|
|
|
|
|
|}
Tabuľka ukazuje použitie zásobníka reprezentovaného celočíselným poľom (zasobnik.pamat[ ]) pre vyhodnotenie postfixového výrazu 5 9 8 + 4 6 * * 7 + * uloženého v znakovom poli (vyraz[ ]). Tento výraz postupne prechádzame zľava doprava. Ak narazíme na znak reprezentujúci číslo, vložíme ho na vrchol zásobníka (zasobnik.pamat[zasobnik.vrchol]), ak narazíme na znak reprezentujúci operátor, potom vyberieme z vrcholu zásobníka 2 operandy, aplikujeme na ne operátor a namiesto týchto dvoch operandov vložíme na vrchol zásobníka výsledok samotnej operácie.
Na reprezentáciu zásobníka použijeme štruktúru LIFO. Pre základné operácie so zásobníkom, vloženie položky na vrchol zásobníka a vybratie položky z jeho vrcholu, si vytvoríme dve funkcie:
<source lang="c">
stav zasobnika push(LIFO &zasobnik, int x);
int pop(LIFO &zasobnik);
</source>
'''Príklad vstupu do programu:'''

5 9 8 + 4 6 * * 7 + *

'''Príklad výstupu z programu:'''

2075

'''Možné riešenie:'''

<source lang="c" line>
#include<iostream>
#include <string.h>
using namespace std;

#define MAX_PAMAT 40

enum stav_zasobnika{OK=-1, FULL=INT_MAX, EMPTY=INT_MIN};

typedef struct {
double pamat[ MAX_PAMAT ];
int vrchol;
} LIFO;

/** pre ucely ladenia */
void show(LIFO &zasobnik){
cout<<"|";
for(int i=0; i<zasobnik.vrchol; i++) {
cout<<zasobnik.pamat[i]<<"|";
}
cout<<endl;
}

//VLOZI novu polozku 'x' do pola 'zasobnik.pamat' (do zasobnika) a zvacsi indexovu premennu //'zasobnik.vrchol' o 1
stav_fronty push(LIFO &zasobnik,double x) {

if(zasobnik.vrchol<MAX_PAMAT)
zasobnik.pamat[zasobnik.vrchol++]=x;
else
return FULL;
return OK;
}

//zmensi indexovu premennu 'zasobnik.vrchol' o 1 a VYBERIE poslednu vlozenu polozku z pola //'zasobnik.pamat' (zo zasobnika)
double pop(LIFO &zasobnik) {
if(zasobnik.vrchol>0)
return zasobnik.pamat[--zasobnik.vrchol];
else
return EMPTY;
}

int main()
{
LIFO f; //deklaracia strukturovej premennej typu 'LIFO' reprezentujucej zasobnik
f.vrchol=0;
int i,j,N;
char vyraz[40];

//cout<<"Vlozte postfixovy vyraz na vyhodnotenie:\n";
cin.getline(vyraz,39);

N=(int)strlen(vyraz); //v 'X' je dlzka nacitaneho retazca zo standardneho vstupu

// v cykle 'for' prechadzame vstupny vyraz ulozeny v poli 'vyraz' zlava doprava.
// Ak narazime na znak reprezentujuci cislo, vlozime ho na vrchol
// zasobnika ('f.pamat[f.vrchol]'), ak narazime na znak
// reprezentujuci operator, potom vyberieme z vrcholu zasobnika 2 operandy, aplikujeme na ne
// operator a namiesto tychto dvoch operandov vlozime na vrchol zasobnika vysledok samotnej
// operacie

for(i=0; i<N; i++)
{
if (vyraz[i]==' ') {
continue;
}
if (vyraz[i]=='+') {
push(f, (pop(f) + pop(f)));
continue;
}

if (vyraz[i]=='*') {
push(f, (pop(f) * pop(f)));
continue;
}

if (vyraz[i]=='/') {
push(f, (pop(f) / pop(f)));
continue;
}

if (vyraz[i]=='-') {
push(f, (pop(f) - pop(f)));
continue;
}

j=0;
while((vyraz[i]>='0' && vyraz[i]<='9') || vyraz[i]=='.') {
buffer[j] = vyraz[i];
i++;
j++;
}
buffer[j]=0;
x = atof (buffer);
if(FULL == push(f,x)){
cout<<"LIFO overflow";
break;
}
}
//na vrchole zasobnika je uz vysledok vyhodnoteneho postfixoveho aritmetickeho vyrazu, takze ho
//vypiseme
cout<<pop(f);
return 0;
}
</source>