PE DRUMURI DE MUNTEPE DRUMURI DE MUNTE

Dragi colegi,Dragi colegi,având in vedere că se apropie ultima având in vedere că se apropie ultima vacanța de iarnă din viața de licean, vacanța de iarnă din viața de licean,

m-am gândit că ar fi frumos să m-am gândit că ar fi frumos să petrecem împreună această vacanță. petrecem împreună această vacanță. Așa căAșa că,, vă invit să vizităm cabanele vă invit să vizităm cabanele

din Munții Parâng.din Munții Parâng.

Pentru a fi operativiPentru a fi operativi,, rog pe Andrei rog pe Andrei și pe Răzvan să stabilească cabanele și pe Răzvan să stabilească cabanele

la care vom poposi în timpul la care vom poposi în timpul excursiei noastre.excursiei noastre.

Vreau să le mulțumesc colegilor Vreau să le mulțumesc colegilor Andrei și Răzvan pentru Andrei și Răzvan pentru

promptitudinepromptitudine,, și să vă anunț că și să vă anunț că au stabilit că vom sta la au stabilit că vom sta la

următoarele cabane:următoarele cabane:Mija, Căsuța din povești, Mija, Căsuța din povești, Telescaun, IEFS, Aurora, Telescaun, IEFS, Aurora,

Vărfuri semețe, Groapa seacă și Vărfuri semețe, Groapa seacă și Trei Brazi.Trei Brazi.

Pentru a stabili traseul, Andrei a Pentru a stabili traseul, Andrei a și schițat cabanele …și schițat cabanele …

IEFS GROAPA SEACĂ

CĂSUȚA DIN POVEȘTI

TREI BRAZI

VÂRFURI SEMEȚE

TELESCAUN

MIJA

AURORA

Cum ați vrea să ne deplasăm? Pe Cum ați vrea să ne deplasăm? Pe traseele montane pe care noi le traseele montane pe care noi le

cunoaștem deja, sau să vorbim cu cunoaștem deja, sau să vorbim cu tata lui Ionel să ne ducă cu mașina?tata lui Ionel să ne ducă cu mașina?Stiți că acum de când se lucrează la Stiți că acum de când se lucrează la

reabilitarea drumurilor există reabilitarea drumurilor există restricții de deplasare pe acestea, restricții de deplasare pe acestea, nu? Se circulă doar pe un singur nu? Se circulă doar pe un singur

sens.sens.

Pentru a fi mai clar în exprimare, Pentru a fi mai clar în exprimare, și pentru a lua o decizie rapidă, și pentru a lua o decizie rapidă, am evidențiat sensurile de acces am evidențiat sensurile de acces

între cabanele stabilite.între cabanele stabilite.

IEFS GROAPA SEACĂ

CĂSUȚA DIN POVEȘTI

TREI BRAZI

VÂRFURI SEMEȚE

TELESCAUN

MIJA

AURORA

Cred că ar fi bine să analizăm aceste două posibilități de Cred că ar fi bine să analizăm aceste două posibilități de deplasare cu foarte multă seriozitate și să stabilim acele deplasare cu foarte multă seriozitate și să stabilim acele modalități de deplasaremodalități de deplasare,, astfel încât timpul consumat pe astfel încât timpul consumat pe deplasări să fie minim, pentru a ne putea bucura cât mai deplasări să fie minim, pentru a ne putea bucura cât mai

mult de sportul nostru preferat…mult de sportul nostru preferat…

schiatul.schiatul.

M-am gândit să o convingem și pe M-am gândit să o convingem și pe doamna dirigintă să ne însoțească în doamna dirigintă să ne însoțească în

excursie .excursie .Dar cum să procedăm?Dar cum să procedăm?

Și ca fim mai convingători îi spunem Și ca fim mai convingători îi spunem că acestă excursie e una tematică și că acestă excursie e una tematică și

ne este de mare folos pentru ne este de mare folos pentru aplicațiile pe care tocmai le-am aplicațiile pe care tocmai le-am

studiat împreună cu dumneaistudiat împreună cu dumneaieiei la la ora de informatică…ora de informatică…

Andrei ai vreo idee?Andrei ai vreo idee?Ai dreptate; te-ai gandit foarte bine; așa Ai dreptate; te-ai gandit foarte bine; așa

vom proceda:vom proceda:1. Ioana va determina toate drumurile 1. Ioana va determina toate drumurile

posibile – pe traseele turistice, pentru că posibile – pe traseele turistice, pentru că nouă ne place și peisajul - și dintre nouă ne place și peisajul - și dintre

acestea îl vom alege pe cel mai scurt- ca acestea îl vom alege pe cel mai scurt- ca timp de deplasare;timp de deplasare;

2.Răzvan va determina traseul optim de 2.Răzvan va determina traseul optim de deplasare cu mașina astfel încât deplasare cu mașina astfel încât

consumul de combustibil să fie minim.consumul de combustibil să fie minim.

3.Ramona îi va ajuta pe colegi, 3.Ramona îi va ajuta pe colegi, punându-le la dispoziție datele punându-le la dispoziție datele legate de timpii de deplasare și legate de timpii de deplasare și

consumul de combustibili.consumul de combustibili.

Bravo Ramona! Se pare că ești Bravo Ramona! Se pare că ești nerăbdatoare să mergi în excursie, nerăbdatoare să mergi în excursie,

că ai terminat foarte repede; spune-că ai terminat foarte repede; spune-ne ce ai realizat:ne ce ai realizat:

-cunoscând legăturile şi distanţele -cunoscând legăturile şi distanţele dintre cabane, putem identifica dintre cabane, putem identifica

cabanele ca fiind nodurile unui graf, cabanele ca fiind nodurile unui graf, iar drumurile dintre cabane iar drumurile dintre cabane

muchiile/arcele grafului .muchiile/arcele grafului .

Iată cele două situaţii despre care vă vorbeam:

1 2

3

4 5

6

7

8

2

35

6

43

7

5

I

Pentru Ioana: Pentru Ioana: Matricea Matricea costurilorcosturilor corespunzătoare corespunzătoare

este:este:00 00 00 22 33 00 00 7700 00 00 55 00 00 00 6600 00 00 00 00 00 44 0022 55 00 00 00 00 00 0033 00 00 00 00 33 00 0000 00 00 00 33 00 00 5577 00 44 00 00 00 00 0000 66 00 00 00 55 00 00

1 2

3

4 5

67

8

23

7

3

5

4

56

II

Pentru RPentru Răzvan:ăzvan:Matricea Matricea costurilorcosturilor corespunzătoare corespunzătoare

esteeste00 00 00 22 33 00 00 7700 00 00 00 00 00 00 0000 00 00 00 00 00 44 0000 55 00 00 00 00 00 0000 00 00 00 00 33 00 0000 00 00 00 00 00 00 5577 00 00 00 00 00 00 0000 66 00 00 00 00 00 00

Le urez acum spor la treabă Ioanei şi lui Răzvan şi sperăm că vor găsi soluţia în cel mai scurt

timp.

Pentru că împreună suntem întotdeauna mai

operativi, ne-am gândit să găsim o soluţie care să poată fi aplicată în ambele situaţii. Şi iată ce am

reuşit să obţinem:

Trebuie să găsim o modalitate de staţionare la cabane astfel încât să

rezolvăm ceea ce ne-am propus. Astfel, pentru rezolvarea problemei am apelat la cunoştinţele învăţate la ora de informatică, şi vă pot spune

următoarele:

Pentru determinarea matricei drumurilor minime vom folosi

algoritmul lui Roy-Floyd; pentru fiecare vârf se verifică dacă prin

intermediul lui se poate obţine între două vârfuri un drum de cost mai

mic decât până la momentul respectiv . Dacă este posibil, atunci

costul minim se va actualiza şi vârful intermediar este stocat.

În final se va reconstitui traseul parcurs pentru obţinerea drumului

de cost minim. Iniţial se copiază matricea costurilor asociată grafului într-o matrice, pe care am notat-o

cu D, iar după n paşi se va determina forma ei finală. Aceasta

va conţine valorile drumurilor pentru toate perechile de noduri.

#include<stdio.h>#include<conio.h> int a[20][20], d[20][20], c[20][20],drum [20][20],i,j,n,m,k; void Floyd (void){ for (i=1;i<=n;i++) for (j=1;j<=n;j++) { d[i][j]=c[i][j];drum[i][j]=0;} for (i=1;i<=n;i++) d[i][i]=0; for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (d[i][k]+d[k][j]<d[i][j]) {d[i][j]=d[i][k]+d[k][j]; drum[i][j]=k;}}

void traseu (int i, int j){ int k= drum[i][j]; if (k!=0) { traseu (i,k); printf (“%d”,k); traseu (k,j); } }

void main(void){ int cost; FILE *f=fopen(“floyd.in”,”r”); fscanf(f,”%d %d”, &n, &m); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { a[i][j]=0; c[i][j]=10000; } for (k=1;k<=m;k++) { fscanf(f,”%d %d %d”, &i, &I, &cost); a[i][j]=1; c[i][j]=cost; } fclose(f); floyd();

for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (d[i][j]==10000) printf(“ \n Nu exista drumuri intre %d si %d “, I, j); else { clrscr(); printf( “ \n Costul minim intre %d si %d = %d \t”,i, j,d[i][j]); printf(“Traseul: “); printf(“%d”, i); traseu(i,j); printf(“%d”, j); getch(); }}

executa program

Rămâne în continuare, pe baza a ceea ce v-am arătat să stabilim

traseul şi să pornim la drum…pe drumuri de munte…