Document, comentariu, eseu, bacalaureat, liceu si facultate
Top documenteAdmitereTesteUtileContact
      
    


 


Ultimele referate adaugate

Adauga referat - poti sa ne ajuti cu un referat?

Politica de confidentialitate



Ultimele referate descarcare de pe site
  CREDITUL IPOTECAR PENTRU INVESTITII IMOBILIARE (economie)
  Comertul cu amanuntul (economie)
  IDENTIFICAREA CRIMINALISTICA (drept)
  Mecanismul motor, Biela, organe mobile proiect (diverse)
  O scrisoare pierduta (romana)
  O scrisoare pierduta (romana)
  Ion DRUTA (romana)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  Starea civila (geografie)
 

Ultimele referate cautate in site
   domnisoara hus
   legume
    istoria unui galban
   metanol
   recapitulare
   profitul
   caract
   comentariu liric
   radiolocatia
   praslea cel voinic si merele da aur
 
despre:
 
PROBLEMA COLORARII HARTILOR
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 

Enunt: b6m12mk
Fiind data o harta nu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari de frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata.
Rezolvare:
Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5:


O solutie a acestei probleme este urmatoarea:
· tara 1 -; culoarea 1
· tara 2 -; culoarea 2
· tara 3 -; culoarea 1;
· tara 4 -; culoarea 3;
· tara 5 -; culoarea 4;
Harta este furnizata programului cu ajutorul unei matrice An,n
1, daca tara i se invecineaza cu tara j;
A(i,j) =
0 , altfel
Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar staki culoarea atasata tarii k. Stiva are inaltimea n si pe fiecare nivel ia valori intre 1 si 4.

Rezolvare PASCAL:

Program colorarea_hartilor;
Type stiva = array a1…100i of integer; var st : stiva; i, j, n, k : integer; as, ev : boolean; a: array a1..20,1..20i of integer;

procedure init(k:integer; var st:stiva); begin staki:=0; end;

procedure succesor(var as:boolean; var st:stiva; k:integer); begin if staki < 4 then begin staki:=staki+1; as:true end else as:false end;

procedure valid (var ev:boolean; st:stiva; k:integer); var i:integer; begin ev:true; for i:=1 to k-1 do if (staii=staki) and (aai,ki=1) then ev:false end;

function solutie(k:integer):integer; begin solutie:=(k=n); end;

procedure tipar; var i:integer; begin for i:= 1 to n do




writeln(’Tara =’, i,’; culoarea=’,staii);
writeln(’===================’); end;

begin
write(’Numarul de tari = ’); readln(n); for i:= 1 to n do for j:=1 to i-1 do begin
write(’aa’,i,’,’,j,’i=’); readln(aai,ji) end; k:=1; init(k,st);
while k>0 do begin repeat succesor(as,st,k); if as then valid(ev,st,k); until (not as) or (as and ev); if as then if solutie (k) then tipar else begin k:=k+1; init(k,st) end else k:=k-1 end end.


Colt dreapta
Creeaza cont
Comentarii:

Nu ai gasit ce cautai? Crezi ca ceva ne lipseste? Lasa-ti comentariul si incercam sa te ajutam.
Esti satisfacut de calitarea acestui document, eseu, cometariu? Apreciem aprecierile voastre.

Nume (obligatoriu):

Email (obligatoriu, nu va fi publicat):

Site URL (optional):


Comentariile tale: (NO HTML)


Noteaza documentul:
In prezent fisierul este notat cu: ? (media unui numar de ? de note primite).

2345678910

 
Copyright 2005 - 2024 | Trimite document | Harta site | Adauga in favorite
Colt dreapta