|
|
| (8 medziľahlých úprav od 2 ďalších používateľov nie je zobrazených) |
| Riadok 1: |
Riadok 1: |
| − | [[Kategória:Študijné materiály]]
| |
| − | [[Kategória:Programovanie]]
| |
| − | [[Kategória:jazyk C]]
| |
| | {{Draft}} | | {{Draft}} |
| | {{Skripta programovanie (zbierka úloh)}} | | {{Skripta programovanie (zbierka úloh)}} |
| | + | |
| | + | ==Triedenie poľa komplexných čísel== |
| | + | ===Zadanie=== |
| | + | Vytvorte program, ktorý usporiada pole komplexných čísel. Úlohu riešte pomocou algoritmu Quicksort (definovaného v quicksort) a pomocou vstavanej funkcie jazyka C qsort. Porovnajte dosiahnuté výsledky (rýchlosť výpočtu). |
| | + | |
| | + | Viac na [[Triedenie poľa komplexných čísel (riešené príklady)]] |
| | + | |
| | | | |
| | ==Triedenie poľa štruktúr== | | ==Triedenie poľa štruktúr== |
| − | '''Zadanie'''
| + | ===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: | | 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 | | Meno Priezvisko , Rok_narodenia |
| − | | + | ===Metodický komentár=== |
| − |
| |
| − | '''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). | | 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). |
| | | | |
| | + | Viac na [[Triedenie poľa štruktúr (riešené príklady)]] |
| | | | |
| − | '''Vzorové dáta'''
| + | ==Triedenie poľa ukazovateľov alebo Triedime štruktúry efektívne== |
| − | Janko Maly , 1978
| + | ===Zadanie=== |
| − | Martin Starsi , 1939
| + | 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. |
| − | Andrea Mlada , 1990
| + | ===Metodický komentár=== |
| − | 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. | | :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. |
| | | | |
| − | | + | Viac na [[Triedenie poľa smerníkov (riešené príklady)]] |
| − | '''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.
| |
|
|
Toto je projekt, na ktorom sa ešte stále pracuje!!
Aj keď sú v tomto dokumente použiteľné informácie, ešte nie je dokončený. Svoje návrhy môžete vyjadriť v diskusii o tejto stránke.
|
Triedenie poľa komplexných čísel
Zadanie
Vytvorte program, ktorý usporiada pole komplexných čísel. Úlohu riešte pomocou algoritmu Quicksort (definovaného v quicksort) a pomocou vstavanej funkcie jazyka C qsort. Porovnajte dosiahnuté výsledky (rýchlosť výpočtu).
Viac na Triedenie poľa komplexných čísel (riešené príklady)
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).
Viac na Triedenie poľa štruktúr (riešené príklady)
Triedenie poľa ukazovateľov alebo 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.
Viac na Triedenie poľa smerníkov (riešené príklady)
