ALTE DOCUMENTE
|
|||||||||
PROBLEME DIVERSE
De multe ori suntem pusi în fata unor probleme pe care le întelegem usor dar nu stim cum sa le rezolvam cât mai simplu si elegant. Va propunem câteva metode care bine însusite pot duce, uneori, la o rapida rezolvare a problemelor dificile. Evident ca, nu toate problemele pot fi încadrate în aceste tipare propuse dar fiecare programator poate sa-si formeze un astfel de "portofoliu" de metode cu care sa poate aborda orice problema. Metodele prezentate în continuare pot constitui un început.
14.1. GENERAREA COMBINĂRILOR
Fie o multime oarecare de n elemente care poate fi pusa într-o corespondenta biunivoca cu multimea A=. Ne propunem sa determinam toate m-combinarile (m n) ale multimii A (submultimi de m elemente ale multimii A). Vom rezolva problema, nerecursiv, pornind de la m-combinarea V=(1,2,...,m) determinând succesiv toate m-combinarile ordonate lexicografic crescator.
Fie V=(v1,v2,...,vm) o m-combinare oarecare, atunci m-combinarea urmatoare în ordine lexicografica crescatoare se obtine astfel:
se determina cel mai mare indice i satisfacând relatiile:
vi<n-m+i, vi+1=n-m+i+1,..., vm-1=n-1, vm=n. (1)
se trece la vectorul urmator:
(v1,...,vi-1,vi+1,vi+2,...,vi+n-i+1);
daca nu exista un astfel de indice i (care sa satisfaca relatiile (1)) înseamna ca vectorul V contine ultima m-combinare si anume: (n-m+1,n-m+2, ...,n).
Dam în continuare o functie C care genereaza o m-combinare cu n elemente având ca parametru cod o variabila booleana care pentru valoarea 0 genereaza prima m-combinare iar pentru valoarea 1 genereaza urmatoarea m-combinare. Functia comb reîntoarce valoarea 1 daca s-a generat o m-combinare oarecare si valo 656f56g area 0 daca s-a generat ultima m-combinare (în acest caz cod are valoarea 0). Se va folosi un vector global v în care se genereaza m-combinarile.
#define dim 50
#include <stdio.h>
int v[dim+1], n, m;
// functia generatoare a m-combinarilor
int comb(cod)
int cod;
i=m+1;
// cautarea indicelui i pentru satisfacerea rela iilor (1)
do
while (v[i] >= n-m+i);
if (i)
else return (0);
void main(void)
getche();
14.2. METODA GREEDY
Se aplica problemelor în care se da o multime A continând n date (de orice natura si structura) de intrare cerându-se sa se determine o submultime B (B A) care sa îndeplineasca anumite conditii pentru a fi acceptata. Cum, în general, exista mai multe astfel de submultimi (numite solutii posibile) se mai da si un criteriu conform caruia dintre aceste submultimi sa alegem una singura (numita solutie optima) ca rezultat final. Foarte multe probleme de cautare se înscriu în acest tip.
Mentionam ca, în general, solutiile posibile au urmatoarele proprietati:
- se presupune ca este solutie posibila;
- daca B este solutie posibilati C B atunci si C este solutie posibila;
Vom da în continuare o varianta a tehnicii greedy (denumire care în traducere înseamnna lacomie, înghitire) în care se porneste de la multimea vida. Apoi se alege pe rând, într-un anumit fel, un element din A neales înca. Daca adaugarea lui la solutia partial anterior construita conduce la o solutie posibila, atunci se adauga, altfel se alege un nou element. Tot acest procedeu se repeta pentru toate elementele din A. Dam în continuare în pseudocod o procedura:
procedure GREEDY (n,A,B)
B:=
for i=1,n do
call ALEGE (A,i,x);
call POSIBIL (B,x,cod);
if cod=1 then
call ADAUG (B,x);
endif;
endfor;
return;
end procedure
Despre procedurile apelate din GREEDY precizam urmatoarele:
procedura ALEGE furnizeaza în x un element din A aj si interschimba ai cu aj; daca la fiecare pas se cerceteaza ai atunci procedura se simplifica;
procedura POSIBIL verifica daca elementul x poate fi adaugat sau nu multimii partiale construita pâna la pasul curent furnizând o valoare booleana cod cu semnificatia:
cod = 1, daca B U , este solutie posibila
cod = 0, altfel
procedura ADAUG înlocuieste pe B cu B
Obs. Procedurile de mai sus nu sunt necesare întotdeauna, acest fapt depinzând de complexitatea problemei. Oricum trebuie retinut cadrul de rezolvare al acestui tip de problema.
Problema rezolvata
Se da o multime de valori reale X=. Se cere submultimea Y X astfel ca y /y Y, sa fie maxima.
Evident ca problema este foarte simpla (în Y trebuie introduse elementele strict pozitive din X; evitam sa mai construim procedurile ALEGE, POSIBIL, ADAUG) si vom da rezolvarea ei în pseudocod:
procedure SUMA (n,X,Y,k)
integer n,X(n),Y(n),k
k:=0;
for i=1,n do
if x(i) > 0 then k:=k+1;
y(k):=x(i)
endif;
endfor;
return;
end procedure
Probleme propuse
Se dau n siruri S1,S2,...,Sn ordonate crescator, de lungimi L1,L2, ...,Ln. Sa se obtina un sir S de lungime L1+L2+...+Ln cu toate elementele celor n siruri ordonate crescator (problema de interclasare).
Indicatie: Vom interclasa succesiv câte doua siruri în final obtinând sirul ordonat crescator. Complexitatea interclasarii a doua siruri A si B de lungimi a si b depinde direct proportional de a+b (pentru ca se fac a+b deplasari de elemente). Se pune problema gasirii ordinii optime în care trebuie efectuate aceste interclasari astfel ca numarul total de deplasari sa fie minim.
Vom da un exemplu pentru a lamuri mai bine lucrurile:
fie 3 siruri de lungimi (90,40,10). Interclasam sirul S1 cu S2 apoi sirul rezultat cu S3; putem nota acest lucru formal prin (S1+S2)+S3. Se obtin (90+40) + (130+10)=270 deplasari. Daca vom interclasa sirurile în ordinea (S2+S3)+S1 vom obtine (40+10)+ (50+90)=190 de deplasari. De aici concluzia ca întotdeauna vom interclasa sirurile de lungimi minime din sirurile ramase.
Gasiti tripletele de numere pitagorice din Nn x Nn x Nn (prin Nn notat multimea ). Încercati optimizarea timpului de executie a programului.
Fie multimea m-combinarilor luate din n elemente si fie k<m un numar natural. Sa se dea un algoritm si apoi sa se scrie un program C astfel încât sa se determine o submultime de m-combinari cu proprietatea ca oricare doua m-combinari au cel mult k elemente comune.
Sa se determine multimile interior stabile (MIS) ale unui graf oarecare dat prin matricea sa de adiacenta.
14.3. METODA BACKTRACKING (CĂUTARE CU REVENIRE)
Aceasta metoda se aplica problemelor ce pot fi reprezentate sub forma unui arbore finit iar cautarea solutiei presupune parcurgerea arborelui în adâncime (DF=Depth First).
Problemele de acest tip au în general solutia de forma x=(x1, . . . ,xn) S1x . . . xSn, fiecare Sk fiind o multime finita. Mai facem câteva precizari preliminare:
a) pentru fiecare problema sunt date anumite relatii între componentele x1, . . . ,xn ale lui
x numite conditii interne;
b) produsul cartezian S=S1x...xSn se mai numeste spatiul solutiilor posibile, iar solutiile
posibile care satisfac conditiile interne se numesc solutii rezultat;
c) în general se cer doua lucruri în astfel de probleme:
- determinarea tuturor solutiilor rezultat;
- determinarea doar a acelor solutii care optimizeaza o functie obiectiv data.
Cum rezolvam astfel de probleme? Exista doua modalitati de rezolvare:
1) tehnica directa (numita si tehnica fortei brute) prin care se genereaza toate elementele spatiului de solutii posibile si apoi se verifica fiecare daca este sau nu o solutie rezultat; aceasta tehnica necesita un timp prohibitiv (daca fiecare Si are doar 2 componente complexitatea este O(2n); totodata ar fi necesara imbricarea a n cicluri cu n aprioric necunoscut).
2) backtracking care evita generarea tuturor solutiilor posibile.
Sa dam în continuare câteva repere ale rezolvarii:
solutia este construita progresiv, componenta cu componenta;
lui xk i se atribuie o valoare (evident ca numai din Sk) daca si numai daca x1, . . . ,xk-1 au deja valori;
se verifica conditiile de continuare (strâns legate de conditiile interne) daca are sens trecerea la xk+1;
daca nu are sens (adica conditiile de continuare nu sunt îndeplinite atunci facem o noua alegere pentru xk sau daca am epuizat valorile din Sk atunci k:=k-1 i se face o noua alegere pentru xk-1; s.a.m.d.
2. daca are sens atunci k:=k+1 si se testeaza daca k>n:
21) daca inegalitatea este adevarata atunci se afiseaza solutia astfel determinata
si k:=k-1 continuând procesul de la punctul 1;
22) daca inegalitatea este falsa se continua procesul de la punctul 1.
Procedura rezolvarii unor astfel de probleme este:
procedure BT(n,x)
integer n;
array x(n);
k:=1;
while k>0 do
cod:=0;
while ([mai exist o valoare α din Sk netestat] and cod=0)
x(k):=α;
if k(x(1),...,x(k)) then cod:=1;
endif;
endwhile;
if cod=0 then
k:=k-1
else
if k=n then write (x(1),...,x(n))
else k:=k+1
endif
endif;
endwhile;
return;
end procedure
Vom face câteva precizari:
1o. Predicatul k(x1, . . . , xk) reprezinta conditiile de continuare pentru x1, . . . , xk;
2o. Cod este o valoare ce indica îndeplinirea/neîndeplinirea conditiilor de continuare;
3o. Daca predicatul k(x1, . . . , xk) este adevarat " k atunci se vor afla toti vectorii din S;
4o. Backtracking poate fi usor reprezentat pe un arbore construit astfel:
- nivelul 1 contine radacina;
- din orice nod de pe nivelul k pleaca sk muchii spre nivelul k+1, etichetate cu cele
sk elemente ale lui Sk;
- nivelul n+1 va contine s1*s2*. . .* sn noduri frunza;
- pentru fiecare nod de pe nivelul n+1 etichetele muchiilor continute în drumul ce
leaga radacina de acest nod reprezinta o solutie posibila;
Daca multimile Sk reprezinta progresii aritmetice atunci algoritmul general se modifica astfel:
procedure BTA(n,a,b,h)
integer n;
array primul(n),ultimul(n),ratia(n),x(n);
k:=1;
x(1):=primul(1)-ratia(1);
while k>0 do
cod:=0;
while ( x(k)+ratia(k) ultimul(k) and cod=0 )
x(k):=x(k)+ratia(k);
if k(x(1),...,x(k)) then cod:=1 endif;
endwhile;
if cod=0 then
k:=k-1
else
if k=n then write (x(1),...,x(n))
else k:=k+1
x(k):=a(k)-h(k)
endif
endif;
endwhile;
return;
end procedure
unde:
- primul(n) reprezinta vectorul primilor termeni ai progresiilor aritmetice;
- ultimul(n) reprezinta vectorul ultimilor termeni ai progresiilor aritmetice;
- ratia(n) reprezinta vectorul ratiilor progresiilor aritmetice;
De retinut cele doua avantaje ale acestui procedeu:
evitarea imbricarii unui numar oarecare de cicluri aprioric variabil (în algoritmul propus se imbrica doar doua cicluri pretestate while);
evitarea construirii spatiului tuturor solutiilor posibile S1xS2x . . . xSn.
Problema rezolvata
În câte moduri se pot aranja 8 dame pe tabla de sah astfel încât sa nu se "bata" reciproc. Sa se foloseasca al doilea algoritm dintre cei mentionati anterior.
Prima varianta
Acest program respecta algoritmul anterior cu unele mici modificari. Facem precizarea ca vectorul x contine în componenta x[i] numarul coloanei de pe tabla de sah pe care se va afla dama de pe linia i. Tiparirea va reprezenta o permutare (din cele 8! solutii posibile). Se vor afla 92 de solutii. Lasam pe seama cititorului sa deduca analogiile si diferentele între algoritm si program.
#include <stdio.h>
#include <math.h>
void main (void)
}
}
if (cod= =0) k--;
else }
else x[++k]=0;
}
}
A doua varianta:
#include <stdio.h>
#include <math.h>
#define n 100
int x[100],cod,k,nc,nsol;
int Verifica(void)
return cod1;
void ScrieSolutie(void)
void CitesteDate(void)
void main (void)
if (cod= =0) k--;
else
}
A doua varianta este modulara, mai usor de înteles si generalizeaza problema damelor pâna la tabla de sah de 100x100. Lasam pe seama cititorului modificarea functiei ScrieSolutie pentru a afla în mod grafic tabla de sah.
Daca în functia Verifica se sterge instructiunea notat cu (*) atunci se obtin toate permutarile de n obiecte.
Probleme propuse
Sa se rezolve problema turelor de sah dupa al doilea algoritm. În câte moduri se pot aranja n turnuri pe tabla de sah astfel încât sa nu se "bata" reciproc.
Sa se afiseze pozitiile succesive ale unui cal pe tabla de sah, pornind dintr-o pozitie data, astfel încât sa fie atinse toate casutele tablei de sah.
Având un fisier cu o multime de cuvinte din limba româna de aceeasi lungime k sa se scrie un program C care afiseaza toate careurile rebusiste fara puncte negre. ( Problema e fascinanta implicând si cunostinte gramaticale dar si cunoscând faptul ca nu s-au construit careuri de 10x10 fara puncte negre manual si nici cu ajutorul calculatorului; se poate încerca apoi si cu k:=11,12, . . .).
Un intreprinzator dispune de un capital C si are n variante de investitii. Pentru fiecare investitie i cunoaste fondurile de investitie fi precum si beneficiile bi. Se cere un program care sa deduca toate variantele posibile de investitii al intreprinzatorului. Se mai dau si conditiile C ci " i
Având un graf neorientat caracterizat prin matricea costurilor sa se determine prin bactraking circuitul de cost minim pornind dintr-un vârf dat.
Având un graf neorientat caracterizat prin matricea de incidenta a vârfurilor sa se determine prin bactraking multimile interior stabile maximale.
Sa se determine toate cuvintele binare de lungime 10 care contin exact 5 cifre de 1.
Sa se determine toate cuvintele binare de lungime 10 care contin cel mult 5 cifre de 1.
Sa se determine toate cuvintele din * (multimea tuturor cuvintelor peste alfabetul Σ se noteaza cu Σ* ) de lungime 10 care contin exact 2 simboluri 'a'; 3 simboluri 'b' si 5 simboluri 'c'.
Sa se determine toate cuvintele din * de lungime n care contin exact na simboluri 'a'; nb simboluri 'b' si nc simboluri 'c' (cu conditia n=na+nb+nc).
Sa se determine toate tripletele (x1,x2,x3) de numere astfel ca:
x1+x2+x3 suma
x1*x2*x3 produs
cu valorile suma si produs date iar x1 S1, x2 S2 si x3 S3 ; S1, S2 si S3 fiind trei progresii aritmetice date deasemenea.
Sa se determine toate variantele de pronosport cu 13 rezultate din care contin exact n1 simboluri '1'; nx simboluri 'x' si n2 simboluri '2' (cu conditia n1+nx+n2=13).
Sa se determine toate variantele de pronosport cu 13 rezultate din care contin cel mult n1 simboluri '1'; cel mult nx simboluri 'x' si simboluri '2' în rest (cu conditia n1+nx
14.4. METODA DIVIDE ET IMPERA (DIVIDE sI STĂPÂNEsTE)
Aceasta modalitate de elaborare a programelor consta în împartirea repetata a unei probleme de dimensiune mai mare în doua sau mai multe subprobleme de acelasi tip urmata de combinarea solutiilor subproblemelor rezolvate pentru a obtine solutia problemei initiale.
Se da un vector A=(a1,...,an) si trebuie efectuata o prelucrare oarecare asupra elementelor sale.
Presupunem ca:
" p,q cu 1 p < q m a.î. prelucrarea secventei se poate face prelucrând subsecventele:
si si apoi combinând rezultatele pentru a obtine prelucrarea întregii secvente .
Daca se reuseste o astfel de formalizare a problemei atunci ea poate fi rezolvata cu ajutorul acestei metode.
Vom da în continuare o procedura recursiva în pseudocod:
procedure DI (p,q,α)
if q-p eps then
call PREL (p,q,α)
else
call IMPARTE (p,q,m) ;
call DI (p,m,β);
call DI (m+1,q,γ);
call COMB (β,γ,α);
endif;
return;
end procedure
Câteva precizari se impun:
procedura trebuie apelata prin call DI (1,n,α) în α obtinându-se rezultatul final;
eps este lungimea maxim a unei secvene notata prin (p,q) pentru care se face prelucrarea directa fara a mai fi necesara împartirea în subprobleme;
procedura PREL realizeaza prelucrarea directa a secventelor (p,q);
procedura COMB realizeaza combinarea rezultatelor β si γ ale prelucrarii a doua secvente vecine (p,m) si (m+1,q) obtinând rezultatul α al prelucrarii întregii secvente (p,q);
prin procedura IMPARTE se obtine valoarea lui m.
Vom da ca exemplu problema sortarii crescatoare a unui sir de întregi prin interclasare.
deoarece secventele (i,i+1) sunt usor de ordonat acestea vor constitui secventele ce se vor prelucra, deci eps = 1;
- m se va calcula ca (p+q)/2, deci nu mai e nevoie de procedura speciala IMPARTE;
procedura COMB va interclasa întotdeauna doua secvente (p,m) si (m+1,q) ordonate crescator;
vom folosi un vector x drept structura globala si vom face toate prelucrarile pe elementele sale nemaiavând nevoie de zonele α,β;
pentru zona γ vom folosi un vector local y în procedura COMB acesta continând elementele corespondente din x dar ordonate crescator; tot în procedura COMB se vor copia apoi elementele lui y din portiunea (p,q) în x;
evident ca procedurile din schema generala a algoritmului sunt functii C cititorul facând analogiile necesare.
#include <stdio.h>
#include <conio.h>
#define nrelem 100
int x[nrelem];
int n;
void PREL (int p, int q)
void COMB (int inf, int mijloc, int sup)
for(l=i; l<=mijloc; y[k++]=x[l++]);
for(l=j; l<=sup; y[k++]=x[l++]);
for(k=inf; k<=sup; x[k++]=y[k]);
void DI (int p, int q)
return;
void main(void)
DI (1,n);
printf("\nsirul sortat crescator este:\n");
for (i=1; i<=n; i++) printf("x[%d]=%d\n",i,x[i]);
getch();
14.5. METODA PROGRAMĂRII DINAMICE
Aceasta metoda este aplicabila problemelor de optim în care solutia poate fi privita ca rezultatul unui sir de decizii d1, . . . ,dn. Fiecare decizie depinde de deciziile deja luate si nu este unic determinata (spre deosebire de tehnica greedy unde fiecare decizie care se ia trebuie sa fie unica). Totodata este necesar sa fie satisfacuta una din variantele principiului optimalitatii pentru a putea fi aplicata aceasta metoda.
Vom formaliza acest principiu al optimalitatii:
fie d1,...,dn un sir optim de decizii (SOD) care transforma starea so în starea sn, trecând prin starile intermediare s1, . . . ,sn-1; vom nota acest fapt prin (d1,dn) este SOD pentru perechea de stari (so,sn);
grafic procesul este descris ca în figura urmatoare:
d1 d2 dn
*----->*---->*------>* . . . *------>*
so s1 s2 sn-1 sn
Vom da acum mai multe variante ale principiului optimalitatii:
daca (d1,dn) este SOD pentru (so,sn) atunci (d2,dn) este SOD pentru (s1,sn);
2) daca (d1,dn) este SOD pentru (so,sn) atunci " i din avem
a) (d1,di) este SOD pentru (so,si) SAU
b) (di+1,dn) este SOD pentru (si,sn).
3) daca (d1,dn) este SOD pentru (so,sn) atunci " i din avem
a) (d1,di) este SOD pentru (so,si) sI
b) (di+1,dn) este SOD pentru (si,sn).
Ultima varianta este cea mai generala si mai completa. Odata verificat o forma a principiului optimalitatii, metoda programarii dinamice consta în a scrie relatiile de recurenta si apoi de a le rezolva. În general relatiile de recurenta sunt de 2 tipuri :
fiecare decizie di depinde de di+1,...,dn - relatii de recurenta înainte, deciziile vor fi luate în ordinea dn, dn-1, . . . ,d1;
fiecare decizie di depinde de d1, . . . ,di-1 - relatii de recurenta înapoi, deciziile vor fi luate în ordinea d1, d2, . . . , dn.
Problema rezolvata
Fie G=(X,Γ) un 1-graf orientat caruia îi atasam matricea costurilor, (fiecare arc (i,j) Γ este etichetat cu o valoare reala strict pozitiva). Se pune problema gasirii drumului de valoare minim (DVM) între oricare 2 vârfuri i si j.
Rezolvare
Verificam prima varianta a principiului optimalitatii:
- fie i, i1, i2, . . . , im, j DVM între i si j atunci evident ca i1, . . . , im, j este DVM între i1 si
j;
- notam prin L(i,k) lungimea DVM dintre i si k, " k X;
- notam deasemenea dkj valoarea arcului (k,j);
- ecuatiile de recurenta sunt:
L(i,j) = min
(k,j)
#include<stdio.h>
#include<values.h>
#define nn 10
int d[nn+1][nn+1],i,j,n;
int L(int i,int j)
return m;
}
void citestematrice(void)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if (d[i][j]= = -1) d[i][j]=MAXINT;
void citeste(void)
void afiseaza(int val)
void main(void)
Probleme propuse
Se da o matrice A=(aij), i=1,...,n; j=1,...,m cu elementele din multimea . Doua elemente din A aij si akl se numesc 4-vecine daca i-k j-l
Notam cu So, S1 si S2 submultimile formate din elementele matricii egale cu 0, 1 respectiv 2. Submultimea S1 se împarte în grupuri astfel: aij si akl fac parte din acelasi grup daca sunt 4-vecine sau daca apq S1 : aij si apq sunt 4-vecine iar apk si akl sunt din acelasi grup. Un element akl So îl vom numi spion al grupului G S1 dac aij G a.î. akl si aij s fie vecine. Un spion este perfect dac are toti vecinii din G.
Se cere:
a) cel mai numeros grup ( S1) care are un singur spion (daca exista).
b) toate grupurile care au cel putin doi spioni perfecti.
Se da o matrice cu elemente care au valori din , care reprezinta un teren cu drumuri si obstacole . În acest teren se afla un tanc si o tinta. Acest tanc poate primi comenzi pentru rotirea tevii (cu 90o în ambele sensuri), pentru deplasare (în directia tevii cu o linie sau cu o coloana) sau pentru tragere (în directia tevii pentru a nimeri tinta) în cazul în care între tanc si tinta nu exista nici un obstacol. Considerând ca deplasarea nu se poate efectua prin obstacole, se cere cel mai scurt drum necesar tancului pentru a putea distruge tinta si sirul comenzilor efectuate în cazul în care exist un astfel de drum.
Se d o matrice cu elemente din , reprezentând o padure cu capcane (0) si carari (1). În aceasta padure se afla o vulpe (2) si mai multi lupi (3). Fiecare lup încearca sa se apropie de vulpe fara a sti unde se afla capcanele, iar în cazul în care cade într-o capcana, moare. Vulpea încearca sa se îndeparteze de cel mai apropiat lup, având însa posibilitatea sa descopere si capcanele si sa le ocoleasca. Atât vulpea cât si lupii îi pot modifica pozitia doar cu o linie sau cu o coloana în fiecare moment. Sa se spuna daca vulpea reuseste sa scape de lupi.
Se considera un teren dreptunghiular sub forma unei matrici A de m linii si n coloane. Elementele aij ale matricii contin cotele (înaltimile) diferitelor portiuni astfel obtinute. Se presupune ca o bila se gaseste pe o portiune (io,jo) având cota a(io,jo).
Se cere un program care sa precizeze toate traseele (începând cu (io,jo) ) posibile pe care le poate urma bila spre a iesi din teren, stiind ca bila se poate deplasa în orice portiune de teren 4-învecinat cu o cota strict inferioara cotei terenului pe care se gaseste bila.
Se cere un program care rezolva problema labirintului (nerecursiv).
O matrice de m linii si n coloane reprezinta un labirint daca:
a(i,j) = o - semnificând culoar;
a(i,j) = 1 - semnificând zid.
Un traseu de iesire pornind de la o portiune (io,jo) trebuie sa fie o succesiune de perechi (io, jo), (i1, j1) . . . (ik, jk) astfel încât 2 perechi învecinate sa fie 4-vecine si a(ip,jp)=0
" p=0, . . . ,k.
ANEXĂ
UN MEMENTO AL SINTAXEI LIMBAJULUI C
SINTAXA LIMBAJULUI C
În descrierea sintaxei limbajului vom folosi urmatoarele notatii:
a) ::= cu semnificatia "prin definitie este";
b) pentru a separa alternativele unei definitii sintactice;
c) < > pentru definirea unor metavariabile;
d) [ ] pentru delimitarea elementelor optionale;
e) .. pentru a indica elementele care se pot repeta.
Exemplu: Pentru a defini un "întreg_zecimal" ca o succesiune de cifre semnificative vom scrie:
<Întreg_zecimal> ::= <Cifra_nenula> [<Cifra>] ..
A. Atomi lexicali
<Cuvinte_cheie> ::= auto break case char const continue default do double|
else enum extern float for goto if int|long register |
return short signed sizeof static|struct switch typedef
union unsigned void volatile while
<Nume> ::= <Litera>[<Litera> <Cifra>] ..
<Litera> ::= a b c d e f g h i j k l m n o p q r s t u v w x y z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z
<Cifra> ::= 0
<Constanta> ::= <Constanta_întreaga> <Constanta_reala>
<Constanta_enumerare> <Constanta_caracter>
<Constanta_întreaga> ::= <Numar_întreg>[<Sufix_întreg>
<Numar_întreg> ::= <Întreg_zecimal> <Întreg_hexazecimal> <Întreg_octal>
<Întreg_zecimal> ::= <Cifra_nenula>[<Cifra>] ..
<Cifra_nenula> ::= 1
<Întreg_hexazecimal> ::= 0x<Cifra_hexa> ..
<Cifra_hexa> ::= <Cifra> a b c d e f A B C D E F
<Întreg_octal> ::= 0[<Cifra_octala>] ..
<Cifra_octal_> ::= 0
<Sufix_întreg> ::= <Sufix_unsigned>[<Sufix_long>] <Sufix_long>[<Sufix_unsigned>]
<Sufix_unsigned> ::= U u
<Sufix_long> ::= L l
<Constanta_reala> ::= <Constanta_fract>[<Exponent>][<Sufix_real>]
<Cifra> .. <Exponent>[<Sufix_real>]
<Constanta_fract> ::= [<Cifra>] .. . <Cifra>.. <Cifra>.. .
<Exponent> ::= E e <Cifra> ..
<Sufix_real> ::= F f L l
<Constanta_enumerare> ::= <Nume>
<Constanta_caracter> ::= '<Caracter_C> ..' L'<Caracter_C>'
<Caracter_C> ::= <Orice_caracter_tiparibil_cu exceptia: ' i \>
<Secventa_escape>
<Secventa_escape> ::= \" \a \b \f \n \r \t \v
\<Cifra_octala>[<Cifra_octala>[<Cifra_octala>]] \x<Cifra_hexa> ..
<sir_de_caractere> ::= "[<Caracter_S> ..]"
<Caracter_S> ::= <Orice_caracter_tiparibil_cu exceptia: ' si \> <Secventa_escape>
<Operatori_si_semne_de_punctuatie >::= + & ->
/= &= << >> <<= >>= <=
>= < > &&
B. Declaratii
<Unitate_de_compilare> ::= <O_declaratie> ..
<O_declaratie> ::= <Def_functie> <Declaratie>;
<Declaratie> ::= [<Specificatori>][<Lista_declaratori>]
<Specificatori> ::= <Specificator> ..
<Specificator> ::= <Clasa_memorare> <Tip> typedef
<Clasa_memorare> ::= auto register static extern
<Tip> ::= <Tip_simplu> <Nume_typedef> <Calificator>
<Descriere_tip_enumerare> <Descriere_tip_neomogen>
<Tip_simplu> ::= char short int long signed unsigned float double void
<Nume_typedef> ::= <Nume>
<Descriere_tip_enumerare> ::= enum<Nume> enum[<Nume>]
<Lista_enum> ::= <Enumerator>[,<Enumerator>] ..
<Enumerator> ::= <Nume>[=<Expr_constant_>
<Tip_neomogen> ::= struct union
<Lista_câmpuri> ::= <Decl_câmpuri>;[<Decl_câmpuri>;] ..
<Decl_câmpuri> ::= [<Specificatori>][<Câmp>[,<Câmp>] ..]
<Câmp> ::= <Declarator> [<Nume>]:<Expr_constanta>
<Lista_declaratori> ::= <Decl_init>[,<Decl_init>] ..
<Decl_init> ::= <Declarator>[<Ini ializare>]
<Declarator> ::= [<Indirect>..]<Denumire>[<Decl_F_T>]
<Indirect> ::= *[<Calificator> ..]
<Denumire> ::= <Nume> (<Declarator>)
<Decl_F_T> ::= ([<L_declar_par>]) <Decl_tablou> ..
<Decl_tablou> ::= [] [<Expr_constanta>]
<L_declar_par> ::= <Decl_par>[,<Decl_par>] .. [, ..]
<Decl_par> ::= <Tip>..<Declarator> <Decl_tip>
<Decl_tip> ::= <Tip>..[<Indirect>..][(<Decl_tip>)][<Decl_F_T>]
<Initializare> ::= =<Expr>
<Lista_init>::=<Expr>[,<Lista_init> .. [,<Lista_init>] ..
<Def_functie> ::= [<Specif_functie> ..]<Declarator>[<Declaratie>;] .. <Bloc>
<Specif_functie> ::= extern static <Tip>
C. Expresii
<Expr> ::= <Expresie>[,<Expresie>] ..
<Expresie> ::= <Expr_conditionala>|<Expr_unara><Oper_atribuire><Expresie>
<Oper_atribuire> ::= + <<= >>= &=
<Expr_conditionala> ::= <Expr_SAU_logic>
<Expr_SAU_logic> ? <Expr> : <Expr_condi ionala>
<Expr_SAU_logic> ::= <Expr_sI_logic> <Expr_SAU_logic> !! <Expr_sI_logic>
<Expr_sI_logic> ::= <Expr_SAU> <Expr_sI_logic> && <Expr_SAU>
<Expr_SAU> ::= <Expr_SAU_exclusiv> <Expr_SAU><Expr_SAU_exclusiv>
<Expr_SAU_exclusiv> ::= <Expr_sI> <Expr_SAU_exclusiv> ^ <Expr_sI>
<Expr_sI> ::= <Expr_egalitate> <Expr_sI> & <Expr_egalitate>
<Expr_egalitate> ::= <Expr_rela ionala> <Expr_egalitate>==Expr_relationala>
<Expr_egalitate> != <Expr_relationala>
<Expr_relationala> ::= <Expr_deplasare> <Expr_relationala> < <Expr_deplasare>
<Expr_relationala> > <Expr_deplasare>
<Expr_relationala> <= <Expr_deplasare>
<Expr_relationala> >= <Expr_deplasare>
<Expr_deplasare> ::= <Expr_aditiva> <Expr_deplasare> << <Expr_aditiva>
<Expr_deplasare> >> <Expr_aditiva>
<Expr_aditiva> ::= <Expr_multiplicativa> <Expr_aditiva> + <Expr_multiplicativa>
<Expr_aditiva> - <Expr_multiplicativa>
<Expr_multiplicativa>::= <Expr_multiplicativa> * <Expr_prefixata>
<Expr_multiplicativa> / <Expr_prefixata>
<Expr_multiplicativa> % <Expr_prefixata>
<Expr_prefixata> ::= <Expr_unara> (<Decl_tip>)<Expr_prefixata>
<Expr_unara> ::= <Expr_postfixata> <Op_unar><Expr_prefixata>
++<Expr_unara> --<Expr_unara> sizeof<Expr_unara>
sizeof(<Decl_tip>)
<Op_unar> ::= &
<Expr_postfixata> ::= <Termen> <Expr_postfixata>[<Expr>]
<Expr_postfixata>(<Lista_Expresii>) <Expr_postfixata> . <Nume>
<Expr_postfixata> -> <Nume> <Expr_postfixata> ++ <Expr_postfixata>--
<Termen> ::= <Nume> <Constanta> <sir_de_caractere> (<Expr>)
<Lista_Expresii> ::= [<Expr>] ..
<Expr_constanta> ::= <Expr_conditionala>
D. Instructiuni
<Instr>::= <Instr_etichetata> <Instr_compusa> <Instr_expresie> Instr_de_selectie>
<Instr_de_ciclare> <Instr_de_salt>
<Instr_etichetata> ::= <Nume>:<Instr> case <Expr_constanta
<Instr_expresie> ::= [<Expr>];
<Instr_de_selectie> ::= if (<Expr>) <Instr> if (<Expr>) <Instr> else <Instr>
switch (<Expr>) <Instr>
<Instr_de_ciclare> ::= while (<Expr>)<Instr>;
do <Instr> while (<Expr>);
for ( [<Expr>];[<Expr>];[<Expr>] ) [<Instr>];
<Instr_de_salt> ::= goto <Nume>; continue; break; return [<Expr>];
|
