Triedenie poľa komplexných čísel (riešené príklady) - História úprav

Juraj na 20:28, 16. august 2010

2010-08-16T20:28:17Z

Juraj: /* Námety na zlepšenie */

2010-03-10T11:10:12Z

Námety na zlepšenie

Juraj na 09:19, 10. marec 2010

2010-03-10T09:19:22Z

Juraj na 18:13, 8. marec 2010

2010-03-08T18:13:08Z

Zobraziť rozdiely

Juraj na 14:17, 8. marec 2010

2010-03-08T14:17:34Z

Juraj na 13:49, 8. marec 2010

2010-03-08T13:49:37Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Skripta programovanie (zbierka úloh)}} Majme známu štruktúru komplexné čí…“

2010-03-08T13:46:26Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:jazyk C {{Skripta programovanie (zbierka úloh)}} Majme známu štruktúru komplexné čí…“

Nová stránka

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

Majme známu štruktúru komplexné číslo - CPLX. Ako iste viete, komplexné číslo obsahuje 2 časti:reálnu časť (re) a imaginárnu časť (im). Ľubovoľné komplexné číslo C=a+i*b dokážeme zobraziť v komplexnej rovine ako vektor so začiatkom v bode [0,0] a koncom v bode C=[a,b].

Veľkosť komplexného čísla |C| je vlastne vzdialenosť od počiatku súradnicovej sústavy. Vypočítame ho pomocou pytagorovej vety ako: |C|=(a*a+b*b)^1/2

Majme pole komplexných čísel, ktoré chceme zotriediť podľa ich veľkosti. V hlavnom programe main načítam číslo n a následne n komplexných čísel. Tieto komplexné čísla načítajte do jednorozmerného poľa komplexných čísel, ktoré má presne veľkosť n (použite dynamickú alokáciu).

Ako triediaci algoritmus použijeme [[Triedenie delením|quicksort]], pretože je značne efektívny. Metóda triedenia quicksort bola vysvetlená na prednáške. Len v krátkosti: quicksort je rekurzívny algoritmus, ktorý si rozdelí usporiadavané pole na 2 časti: prvky v prvej časti sú menšie ako stredný prvok (pivot) a prvky v druhej časti sú väčšie ako stredný prvok. Potom sa rekurzívne aplikuje algoritmus quickosrt na prvú aj druhú časť triedeného poľa, pokiaľ je počet prvkov v danej časti poľa väčší ako 1.

V tomto príklade usporiadavame pole celých čísel. Našou úlohou je ale usporiadať pole komplexných čísel. Vo funkcii QuickSort sa zmení prvý parameter na pole komplexných čísel: CPLX data[]. Ďalej je treba zmeniť tú časť kódu, kde sa navzájom porovnávajú prvky triedeného poľa (podčiarknuté časti kódu). V tomto prípade sú to dva cykly while, kde sa určujú indexy i a j, ktoré slúžia pri usporiadavaní poľa na časť väčšiu a menšiu ako je pivot. Tieto časti kódu nahradíme porovnávacou funkciou, ktorá bude porovnávať dve komplexné čísla x a y. Ak platí že x>y, tak funkcia vráti 1, inak vráti 0. Týmto zručíme rovnakú funkcionalitu ako relačný operátor ‘>’. Funkcia bude mať 2 parametre typu CPLX a návratová hodnota bude int.

<source lang="c" line>
int porovnaj(CPLX a, CPLX b)
{
if(abs(a)>abs(b))
return 1;
else
return 0;
}
</source>

Na skontrolovanie správnosti usporiadania poľa komplecných čísel môžeme použiť jednoduchú funkciu, ktorá overí či prvok s indexom i+1 je väčší ako prvok s indexom i. Pri prvej nezhode funkcia vráti hodnotu 0. Ak sa pre všetky prvky platí predpoklad prvok[i+1]>prvok[i] , tak vráti funkcia hodnotu 1.
<source lang="c" line>
int skontroluj(CPLX data[ ],int n)
{
for(int i=1;i
{
if(porovnaj(data[i-1],data[i])>1)
return 0;
}
return 1;
}
</source>
Ak máme pripravenú porovnávaciu funkciu, tak aplikovanie iného algoritmu triedenia je veľmi jednoduché. Stačí v danom kóde zameniť časť kódu, kde sa robí porovnávanie prvkov.
Jazyk C obsahuje vstavanú funkciu qsort, ktorá usporiadava pole prvkov pomocou algoritmu quicksort. Hlavička funkcie vyzerá nasledovne:
<source lang="c">
void qsort(void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));
</source>
Opis funkcie qsort je na stránke {{funkcia_c|qsort}}

Použitie funkcie qsort pre náš príklad:
<source lang="c">
qsort((void *)ccisla2,n,sizeof(ccisla2[0]),porovnajQ);
</source>

<source lang="c" line>
int porovnajQ(const void *a, const void *b)
{ if(abs((*(CPLX *)a))>abs((*(CPLX *)b)))
return 1;
if(abs((*(CPLX *)a))<abs((*(CPLX *)b)))
return -1;
return 0;
}
</source>

Podľa definície funkcie qsort musí mať porovnávacia funkcia 2 argumenty typu ukazateľ na void. Teda parametre a a b sú typu ukazateľ na void. My však potrebujeme porovnať 2 komplexné čísla (bez ukazovateľov). Ako prvé musíme a a b pretypovať z ukazateľa na void na ukazateľ na CPLX. Toto urobíme následovne: (CPLX *)a.Teraz je a ukazateľ na CPLX. Ale ako už bolo povedané, my máme k dispozícii len komplexné čísla (CPLX), nie ukazatele. Z teórie ukazateľov vieme vzťah medzi ukazateľom a poľom – že ak je x ukazovateľ na nejaký dátový typ, tak *x je obsah prvého (s indexom 0) prvku. Teda, ak je (CPLX *)a ukazovateľ na CPLX, tak(*(CPLX *)a)je obsah tohto ukazateľa – čiže komplexné číslo a.

Na záver porovnajte, či oba algoritmy dosahujú zhodné výsledky – stačí porovnať polia usporiadané funkciou QuickSort a funkciou qsort.

<source lang="c" line>
int skontroluj(CPLX data1[ ],CPLX data2[ ],int n)
{ for(int i=0;i<n;i++)
if(porovnaj(data1[i],data2[i])!=0)
return 0;
return 1;
}
</source>

← Staršia verzia		Verzia zo dňa a času 20:28, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:jazyk C]]~~
	{{Skripta programovanie (zbierka úloh)}}		{{Skripta programovanie (zbierka úloh)}}

@@ Riadok 238: / Riadok 238: @@
 Aby sme mohli využiť myšlienku automatického generovania komplexných čísiel namiesto ich manuálneho zadávania je postačujúce modifikovať vyššie uvedený program nasledovným spôsobom.
-Načítavanie komplexných čísiel sa v programe realizuje na riadku 76 volaním funkcie nacitajCPLX(ccisla1[i]); Namiesto tohto riadku bude výhodné uviesť generujjCPLX(ccisla1[i]); Funkciu generujCPLX() síce ešte nemáme vytvorenú, ale jej význam je zrejmý. Jej jediným účelom je nahradiť načítanie dvoch reálnych čísiel z klávesnice ich vygenerovaním. Aby sme zachovali jednotnosť oboch funkcií (nacitajCLPX a generujCLPX), keďže plnia podobnú úlohu, budú mať obe funkcie rovnaký funkčný prototyp líšiaci sa len menom funkcie. Definícia funkcie môže byť nasledovná:
+Načítavanie komplexných čísiel sa v programe realizuje na riadku 80 volaním funkcie nacitajCPLX(ccisla1[i]); Namiesto tohto riadku bude výhodné uviesť generujjCPLX(ccisla1[i]); Funkciu generujCPLX() síce ešte nemáme vytvorenú, ale jej význam je zrejmý. Jej jediným účelom je nahradiť načítanie dvoch reálnych čísiel z klávesnice ich vygenerovaním. Aby sme zachovali jednotnosť oboch funkcií (nacitajCLPX a generujCLPX), keďže plnia podobnú úlohu, budú mať obe funkcie rovnaký funkčný prototyp líšiaci sa len menom funkcie. Definícia funkcie môže byť nasledovná:
 <source lang="c">
 void generujCPLX(CPLX &c)
@@ Riadok 251: / Riadok 251: @@
 <nowiki>#</nowiki>include <stdlib.h>
-Navyše, aby pri každom spustení programu sa generovali iné postupnosti čísiel, je potrebné pridať volanie funkcie, ktorá inicializuje generátor náhodných čísiel. Preto pred prvé volanie funkcie [[rand (jazyk C)|rand()]] pridáme riadok [[srand (jazyk C)|srand()]]. Môžeme tak urobiť napríklad vložením srand(time(NULL)) hneď za deklarácie premenných vo funkcii main(), t.j. na riadok 71.
+Navyše, aby pri každom spustení programu sa generovali iné postupnosti čísiel, je potrebné pridať volanie funkcie, ktorá inicializuje generátor náhodných čísiel. Preto pred prvé volanie funkcie [[rand (jazyk C)|rand()]] pridáme riadok [[srand (jazyk C)|srand()]]. Môžeme tak urobiť napríklad vložením srand(time(NULL)) hneď za deklarácie premenných vo funkcii main(), t.j. medzi riadky 74-75.
 Kvôli inicializovaniu generátora pseudonáhoných čísel treba pridať knižnicu time.h.
 Týtmo spôsobom sme veľmi jednoducho doplnili program o automatické generovanie komplexných čísiel. Teraz už môžeme využiť funkciu [[clock (jazyk C)|clock()]] pre stanovenie doby triedenia.

@@ Riadok 10: / Riadok 10: @@
 V programe načítajte číslo n a následne n komplexných čísel. Pre uloženie týchto čísel vytvorte také veľké pole aké je potrebné.
-==Analýza problému==
+===Analýza problému===
 Komplecné číslo pozostáva z 2 častí: reálna zložka a imaginárna zložka. Komplexné číslo C zapíšeme ako:
@@ Riadok 38: / Riadok 38: @@
 int porovnaj(CPLX a, CPLX b)
+{
-  return abs(a)- abs(b) ;
+   if(abs(a)>abs(b))
+}
 </source>
@@ Riadok 99: / Riadok 103: @@
+}
 </source>
-==Riešenie pomocou funkcie qsort==
+===Riešenie pomocou funkcie qsort===
 Jazyk C obsahuje vstavanú funkciu qsort, ktorá usporiadava pole prvkov pomocou algoritmu Quicksort. Hlavička funkcie vyzerá nasledovne:
 <source lang="c">
@@ Riadok 130: / Riadok 134: @@
 </source>
-==Riešenie v jazyku C==
+===Riešenie v jazyku C===
 Úlohou je porovnať rýchlosť oboch implementovaných algoritmov triedenia. Aby mali oba algoritmy rovnaké počiatočné podmienky, vytvoríme si dve zhodné polia komplexných čísel (ccisla1, ccisla2). Potom každýý algoritmus bude triediť rovnaké vstupné dáta.
 <source lang="c" line>
@@ Riadok 147: / Riadok 151: @@
 int porovnaj(CPLX a, CPLX b)
+{
-  return abs(a)-abs(b);
+   if(abs(a)>abs(b))
+}
@@ Riadok 176: / Riadok 184: @@
 int skontroluj(CPLX data[ ],int n)
 {   for(int i=1;i<n;i++)
-         if(porovnaj(data[i-1],data[i])>0)
+         if(abs(data[i-1])>abs(data[i]))
              return -1;
      return 0;
@@ Riadok 225: / Riadok 233: @@
 Pre meranie dĺžky trvania algoritmov môžeme použiť funkciu [[clock (jazyk C)|clock]].

@@ Riadok 41: / Riadok 41: @@
 void qsort(void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));
 </source>
-Opis funkcie qsort je na stránke {{funkcia_c|qsort}}
 Použitie funkcie qsort pre náš príklad: