Triedenie poľa komplexných čísel (riešené príklady)
Obsah
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).
Vstupné a výstupné údaje
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
Komplecné číslo pozostáva z 2 častí: reálna zložka a imaginárna zložka. Komplexné číslo C zapíšeme ako:
C=a+bi
Ľ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].
V jazyku C si pre komplexné číslo vytvoríme dátovú štruktúru, ktorá ho bude reprezentovať. V štruktúre definujeme 2 časti: reálnu (Re) a imaginárnu (Im). Obe časti sú typu double. Štruktúru si pomenujeme CPLX.
1 struct CPLX{
2 double Re,Im;
3 };
Veľkosť komplexného čísla |C| je vzdialenosť od počiatku súradnicovej sústavy. Vypočítame ho pomocou Pytagorovej vety ako:
[math]\left |C\right |=\sqrt{a^2+b^2}[/math]
Majme pole komplexných čísel, ktoré chceme zotriediť podľa ich veľkosti. V programe máme začítať hodnotu n a následne n komplexných čísel. Pre uloženie týchto čísel vytvoríme jednorozmerné pole komplexných čísel. Veľkosť poľa je daná hodnotou n. Pre vytvorenie takéhoto poľa použijeme dynamickú alokáciu pamäti.
Ako triediaci algoritmus použijeme Quicksort, pretože je efektívny.
V samotnom algorime triedenia sa vyskytujú časti, kde sa porovnávajú prvky poľa vzájomne medzi sebou. Jazyk C nedovoľuje porovnávanie premenných typu štruktúra. Aby sme dokázali porovnávať premenné typu CPLX (komplexné číslo) vytvoríme si porovnávaciu funkciu. Funkcia porovnaj bude mať 2 parametre - komplexné čísla ktoré budeme porovnávať. Návratová hodnota funkcie bude typu int.
Funkcia porovnaj:
int porovnaj(CPLX a, CPLX b)
{
if(abs(a)>abs(b))
return 1;
if(abs(a)<abs(b))
return -1;
return 0;
}
Pre porovnanie hodnoty 2 komplexných čísel vypočítame absolútnu hodnotu každého komplexného čísla a porovnáme tieto hodnoty.
Parametre funkcie
a, b - komplexné čísla (dátový typ CPLX), ktoré budeme porovnávať.
Návratová hodnota
- kladné číslo - ak platí, že a>b
- záporné číslo - ak platí, že a<b
- 0 - ak platí, že a=b
Použitie porovnávacej funkcie
1 CPLX x, y;
2 // nacitanie hodnot x, y
3 if(porovnaj(x,y)>0)
4 cout<<"Cislo x je vascie ako y";
5 if(porovnaj(x,y)<0)
6 cout<<"Cislo x je mensie ako y";
7 else
8 cout<<"Cisla x a y su rovnake";
9 }
Na skontrolovanie správnosti usporiadania poľa komplexný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 -1. Ak sa pre všetky prvky platí predpoklad prvok[i+1]>prvok[i] , tak vráti funkcia hodnotu 0.
1 int skontroluj(CPLX *data,int n)
2 {
3 for(int i=1;i<n;i++)
4 {
5 if(porovnaj(data[i-1],data[i])>1)
6 return -1;
7 }
8 return 0;
9 }
Ak máme pripravenú porovnávaciu funkciu, tak aplikovanie iného algoritmu triedenia je jednoduché. Stačí v danom kóde zameniť časť kódu, kde sa robí porovnávanie prvkov.
1 void QuickSort(CPLX *data,int lavy, int pravy)
2 { if(lavy<pravy)
3 { int i = lavy, j = pravy;
4 CPLX p = data[ (lavy + pravy) / 2 ];
5 do {
6 while ( porovnaj(p,data[ i ])>0 ) i++; // pouzitie funkcie porovnaj
7 while ( porovnaj(data[ j ],p)>0 ) j--; // pouzitie funkcie porovnaj
8 if (i <= j)
9 { zamen(data[ i ], data[ j ]);
10 i++; j--;
11 }
12 } while (i <= j);
13 QuickSort(data, lavy, j);
14 QuickSort(data, i, pravy);
15 }
16 }
Riešenie pomocou funkcie qsort
Jazyk C obsahuje vstavanú funkciu qsort, ktorá usporiadava pole prvkov pomocou algoritmu Quicksort. Hlavička funkcie vyzerá nasledovne:
void qsort(void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));
Opis funkcie qsort je na stránke qsort
Použitie funkcie qsort pre náš príklad:
qsort((void *)ccisla2,n,sizeof(ccisla2[0]),porovnajQ);
kde porovnajQ je porovnávacia funkcia:
1 int porovnajQ(const void *a, const void *b)
2 { if(abs((*(CPLX *)a))>abs((*(CPLX *)b)))
3 return 1;
4 if(abs((*(CPLX *)a))<abs((*(CPLX *)b)))
5 return -1;
6 return 0;
7 }
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:
a // ukazateľ na void
(CPLX *)a // a je ukazateľ na void pretypovaný na ukazateľ na CPLX
*(CPLX *)a // hondota komplexneho cisla, ktore sme ziskali
// z ukazateľa na void a pretypovali na ukazateľ na CPLX
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.
1 #include <iostream>
2 #include <math.h>
3 using namespace std;
4
5 struct CPLX{double re,im;};
6
7 void nacitajCPLX(CPLX &c)
8 { cin>>c.re>>c.im; }
9
10 double abs(CPLX x)
11 { return sqrt( (x.re*x.re)+ (x.im*x.im) ); }
12
13 int porovnaj(CPLX a, CPLX b)
14 {
15 if(abs(a)>abs(b))
16 return 1;
17 if(abs(a)<abs(b))
18 return -1;
19 return 0;
20 }
21
22 void zamen (CPLX &a, CPLX &b)
23 {
24 CPLX tmp=a;
25 a=b;
26 b=tmp;
27 }
28
29 void QuickSort(CPLX *data,int lavy, int pravy)
30 { if(lavy<pravy)
31 { int i = lavy, j = pravy;
32 CPLX p = data[ (lavy + pravy) / 2 ];
33 do {
34 while ( porovnaj(p,data[ i ])>0 ) i++;
35 while ( porovnaj(data[ j ],p)>0 ) j--;
36 if (i <= j)
37 { zamen(data[ i ], data[ j ]);
38 i++; j--;
39 }
40 } while (i <= j);
41 QuickSort(data, lavy, j);
42 QuickSort(data, i, pravy);
43 }
44 }
45
46 int skontroluj(CPLX data[ ],int n)
47 { for(int i=1;i<n;i++)
48 if(abs(data[i-1])>abs(data[i]))
49 return -1;
50 return 0;
51 }
52
53 void vypis(CPLX *data,int n)
54 { for(int i=0;i<n;i++)
55 { cout<<data[i].re;
56 if(data[i].im>0)
57 cout<<"+i"<<data[i].im;
58 else
59 cout<<"-i"<<-data[i].im;
60 cout<<" ("<<abs(data[i])<<")";
61 cout<<endl;
62 }
63 }
64
65 int porovnajQ(const void *a, const void *b)
66 { if(abs((*(CPLX *)a))>abs((*(CPLX *)b)))
67 return 1;
68 if(abs((*(CPLX *)a))<abs((*(CPLX *)b)))
69 return -1;
70 return 0;
71 }
72
73 int main()
74 { int n;
75 cin>>n;
76 CPLX *ccisla1=new CPLX[n];
77 CPLX *ccisla2=new CPLX[n];
78
79 for(int i=0;i<n;i++)
80 { nacitajCPLX(ccisla1[i]);
81 ccisla2[i]=ccisla1[i];
82 }
83
84 int k;
85 QuickSort(ccisla1,0,n-1);
86 k=skontroluj(ccisla1,n);
87 cout<<"kontola QuickSort:"<<k<<endl;
88
89 qsort((void *)ccisla2,n,sizeof(ccisla2[0]),porovnajQ);
90 k=skontroluj(ccisla2,n);
91 cout<<"kontola qsort:"<<k<<endl;
92 return 0;
93 }
Pre meranie dĺžky trvania algoritmov môžeme použiť funkciu clock.
Námety na zlepšenie
Program od použivateľa vyžaduje najprv zadanie čísla n a následne zadanie n komplexných čísiel. Tento úkon zadávania komplexných čísiel z klávesnice môže byť pre väčšie hodnoty n pomerne prácny. Preto bez ujmy na názornosti príkladu môžeme nahradiť zadávanie komplexných čísiel z klávesnice ich automatickým generovaním. Týmto spôsobom môžeme generovať tisíce komplexných čísiel, triediť ich rôznymi algoritmami, porovnávať výkonnosť jednotlivých algoritmov, voliť rôzne reprezentácie ukladania komplexných čísiel v pamäti a vyhodnocovať efektivitu ich ukladania s pohľadu triedenia.
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 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á:
void generujCPLX(CPLX &c)
{ int x;
while((x=rand())==0)
;
c.re = (rand()-RAND_MAX/2)/(double)x;
c.im = (rand()-RAND_MAX/2)/(double)x;
}
Keďže v definícii funkcie používame funkciu rand(), ktorá je definovaná v knižnici stdlib.h musíme hneď za druhý riadok pridať: #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() pridáme riadok 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() pre stanovenie doby triedenia.
