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

Algoritmy a programovanie - zbierka úloh

---

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie

Lineárny zoznam

Binárny strom

Numerické algoritmy

Š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:

1. 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:
   1. 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“.
   2. 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“.
2. 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).
3. 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:

 1 #include <iostream.h>
 2 
 3 using namespace std;
 4 
 5 struct TZlomok { int citatel, menovatel; };
 6 void CitajZlomok(TZlomok &z)
 7 {
 8    cin >> z.citatel;
 9    cin >> z.menovatel;
10 }
11 
12 int NSD(int a, int b)
13 {
14    while (b)
15    {
16       int c = a % b;
17       a = b;
18       b = c;
19    }
20    return a;
21 }
22 
23 void SkratZlomok(TZlomok &z)
24 {
25    int nsd = NSD(z.citatel, z.menovatel);
26    z.citatel /= nsd;
27    z.menovatel /= nsd;
28 }
29 
30 void VypisZlomok(TZlomok z)
31 {
32    SkratZlomok(z);
33    int cela_cast = z.citatel / z.menovatel;
34    if (cela_cast)
35    {
36       cout << cela_cast;
37       int zvysok = z.citatel % z.menovatel;
38       if (zvysok) cout << " " << zvysok << "/" << z.menovatel;
39    }
40    else
41    {
42       cout << z.citatel;
43       if (z.citatel) // ak je nula, napise len ju a nie napr. 0/1
44       cout << "/" << z.menovatel;
45    }
46    cout << endl;
47 }
48 
49 TZlomok Zlomok(int cit, int men)
50 {
51    TZlomok z;
52    z.citatel = cit;
53    z.menovatel = men;
54    SkratZlomok(z);
55    return z;
56 }
57 
58 TZlomok SucinZlomkov(TZlomok z1, TZlomok z2)
59 {
60    return Zlomok(z1.citatel * z2.citatel, z1.menovatel * z2.menovatel);
61 }
62 
63 TZlomok SucetZlomkov(TZlomok z1, TZlomok z2)
64 {
65    return Zlomok(z1.citatel * z2.menovatel + z2.citatel * z1.menovatel,
66    z1.menovatel * z2.menovatel);
67 }
68 
69 TZlomok PodielZlomkov(TZlomok z1, TZlomok z2)
70 {
71    return Zlomok(z1.citatel * z2.menovatel, z1.menovatel * z2.citatel);
72 }
73 
74 int main()
75 {
76    TZlomok z1, z2;
77    CitajZlomok(z1); VypisZlomok(z1);
78    CitajZlomok(z2); VypisZlomok(z2);
79    cout << "sucin: "; VypisZlomok(SucinZlomkov(z1, z2));
80    cout << "sucet: "; VypisZlomok(SucetZlomkov(z1, z2));
81    cout << "podiel: "; VypisZlomok(PodielZlomkov(z1, z2));
82    return 0;
83 }

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.

Spracovanie postfixového výrazu 5 9 8 + 4 6 * * 7 + *

index v pamati zásobníka čí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:

  stav zasobnika push(LIFO &zasobnik, int x);
  int pop(LIFO &zasobnik);

Príklad vstupu do programu:

5 9 8 + 4 6 * * 7 + *

Príklad výstupu z programu:

2075

Možné riešenie:

  1 #include<iostream>
  2 #include <string.h>
  3 using namespace std;
  4 
  5 #define MAX_PAMAT 40 
  6 
  7 enum stav_zasobnika{OK=-1, FULL=INT_MAX, EMPTY=INT_MIN}; 
  8 
  9 typedef struct {
 10     double pamat[ MAX_PAMAT ];
 11     int vrchol;
 12 } LIFO;
 13 
 14 /** pre ucely ladenia */
 15 void show(LIFO &zasobnik){
 16     cout<<"|";
 17     for(int i=0; i<zasobnik.vrchol; i++) {
 18         cout<<zasobnik.pamat[i]<<"|";
 19     }
 20     cout<<endl;
 21 }
 22 
 23 //VLOZI novu polozku 'x' do pola 'zasobnik.pamat' (do zasobnika) a zvacsi indexovu premennu //'zasobnik.vrchol' o 1
 24 stav_fronty push(LIFO &zasobnik,double x) {
 25 
 26     if(zasobnik.vrchol<MAX_PAMAT)
 27         zasobnik.pamat[zasobnik.vrchol++]=x;
 28     else
 29         return FULL;
 30     return OK;
 31 }
 32 
 33 //zmensi indexovu premennu 'zasobnik.vrchol' o 1 a VYBERIE poslednu vlozenu polozku z pola //'zasobnik.pamat' (zo zasobnika)
 34 double pop(LIFO &zasobnik) {
 35     if(zasobnik.vrchol>0)
 36         return zasobnik.pamat[--zasobnik.vrchol];
 37     else
 38         return EMPTY;
 39 }
 40 
 41 int main()
 42 {
 43       LIFO f; //deklaracia strukturovej premennej typu 'LIFO' reprezentujucej zasobnik
 44       f.vrchol=0;
 45       int i,j,N;
 46       char vyraz[40];
 47 
 48       //cout<<"Vlozte postfixovy vyraz na vyhodnotenie:\n";
 49       cin.getline(vyraz,39);
 50 
 51       N=(int)strlen(vyraz); //v 'X' je dlzka nacitaneho retazca zo standardneho vstupu 
 52 
 53       // v cykle 'for' prechadzame vstupny vyraz ulozeny v poli 'vyraz' zlava doprava. 
 54       // Ak narazime na znak reprezentujuci cislo, vlozime ho na vrchol 
 55       // zasobnika ('f.pamat[f.vrchol]'), ak narazime na znak
 56       // reprezentujuci operator, potom vyberieme z vrcholu zasobnika 2 operandy, aplikujeme na ne
 57       // operator a namiesto tychto dvoch operandov vlozime na vrchol zasobnika vysledok samotnej
 58       // operacie
 59 
 60       for(i=0; i<N; i++)
 61       {
 62         if (vyraz[i]==' ') {
 63           continue;
 64         }
 65         if (vyraz[i]=='+') {
 66             push(f, (pop(f) + pop(f)));
 67             continue;
 68         }
 69 
 70         if (vyraz[i]=='*') {
 71             push(f, (pop(f) * pop(f)));
 72             continue;
 73         }
 74 
 75         if (vyraz[i]=='/') {
 76             push(f, (pop(f) / pop(f)));
 77             continue;
 78         }
 79 
 80         if (vyraz[i]=='-') {
 81             push(f, (pop(f) - pop(f)));
 82             continue;
 83         }
 84 
 85         j=0;
 86         while((vyraz[i]>='0' && vyraz[i]<='9') || vyraz[i]=='.') {
 87             buffer[j] = vyraz[i];
 88             i++;
 89             j++;
 90         }
 91         buffer[j]=0;
 92         x = atof (buffer);
 93         if(FULL == push(f,x)){
 94             cout<<"LIFO overflow";
 95             break;
 96         }
 97      }
 98       //na vrchole zasobnika je uz vysledok vyhodnoteneho postfixoveho aritmetickeho vyrazu, takze ho
 99       //vypiseme
100       cout<<pop(f); 
101       return 0;
102 }