Reprezentarea unui graf cu ajutorul calculatorului

Reprezentarea unui graf  cu ajutorul calculatorului

Tema nr. 4:

Scrieti programul C care permite plasarea a n noduri in varfurile unui poligon regulat inscris intr-un cerc, cu posibilitatea de a trasa linii intre oricare doua varfuri ale poligonului. (Nodurile le vom presupune ca fiind primele litere ale alfabetului latin)

Analiza:

Daca dorim sa reprezentam grafic un nod, suntem in situatia urmatoare:

Evident ca cercul mare nu o sa-l reprezentam grafic, insa avem nevoie sa ni-l imaginam pentru a realiza reprezentarea grafica a cercului mic (care va reprezenta nodul). Coordonatele centrului sau, , sunt catete in triunghiul dreptunghic ce are ipotenuza egala cu raza cercului mare (pe care o vom nota cu ). Acest triunghi are un unghi avand masura egala cu , deoarece suma masurilor unghiurilor in jurul unui punct este , iar daca sunt astfel de unghiuri, fiecare va avea masura egala cu , iar aceasta reprezinta masura celui de-al -lea unghi (putem considera ).

In acest triunghi: si , deci avem urmatoarele relatii pentru determinarea coordonatelor centrului cercului ce reprezinta nodul:

Insa aceste formule sunt adevarate numai daca coordonatele centrului cercului mare sunt . Dar aceasta este imposibil deoarece acestea in C reprezinta coordonatele coltului din stanga sus a ecranului. Daca consideram ca cercul mare are centrul , atunci formulele de mai sus vor deveni:

Acestea sunt formulele de calcul a coordonatelor centrului fiecarui nod, si sunt relative la coltul din stanga sus al ecranului, adica exact cum se considera coordonatele unui punct in C.

Pentru a obtine o figura echidistanta de marginile monitorului vom considera centrul cercului mare ca fiind plasat in mijlocul monitorului, adica coordonatele sale vor fi:

Practic, ceea ce avem de facut este sa desenam cate un cerc cu centrul avand aceste coordonate (folosind functia pieslice sau fillellipse) de raza , iar in centrul acestui cerc sa scriem cate o litera, a -a litera mare din alfabetul latin pentru al -lea astfel de cerc:

for(k=0; k<n; k++)

Si cu aceasta am desenat nodurile. Insa mai trebuie sa desenam si arce, adica linii intre coordonatele centrelor a doua noduri. Aceasta se realizeaza astfel:

printf('Primul nod: ');

scanf('%c', &c1); c1=toupper(c1);

i = c1 - 'A';

printf('Al doilea nod: ');

fflush(stdin); scanf('%c', &c2); c2 = toupper(c2);

j = c2 - 'A';

x0 = getmaxx()/2;

y0 = getmaxy()/2;

xi = x0 + R*cos(2*i*PI/n);

yi = y0 - R*sin(2*i*PI/n);

xj = x0 + R*cos(2*j*PI/n);

yj = y0 - R*sin(2*j*PI/n);

line(xi, yi, xj, yj);

Tot ce mai avem de facut e sa integram aceste lucruri intr-un program, in care mai avem de realizat initializarea modului de lucru grafic, testarea corectitudinii datelor de intrare, si eventual atentia la detalii de design:

Programul:

#include <conio.h>

#include <graphics.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h> // for exit

#include <ctype.h> // for toupper

#define PI 2*asin(1)

#define R 200

#define r 20

#define CALE 'C:BORLANDCBGI'

void main(void)

initializare_mod_grafic();

desenare(n);

outtextxy(getmaxx()/2-10, getmaxy()-10, 'Apasati o tasta');

getch();

setcolor(BLACK);

outtextxy(getmaxx()/2-10, getmaxy()-10, 'Apasati o tasta');

textcolor(WHITE);

//closegraph();

fflush(stdin);

printf('nIntroduceti un arc? '); scanf('%c',&op); op=toupper(op);

while (op=='D')

printf('Al doilea nod: ');

fflush(stdin); scanf('%c', &c2); c2 = toupper(c2);

j = c2 - 'A';

if((j<0) || (j>=n))

x0 = getmaxx()/2;

y0 = getmaxy()/2;

xi = x0 + R*cos(2*i*PI/n);

yi = y0 - R*sin(2*i*PI/n);

xj = x0 + R*cos(2*j*PI/n);

yj = y0 - R*sin(2*j*PI/n);

setcolor(WHITE);

line(xi, yi, xj, yj);

outtextxy(getmaxx()/2-10, getmaxy()-10, 'Apasati o tasta');

getch();

setcolor(BLACK);

outtextxy(getmaxx()/2-10, getmaxy()-10, 'Apasati o tasta');

textcolor(WHITE);

alt_arc:

sterge();

gotoxy(1,2);

printf('Mai introduceti un arc? ');

fflush(stdin); scanf('%c',&op); op=toupper(op);

}

closegraph();

} /* main */

void initializare_mod_grafic(void)

} /* initializare_mod_grafic */

void desenare(int n)

;

x0 = getmaxx()/2;

y0 = getmaxy()/2;

for(k=0; k<n; k++)

setcolor(WHITE);

} /* desenare */

void sterge(void)

Observatii:

Acest program NU manipuleaza un graf (din acest motiv nici nu am dat aici definitia grafului, ci in laboratorul urmator), ci tot ceea ce realizeaza sunt niste desene, insa acestea sunt alese in asa fel incat sa simuleze modul de reprezentare a unui graf real.

Singura verificare ce se face asupra numarului de noduri este ca acesta sa fie intreg si pozitiv, astfel, desi nu se intentioneaza folosirea sa in acest fel, programul functioneaza si daca trebuie sa reprezinte un numar de noduri mai mare decat numarul de litere mari din alfabet, denumindu-le dupa nodul cu numele "Z" astfel: "[", "", "]", "^", etc, adica urmatoarele caractere ASCII dupa "Z".

Din motive de design am ales ca interogatoriul cu privire la adaugarea unui nou "arc" sa se efectueze tot timpul in coltul din stanga sus al ecranului (pentru a nu interfera scrisul cu desenul), si astfel avem nevoie de "stergerea" portiunii respective. Acest lucru l-am realizat desenand un poligon in regiunea respectiva pe care sa-l "umplem" cu culoarea neagra (acest lucru il realizeaza functia sterge()).