Exemplu de proiect din perspectiva elevului

Carmen Avramescu Grafuri orientate

Greierele si furnica (graf turneu) - enunt Un musuroi de furnici si-a construit in pamant un mic orasel. Acesta este alcatuit din niste incaperi, numite camere, unde se vor depozita provizii de mancare. Unele dintre aceste camere sunt legate intre ele prin niste coridoare numite galerii. Regina furnicilor decide sa-l ajute pe greierele din fabula, care nu avea nici o provizie pentru iarna, dar acesta va trebui sa-si procure singur mancarea, vizitand toate camerele oraselului, dar trecand, prin galerii, exact o singura data prin fiecare camera.

Greierele si furnica (graf turneu) - enunt Se stie ca intre oricare doua camere exista o galerie de legatura care poate fi parcursa intr-un singur sens. Greierele va trebui sa gaseasca un traseu in conditiile trasate de regina si, in aceste conditii, va putea sa-si ia din fiecare camera ce si cat isi doreste. Realizati un program care sa-I stabileasca greierului traseul de urmat. De la tastatura se citeste macheta orasului, adica reteaua de camere si galerii. Traseul va fi tiparit pe ecran sub forma unei secvente de numere reprezentand numerele de ordine ale camelor prin care va trece greierele, in ordinea in care vor fi vizitate de catre acesta.

Reprezentare Oraselul furnicilor poate fi privit ca un graf, in care nodurile sunt camerele iar arcele sunt galeriile de legatura dintre camere. Deoarece enuntul precizeaza ca intre oricare doua camere exista o galerie de legatura care poate fi parcursa intr-un singur sensputem formula urmatoarele concluzii: graful este orientat, intre oricare doua noduri exista un arc si numai unul care le leaga, arcul respectiv avand una din cele doua orientari posibile. Obs: Un graf orientat cu proprietatea de mai sus se numeste graf turneu.

Reprezentare Intrucat traseul greierului trebuie sa treaca prin fiecare camera exact o singura data, putem spune ca un astfel de traseu este un drum elementar care trece prin toate nodurile grafului.

Greierele si furnica graful turneu

Algoritmul de rezolvare

Exemplu:Pentru graful acesta datele de intrare vor fi:2 1

n=5 01100 00100 00000

5 4

3

10000 10010 La final se va afisa: 54123

Explicatie: Memoram drumul intr-un vector de noduri Plecam, de exemplu, cu arcul (1,2) luat in sensul parcurgerii lui (pe graful de mai sus exact in aceasta ordine) In continuare, pentru fiecare dintre celelalte noduri incercam sa gasim pozitia pe care o va avea in cadrul drumului De ex: mai sus urmatorul nod este 3, de aici avem doar un singur arc de la 2 la 3; deci vom plasa 3 in drum dupa 2 pentru a respecta sensul de parcurgere; in acest moment drumul este (1,2,3); pentru 4 observam ca avem arcul (4,1) care determina plasarea lui 4 inainte de 1; in acest moment drumul este (4,1,2,3) Pentru 5 obervam c avem arcul (5,4) care va determina plasarea lui 5 inainte de 4; Dupa ce am parcurs toate nodurile drumul cautat este: (5,4,1,2,3)

Greierele si furnica -Graful turneu

Implementarea algorimului in limbajul de programare C++

Functia de citire a datelor de intrare#include #include ifstream f("asd.txt"); int a[20][20],n,v[20]; void citire () {int i,j; f>>n; for(i=1;ia[i][j]; }

Functia de generare a drumului

Functia de generare a drumuluifor(j=i;j>=p;j--) v[j+1]=v[j]; v[p]=k; i++; } }

Functia principala mainvoid main() {int i; citire(); drum(); for(i=1;i