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

Triedenie(riešené príklady)

2010-02-23T21:04:39Z

Mstepanovsky:

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}

==Triedenie poľa štruktúr==
'''Zadanie'''

Zostavte program, ktorý bude triediť dáta uložené v súbore na základe užívateľom zadaného kritéria. Program po spustení načíta dáta zo súboru a uloží ich do poľa štruktúr. Následne na monitor zobrazí výzvu, v ktorej bude mať užívateľ možnosť vybrať kritérium triedenia. Pre jednoduchosť uvažujme príklad, v ktorom budeme triediť zamestnancov nejakej fiktívnej firmy podľa mena, priezviska alebo podľa roku jeho narodenia. Dáta v súbore nech sú uložené vo formáte kde jednotlivé položky sú oddelené medzerami čiarkami v tvare:
Meno Priezvisko , Rok_narodenia

'''Metodický komentár'''

Cieľom tejto úlohy je precvičiť prácu so štruktúrami v jazyku C, použitie funkcie rýchleho triedenia (quick sort) z knižnice ''stdlib.h'', načítavanie dát zo súboru, a pomôcť osvojiť si základné znalosti pri práci s ukazovateľmi (predávanie ako parameter do funkcie, pretypovávanie).

'''Vzorové dáta'''
Janko Maly , 1978
Martin Starsi , 1939
Andrea Mlada , 1990
Jozko Cierny , 1985
Alenka Biela , 1985
Janko Maly , 1983
Alzbetka Mudra , 1978

'''Zjednodušujúce predpoklady'''

Dĺžka mena ani priezviska neprekračuje rozsah 20 znakov. V zdrojovom súbore sa nebude nachádzať viac ako 100 záznamov. Zdrojový súbor sa nachádza v tom istom adresáry ako samotný program (*.exe súbor) a jeho názov je: data.txt.

'''Vzorová výzva programu'''
Vyber kriterium triedenia.
Meno 1
Priezvisko 2
Rok narodenia 3
Pre ukoncenie programu 0
Volba: _

'''Vzorový vstup'''
1

'''Vzorový výstup'''
--------------------------------------------------------
ZAMESTNANEC ROK NARODENIA
--------------------------------------------------------
Alenka Biela 1985
Alzbetka Mudra 1978
Andrea Mlada 1990
Janko Maly 1983
Janko Maly 1978
Jozko Cierny 1985
Martin Starsi 1939
--------------------------------------------------------

'''Návod ako začať'''

Zo zadania vyplýva, že hlavným účelom programu je triediť (vzostupne príp. zostupne zoradzovať) zamestnancov podľa triediaceho kritéria (meno, priezvisko, rok). Aby sme pri manipulácii (triedení) s jednotlivými zamestnancami pracovali ucelene so všetkými dátami vzťahujúcimi sa ku konkrétnemu zamestnancovi naraz, bude výhodné použiť štruktúru, ktorá nám tieto dáta takpovediac "zabalí". Takto budeme mať údaje o jednom zamestnancovi pohromade a budeme môcť s nimi pohodlne manipulovať. Týmto sme vyriešili problém ako reprezentovať jedného zamestnanca. Teraz sa vynára otázka ako efektívne pracovať s celým súborom zamestnancov. Pretože vieme, že v zdrojovom súbore sa nebude nachádzať viac ako 100 zamestnancov, bude vcelku výhodné použiť statické pole štruktúr na pamätanie všetkých zamestnancov. Dĺžka tohto poľa bude 100 položiek. Jedna položka poľa potom bude predstavovať jedného konkrétneho zamestnanca. Utriedenie zamestnancov potom budeme realizovať utriedením tohto poľa. Pre triedenie poľa ponúka knižnica ''stdlib.h'' funkciu rýchleho triedenia ''qsort''. Parametre a použitie funkcie ''qsort'' z knižnice ''stdlib.h'' si teraz vysvetlíme.

Úplný funkčný prototyp funkcie ''qsort'' je nasledovný:
<source lang="c">
void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *, const void *));
</source>
Ako vidíme funkcia má štyri parametre, ktorých význam je:
*''base'' - ukazovateľ typu void ukazujúci na nultý element triedeného poľa
*''nelem'' - počet elementov v triedenom poli
*''width'' - veľkosť jedného elementu v bajtoch
*''fcmp'' - ukazovateľ na porovnávaciu funkciu, ktorá porovnáva dva elementy triedeného poľa

Porovnávacia funkcia vyžaduje dva argumenty - ukazovatele typu ''const void *''. Označme tieto argumenty ''elem1'' a ''elem2''. Potom úplný funkčný prototyp porovnávacej funkcie bude:
<source lang="c">
int (*fcmp)(const void *elem1, const void *elem2);
</source>

Od funkcie ''fcmp'' sa vyžaduje aby vracala celé číslo v závislosti od výsledku porovnania argumentov ''elem1'' a ''elem2'' nasledovne:
* ak *''elem1'' < *''elem2'' potom ''fcmp'' vráti celé číslo < 0
* ak *''elem1'' == *''elem2'' potom ''fcmp'' vráti 0
* ak *''elem1'' > *''elem2'' potom ''fcmp'' vráti celé číslo > 0

Pri porovnávaní elementov elem1 a elem2 symbol < znamená, že elem1 je menší ako elem2 v tom zmysle, že v utriedenom poli sa elem1 nachádza pred elem2. Podobne pre symbol >. Ak sú porovnávané elementy z pohľadu triediaceho kritéria ekvivalenté (symbol ==) potom funkcia vráti nulu. Napríklad ak porovnávame dva reťazce a kritériom je abcedné usporiadanie, potom reťazec "Alexandra" je menší ako reťazec "Zora". Ak by sme však chceli triediť podľa dĺžky reťazca, potom reťazec "Alexandra" je väčší ako reťazec "Zora".

Triedenie poľa sa potom realizuje volaním funkcie ''qsort'' s patričnými parametrami.

''Poznámka'': Pri porovnávaní porovnávame obsahy argumentov ''elem1'' a ''elem2'', to znamená, že píšeme napr. *''elem1'' < *''elem2'' namiesto ''elem1'' < ''elem2''. Zápis ''elem1'' < ''elem2'' by totiž znamenal, že máme porovnať hodnotu ''elem1'' a ''elem2'' čo by znamenalo, že máme porovnať nejaké adresy uložené v premenných ''elem1'' a ''elem2'' (tieto premenné sú ukazovatele a teda pamätajú adresu, nie samotnú štruktúru). Porovnanie ''elem1'' < ''elem2'' by teda bolo syntakticky správne, ale nemalo by zmysel. Chceme predsa porovnávať zamestnancov a nie adresy pamäte kde sú títo zamestnanci uložení.

Použitie funkcie ''qsort'' ilustrujeme na nasledujúcom jednoduchom príklade:
<source lang="c">
#include <stdio.h>
#include <stdlib.h>
#define POCET_PRVKOV 6

int pole[POCET_PRVKOV] = { 45, 11, 100, 30, 20, 27 };

int Porovnaj_cele_cisla (const void * a, const void * b)
{
// Parameter "a" je ukazovateľ typu "const void *". Preto ho pred použitím musíme pretypovať na poiter na "int". Čiže: "(int *)a".
// Pretože zápis "(int *)a" predstavuje ukazovateľ a my chceme porovnávať celé číslo, ktoré je uložené tam kde tento ukazovateľ ukazuje
// musíme ďalej napísať: "*(int *)a". Týmto zápisom sa dostaneme k hodnote čísla na ktoré ukazuje predaný parameter "const void * a".
// Podobne pre parameter "b".
return ( *(int*)a - *(int*)b );
}

int main ()
{
int n;
// Vzostupné utriedenie poľa:
qsort (pole, POCET_PRVKOV, sizeof(int), Porovnaj_cele_cisla);

// Výpis na monitor:
for (n=0; n<POCET_PRVKOV; n++)
printf ("%d ",values[n]);
return 0;
}
</source>

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

<source lang="c" line >
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>

#define NAZOV_SUBORU "data.txt"

// Vytvorenie pomenovanej struktury s nazvom "ZAMESTNANEC"
struct ZAMESTNANEC {
char meno[21];
char priezvisko[21];
int rok_narodenia;
};

// Uplne funkcne prototypy pouzivanych funkcii:
int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V); // Nacitanie jedineho zamestnanca zo suboru
void vypisZAMESTNANEC(ZAMESTNANEC V); // Vypisanie jedineho zamestnanca na monitor
int porovnajROK(const void *V1, const void *V2); // Porovnanie dvoch zamestnancov podla roku narodenia
int porovnajMENO(const void *V1, const void *V2); // Porovnanie dvoch zamestnancov podla mena
int porovnajPRIEZV(const void *V1, const void *V2); // Porovnanie dvoch zamestnancov podla priezviska

// Hlavna funkcia programu:
int main(int argc, char* argv[])
{
ZAMESTNANEC pole[100]; // pole struktur pre uchovavanie jednotlivych zamestnancov
int Pocet_zamestnancov = 0; // pocet nacitanych zamestnancov
int volba; // kriterium triedenia / ukoncenia programu
FILE *fr; // pointer na subor
int i; // pomocna premenna

// Otvorenie zdrojoveho suboru v rezime "read"
if((fr=fopen(NAZOV_SUBORU,"r"))==NULL)
{
printf("\n Pozadovany subor sa nepodarilo otvorit!\n");
system("pause");
exit(1);
}

// Nacitanie vsetkych zamestnancov zo suboru
for(i=0; nacitajZAMESTNANEC(fr,&pole[i]); i++)
{
;
}
Pocet_zamestnancov = i;
fclose(fr); // zatvorenie suboru, data uz su nacitane..
fr = NULL; // zaroven nastavime na NULL pre pripad aby sme v pripade chybneho pouzitia tohto poitera boli vcas varovani

// Hlavny cyklus programu
do{
printf("\n Vyber kriterium triedenia. \n"
" Meno 1\n"
" Priezvisko 2\n"
" Rok narodenia 3\n\n"
" Pre ukoncenie programu 0\n\n"
" Volba: ");
scanf("%d",&volba);

switch(volba)
{
case 0: break;
case 1: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajMENO); break; // namiesto sizeof(ZAMESTNANEC) mozeme pouzit sizeof(pole[0])
case 2: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajPRIEZV); break;
case 3: qsort((void*)pole,Pocet_zamestnancov,sizeof(ZAMESTNANEC),porovnajROK); break;
default:
printf("\n Neocakavany vstup. Program bude ukonceny.\n");
volba=0;
}
if(volba) // Vypisanie utriedeneho pola na monitor
{
clrscr(); //vycistime si obrazovku
printf("--------------------------------------------------------\n");
printf(" ZAMESTNANEC ROK NARODENIA\n");
printf("--------------------------------------------------------\n");
for(i=0; i<Pocet_zamestnancov; i++)
vypisZAMESTNANEC(pole[i]);
printf("--------------------------------------------------------\n");
}
}while(volba);

system("pause");
return 0;
}

// Definicie pouzivanych funkcii:
//---------------------------------------------------------------------------
int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
{
int a;
a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
if(a == EOF) a = 0;
return a;
}
//---------------------------------------------------------------------------
void vypisZAMESTNANEC(ZAMESTNANEC V)
{
printf(" %-20s %-20s %d\n", V.meno, V.priezvisko, V.rok_narodenia);
}
//---------------------------------------------------------------------------
int porovnajROK(const void *V1, const void *V2)
{
return ((ZAMESTNANEC*)V1)->rok_narodenia - ((ZAMESTNANEC*)V2)->rok_narodenia;
}
//---------------------------------------------------------------------------
int porovnajMENO(const void *V1, const void *V2)
{
return strcmp(((ZAMESTNANEC*)V1)->meno, ((ZAMESTNANEC*)V2)->meno);
}
//---------------------------------------------------------------------------
int porovnajPRIEZV(const void *V1, const void *V2)
{
return strcmp(((ZAMESTNANEC*)V1)->priezvisko, ((ZAMESTNANEC*)V2)->priezvisko);
}
</source>

'''Komentár k uvedenému riešeniu'''

V programe sa na prvý pohľad nachádza zopár zvláštností. Prvou je prázdne telo cyklu ''for'' pri načítavaní zamestnancov zo súboru - pozri riadok xx programu (nachádza sa tam len bodkočiarka za účelom zdôraznenia vedomého vypustenia tela funkcie). Dôvodom je, že samotné načítanie zamestnancov sa nachádza v porovnávacej (testovacej) časti cyklu ''for''. Ak sa úspešne načíta nejaký zamestnanec zo súboru potom funkcia ''nacitajZAMESTNANEC'' vracia nenulové kladné číslo, v opačnom prípade nulu a cyklus ''for'' sa skončí. Druhou zvláštnosťou je spôsob načítavania položiek "meno", "priezvisko" a "rok_narodenia" v tele definicie funkcie ''nacitajZAMESTNANEC'' - pozri riadok xx. V tomto prípade s výhodou využívame možností funkcie ''fscanf'', pričom využívame skutočnosť, že jednotlivé položky sú oddelené medzerou a čiarkou. Treťou zvláštnosťou je použitie typu ''const void *'' v parametroch a následné pretypovávanie v tele na pointer na pomenovanú štruktúru ZAMESTNANEC vo všetkých troch porovnávacích funkciách - ''porovnajMENO'', ''porovnajPRIEZV'' a ''porovnajROK''. Toto priamo súvisí s požiadavkou na parametre porovnávacej funkcie, ktorá musí vyhovovať funkčnému prototypu funkcie triedenia - ''qsort''.

'''Nedostatky uvedeného riešenia a námety na zlepšenie'''

Program nie je vhodný na triedenie väčšieho množstva dát. Pri triedení sa manipuluje s celými položkami (štruktúra ZAMESTNANEC), ktoré majú v tomto prípade veľkosť sizeof(ZAMESTNANEC) == 48 Bajtov. Funkcia ''qsort'' tak musí pri triedení kopírovať celý obsah, čo môže byť časovo náročné. Ak by navyše jednotlivé položky uchovávali ešte väčie množstvo dát (ďalšie údaje o zamestnancovi, ako napríklad pracovné zaradenie, osobné hodnotenie zamestnanca, kontaktné informácie a pod.) bola by situácia ešte horšia. Podobný nedostatok má aj funkcia vypisZAMESTNANEC. V tomto prípade však tento problém nie je kritický. Prvou možnosťou ako zefektívniť triedenie je redukovanie veľkosti štruktúry ZAMESTNANEC. To sa dá docieliť použitím dynamicky alokovanej pamäte pre uchovávanie mena a priezviska zamestnanca. V tomto prípade by mohla štruktúra ZAMESTNANEC vyzerať nasledovne:

<source lang="c" >
struct ZAMESTNANEC {
char *meno;
char *priezvisko;
int rok_narodenia;
};
</source>

Potom by sa pamäťové nároky na uchovávanie redukovali na 12 Bajtov. Je však nevyhnutné pamätať na to, že adresy uchovávané v položkách "meno" a "priezvisko" môžu byť ľubovolné (sú neinicializované) a preto môžu ukazovať na ľubovolné miesto v pamäti. Preto treba použiť dynamickú alokáciu pamäte (funkcia malloc, resp. operátor new) a ukazovatele "meno" a "priezvisko" správne nastaviť (využitím návratovej hodnoty funkcie malloc, resp. operátora new).

Ďalšou možnosťou ako zefektívniť triedenie je použitie poľa ukazovateľov na prvky typu ZAMESTNANEC. Ukazovateľ na typ ZAMESTNANEC (či už pôvodný alebo tu uvedený) má veľkosť 4 Bajty. Z pohľadu triedenia funkciou qsort je preto tento spôsob ešte výhodnejší.

Použitím kombinácie oboch možností (dynamicky alokovaný priestor pre uchovávenie jednotlivých záznamov typu ZAMESTNANEC a použitie poľa ukazovateľov na prvky typu ZAMESTNANEC pre účely triedenia) je možné dosiahuť hospodárne využitie pamäte a zároveň efektívne triedenie rozsiahlejšieho súboru dát.

Druhou možnosťou sa zaoberá nasledujúca časť - Triedenie poľa ukazovateľov.

==Triedenie poľa ukazovateľov ''aneb'' Triedime štruktúry efektívne==
'''Zadanie'''

Uvažujme rovnaké zadanie ako v predošlom. Navyše požadujme viacúrovňové (vnorené) triedenie podľa triediaceho kritéria s nižšou prioritou ak sú položky podľa aktuálneho triediaceho kritéria ekvivalentné. V našom jednoduchom príklade to znamená, že ak napríklad triedime zamestnancov podľa krstného mena a mená niektorých zamestnancov sú rovnaké, potom budú títo utriedení podľa priezviska. Naopak, ak budeme triediť podľa priezviska a priezviská niektorých zamestnancov budú rovnaké, potom ich utriedime podľa krstného mena. Túto situáciu môžeme rozšíriť aj o triedenie podľa roku narodenia. V tomto prípade môžeme definovať prioritu jednotlivým triediacim kritériam a triediť následne podľa priorít.

'''Metodický komentár'''

:Cieľom tejto úlohy v porovaní s predchádzajúcou je efektívne triediť dáta použitím ukazovateľov a poukázať na ďalšie možnosti pri ich triedení. Využijú sa pokročilejšie techniky práce s ukazovateľmi, dynamická alokácia a realokácia pamäte.

'''Vzorové dáta'''
:Ako v predošlom.

'''Zjednodušujúce predpoklady'''

:Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte.
:V súbore sa teda môže nachádzať niekoľko desiatok, ale aj stoviek tisícov záznamov.

'''Vzorová výzva programu'''
Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)
Meno, Priezvisko, Rok 1
Priezvisko, Meno, Rok 2
Rok, Meno, Priezvisko 3
Rok, Priezvisko, Meno 4
Pre ukoncenie programu 0
Volba: _

'''Vzorový vstup'''
1

'''Vzorový výstup'''
--------------------------------------------------------
ZAMESTNANEC ROK NARODENIA
--------------------------------------------------------
Alenka Biela 1985
Alzbetka Mudra 1978
Andrea Mlada 1990
Janko Maly 1978
Janko Maly 1983
Jozko Cierny 1985
Martin Starsi 1939
--------------------------------------------------------

'''Návod ako začať'''

Prvým významným rozdielom v porovnaní s predchádzajúcim zadaním je skutočnosť, že počet záznamov (zamestnancov) v súbore nie je obmedzený a je vopred neznámy. Z toho dôvodu je použitie statického poľa štruktúr neefektívne. Riešením je dynamická alokácia pamäte. Mohli by sme tak dynamicky alokovať pole štruktúr podľa aktuálnej potreby programu. Ak sa však zamyslíme nad požiadavkou efektívneho triedenia zamestnancov prichádzame k záveru, že ani toto riešenie by nebolo vhodné. Dôvodom je činnosť funkcie ''qsort'', ktorá pri triedení manipuluje s celými položkami poľa, ktoré by v tomto prípade boli štruktúry (keďže by sa jednalo o pole štruktúr či už staticky alebo dynamicky alokované). Funkcia ''qsort'' by tak musela pracovať pri triedení s pomerne veľkým objemom dát. Riešením tejto situácie je použitie dynamicky alokovaného poľa ukazovateľov. Jednotlivé položky poľa by potom už neboli samotné štruktúry, ale adresy týchto štruktúr. Ako vieme, veľkosť adresy je 4 bajty (resp. 8B v 64-bitovom OS). Takže funkcia ''qsort'' bude triediť pole adries tak aby po zotriedení boli splnené požiadavky triedenia dané prioritami triediacich kritérií. Ak zhrnieme doteraz povedané, tak pre pamätanie celého súboru zamestnancov je výhodné použiť dynamicky alokované pole ukazovateľov, v ktorom pre každý prvok poľa budeme dynamicky alokovať pamäťový priestor pre pamätanie štruktúry uchovávajúcej údaje o jednom konkrétnom zamestnancovi.

Druhým významným rozdielom je požiadavka na viacúrovňové triedenie. Pri písaní porovnávacích funkcií zohľadňujúcich tri úrovne priorít triediacih kritérií je výhodné začať od písania funkcií pre jednoúrovňové triedenie (pozri predchádzajúci príklad), tieto ďalej využiť pri písaní dvojúrovňových, a tieto spolu zasa pri písaní trojúrovňových. Takto môžeme veľmi jednoducho a prehľadne podľa potreby napísať rôzne mnohoúrovňové porovnávacie funkcie.

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

<source lang="c" line >
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>

#define NAZOV_SUBORU "data.txt"
#define KROK_REALOKACIE 100

// Vytvorenie pomenovanej struktury s nazvom "ZAMESTNANEC"
struct ZAMESTNANEC {
char meno[21];
char priezvisko[21];
int rok_narodenia;
};

// Uplne funkcne prototypy pouzivanych funkcii:
int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V); // Nacitanie jedineho zamestnanca zo suboru
void vypisZAMESTNANEC(ZAMESTNANEC V); // Vypisanie jedineho zamestnanca na monitor
int porovnajROK(const void *V1, const void *V2); // Porovnanie dvoch zamestnancov podla roku narodenia
int porovnajMENO(const void *V1, const void *V2); // Porovnanie dvoch zamestnancov podla mena
int porovnajPRIEZV(const void *V1, const void *V2); // Porovnanie dvoch zamestnancov podla priezviska
int porovnajPRIEZV_MENO(const void *V1, const void *V2); // Porovnanie najprv podla priezviska potom podla mena
int porovnajMENO_PRIEZV(const void *V1, const void *V2); // podobne dalej...
int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2);
int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2);
int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2);
int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2);

// Hlavna funkcia programu:
int main(int argc, char* argv[])
{
ZAMESTNANEC **pole; // Pozor, zmena v porovnani s predchadzajucim riesenim!
int Pocet_zamestnancov = 0; // Pocet nacitanych zamestnancov
int maxPocet_zamestnancov = 100; // Prednastaveny maximalny pocet zamestnancov
int volba; // kriterium triedenia / ukoncenia programu
FILE *fr; // pointer na zdrojovy subor, z ktoreho budeme nacitavat zamestnancov
int (*sortFun)(const void *,const void *); // pointer na funkciu, pomocou ktorej budeme triedit
int i; // pomocna premenna

// Otvorenie zdrojoveho suboru v rezime "read"
if((fr=fopen(NAZOV_SUBORU,"r"))==NULL)
{
printf("\n Pozadovany subor sa nepodarilo otvorit!\n");
system("pause");
exit(1);
}

// Prvotna alokacia pamate pre pole pointrov na pomenovanu strukturu ZAMESTNANEC
if((pole=(ZAMESTNANEC**)malloc(maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
{
printf(" Nedostatok pamate!\n");
system("pause");
exit(1);
}

//Najprv si musime alokovat priestor pre prveho zamestnanca (aby data, ktore nacitame sme mali kam ulozit)
if((pole[0]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
{
printf("\n Nedostatok pamete...\n");
exit(1);
}

// Nacitanie vsetkych zamestnancov zo suboru
for(i=0; nacitajZAMESTNANEC(fr,pole[i]); i++)
{
//Alokujeme si miesto pre dalsieho zamestnanca:
if((pole[i+1]=(ZAMESTNANEC*)malloc(sizeof(ZAMESTNANEC)))==NULL)
{
printf("\n Nedostatok pamete pre pridanie dalsieho zamestnanca...\n");
system("pause");
exit(1);
}

// V pripade potreby realokujeme pole pinterov: (Tato situacia nastane
// ak pocet zamestnancov v subore je vacsi ako aktualne nastavna hodnota
// premennej maxPocet_zamestnancov)
if(i == maxPocet_zamestnancov-2)
{
maxPocet_zamestnancov += KROK_REALOKACIE; // Zvysime maximalny pocet zamestnancov
//printf("...realokujem...");
if((pole=(ZAMESTNANEC**)realloc(pole,maxPocet_zamestnancov*sizeof(ZAMESTNANEC*)))==NULL)
{
printf(" Nedostatok pamate pre realokaciu pola pointerov!\n");
system("pause");
exit(1);
}
}
}
Pocet_zamestnancov = i;
fclose(fr); // zatvorenie suboru, data uz su nacitane..
fr = NULL; // zaroven nastavime na NULL pre pripad aby sme v pripade chybneho pouzitia tohto poitera boli vcas varovani

// Hlavny cyklus programu
do{
printf("\n Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)\n"
" Meno, Priezvisko, Rok 1\n"
" Priezvisko, Meno, Rok 2\n"
" Rok, Meno, Priezvisko 3\n"
" Rok, Priezvisko, Meno 4\n\n"
" Pre ukoncenie programu 0\n\n"
" Volba: ");
scanf("%d",&volba);

switch(volba)
{
case 0: break;
case 1: sortFun = porovnajMENO_PRIEZV_ROK; break;
case 2: sortFun = porovnajPRIEZV_MENO_ROK; break;
case 3: sortFun = porovnajROK_MENO_PRIEZV; break;
case 4: sortFun = porovnajROK_PRIEZV_MENO; break;
default:
printf("\n Neocakavany vstup. Program bude ukonceny.\n");
volba=0;
}
if(volba) // Vypisanie utriedeneho pola na monitor
{
// Utriedenie zamestnancov:
qsort((void*)pole,Pocet_zamestnancov,sizeof(pole[0]),sortFun);

clrscr(); //vycistime si obrazovku
printf("--------------------------------------------------------\n");
printf(" ZAMESTNANEC ROK NARODENIA\n");
printf("--------------------------------------------------------\n");
for(i=0;i<Pocet_zamestnancov;i++)
vypisZAMESTNANEC(*pole[i]);
printf("--------------------------------------------------------\n");
}
}while(volba);

// Na zaver nasleduje uvolnenie pamate, ktoru sme alokovali.
// Najprv musime uvolnit pamet, ktoru sme alokovali pre jednotlivych zamestnancov.
for(i=0; i<skutocnyPocet_zamestnancov + 1;i++) //Pocet alokovanych zamestnancov je o jednehoneho viac...
free(pole[i]);

//Potom uvolnime pamat alokovanu pre pointre
free(pole);
poleStud = NULL; // a nastavime na NULL (nie je nevyhnutne potrebne)

system("pause");
return 0;
}

// Definicie pouzivanych funkcii:
//---------------------------------------------------------------------------
int nacitajZAMESTNANEC(FILE *fr, ZAMESTNANEC *V)
{
int a;
a = fscanf(fr,"%s %s , %d", V->meno, V->priezvisko, &V->rok_narodenia);
if(a == EOF) a = 0;
return a;
}
//---------------------------------------------------------------------------
void vypisZAMESTNANEC(ZAMESTNANEC V)
{
printf(" %-20s %-20s %d\n", V.meno, V.priezvisko, V.rok_narodenia);
}
//---------------------------------------------------------------------------
int porovnajROK(const void *V1, const void *V2)
{
return (*(ZAMESTNANEC**)V1)->rok_narodenia - (*(ZAMESTNANEC**)V2)->rok_narodenia;
}
//---------------------------------------------------------------------------
int porovnajMENO(const void *V1, const void *V2)
{
return strcmp((*(ZAMESTNANEC**)V1)->meno, (*(ZAMESTNANEC**)V2)->meno);
}
//---------------------------------------------------------------------------
int porovnajPRIEZV(const void *V1, const void *V2)
{
return strcmp((*(ZAMESTNANEC**)V1)->priezvisko, (*(ZAMESTNANEC**)V2)->priezvisko);
}
//---------------------------------------------------------------------------
int porovnajPRIEZV_MENO(const void *V1, const void *V2)
{
int a = porovnajPRIEZV(V1, V2);
if(a == 0) a = porovnajMENO(V1, V2);
return a;
}
//---------------------------------------------------------------------------
int porovnajMENO_PRIEZV(const void *V1, const void *V2)
{
int a = porovnajMENO(V1, V2);
if(a == 0) a = porovnajPRIEZV(V1, V2);
return a;
}
//---------------------------------------------------------------------------
int porovnajMENO_PRIEZV_ROK(const void *V1, const void *V2)
{
int a = porovnajMENO_PRIEZV(V1, V2);
if(a == 0) a = porovnajROK(V1, V2);
return a;
}
//---------------------------------------------------------------------------
int porovnajPRIEZV_MENO_ROK(const void *V1, const void *V2)
{
int a = porovnajPRIEZV_MENO(V1, V2);
if(a == 0) a = porovnajROK(V1, V2);
return a;
}
//---------------------------------------------------------------------------
int porovnajROK_PRIEZV_MENO(const void *V1, const void *V2)
{
int a = porovnajROK(V1, V2);
if(a == 0) a = porovnajPRIEZV_MENO(V1, V2);
return a;
}
//---------------------------------------------------------------------------
int porovnajROK_MENO_PRIEZV(const void *V1, const void *V2)
{
int a = porovnajROK(V1, V2);
if(a == 0) a = porovnajMENO_PRIEZV(V1, V2);
return a;
}
</source>

'''Komentár k uvedenému riešeniu'''

Bude zverejnený neskôr.

'''Nedostatky uvedeného riešenia a námety na zlepšenie'''

Program nie je vhodný na triedenie extrémne rozsiahlych dát. Riešením tohto nedostatku je použitie iných triediacich funkcií, ktoré pracujú na princípe triedenia triedeného súboru po častiach. Ďalším nedostatkom je výpis utriedených dát na monitor. Táto operácia môže byť pri väčšom počte záznamov časovo veľmi zdĺhavá. Oveľa výhodnejšie a zároveň rýchlejšie je zapisovať výsledky do súboru. V tomto prípade by postačovalo modifikovať funkciu ''vypisZAMESTNANEC'' tak, aby vyhovovala tomuto účelu.
<source lang="c">
vypisZAMESTNANEC(FILE *fw, ZAMESTNANEC *V)
{
fprintf(fw," %-20s %-20s %d\n", V->meno, V->priezvisko, V->rok_narodenia); // Zaroven efektivnejsie pristupujeme k polozkam zamestnanca (parameter V je pointer...)
}
</source>

Ak by sme si ďalej zadefinovali funkciu na výpis všetkých zamestnancov celý program by sme zjednodušili a výpis zamestnancov by bol univerzálnejší v tom zmysle, že výpis zamestnancov či už do súboru alebo na monitor by mal jednotnú podobu. Funkcia na výpis všetkých zamestnancov by mohla vyzerať nasledovne:
<source lang="c">
vypisZAMESTNANCOV(FILE *fw, ZAMESTNANEC **pole, int Pocet_zamestnancov)
{
printf("--------------------------------------------------------\n");
printf(" ZAMESTNANEC ROK NARODENIA\n");
printf("--------------------------------------------------------\n");
for(i=0;i<Pocet_zamestnancov;i++)
vypisZAMESTNANEC(fw, pole[i]);
printf("--------------------------------------------------------\n");
}
</source>
Potom by jednoducho stačilo otvoriť nejaký súbor v režime "write" a zavolať túto funkciu na zápis všetkých zamestnancov do súboru. Ak by sme však chceli vypísať zamestnancov na monitor, potom namiesto ukazovateľa na otvorený súbor zadáme ''stdout''. Čiže do programu vložíme riadok:
<source lang="c">
vypisZAMESTNANCOV(stdout,pole,Pocet_zamestnancov);
</source>

Triedenie(riešené príklady)

2010-02-23T16:01:43Z

Mstepanovsky:

Triedenie(riešené príklady)

2010-02-23T12:28:03Z

Mstepanovsky: Vytvorená stránka „==Triedenie poľa štruktúr== '''Zadanie''' Zostavte program, ktorý bude triediť dáta uložené v súbore na základe užívateľom zadaného kritéria. Program po spu…“

==Triedenie poľa štruktúr==
'''Zadanie'''

Zostavte program, ktorý bude triediť dáta uložené v súbore na základe užívateľom zadaného kritéria. Program po spustení načíta dáta zo súboru a uloží ich do poľa štruktúr. Následne na monitor zobrazí výzvu, v ktorej bude mať užívateľ možnosť vybrať kritérium triedenia. Pre jednoduchosť uvažujme príklad, v ktorom budeme triediť zamestnancov nejakej fiktívnej firmy podľa mena, priezviska alebo podľa roku jeho narodenia. Dáta v súbore nech sú uložené vo formáte kde jednotlivé položky sú oddelené medzerami čiarkami v tvare:
Meno Priezvisko , Rok_narodenia

'''Metodický komentár'''

Cieľom tejto úlohy je precvičiť prácu so štruktúrami v jazyku C, použitie funkcie rýchleho triedenia (quick sort) z knižnice ''stdlib.h'', načítavanie dát zo súboru, a pomôcť osvojiť si základné znalosti pri práci s ukazovateľmi (predávanie ako parameter do funkcie, pretypovávanie).

'''Vzorové dáta'''
Janko Maly , 1978
Martin Starsi , 1939
Andrea Mlada , 1990
Jozko Cierny , 1985
Alenka Biela , 1985
Janko Maly , 1983
Alzbetka Mudra , 1978

'''Zjednodušujúce predpoklady'''

Dĺžka mena ani priezviska neprekračuje rozsah 20 znakov. V zdrojovom súbore sa nebude nachádzať viac ako 100 záznamov. Zdrojový súbor sa nachádza v tom istom adresáry ako samotný program (*.exe súbor) a jeho názov je: data.txt.

'''Vzorová výzva programu'''
Vyber kriterium triedenia.
Meno 1
Priezvisko 2
Rok narodenia 3
Pre ukoncenie programu 0
Volba: _

'''Vzorový vstup'''
1

'''Vzorový výstup'''
--------------------------------------------------------
ZAMESTNANEC ROK NARODENIA
--------------------------------------------------------
Alenka Biela 1985
Alzbetka Mudra 1978
Andrea Mlada 1990
Janko Maly 1983
Janko Maly 1978
Jozko Cierny 1985
Martin Starsi 1939
--------------------------------------------------------

'''Návod ako začať'''

Zo zadania vyplýva, že hlavným účelom programu je triediť (vzostupne príp. zostupne zoradzovať) zamestnancov podľa triediaceho kritéria (meno, priezvisko, rok). Aby sme pri manipulácii (triedení) s jednotlivými zamestnancami pracovali ucelene so všetkými dátami vzťahujúcimi sa ku konkrétnemu zamestnancovi naraz, bude výhodné použiť štruktúru, ktorá nám tieto dáta takpovediac "zabalí". Takto budeme mať údaje o jednom zamestnancovi pohromade a budeme môcť s nimi pohodlne manipulovať. Týmto sme vyriešili problém ako reprezentovať jedného zamestnanca. Teraz sa vynára otázka ako efektívne pracovať s celým súborom zamestnancov. Pretože vieme, že v zdrojovom súbore sa nebude nachádzať viac ako 100 zamestnancov, bude vcelku výhodné použiť statické pole štruktúr na pamätanie všetkých zamestnancov. Dĺžka tohto poľa bude 100 položiek. Jedna položka poľa potom bude predstavovať jedného konkrétneho zamestnanca. Utriedenie zamestnancov potom budeme realizovať utriedením tohto poľa. Pre triedenie poľa ponúka knižnica ''stdlib.h'' funkciu rýchleho triedenia ''qsort''. Parametre a použitie funkcie ''qsort'' z knižnice ''stdlib.h'' si teraz vysvetlíme.

Úplný funkčný prototyp funkcie ''qsort'' je nasledovný:
<source lang="c">
void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *, const void *));
</source>
Ako vidíme funkcia má štyri parametre, ktorých význam je:
*''base'' - pointer typu void ukazujúci na nultý element triedeného poľa
*''nelem'' - počet elementov v triedenom poli
*''width'' - veľkosť jedného elementu v bajtoch
*''fcmp'' - pointer na porovnávaciu funkciu, ktorá porovnáva dva elementy triedeného poľa

Porovnávacia funkcia vyžaduje dva argumenty - pointery typu ''const void *''. Označme tieto argumenty ''elem1'' a ''elem2''. Potom úplný funkčný prototyp porovnávacej funkcie bude:
<source lang="c">
int (*fcmp)(const void *elem1, const void *elem2);
</source>
Od funkcie ''fcmp'' sa vyžaduje aby vracala celé číslo v závislosti od výsledku porovnania argumentov ''elem1'' a ''elem2'' nasledovne:
* ak *''elem1'' < *''elem2'' potom ''fcmp'' vráti celé číslo < 0
* ak *''elem1'' == *''elem2'' potom ''fcmp'' vráti 0
* ak *''elem1'' > *''elem2'' potom ''fcmp'' vráti celé číslo > 0

Pri porovnávaní elementov elem1 a elem2 symbol < znamená, že elem1 je menší ako elem2 v tom zmysle, že v utriedenom poli sa elem1 nachádza pred elem2. Podobne pre symbol >. Ak sú porovnávané elementy z pohľadu triediaceho kritéria ekvivalenté (symbol ==) potom funkcia vráti nulu. Napríklad ak porovnávame dva reťazce a kritériom je abcedné usporiadanie, potom reťazec "Alexandra" je menší ako reťazec "Zora". Ak by sme však chceli triediť podľa dĺžky reťazca, potom reťazec "Alexandra" je väčší ako reťazec "Zora".

Triedenie poľa sa potom realizuje volaním funkcie ''qsort'' s patričnými parametrami.

''Poznámka'': Pri porovnávaní porovnávame obsahy argumentov ''elem1'' a ''elem2'', to znamená, že píšeme napr. *''elem1'' < *''elem2'' namiesto ''elem1'' < ''elem2''. zápis ''elem1'' < ''elem2'' by totiž znamenal, že máme porovnať hodnotu ''elem1'' a ''elem2'' čo by znamenalo, že máme porovnať nejaké adresy uložené v premenných ''elem1'' a ''elem2'' (tieto premenné sú ukazovatele a teda pamätajú adresu, nie samotnú štruktúru). Porovnanie ''elem1'' < ''elem2'' by teda bolo syntakticky správne, ale nemalo by zmysel. Chceme predsa porovnávať zamestnancov a nie adresy pamäte kde sú títo zamestnanci uložení.

Použitie funkcie ''qsort'' ilustrujme na nasledujúcom jednoduchom príklade:
<source lang="c">
#include <stdio.h>
#include <stdlib.h>
#define POCET_PRVKOV 6

int pole[POCET_PRVKOV] = { 45, 11, 100, 30, 20, 27 };

int Porovnaj_cele_cisla (const void * a, const void * b)
{
// Parameter "a" je pointer typu "const void *". Preto ho pred použitím musíme pretypovať na poiter na "int". Čiže: "(int *)a".
// Pretože zápis "(int *)a" predstavuje pointer a my chceme porovnávať celé číslo, ktoré je uložené tam kde tento pointer ukazuje
// musíme ďalej napísať: "*(int *)a". Týmto zápisom sa dostaneme k hodnote čísla na ktoré ukazuje predaný parameter "const void * a".
// Podobne pre parameter "b".
return ( *(int*)a - *(int*)b );
}

int main ()
{
int n;
qsort (pole, POCET_PRVKOV, sizeof(int), Porovnaj_cele_cisla);
for (n=0; n<POCET_PRVKOV; n++)
printf ("%d ",values[n]);
return 0;
}
</source>

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

Bude zverejnené neskôr.

'''Komentár k uvedenému riešeniu'''

Bude zverejnený neskôr.

'''Nedostatky uvedeného riešenia a námety na zlepšenie'''

Budú zverejnené neskôr.

==Triedenie poľa ukazovateľov ''aneb'' Triedime štruktúry efektívne==
'''Zadanie'''

Uvažujme rovnaké zadanie ako v predošlom s tým rozdielom, že načítané dáta nebudeme ukladať do poľa štruktúr. Navyše požadujme vnorené triedenie podľa triediaceho kritéria s nižšou prioritou ak sú položky podľa aktuálneho triediaceho kritéria ekvivalentné. V našom jednoduchom príklade to znamená, že ak napríklad triedime zamestnancov podľa krstného mena a mená niektorých zamestnancov sú rovnaké, potom budú títo utriedení podľa priezviska. Naopak, ak budeme triediť podľa priezviska a priezviská niektorých zamestnancov budú rovnaké, potom ich utriedime podľa krstného mena. Túto situáciu môžeme rozšíriť aj o triedenie podľa roku narodenia. V tomto prípade môžeme definovať prioritu jednotlivým triediacim kritériam a triediť následne podľa priorít.

'''Metodický komentár'''

Cieľom tejto úlohy v porovaní s predchádzajúcou je efektívne triediť dáta použitím ukazovateľov a poukázať na ďalšie možnosti pri ich triedení. Využijú sa pokročilejšie techniky práce s ukazovateľmi, dynamická alokácia a realokácia pamäte.

'''Vzorové dáta'''
Ako v predošlom.

'''Zjednodušujúce predpoklady'''

Rovnaké ako v predošlom s tým rozdielom, že počet záznamov v súbore nie je obmedzený. Predpokladáme však, že systém má dostatok voľnej pamäte. V súbore sa teda môže nachádzať niekoľko desiatok, ale aj stoviek tisícov záznamov.

'''Vzorová výzva programu'''
Vyber postupnost kriterii triedenia. (Prve kriterium ma najvacsiu prioritu.)
Meno, Priezvisko, Rok 1
Priezvisko, Meno, Rok 2
Rok, Meno, Priezvisko 3
Rok, Priezvisko, Meno 4
Pre ukoncenie programu 0
Volba: _

'''Vzorový vstup'''
1

'''Vzorový výstup'''
--------------------------------------------------------
ZAMESTNANEC ROK NARODENIA
--------------------------------------------------------
Alenka Biela 1985
Alzbetka Mudra 1978
Andrea Mlada 1990
Janko Maly 1978
Janko Maly 1983
Jozko Cierny 1985
Martin Starsi 1939
--------------------------------------------------------

'''Návod ako začať'''

Prvým významným rozdielom v porovnaní s predchádzajúcim zadaním je skutočnosť, že počet záznamov (zamestnancov) v súbore nie je obmedzený a je vopred neznámy. Z toho dôvodu je použitie statického poľa štruktúr neefektívne. Riešením je dynamická alokácia pamäte. Mohli by sme tak dynamicky alokovať pole štruktúr podľa aktuálnej potreby programu. Ak sa však zamyslíme nad požiadavkou efektívneho triedenia zamestnancov prichádzame k záveru, že ani toto riešenie by nebolo vhodné. Dôvodom je činnosť funkcie ''qsort'', ktorá pri triedení manipuluje s celými položkami poľa, ktoré by v tomto prípade boli štruktúry (keďže by sa jednalo o pole štruktúr či už staticky alebo dynamicky alokované). Funkcia ''qsort'' by tak musela pracovať pri triedení s pomerne veľkým objemom dát. Riešením tejto situácie je použitie dynamicky alokovaného poľa ukazovateľov. Jednotlivé položky poľa by potom už neboli samotné štruktúry, ale adresy týchto štruktúr. Ako vieme, veľkosť adresy je 4 bajty (resp. 8B v 64-bitovom OS). Takže funkcia ''qsort'' bude triediť pole adries tak aby po zotriedení boli splnené požiadavky triedenia dané prioritami triediacich kritérií.

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

Bude zverejnené neskôr.

'''Komentár k uvedenému riešeniu'''

Bude zverejnený neskôr.

'''Nedostatky uvedeného riešenia a námety na zlepšenie'''

Budú zverejnené neskôr.

Rekurzia (riešené príklady)

2010-02-23T10:47:09Z

Mstepanovsky: /* Prevod čísel z 10-vej sústavy */

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:jazyk C]]
{{Draft}}
{{Skripta programovanie (zbierka úloh)}}
__TOC__

==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'''
{|
|-
!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>
#include <conio.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);
}
}

void main()
{
double r;
int sustava;
cout << "cislo v 10-kovej sustave: "; cin >> r;
cout << "cielova sustava: "; cin >> sustava;
cout << "prevedene: ";
Prevod(r, sustava, 6);
getch();
}
</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,10,13,17,19, ...

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 zbyto4n7m 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/