Date post: | 09-Oct-2015 |
Category: |
Documents |
Upload: | lungupavel |
View: | 177 times |
Download: | 7 times |
of 77
5/19/2018 Probleme Rezolvate - 2005 - Pascal
1/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
2005BACKTRACKING
ATESTAT - 2005 - 1 - Se citesc de la tastatur dou numere naturale ni k(0 < k < n < 12). S safieze toate irurile formate din k literedistincte, litere alese dintre primele n ale alfabetuluenglez. Exemplu: pentru k = 2 i n = 4, se afieaz, nu neaprat n aceast ordine, irurile: AB, BAAC, CA, AD, DA, BC, CB, BD, DB, CD, DC.
Rezolvare:Aplicm algoritmul BACKTRACKINGpentru generarea aranjamentelor.
program ATESTAT_2005_1_ARANJAMENTE_1;
uses CRT;CONST Kmax = 20; { nr . max al el ement el or di n A } Nmax = 50; { nr . max al el ement el or di n B sau nr . val or i l or f unct i ei }
TYPE f unct i e = arr ay [ 1. . Kmax ] of 0. . Nmax;VAR k, poz, i : 1 . . Kmax; { se consi dera k = 1 ) AND ( k = k ) AND ( n >= 1 ) AND ( n 0 do { cat t i mp st i va nu este vi da } begi n while f [poz] < n do { cat t i mp nu s- au epui zat t oat e } { el ement el e di n B } begi n f [ poz] : = f [ poz] + 1; {INSERARE} i f not ( f [ poz] I N I MAG ) t hen begi n i f poz = k t hen { daca stiva este plina } begi n f or i : = 1 t o k do
5/19/2018 Probleme Rezolvate - 2005 - Pascal
2/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
4
begi n {t i pari r e SOLUTI E} wr i t e ( CHR (64 + f[i] ) , ' ' ) ; end; r eadl n; end el se begi n I MAG : = I MAG + [ f [ poz] ] ; poz := poz + 1 ; {pas INAINTE} f [ poz] : = 0 {r ei ni t i al i zar e el ement } end; end; { sf . I F NOT } end; { sf . WHI LE i nt er i or } poz := poz - 1; {pas INAPOI} I MAG : = I MAG - [ f [ poz] ] ; end; { sf . WHI LE exter i or } r eadl nEND.
ATESTAT - 2005 - 2 - Civa copii cu vrste ntre 2 si 7 ani trebuie s fie vizitai de Mo Crciun.Scriei un program care determin toate modurile diferiten care pot ei s fie aezai n lista lui MoCrciun, astfel nct s fie vizitai toi copiiii vizitele s se fac n ordinea cresctoarea vrsteilor. Se citesc de la tastatur: n = numrul de copii (0 < n < 10), apoi numele i vrsta fiecruia dintrecei n copii. Se scriu, pe linii diferite, liste cu numele copiilor, n ordinea n care vor fi vizitai de MoCrciun. O list este format din toate cele n nume ale copiilor, ntr-o anumit ordine, oricare dounume succesive fiind desprite prin spaii.Exemplu:Pentru datele de intrare: n = 4, Dan 6, Cristina 4, Corina 2, Iulia 4se scriu urmtoarele soluii:
Corina Iulia Cristina DanCorina Cristina Iulia Dan
Rezolvare:Definim o procedur ORDONEAZ,pentru ordonarea numelor copiilor.
program ATESTAT_2005_2_MOS_CRACIUN_SI_COPIII;
uses crt ;const nmax = 100;t ype vect or = arr ay [ 1. . nmax] of i nt eger; vect or_nume = arr ay [ 1. . nmax] of st r i ng; vect or _vi r st a = ar r ay [ 1. . nmax] of i nt eger ;var f : vector ; sol , n, i : i nt eger ;
i ncep, sf : i nt eger; NUME : vect or _nume; VI RSTA : vect or _vi r st a; EGAL : bool ean; t : i nt eger ; k : i nteger ; {cont or care numara el ement el e veci ne egal e i n vect orul VI RSTA } pozi t i e : i nt eger ; {pozi t i a i ncepi nd de l a car e apar el ement e egal e} {i n vect or ul VI RSTA}
5/19/2018 Probleme Rezolvate - 2005 - Pascal
3/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
5
procedure ORDONEAZA ( VAR v1: vect or _vi r st a; VAR v2 : vect or_nume; q: i nt eger ) ; var k1, j , aux: i nt eger ; s i raux : str i ng; begi n r epeat k1: = 0; j : = 1; r epeat i f v1[ j ] > v1 [ j +1] t hen begi n aux : = v1 [ j ] ; v1 [ j ] : = v1 [ j +1] ; v1 [ j +1] : = aux;
siraux : = v2 [ j ] ; v2 [ j ] : = v2 [ j +1] ; v2 [ j +1] : = siraux;
k1 : = 1 end; j : = j + 1 unt i l ( j > q- 1) unt i l ( k1 = 0) ;
end;procedur eVERIFICA ( pozi t i a : i nt eger ; f : vect or ; VAR CONTI N : bool ean ) ; LABEL 10; VAR j : i nteger ; begi n CONTI N : = TRUE; f or j : = 1 t o pozi t i a - 1 do begi n i f f [ j ] = f [pozi t i a] then begi n CONTI N : = FALSE; GOTO 10 end; end;10: end;procedur e SCRIE ; var j : i nteger ; begi n sol : = sol + 1; wr i t e ( ' Sol ut i a nr . ' , sol , ' ' ) ; f or t : = 1 t o i ncep - 1 do begi n wri t e ( NUME [ t ] , ' ' ) ;
end; f or j : = 1 t o sf - i ncep + 1 do begi n wr i t e ( NUME [ f [ j ] + i ncep - 1 ] , ' ' ) end; f or t : = sf + 1 t o n do begi n wri t e ( NUME [ t ] , ' ' ) ; end; wri t el n; r eadl n; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
4/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
6
procedur e PERMUTA ( i ncep, s f : i nt eger ) ; LABEL 20; var m : i nt eger ; poz : i nt eger ; CONTI N : bool ean;
begi n
m : = sf - i ncep + 1;
poz : = 1; f [ poz] : = 0; whi l e poz > 0 do begi n CONTI N : = FALSE; whi l e f [ poz] < m do begi n f [ poz] : = f [ poz] + 1; VERIFICA (poz, f, CONTIN); i f CONTI N = TRUE t hen GOTO 20 end;
20: i f ( CONTI N = TRUE ) AND ( poz = m) t hen SCRI E; i f ( CONTI N = TRUE ) and ( poz < m) t hen begi n poz : = poz + 1; f [ poz] : = 0; end; i f CONTI N = FALSE t hen poz : = poz - 1 end; {sf . WHI LE exter i or } end;
Begin { PROGRAM PRINCIPAL }
cl r scr ;
sol : = 0;
wr i t e ( ' Dat i numar ul de copi i , n = ' ) ; r eadl n ( n) ; wr i t el n; wr i t el n;
f or i : = 1 t o n do begi n wr i t e ( ' Dat i NUMELE copi l ul ui ' , i , ' nume = ' ) ; r eadl n ( nume [ i ] ) ; wr i t e ( ' Dat i VI RSTA copi l ul ui ' , i , ' vi rst a = ' ) ;
readl n ( vi r s ta [ i ] ) ; wr i t el n; wr i t el n ( ' *****************************************' ) ; wr i t el n end; ORDONEAZA (virsta, nume, n);
wr i t el n; wr i t el n ( ' Apasat i ENTER pent r u ur mat oar ea sol ut i e' ) ; r eadl n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
5/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
7
i : = 1; whi l e i < n do begi n EGAL : = FALSE; k : = 0; whi l e ( VI RSTA [ i ] = VI RSTA [ i +1] ) AND ( i < n ) do begi n EGAL : = TRUE; k : = k + 1; i : = i + 1 end; i f EGAL = TRUE t hen begi n k : = k + 1; pozitie := i - k + 1; i ncep : = pozi t i e; sf := pozitie + k - 1;
PERMUTA (incep, sf);
end; i : = i + 1 end; wri t el n;
i f sol = 0 t hen wr i t el n ( ' Nu exi sta sol ut i e' ) ; r eadl nEND.
ATESTAT - 2005 - 3 - Se citesc de la tastatur numerele naturale n i k (0 < n
5/19/2018 Probleme Rezolvate - 2005 - Pascal
6/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
8
procedur e SCRIE; begi n f or i : = 1 t o k - 1 do begi n wr i te (w [ f [ i ] ] ) ; end; wr i t e ( w [ f [ k] ] ) ; wri t el n; end;
f unct i onNRCIFRE ( x : i nt eger) : i nt eger ; begi n i f x = 0 t hen nrci f : = 1 el se begi n nr ci f : = 0; whi l e x 0 do begi n nr ci f : = nr ci f + 1; x : = x DI V 10 end; end; NRCI FRE : = nrci f
end;
procedur e ORDONEAZA ( var v: vector; q: i nt eger ) ; var k, j , aux: i nt eger; begi n r epeat k: = 0; j : = 1; r epeat i f v[ j ] > v [ j +1] t hen begi n aux : = v[j ] ; v[ j ] : = v[ j +1] ; v[ j +1] : = aux; k : = 1 end; j : = j + 1 unt i l ( j > q- 1) unt i l ( k = 0) ; end;
Begin { PROGRAM PRINCIPAL }
CLRSCR; wr i t e ( ' Dat i numar ul n ( de ex. n = 215) , n = ' ) ; r eadl n ( n) ; nrcif := NRCIFRE (n);
STR (n, sir); f or i : = 1 t o nrci f do begi n VAL (sir [i], a, er); w [ i ] : = a; end; ORDONEAZA (w, nrcif);
wr i t el n ( ' Pr eci zat i ci t e ci f r e vor avea numer el e gener at e, de ex. k = 2' ) ; wri t e ( ' Dat i k = ' ) ; r eadl n ( k); wr i t el n ( ' Apasat i ENTER pent r u af i sar ea ur mat oar ei sol ut i i ' ) ; r eadl n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
7/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
9
x : = 1; f [ x] : = 0; whi l e x > 0 do begi n i f f [ x] < nrc i f t hen begi n f [ x] : = f [ x] + 1; i f x = k t hen begi n SCRI E; r eadl n; end el se begi n x := x + 1; {PAS INAINTE}
f [ x] : = 0 end end el se x := x 1 {PAS INAPOI}
end; r eadl nEND.
ATESTAT - 2005 - 4 - S se genereze toate irurilede n(n < 6, numr natural dat de la tastaturnote muzicaledin mulimea {do, re, mi, fa, sol, la, si}. Orice not poate s nu apar sau se poatrepeta n cadrul unui ir. Fiecare ir va fi afiat pe cte o linie, n cadrul liniei, notele fiind separatprin cte un spaiu.
Exemplu: pentru n = 5, unul dintre irurile generate este:mi do do si mi
Rezolvare:
program ATESTAT_2005_4_Produs_cartezian;
uses CRT;t ype vector = ar r ay [ 1. . 20] of i nt eger ;var p, i , x, n : i nt eger ; f : vector; not a : arr ay [ 1. . 7] of str i ng;procedur e SCRIE; begi n wr i te ( ' { ' ) ; f or i : = 1 t o n - 1 do
begi n wr i t e ( not a [ f [ i ] ] , ' , ' ) ; end; wr i te ( nota [ f [n] ] , ' ' ) ; wr i te ( ' } ' ) ; wri t el n; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
8/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
10
Begin { PROGRAM PRINCIPAL }
CLRSCR; wr i t el n ( ' Pr eci zat i ci t e not e t r ebui e sa cont i na si r ul , de exempl u n = 6' ) ; wri t e ( ' Dat i n = ' ) ; r eadl n ( n) ;
p : = 7; {numar ul t ot al de not e: do, r e, . . . si }
wri t el n; wr i t el n ( ' Apasat i ENTER dupa f i ecar e sol ut i e' ) ; r eadl n;
not a [ 1] : = ' do' ; not a [ 2] : = ' r e' ; not a [ 3] : = ' mi ' ; not a [ 4] : = ' f a' ; not a [ 5] : = ' sol ' ; not a [ 6] : = ' l a' ; not a [ 7] : = ' s i ' ;
x : = 1; f [ x] : = 0; whi l e x > 0 do begi n
i f f [ x] < p t hen begi n f [ x] : = f [ x] + 1; i f x = n t hen begi n SCRIE;
r eadl n; end el se begi n x := x + 1; {PAS INAINTE} f [ x] : = 0 end end el se x := x 1 {PAS INAPOI} end; r eadl nEND.
ATESTAT - 2005 - 5 - S se genereze toate cuvintele de lungime n(n < 10) ale alfabeltului Morse(formate doar din caracterele '-' i '.'), care nu ncep i nu se termin cu caracterul '-'. Fiecare cuvnt
va fi afiat pe cte o linie.Rezolvare:
Vom genera produsul cartezian M x M x M ...x M, de n ori, n care mulimea M este format
doar din caracterele . i -. Asociem: cifrei 1, caracterul "-" cu codul ASCII 45
i cifrei 2, caracterul "." cu codul ASCII 46.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
9/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
11
program ATESTAT_2005_5_Codul_Morse_produs_cartezian;uses CRT;t ype vector = ar r ay [ 1. . 20] of i nt eger ;var p, i , x, n : i nt eger ; m, f : vector ;
procedure SCRIE;
begi n f or i : = 1 t o n do
wr i t e ( CHR (44 + f[i] ) , ' ' ) ; wri t el n; end;Begin { PROGRAM PRINCIPAL }
CLRSCR; wr i t el n ( ' Pr eci zat i de ci t e or i t r ebui e i nmul t i t a mul t i mea M cu ea i nsasi ' ) ; wri t e ( ' Dat i n = ' ) ; readl n ( n) ;
wr i t el n ( ' Mul t i mea M ar e doar p = 2 el ement e: . si - ' ) ; p : = 2; wr i t el n; wr i t el n ( ' Apasat i ENTER dupa f i ecar e sol ut i e' ) ; r eadl n; x : = 1; f [ x] : = 0; whi l e x > 0 do
begi n i f f [ x] < p t hen begi n f [ x] : = f [ x] + 1; i f x = n t hen begi n i f NOT ( f [ 1] = 1 ) AND NOT ( f [ n] = 1 ) t hen begi n SCRIE; r eadl n; end; end el se begi n x := x + 1; {PAS INAINTE} f [ x] : = 0 end end el se x := x 1 {PAS INAPOI} end; r eadl nEND.
ATESTAT - 2005 - 6 - Se citete un cuvnt format din maxim 20 de litere distincte. S se afieztoate anagramelecuvntului respectiv. Un cuvnt A este anagramaunui cuvnt C dac Aeste format din aceleai litere ca i cuvntul C, dar aezaten alt ordine.Exemplu: Pentru cuvntul "car", trebuie afiate, nu neaprat n aceast ordine, anagramele:
car -> cra, acr, arc, rca, rac.Rezolvare:
5/19/2018 Probleme Rezolvate - 2005 - Pascal
10/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
12
program ATESTAT_2005_6_PERMUTARI_ITERATIV;uses crt ;const nmax = 100;t ype vect or = arr ay [ 1. . nmax] of i nt eger;var f : vector ; s i r : st r i ng; l ungi me_si r : i nt eger ; sol , n, i : i nt eger ;
procedure VERIFICA ( k : i nt eger ; f : vect or ; VAR CONTI N : bool ean ) ; LABEL 10; begi n CONTI N : = TRUE; f or i : = 1 t o k - 1 do begi n i f f [ i ] = f [ k ] then begi n CONTI N : = FALSE; GOTO 10 end; end;
10: end;procedure SCRIE ;
begi n sol : = sol + 1; wr i t e ( ' Sol ut i a nr . ' , sol , ' ' ) ; f or i : = 1 t o n do
wr i t e ( si r [ f [ i ] ] ) r eadl n; wr i t el n {opt i onal e} end;
procedure PERMUTA ( m : integer );
LABEL 20; var k : i nt eger ; CONTI N : bool ean; begi n k : = 1; f [ k] : = 0; whi l e k > 0 do begi n CONTI N : = FALSE; whi l e f [ k] < m do begi n f [ k] : = f [ k] + 1; VERIFICA (k, f, CONTIN); i f CONTI N = TRUE t hen GOTO 20
end;20: i f ( CONTI N = TRUE ) AND ( k = n) t hen SCRIE; i f ( CONTI N = TRUE ) and ( k < n) t hen begi n k : = k + 1; {PAS INAINTE} f [ k] : = 0 end; i f CONTI N = FALSE t hen k : = k 1 {PAS INAPOI} end; {sf . WHI LE exter i or } end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
11/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
13
Begin { PROGRAM PRINCIPAL }
cl r scr ;
sol : = 0;
wri t el n;
wr i t e ( ' Dat i si r ul car e se va per mut a, si r = ' ) ; readl n ( s i r ) ; wri t el n; wri t el n; wri t el n; wr i t el n ( ' Apasat i ENTER dupa f i ecar e sol ut i e af i sat a' ) ; wri t el n;
l ungi me_si r : = LENGTH ( si r ) ;
n : = l ungi me_si r ;
wri t el n; wri t el n;
PERMUTA (n);
i f sol = 0 t hen wr i t el n ( ' Nu exi sta sol ut i e' ) ; r eadl nEND.
ATESTAT - 2005 - 7 - Se citete din fiierul standard de intrare un numr natural n aparinnd Ni o mulime Mcu pelemente numere ntregi. S se determine i s se scrie elementele produsulucartezian M x M x...x M(de n ori).
Rezolvare:program ATESTAT_2005_7_produs_cartezian;uses CRT;t ype vector = ar r ay [ 1. . 20] of i nt eger ;var p, i , x, n : i nt eger ; m, f : vector ;
procedure SCRIE;
begi n wr i te ( ' { ' ) ; f or i : = 1 t o n - 1 do
begi n wr i t e ( f [ i ] , ' , ' ) ; end; wr i t e ( f [ n] , ' ' ) ; wr i t e ( ' ' ) ; wri t el n; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
12/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
14
Begin { PROGRAM PRINCIPAL }
CLRSCR; wr i t el n ( ' Pr eci zat i de ci t e or i t r ebui e i nmul t i t a mul t i mea M cu ea i nsasi ' ) ; wri t e ( ' Dat i n = ' ) ; readl n ( n) ; wr i t e ( ' Dat i numar ul de el ement e al e mul t i mi i M, p = ' ) ; r eadl n ( p) ; wri t el n; wr i t el n ( ' Apasat i ENTER dupa f i ecar e sol ut i e' ) ; r eadl n; x : = 1; f [ x] : = 0; whi l e x > 0 do begi n i f f [ x] < p t hen begi n f [ x] : = f [ x] + 1; i f x = n t hen begi n SCRI E; r eadl n; end el se begi n x := x + 1; {PAS INAINTE}
f [ x] : = 0
end end el se x := x 1 {PAS INAPOI}
end; r eadl nEND.
ATESTAT - 2005 - 8 - Un copil dorete s introduc nbile numerotate de la 1la nn ncutii, cte obil n fiecare cutie. S se afieze toate posibilitilepe care le are copilul de a pune cele nbile ncele ncutii.
Rezolvare:
program ATESTAT_2005_8_PERMUTARI_ITERATIV;uses crt ;const nmax = 100;t ype vect or = arr ay [ 1. . nmax] of i nt eger;var f : vector ; sol , n, i : i nt eger ;
procedure SCRIE ;
begi n
sol : = sol + 1; wr i t e ( ' Sol ut i a nr . ' , sol , ' ' ) ; f or i : = 1 t o n do begi n wr i te ( f [ i ] : 5 ) end; readl n; wr i tel n end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
13/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
15
procedure VERIFICA ( k : i nt eger ; f : vect or ; VAR CONTI N : bool ean ) ; LABEL 10; begi n CONTI N : = TRUE; f or i : = 1 t o k - 1 do begi n i f f [ i ] = f [ k ] then begi n CONTI N : = FALSE; GOTO 10 end; end;10: end;
procedure PERMUTA ( m : i nteger ) ; LABEL 20; var k : i nt eger ; CONTI N : bool ean; begi n k : = 1; f [ k] : = 0; whi l e k > 0 do begi n
CONTI N : = FALSE; whi l e f [ k] < m do begi n f [ k] : = f [ k] + 1; VERI FI CA ( k, f , CONTI N) ; i f CONTI N = TRUE t hen GOTO 20 end;20: i f ( CONTI N = TRUE ) AND ( k = n) t hen begi n SCRI E; r eadl n; end; i f ( CONTI N = TRUE ) and ( k < n) t hen begi n k : = k + 1; f [ k] : = 0 end; i f CONTI N = FALSE t hen k : = k - 1 end; {sf . WHI LE exter i or } end;
Begin { PROGRAM PRINCIPAL }
cl r scr ; sol : = 0; wri t e( ' Dat i n = ' ) ; readl n ( n) ;
wri t el n; wr i t el n ( ' Apasat i ENTER dupa f i ecar e sol ut i e' ) ; wri t el n; PERMUTA (n); i f sol = 0 t hen wr i t el n ( ' Nu exi sta sol ut i e' ) ; r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
14/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
16
ATESTAT - 2005 - 9 - S se genereze toate PALINDROAMELE care au n cifre, iar cifrele auvalori ntre 0i p. Se citesc de la tastatur ni p(0 < n < 10, 0 < p < 5). Reamintim c un numr estePALINDROM dac numrul coincide cu imaginea lui n oglind. Altfel spus, un numr estePALINDROM dac citit direct i invers rezultatul este acelai.
Exemplu: 121 este PALINDROM.Barem :- declararea variabilelor: 0.5 puncte- citirea datelor de intrare: 1 punct- un algoritm de generareprincipial corect: 3 puncte-
verificarea condiiilor de continuare: 2 puncte- afiarea soluiilor: 2 puncte- corectitudinea sintactica programului : 0.5 puncte- din oficiu 1 punct.
Rezolvare:
program ATESTAT_2005_9_ PALINDROAME;uses CRT;t ype vect or = ar r ay [ 1. . 20] of i nt eger ;var
m, f : vector ; p, poz, A, B, x, n, nrc i f , i : i nt eger ; OK : bool ean; y : ar r ay [ 1. . 100] of i nt eger ;function PUTERE ( z : i nt eger ; t : i nt eger) : i nt eger ; var p1, j : i nt eger; begi n p1 : = 1; f or j : = 1 t o t do p1 : = p1 * z; PUTERE : = p1 end;
function NRCIFRE ( x : i nt eger) : i nt eger ; begi n i f x = 0 t hen nrci f : = 1 el se begi n nr ci f : = 0; whi l e x 0 do begi n nr ci f : = nr ci f + 1; x : = x DI V 10 end; end; NRCI FRE : = nrci f
end;function PALINDROM ( x : i nt eger ) : bool ean; begi n n : = NRCI FRE ( x) ; f or i : = n DOWNTO 1 do begi n y [ i ] : = x MOD 10; x : = x DI V 10; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
15/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
17
OK := TRUE; f or i : = 1 t o n DI V 2 do begi n i f y [ i ] y [ n- i +1] t hen OK := FALSE end; PALI NDROM : = OK end; { sf ar si t f unct i e PALI NDROM }
procedure SCRIE; begi n wr i te ( ' { ' ) ; f or i : = 1 t o n - 1 do begi n wr i t e ( f [ i ] , ' , ' ) ; end; wr i t e ( f [ n] , ' ' ) ; wr i t e ( ' ' ) ; wri t el n; wri t el n; end;Begin { PROGRAM PRINCIPAL }
CLRSCR; wr i t el n ( ' Pr eci zat i numar ul de ci f r e al vi i t or ul ui numar ' ) ; wri t e ( ' Dat i n = ' ) ; readl n ( n) ; {n = nr de mul t i mi al e pr odusul ui car t ezi an }
wri t el n; r epeat wr i t el n ( ' Pr eci zat i car e est e cea mai mar e ci f r a di n vi i t or ul numar ' ) ; wr i t e ( ' Dat i p = ' ) ; readl n ( p) ; unt i l ( p > 0) AND ( p 0 do begi n i f f [ poz] < p t hen begi n f [ poz] : = f [ poz] + 1; i f poz = n t hen begi n x : = 0; f or i : = n downto 1 do begi n x : = x + PUTERE ( 10, n- i ) * f [ i ] ; end; i f PALI NDROM ( x) = TRUE t hen begi n wr i t el n ( ' x = ' , x, ' est e PALI NDROM' ) ; SCRI E; end;
end el se begi n poz := poz + 1; {PAS INAINTE} f [ poz] : = 0 end end el se poz := poz 1 {PAS INAPOI} end; r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
16/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
18
ALOCARE DINAMICA
ATESTAT - 2005 - 10 - S se realizeze operaiile de crearei vizualizarea unei stiveimplementatedinamic, precum i eliminareaunui elementdin stiv.
Barem:- declararea corect a variabilelor: 1 punct- crearea: 4 puncte- vizualizarea: 2 puncte- eliminarea unui element: 2 puncte-
din oficiu: 1 punct
Rezolvare:
program ATESTAT_2005_10_STIVA;
l abel 10, 500;t ype STIVA = ^Nod; Nod = r ecor d chei e : i nt eger ; dat a : i nt eger ; u r m: STIVA end;var p, q, r , baza : STIVA; n, x, i , j : i nteger ; dat a : i nt eger ; c : char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e ( ' i nt r oducet i dat el e nodul ui : ' ) ; r eadl n ( dat a) ; end;
procedure TRAVLISTA ; { t r aver sar e i n or di nea i nt r oducer i i } begi n p: =baza; whi l e pni l do begi n wr i t el n( ' chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p: =p . ur m; wr i t el n end; end;
procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. Li st ei } begi n
baza: =ni l ; new( p) ; wr i t e( ' dat i chei a nodul ui 1 : ' ) ; r eadl n( p . chei e) ; p . urm: =baza; baza: =p; CI TDATA; p . dat a: =dat a end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
17/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
19
procedure INSEREAZAREST ; { i nt roduce cel el al t e el em. - l a s f i rs . l i s tei } begi n new ( q) ; q . urm: =ni l ; p . ur m: =q; i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
18/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
20
el se begi n wr i t el n( ' I NTRODUCETI DATELE NODULUI 1 ' ) ; INSEREAZAPRIMUL; wr i t el n end; i f n > 1 t hen begi n f or j : =2 t o n do begi n INSEREAZAREST; wr i t el n end end; j : =j +1; INSEREAZAREST; wri t el n; wri t el n( ' LI STA ESTE : ' ) ; TRAVLISTA; wri t el n;10: wr i t e( ' DORI TI SA CAUTATI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); i f ( c=' d' ) or ( c=' D' ) t hen begi n
CAUTA end; wri t el n; wr i t e( ' DORI TI SA STERGETI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); wri t el n;
i f ( c=' d' ) or ( c=' D' ) t hen begi n CAUTA; wr i t el n( ' CONTI NUT NOD CU CHEI A ' , X, ' I NAI NTE DE STERGERE ESTE ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wri t el n; STERGE; wri t el n; wr i t el n( ' CONTI NUTUL NODULUI DUPA STERGERE ESTE : ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wri t el n; wr i t el n( ' LI STA DUPA STERGEREA NODULUI CU CHEI A ' , X, ' ESTE : ' ) ; TRAVLISTA; wr i t el n end; wr i t e( ' DORI TI SA RELUATI PROGRAMUL ? APASATI D SAU N ' ) ; r eadl n( c); wri t el n; i f ( c=' d' ) or ( c=' D' ) t hen got o 10;500: r eadl n
END.
ATESTAT - 2005 - 11 - S se realizeze operaiile de crearei vizualizarea unei coziimplementatedinamic, precum i eliminareaunui elementdin coad.Barem:- declararea corect a variabilelor: 1 punct- crearea: 4 puncte- vizualizarea: 2 puncte- eliminarea unui element: 2 puncte- din oficiu: 1 punct
5/19/2018 Probleme Rezolvate - 2005 - Pascal
19/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
21
Rezolvare:
program ATESTAT_2005_11_COADA;l abel 10, 500;t ype
COADA= nod; nod=r ecor d chei e : i nt eger ;
dat a : i nt eger ; urm : COADA end;var q, r , baza, p : COADA; n, x, i , j : i nteger ; dat a : i nt eger ; c : char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e ( ' i nt roducet i dat el e nodul ui : ' ) ; r eadl n ( dat a) ; end;
procedure TRAVLISTA ; { t r aver sar e i n or di nea i nt r oducer i i } begi n p: =baza; whi l e pni l do begi n wr i t el n( ' chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p: =p . ur m; wr i tel n end; end; {sf ar s i t procedura TRAVLI STA}
procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. l i st ei } begi n
baza: =ni l ; new( p) ; wri t e( ' dat i chei a nodul ui 1 : ' ) ; r eadl n( p . chei e) ; p . ur m: =baza; baza: =p; CI TDATA; p . dat a: =dat a end;
procedure INSEREAZAREST ; { i nt roduce cel el al t e el em. - l a s f i rs . l i s tei } begi n new ( q) ; q . urm: =ni l ; p . ur m: =q;
i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
20/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
22
el se begi n q . chei e: =N+1;{ q . dat a: =' ACEST NOD NU SE VA STERGE SI NU SE ADAUGA NI MI C DUPA EL' ; } p: =q end end;
procedure CAUTA ; { caut a un nod dupa chei e } var b: bool ean; begi n b: =f al se; wr i t e( ' DATI CHEI A X = ' ) ; readl n( x); wri t el n; p: =baza; whi l e ( pni l ) and not b do begi n i f p . chei e=x t hen b: =t r ue el se p: =p . urm end; i f not b t hen
wr i t el n( ' NODUL ( CHEI A ) NU EXI STA ' ) el se begi n wr i t el n( ' PRI MUL NOD CARE ARE CHEI A ' , X, ' ESTE ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wr i tel n end end;
procedure STERGE ; { st er ge un nod i ndi cat pr i nt r - o chei e } begi n q: =p . ur m; p : =q^ end;Begin { PROGRAM PRINCIPAL }
wr i t e( ' Dat i numar ul de nodur i N = ' ) ; r eadl n( n) ; wri t el n; i f n=0 t hen begi n wr i t el n( ' LI STA VI DA' ) ; got o 500 end el se begi n wr i t el n( ' I NTRODUCETI DATELE NODULUI 1 ' ) ; INSEREAZAPRIMUL; wr i t el n end;
i f n > 1 t hen begi n f or j : =2 t o n do begi n INSEREAZAREST; wr i t el n end end; j : =j +1; wr i t el n( ' I NTRODUCETI NODUL F A N I O N ' ) ; INSEREAZAREST; wri t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
21/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
23
wri t el n( ' LI STA ESTE : ' ) ; TRAVLISTA; wri t el n;10: wr i t e( ' DORI TI SA CAUTATI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); i f ( c=' d' ) or ( c=' D' ) t hen
CAUTA
wri t el n; wr i t e( ' DORI TI SA STERGETI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); wri t el n; i f ( c=' d' ) or ( c=' D' ) t hen begi n CAUTA; wr i t el n( ' CONTI NUT NOD CU CHEI A ' , X, ' I NAI NTE DE STERGERE ESTE ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wri t el n; STERGE; wri t el n; wr i t el n( ' CONTI NUTUL NODULUI DUPA STERGERE ESTE : ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wri t el n; wr i t el n( ' LI STA DUPA STERGEREA NODULUI CU CHEI A ' , X, ' ESTE : ' ) ; TRAVLISTA;
wr i tel n end; wr i t e( ' DORI TI SA RELUATI PROGRAMUL ? APASATI D SAU N ' ) ; r eadl n( c); wr i t el n; i f ( c=' d' ) or ( c=' D' ) t hen got o 10;500: r eadl nEND.
ATESTAT - 2005 - 12 - S se creeze o list liniar dublu nlnuitavnd ca elemente cuvint
citite din fiierul standard de intrare, pn la ntlnirea caracterului *. S se afieze cuvintele ordine invers citiriii apoi n ordinea n care s-au citit.Barem:- declararea corect a variabilelor: 1 punct- crearea: 4 puncte- vizualizarea: 4 puncte- din oficiu: 1 punct
Rezolvare:
program ATESTAT_2005_12_LISTA_DUBLU_INLANTUITA;uses CRT;
l abel 10, 500;t ype LISTA = ^nod; nod = r ecord chei e : i nt eger ; dat a : st r i ng; ur m, pr eced : LISTA end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
22/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
24
var q, r , baza, p: LISTA; n, x, i , j : i nteger ; dat a: st r i ng; c: char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e ( ' I nt r oducet i dat el e nodul ui : ' ) ; r eadl n ( dat a) ; end;
procedure TRAVLISTA_INCEP_SFARSIT ; { t r aversare l i sta i nceput - > sf i rs i t } begi n p: =baza; wr i t el n ( ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' ) ; wr i t el n ( ' Tr aver sar e i n sens di r ect' ) ; wr i t el n ( ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' ) ; whi l e ( pni l ) AND ( p . data ' *' ) do begi n wr i t el n ( ' NODUL cu chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p:=p^.urm; end; wr i t el n( ' Ul t i mul NOD ( FANI ON) : chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; end;
procedure TRAVLIST_SFARSIT_INCEP; { t r aversare l i sta sf i r s i t - > i nceput }
begi n p: =baza;
q: =p; p: =p . ur m; p . preced : = q;
whi l e ( pni l ) AND ( p . data ' *' ) do begi n
q : = p; p: =p . ur m; p . preced : = q;
end;
wr i t el n ( ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' ) ; wr i t el n ( ' Tr aver sar e i n sens i nver s' ) ; wr i t el n ( ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' ) ;
whi l e p baza do begi n wr i t el n ( ' NOD CURENT chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p: =p . preced; end; wr i t el n( ' NOD CURENT chei a= ' , p . chei e, ' data= ' , p . dat a) ;
end; {sf ar si t pr ocedur a TRAVLIST_SFARSIT_INCEP }procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. l i st ei } begi n baza: =ni l ; new( p) ; wr i t e( ' dat i chei a nodul ui 1 : ' ) ; r eadl n( p . chei e) ; p . urm: =baza; baza: =p; CI TDATA; p . dat a: =dat a end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
23/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
25
procedure INSEREAZAREST ; { i nt r oduce cel el al t e el em. } { pr i n t ehni ca " l a s fars i t ul l i s tei " } begi n new ( q) ; q . urm: =ni l ; p . ur m: =q; i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
24/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
26
i f n=0 t hen begi n wr i t el n( ' LI STA VI DA' ) ; got o 500 end el se begi n wr i t el n( ' I NTRODUCETI DATELE NODULUI 1 ' ) ;
INSEREAZAPRIMUL;
wr i t el n end; i f n > 1 t hen begi n f or j : =2 t o n do begi n
INSEREAZAREST;
wr i t el n end end; j : =j +1;
INSEREAZAREST; wri t el n; wr i t el n( ' LI STA par cur sa de l a I NCEPUT l a SFI RSI T est e : ' ) ;
TRAVLISTA_INCEP_SFIRSIT;
wri t el n; wri t el n ( ' *********************************************' ) ; wri t el n; wr i t el n( ' LI STA par cur sa de l a SFI RSI T l a I NCEPUT est e : ' ) ;
TRAVLIST_SFIRSIT_INCEP;
wri t el n;
500: r eadl nEND.
ATESTAT - 2005 - 13 - Se citete de la tastatur un ir de numere ntregi, care se ncheie cu citireavalorii 0. S se creeze o list liniar simplu nlnuitastfel nct, la parcurgerea listei, elementeles aparn ordinean care au fost citite.a). S se afieze coninutul listei;
b). S se verifice dac elementele listei sunt ordonate cresctor.
Barem:- declaraii corecte: 1 punct- crearea listei: 3 puncte- vizualizarea coninutului: 2 puncte- algoritm de verificare a ordonrii cresctoare: 3 puncte- din oficiu: 1 punct
5/19/2018 Probleme Rezolvate - 2005 - Pascal
25/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
27
Rezolvare:
program ATESTAT_2005_13_LISTA_LINIARA_SIMPLU_INLANTUITA_INTREGI;
uses CRT;
l abel 10, 500;const nmax = 50;
t ype
LISTA = ^Nod; Nod = r ecord chei e : i nt eger ; dat a : i nt eger ; u r m: LISTA end; vect or = ar r ay [ 1. . nmax] of i nt eger ;var q, r , baza, p : LISTA; n, x, i , j : i nteger ; dat a : i nt eger ; c : char ;
v : vector ;function VERIFICA ( v : vector; q: i nt eger ) : bool ean; var j : i nt eger ;
begi n VERI FI CA : = TRUE; j : = 1; r epeat i f v[ j ] > v [ j +1] t hen VERI FI CA : = FALSE; j : = j + 1
unt i l ( j > q- 1) end;
procedure TRAVLISTA ; { t r aver sar e i n or di nea i nt r oducer i i } begi n p: =baza; whi l e pni l do begi n wr i t el n ( ' dat a= ' , p . dat a) ; p: =p . ur m; end; end;
Begin { PROGRAM PRINCIPAL }
cl r scr ; wr i t el n ( ' Dat i el ement el e l i s tei ' ) ; wr i t el n ( ' ********************** ' ) ; i : = 0; {contor car e numara numerel e i nt r oduse } wr i t e ( ' Dat i pr i mul el ement , x = ' ) ; r eadl n ( x) ; wri t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
26/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
28
I f x = 0 t hen begi n wr i t el n ( ' LI STA VI DA' ) ; got o 500 end el se begi n { I NSERARE PRI MUL NOD } i : = i + 1; baza: =ni l ; new ( p) ; p . ur m: =baza; baza: =p; p . dat a : = x; v [ i ] : = x; end; wri t el n; wr i t el n ( ' Dat i ur mat oar el e el ement e' ) ; r epeat wr i t e ( ' Dat i el ement ul ' , i + 1, ' x = ' ) ; r eadl n ( x) ; i f x 0 t hen { I NSERARE URMATOARELE NODURI } begi n i : = i + 1; v [ i ] : = x;
new ( q) ; q . ur m : = ni l ; p . ur m : = q; q . dat a : = x; p : = q end; unt i l x = 0; n : = i ; wri t el n; wr i t el n ( ' Li sta are ' , n, ' el ement e' ) ; wri t el n; wr i t el n( ' LI STA ESTE : ' ) ; TRAVLI STA; wri t el n;
i f VERI FI CA ( v, n) = TRUE t hen wr i t el n ( ' Li st a est e ORDONATA' ) el se wr i t el n ( ' Li st a NU est e ORDONATA' ) ;
500: r eadl nEND.
ATESTAT - 2005 - 14 - S se creeze o list liniar simplu nlnuit format din numere ntregiintroduse de la tastatur. S se afieze coninutul listei, dup care s se realizeze transferulprimului element la sfritul listei.Exemplu: Dac lista conine iniial elementele 2, 51, 4, 7, 14, 25, 69 (n aceast ordine), duptransfer coninutul va fi: 51, 4, 7, 14, 25, 69, 2 (n aceast ordine).Barem:- declaraii corecte: 1 punct- crearea listei: 3 puncte- vizualizarea coninutului: 2 puncte- realizarea transferului cerut: 3 puncte- din oficiu: 1 punct
5/19/2018 Probleme Rezolvate - 2005 - Pascal
27/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
29
Rezolvare:
program ATESTAT_2005_14_LISTA_SIMPLU_INLANTUITA;
uses CRT;l abel 10, 500;t ype LISTA = ^NOD; NOD = r ecord
chei e : i nt eger ; dat a : i nt eger ; u r m: LISTA end;var q, r , baza, p: LISTA; n, x, i , j : i nteger ; dat a: i nt eger ; pr i mul , ul t i mul : i nt eger ; c: char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e( ' i nt roducet i dat el e nodul ui : ' ) ;
r eadl n( dat a) ; end;
procedure TRAVLISTA_INCEP_SFIRSIT ; { t raversare l i sta i nceput - > sf i rs i t } begi n p: =baza; wr i t el n ( ' - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ' ) ;
pr i mul : = p . dat a; wri t el n ( ' Pr i mul = ' , pr i mul ) ; wri t el n; whi l e p ni l do begi n
wr i t el n ( ' NODUL cu chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; ultimul := p^.data; p:=p^.urm;
end; wri t el n;
wr i t el n ( ' Ul t i mul = ' , ul t i mul ) ; wri t el n;
end;
procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. l i st ei } begi n baza: =ni l ;
new( p) ; wri t e( ' dat i chei a nodul ui 1 : ' ) ; r eadl n( p . chei e) ; p . ur m: =baza; baza: =p; CI TDATA; p . dat a: =dat a end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
28/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
30
procedure TRANSFERA ; { i nsereaza un nod NOU dupa un nod cu chei a caut ata } var aux : i nt eger ; begi n aux : = pri mul ; pr i mul : = ul t i mul ; ul t i mul : = aux;
end;
procedure INSEREAZAREST ; { i nt r oduce cel el al t e el em. } { pr i n tehni ca " l a s f i r s . l i s tei " } begi n new ( q) ; q . ur m: =ni l ; p . ur m: =q; i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
29/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
31
procedure STERGE ; { st er ge un nod i ndi cat pr i nt r - o chei e } begi n q: =p . ur m; p : =q^ end;
Begin { PROGRAM PRINCIPAL }
cl r scr ; wr i t e( ' dat i nr. de nodur i N = ' ) ; r eadl n( n) ;
wri t el n; i f n=0 t hen begi n wr i t el n( ' LI STA VI DA' ) ; got o 500 end el se begi n wr i t el n ( ' I NTRODUCETI DATELE NODULUI 1 ' ) ;
INSEREAZAPRIMUL;
wr i tel n
end;
i f n > 1 t hen begi n f or j : =2 t o n do begi n
INSEREAZAREST;
wr i t el n end end; wri t el n; wri t el n ( ' Pr i ma t raver sare a l i stei ' ) ;
TRAVLISTA_INCEP_SFIRSIT;
wri t el n; wri t el n ( ' *********************************************' ) ; wri t el n; r eadl n;
TRANSFERA;
wri t el n; wr i t el n ( ' Dupa TRANSFER, avem: ' ) ; wri t el n;
wr i t el n ( ' Pr i mul = ' , pr i mul ) ; wr i t el n ( ' Ul t i mul = ' , ul t i mul ) ; p : = baza; p . dat a : = pr i mul ;
j : = 1;
whi l e ( p ni l ) AND ( j n) do begi n p: =p . ur m; j : = j + 1; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
30/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
32
p . data : = ul t i mul ;
wri t el n;
wri t el n ( ' A doua t r aver sare a l i stei : ' ) ;
TRAVLISTA_INCEP_SFIRSIT ;
500: r eadl nEND.
ATESTAT - 2005 - 15 - S se descrie operaia de adugarea unui nouelement la o list liniarsimplu nlnuit, implementat dinamic, ce conine caracteren noduri.Barem:- declaraii corecte: 1 punct- crearea listei: 3 puncte- vizualizarea coninutului: 2 puncte- adugarea unui element: 3 puncte- din oficiu: 1 punct
Rezolvare:
program ATESTAT_2005_15_LISTA_LINIARA_SIMPLU_INLANTUITA;
l abel 10, 500;t ype LISTA = ^NOD; NOD = r ecord chei e: i nt eger ; dat a: CHAR; ur m: LISTA end;
var p, q, r , baza : LISTA; n, x, i , j : i nteger ; dat a: CHAR; c: char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e ( ' i nt r oducet i dat el e nodul ui : ' ) ; r eadl n ( dat a) ; end;
procedure TRAVLISTA ; { t r aver sar e i n or di nea i nt r oducer i i } begi n
p: =baza; whi l e pni l do begi n wr i t el n( ' chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p: =p . ur m; wr i t el n end; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
31/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
33
procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. l i st ei } begi n baza: =ni l ; new( p) ; wri t e( ' dat i chei a nodul ui 1 : ' ) ; r eadl n( p . chei e) ; p . ur m: =baza; baza: =p; CI TDATA; p . dat a: =dat a end;
procedure INSEREAZAREST ; { i nt roduce cel el al t e el em. - l a s f i rs . l i s tei } begi n new ( q) ; q . urm: =ni l ; p . ur m: =q; i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
32/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
34
Begin { PROGRAM PRINCIPAL }
wr i t e( ' dat i nr . de nodur i N = ' ) ; r eadl n( n) ; wri t el n; i f n=0 t hen begi n wr i t el n( ' LI STA VI DA' ) ; got o 500 end el se begi n wr i t el n( ' I NTRODUCETI DATELE NODULUI 1 ' ) ; INSEREAZAPRIMUL; wr i t el n end; i f n > 1 t hen begi n f or j : =2 t o n do begi n INSEREAZAREST; wr i t el n end end; j : =j +1;
wr i t el n( ' I NTRODUCETI NODUL F A N I O N ' ) ; INSEREAZAREST; wri t el n; wri t el n( ' LI STA ESTE : ' ) ; TRAVLISTA; wri t el n;10: wr i t e( ' DORI TI SA CAUTATI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); i f ( c=' d' ) or ( c=' D' ) t hen begi n CAUTA end; wri t el n; wr i t e( ' DORI TI SA STERGETI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); wri t el n; i f ( c=' d' ) or ( c=' D' ) t hen begi n CAUTA; wr i t el n( ' CONTI NUT NOD CU CHEI A ' , X, ' I NAI NTE DE STERGERE ESTE ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wri t el n; STERGE; wri t el n; wr i t el n( ' CONTI NUTUL NODULUI DUPA STERGERE ESTE : ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wri t el n;
wr i t el n( ' LI STA DUPA STERGEREA NODULUI CU CHEI A ' , X, ' ESTE : ' ) ; TRAVLISTA; wr i t el n end; { sf arsi t I F } wr i t e( ' DORI TI SA RELUATI PROGRAMUL ? APASATI D SAU N ' ) ; r eadl n( c); wri t el n; i f ( c=' d' ) or ( c=' D' ) t hen got o 10;500: r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
33/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
35
ATESTAT - 2005 - 16 - S se realizeze operaiile de crearei vizualizarea unei liste circulare.Barem:- declaraii corecte: 1 punct- crearea listei: 4 puncte- vizualizarea coninutului: 4 puncte- din oficiu: 1 punct
Rezolvare:
program ATESTAT_2005_16_LISTA_CIRCULARA;l abel 10, 500;t ype LISTA = ^NOD; NOD = r ecord chei e : i nt eger ; dat a : i nt eger ; u r m: LISTA end;var q, r , baza, p : LISTA; n, x, i , j : i nteger ;
dat a : i nt eger ; c : char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e ( ' i nt roducet i dat el e nodul ui : ' ) ; r eadl n ( dat a) ; end;
procedure TRAVLISTA ; { t r aver sar e l i st a i n or di nea i nt r oducer i i } begi n p: =baza;
whi l e p . chei e < n do
begi n wr i t el n( ' chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p: =p . ur m; wr i tel n end;
{af i sare ul t i m nod wr i t el n( ' chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; end;
procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. l i st ei } begi n baza: =ni l ;
new( p) ; wri t e( ' dat i chei a nodul ui 1 : ' ) ; r eadl n( p . chei e) ; p . ur m: =baza; baza: =p; CITDATA; p . dat a: =dat a end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
34/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
36
procedure INSEREAZAREST ; { i nt roduce cel el al t e el em. - l a s f i rs . l i s tei } begi n new ( q) ; q . ur m: =ni l ; p . ur m: =q; i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
35/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
37
i f n > 1 t hen begi n f or j : =2 t o n do begi n INSEREAZAREST; wr i t el n end end; q . urm : = baza; { j : =j +1; } wr i t el n ( ' I NTRODUCETI NODUL F A N I O N ' ) ; INSEREAZAREST;
wri t el n; wr i t el n ( ' LI STA ESTE : ' ) ; TRAVLISTA; wri t el n;500: r eadl nEND.
ATESTAT - 2005 - 17 - S se realizeze operaia de eliminarea unui elementdintr-o list simplnlnuit, implementat dinamic, ce conine numere ntregi citite de la tastatur. S se afieze listnaintei dup tergereaelementului.Barem:- declaraii i citire: 1 punct- crearea listei : 3 puncte- tergerea unui element: 3 puncte- afiarea listei: 2 punct- din oficiu: 1 punct
Rezolvare:
program ATESTAT_2005_17_LISTA SIMPLU INLANTUITA;
l abel 10, 500;t ype LISTA = ^NOD; NOD = r ecord chei e : i nt eger ; dat a : i nt eger ; u r m: LISTA end;var q, r , baza, p : LISTA; n, x, i , j : i nteger ; dat a : i nt eger ; c : char ;
procedure CITDATA; { i nt r oducer e dat e ut i l e } begi n wri t e ( ' i nt roducet i dat el e nodul ui : ' ) ; readl n ( data) ; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
36/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
38
procedure TRAVLISTA ; { t r aver sar e i n or di nea i nt r oducer i i } begi n p: =baza; whi l e pni l do begi n wr i t el n( ' chei a= ' , p . chei e, ' dat a= ' , p . dat a) ; p: =p . ur m; wr i t el n end; end;
procedure INSEREAZAPRIMUL ; {i nt r oduce pr i mul el ement - l a i ncep. l i st ei } begi n baza: =ni l ; new( p) ; wr i t e( ' dat i chei a nodul ui 1 : ' ) ; readl n(p^.cheie) ; p . urm: =baza; baza: =p; CITDATA; p . dat a: =dat a end;
procedure INSEREAZAREST ; { i nt roduce cel el al t e el em. - l a s f i rs . l i s tei } begi n new ( q) ; q . ur m: =ni l ;
p . ur m: =q; i f j
5/19/2018 Probleme Rezolvate - 2005 - Pascal
37/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
39
procedure STERGE ; { st er ge un nod i ndi cat pr i nt r - o chei e } begi n q: =p . ur m; p : =q^ end;Begin { PROGRAM PRINCIPAL }
wr i t e( ' dat i nr . de nodur i N = ' ) ; r eadl n( n) ; wri t el n; i f n=0 t hen begi n wr i t el n( ' LI STA VI DA' ) ; got o 500 end el se begi n wr i t el n( ' I NTRODUCETI DATELE NODULUI 1 ' ) ; INSEREAZAPRIMUL; wr i tel n end; i f n > 1 t hen begi n f or j : =2 t o n do begi n INSEREAZAREST;
wr i t el n end end; j : =j +1; wr i t el n( ' I NTRODUCETI NODUL F A N I O N ' ) ; INSEREAZAREST; wri t el n; wri t el n( ' LI STA ESTE : ' ) ; TRAVLISTA; wri t el n;10: wr i t e( ' DORI TI SA CAUTATI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); i f ( c=' d' ) or ( c=' D' ) t hen begi n CAUTA end; wri t el n; wr i t e( ' DORI TI SA STERGETI UN NOD ? APASATI D SAU N ' ) ; r eadl n( c); wri t el n; i f ( c=' d' ) or ( c=' D' ) t hen begi n CAUTA; wr i t el n( ' CONTI NUT NOD CU CHEI A ' , X, ' I NAI NTE DE STERGERE ESTE ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; STERGE; wri t el n;
wr i t el n( ' CONTI NUTUL NODULUI DUPA STERGERE ESTE : ' ) ; wr i t el n( p . chei e, ' ' , p . dat a) ; wr i t el n( ' LI STA DUPA STERGEREA NODULUI CU CHEI A ' , X, ' ESTE : ' ) ; TRAVLISTA; end; wr i t e( ' DORI TI SA RELUATI PROGRAMUL ? APASATI D SAU N ' ) ; r eadl n ( c); wr i t el n; i f ( c=' d' ) or ( c=' D' ) t hen got o 10;500: r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
38/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
40
GRAFURI
ATESTAT - 2005 - 18 - Se d un graf neorientat Gla care:- n = numrul de vrfuri (n, numr natural pozitiv);- pentru fiecare vrf se cunosc vrfurile adiacente cu el;
S se scrie un program prin care s se afieze:a). gradulfiecrui vrf(nod);b). lista tuturor vrfurilorde gradmaxim;
c). numrul de vrfuriizolate;d). numrul de muchiidin graf.Barem:- declaraii i introducere corect a grafului: 1 punct- realizarea punctului a): 2 puncte- realizarea punctului b): 2 puncte- realizarea punctului c): 2 puncte- realizarea punctului d): 2 puncte- din oficiu: 1 punct
Rezolvare:
Considerm urmtorul graf neorientat:Graful are 5 noduri(vrfuri),notate cu 1, 2, 3, 4, 5 i4 muchii, notate cu[2,3], [2,4], [3,4] i [4,5].
n general, la un graf neorientat cu n vrfuri, matricea de adiacenA este o matriceptraticde ordinul n, simetric, cu elementele:
Este uor de observat c elementele de pe diagonala principalsunt nule(A [i, i] = 0), deoarece [i,i]NU este muchie n graf..
Matricea de adiacen asociat grafului de mai sus este:
n program,matricea de adiacense va construi astfel:I - Se face iniializarea tuturor elementelor matricii cu zero (n acest fel, anulm att elementelediagonalei principale, ct i elementele matricii care nu se asociaz muchiilor). Vom scrie:
For i := 1 to n do For j := 1 to n do A [i, j] := 0;
II A Dac se cunoate numrul muchiilor. Notm cu [x, y]o muchie din graf, unde xi ysuntextremitile muchiei (dou noduri ale grafului). n matricea de adiacen, elementul A [x, y] = 1.Cum matricea de adiacen este i simetric, rezult cu i A [y, x] = 1.Notnd cu m numrul demuchii din graf, vom folosi o structur FOR n care, pentru fiecare muchie i, vom introduceextremitile x i y. Evident, aceste extremiti sunt vrfuri n graf. Vom scrie:
1, dac [i, j] este muchie n graf ; nodurile i i j sunt extremitile muchiei0, n caz contrarA [i, j] =
12
3 4
5
1 2 3 4 51 0 0 0 0 0
2 0 0 1 1 03 0 1 0 1 0
4 0 1 1 0 15 0 0 0 1 0
A (5, 5) =
5/19/2018 Probleme Rezolvate - 2005 - Pascal
39/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
41
For i := 1 to m do Begin Writeln (Dai extremitile muchiei i:) Write (Dai vrful x = ); readln (x); Write (Dai vrful y = ); readln (y); A [x, y] := 1; A [y, x] := 1;{matrice simetric} End;
II B Dac NU se cunoate numrul muchiilor (este cazul problemei noastre), dar, pentrfiecare vrf, se cunosc vrfurile adiacente cu el (se cunosc vecinii fiecrui vrf) . Notm cu xrespectiv cu ydou vrfuri din graf. Evident, att x ct i yiau valori ntre 1 i n (n = numrul totade vrfuri din graf). Pentru fiecare nod x, trebuie s precizm numrul vecinilor si, precum i carsunt acetia. n program vom scrie:
For x:= 1 to ndo begin write (Ci vecini are x, nrvecini= ); readln (nr);
For i := 1 to nrvecinidobegin
write (Dai urmtorul vecin, y = );readln (y);A [x, y] := 1;A [y, x] := 1
end; end;
a Gradulunui vrf v, se noteaz cu d(x)i este dat de numrul muchiilorincidente cu v. program vom folosi un vector notat cu d, cu 5 elemente (5 = numrul de noduri), fiecare elemenreprezentnd gradul unui nod (vrf). Pentru cazul particular al grafului de mai sus, avem:d (1) = 0 d (2) = 2 d (3) = 2 d (4) = 3 d (5) = 1
Se observ c gradul unui nod icoincide cu numrul de cifre de 1 de pe linia i dimatricea de adiacen. Prin urmare, pentru a determina gradul unui nod, numrm cifrele de 1 de pfiecare linie a matricii de adiacen i reinem aceste numere n elementele vectorului d.
b Determinm gradul maxim (elementul maxim din vectorul d) i afim doar numerelnodurilor al cror grad = gradul maxim.
c Un vrf izolat are gradul zero. n matricea de adiacen, unui nod izolat i corespunde o linierespectiv o coloan cu toate elementele egale cu zero. Pentru a determina numrul de vrfuri izolatenumrm liniile din matricea de adiacen care au toate elementele nule.
d Fiecare muchie [x, y] contribuie cu o unitate (1) la gradul nodului xi cu o unitate (1) la gradu
nodului y, deci cu dou uniti (2) la suma gradelor tuturor nodurilor. Cum n graf sunt m muchirezult c suma gradelor tuturor nodurilor = 2m. De aici rezult m.
program ATESTAT_2005_18_GRAF_NEORIENTAT;
uses CRT;CONST nmax = 100;
TYPE vect or = ar r ay [ 1. . nmax] of i nt eger ; mat r i ce = ar r ay [ 1. . nmax, 1. . nmax] of i nt eger ;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
40/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
42
VAR n : i nt eger; {n = numar ul nodur i l or} i , j : i nt eger ; x, y : i nt eger ; {nodur i i n gr af , ext r emi t i al e unei muchi i } A : mat r i ce; {matricea de adiacenta} d : vector ; {vector ul car e cont i ne "gradele" f i ecar ui nod di n gr af } nr veci ni : i nt eger ; {numar ul de veci ni ai unui nod} nr ci f r e1 : i nt eger ; {numar ul de ci f r e egal e cu 1 di n mat r i cea de adi acent a} gradmax : i nt eger; {gr adul maxi m al unui nod} nr ci f r ezer o : i nt eger ; {numar ul ci f r el or egal e cu zer o di n mat r i cea deadi acent a} nr nodur i gr adzero : i nt eger ; {numar ul nodur i l or cu gr adul zero} sumagr ade : i nt eger ; {suma gr adel or t ut ur or nodur i l or } m : i nt eger ; {numar ul de muchi i di n gr af }
Begin { PROGRAM PRINCIPAL }
CLRSCR;
wr i t e ( ' Dat i numar ul de nodur i , n = ' ) ; r eadl n ( n) ;
{Initializarea tuturor elementelor matricii de adiacenta cu zero}
f or i : = 1 t o n do begi n
f or j : = 1 t o n do begi n A [ i , j ] : = 0 end; end; wri t el n;
{Completare matrice de adiacenta}
For x : = 1 t o n do begi n wri t e ( ' Cat i veci ni are nodul ' , x, ' ? Dat i nrveci ni = ' ) ; r eadl n ( nr veci ni ) ;
For i : = 1 t o nr veci ni dobegi n
wr i t e ( ' Pent r u nodul ' , x, ' , dat i ur mat or ul veci n, y = ' ) ;r eadl n ( y) ;A [ x, y] : = 1;A [ y, x] : = 1
end; wri t el n; end; wri t el n;
{a - Determinare grade varfuri}
f or i : = 1 t o n do {i = i ndex l i ni e i n mat r i cea de adi acent a} begi n nr ci f r e1 : = 0;
f or j : = 1 t o n do {j = i ndex col oana i n matr i cea de adi acenta} begi n i f A [ i , j ] = 1 t hen nr ci f r e1 : = nr ci f r e1 + 1; end; d [ i ] : = nrci f re1; wr i tel n ( ' gradul nodul ui ' , i , ' = ' , d [ i ] ) ; end; wri t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
41/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
43
{b - Determinam gradul maxim si afisam nodurile cu gradul maxim}
gradmax : = d [ 1] ; f or i : = 2 t o n do begi n i f gr admax < d [ i ] t hen gradmax : = d [ i ] end; wr i t el n ( ' Gr adul maxi m = ' , gr admax) ; wri t el n; f or i : = 1 t o n do begi n i f d [ i ] = gr admax t hen wr i t el n ( ' Nodul ' , i , ' ar e gr adul maxi m = ' , gr admax) ; end; wri t el n;
{c Determinare noduri cu grad zero}
nr nodur i gr adzero : = 0; f or i : = 1 t o n do begi n nr ci f r ezer o : = 0; f or j : = 1 t o n do begi n i f A [ i , j ] = 0 t hen
nr ci f r ezer o : = nr ci f r ezer o + 1; end; i f nr ci f r ezer o = n t hen nr nodur i gr adzero : = nr nodur i gr adzero + 1; end; wr i t el n ( ' Gr af ul ar e ' , nrnodur i gr adzer o, ' nodur i cu gr adul zer o' ) ; wri t el n;
{d Determinare numar muchii = m}
sumagr ade : = 0; f or i : = 1 t o n do begi n sumagrade : = sumagrade + d [ i ] end; m : = sumagrade DI V 2; wri t el n ( ' Gr af ul are ' , m, ' muchi i ' ) ; r eadl nend.
ATESTAT - 2005 - 19 - Se d un graf neorientat Gcu nvrfuri i mmuchii (n i m sunt numernaturale introduse de la tastatur). S se scrie un program care s verifice dac grafuleste complet.
Barem:- declaraii corecte de variabile: 1 punct- reprezentarea corect a grafului prin matricea de adiacen: 3 puncte
-
realizarea algoritmului de prelucrare: 3 puncte- afiarea rezultatului : 2 puncte- din oficiu: 1 punct
Rezolvare:Un graf este completdac oricare dou noduri sunt adiacente(sunt legate ntre ele printr-
muchie). Altfel spus, n matricea de adiacen, notat cu A, doar elementele de pe diagonalprincipal sunt nule, celelalte elemente sunt egale cu 1, adic matricea are n2 n = n (n 1elemente egale cu 1.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
42/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
44
Altfel spus, fiecare nod are gradul n 1. Cum graful conine n noduri, rezult c sumagradelortuturor nodurilor este = n (n 1) = 2m.
Prin urmare, problema s-ar putea rezolva foarte simplu verificnd dac n (n 1) = 2m, avndn vedere c ni msunt cunoscute (sunt date de intrare).
Presupunnd c nu dorim s verificm doar relaia de mai sus, vom face verificri asupramatricii de adiacen A:a - fie vom numra elementele egale cu 1 din matrice i vom verifica dac numrul total de elementeegale cu 1 este egal cu n (n 1),b - fie vom verifica dac, n matricea de adiacen, numai elementele diagonalei principale sunt nule.
Notm cu [x, y]o muchie din graf, unde x i y sunt extremitile muchiei (dou noduri alegrafului). n matricea de adiacen, elementul A [x, y] = 1. Cum matricea de adiacen este isimetric, rezult cu i A [y, x] = 1. Deoarece se cunoate numrul muchiilor (m), vom folosi ostructur FOR n care, pentru fiecare muchie i, vom introduce extremitile x i y. Evident,aceste extremiti sunt vrfuri n graf. Vom scrie:
For i := 1 to m do Begin Writeln (Dai extremitile muchiei i:) Write (Dai vrful x = ); readln (x); Write (Dai vrful y = ); readln (y); A [x, y] := 1; A [y, x] := 1;{matrice simetric} End;
program ATESTAT_2005_19_GRAF_NEORIENTAT;uses CRT;CONST nmax = 100;
TYPE vect or = arr ay [ 1. . nmax] of i nt eger; mat r i ce = ar r ay [ 1. . nmax, 1. . nmax] of i nt eger ;VAR n : i nt eger; {n = numar ul nodur i l or} m : i nt eger; {numar ul de muchi i di n gr af } x, y : i nt eger ; {nodur i i n gr af , ext r emi t i al e unei muchi i } A : mat r i ce; {matricea de adiacenta} nrcifre1 : i nt eger ; {numar ul de ci f r e egal e cu 1 di n mat r i cea de adi acent a} nrcifrezero : i nt eger ; {numar ul ci f r el or egal e cu zer o di n mat r i cea de adi acent a} i , j : i nt eger ;
Begin { PROGRAM PRINCIPAL }
CLRSCR;
wr i t e ( ' Dat i numar ul de nodur i , n = ' ) ; r eadl n ( n) ;
{Initializarea tuturor elementelor matricii de adiacenta cu zero}
f or i : = 1 t o n do begi n f or j : = 1 t o n do begi n A [ i , j ] : = 0 end; end; wri t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
43/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
45
{Completare matrice de adiacenta}
For i : = 1 t o m do Begi n Writeln (Dai extremitile muchiei i: ) Write (Dai vrful x = ); readln (x) ; Write (Dai vrful y = ); readln (y) ; A [x, y] := 1; A [y, x] := 1; {matricea este simetric} End; wr i t el n;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - {Varianta a - Numrarea cifrelor de 1 din matricea de adiacen} nr ci f r e1 : = 0;
f or i : = 1 t o n do {i = i ndex l i ni e i n mat r i cea de adi acent a} begi n f or j : = 1 t o n do {j = i ndex col oana i n mat r i cea de adi acent a} begi n i f A [ i , j ] = 1 t hen nr ci f r e1 : = nr ci f r e1 + 1; end; end; wri t el n;
i f nrcifre1 = n (n 1) t hen wr i t el n ( Gr af ul est e compl et ) el se wr i t el n ( Gr af ul est e i ncompl et ) ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - {Varianta b - Numrarea cifrelor de zero din matricea de adiacen} nr ci f r ezer o : = 0; f or i : = 1 t o n do {i = i ndex l i ni e i n mat r i cea de adi acent a} begi n f or j : = 1 t o n do {j = i ndex col oana i n mat r i cea de adi acent a} begi n i f A [ i , j ] = 0 t hen nr ci f r ezer o : = nr ci f r ezer o + 1;
end; end; wri t el n; i f nrcifrezero = n t hen wr i t el n ( Gr af ul est e compl et ) el se wr i t el n ( Gr af ul est e i ncompl et ) ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - r eadl n
end.
ATESTAT - 2005 - 20 - Fie G un graf neorientatdat prin numrul de vrfuri i numrul de much(n, respectiv m, numere naturale introduse de la tastatur). S se scrie un program care s verificdac graful conine un ciclu de lungime 4.Barem:- declaraii corecte de variabile: 1 punct- reprezentarea corect a grafului prin matricea de adiacen: 3 puncte- realizarea algoritmului de prelucrare: 3 puncte- afiarea rezultatului : 2 puncte- din oficiu: 1 punct
5/19/2018 Probleme Rezolvate - 2005 - Pascal
44/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
46
Rezolvare:Un ciclu elementar are proprietatea c oricare dou vrfuri ale sale, cu excepia primului i
ultimului, sunt diferite dou cte dou. Lungimeaunui ciclu= numrul de muchiice apar n ciclu.Considernd graful din figura de mai jos, se poate observa uor ciclul 1 2 3 4 1 care
are lungimea 4. Matricea de adiacen a grafului este urmtoarea:
Trebuie doar s se verifice dac exist cicluri de lungime 4 (NU se cere generarea acestora).Pentru ciclul de lungime 4 identificat n graf (1 2 3 4 1), n matricea de adiacen,
liniile corespunztoare nodurilor 1i 3conin amndou cifra 1pe poziiile k = 2i k = 4.De asemenea, liniile corespunztoare nodurilor 2 i 4 conin amndou cifra 1 pe poziiile
k = 1i k = 3.Va trebui s verificm dac, pentru fiecare perechede noduri distincte, liniile (din matricea
de adiacen) corespunztoare acestor noduri conin cifra 1pe cel puin 2poziii (coloane) identice.Notm cu i, respectiv j dou linii distincte din matricea de adiacen, linii
corespunztoare a dou noduri i i j. Evident, i = 1 .. n-1, iar j = i + 1 .. n.Notm cu k indexul de coloan (din matricea de adiacen) pentru care se face testarea
perechii A [i, k] iA [j, k]. Iniializm un contor nrcifrecare numr cifrele de 1,n condiia(A [i, k] = 1 ) AND ( A [j, k] = 1 ).
program ATESTAT_2005_20_GRAF_CU_UN_CICLU_DE_LUNGIME_PATRU ;uses CRT;LABEL
s far s i t ;CONST nmax = 100;
TYPE mat r i ce = ar r ay [ 1. . nmax, 1. . nmax] of i nt eger ;VAR n : i nt eger; {n = numar ul nodur i l or} m : i nt eger; {numar ul de muchi i di n gr af } x, y : i nt eger ; {nodur i i n gr af , ext r emi t i al e unei muchi i } A : mat r i ce; {matricea de adiacenta} i , j , k : i nteger ; nr ci f r e : i nt eger ; {numar a ci f r el e de 1, i n condi t i i l e pr obl emei } GASI T : bool ean; {GASI T = TRUE daca s- a gasi t un ci cl u de l ungi me 4}Begin { PROGRAM PRINCIPAL }
CLRSCR;
wr i t e ( ' Dat i numar ul de noduri, n = ' ) ;
r eadl n ( n) ; wr i t e ( ' Dat i numar ul demuchii, m= ' ) ; r eadl n ( m) ; {Initializarea tuturor elementelor matricii de adiacenta cu zero}
f or i : = 1 t o n do begi n f or j : = 1 t o n do begi n A [ i , j ] : = 0 end; end; wri t el n;
1
2
5 4
3
k
Nod 1 2 3 4 5 i = 1 0 1 0 1 0
2 1 0 1 0 1 j = 3 0 1 0 1 04 1 0 1 0 0
5/19/2018 Probleme Rezolvate - 2005 - Pascal
45/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
47
{Completare matrice de adiacenta}
For i : = 1 t o m do Begi n Writeln (Dai extremitile muchiei i: ) Write (Dai vrful x = ); readln (x) ; Write (Dai vrful y = ); readln (y) ; A [x, y] := 1; A [y, x] := 1; {matricea este simetric} End; wr i t el n;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - GASI T : = FALSE; {pr esupunem ca nu exi st a un ci cl u de l ungi me 4} fo r i := 1 to n 1 do {i = i ndex el ement e de pe una di n liniile testate}
begi n fo r j := i + 1 to n do {j = i ndex el ement e de pe al t a linie testata}
begi n nrcifre := 0; {i ni t i al i zar e cont or pt . f i ecar e per eche t est at a} fo r k := 1 to n do {k = i ndex de coloana}
begi n i f ( A [i, k] = 1 ) AND ( A [j, k] = 1 ) t hen
nrcifre := nrcifre + 1; i f nr ci f r e >= 2 t hen
begi n GASIT := TRUE;
GOTO sfarsitend;
end; end; end;sfarsit: i f GASI T = TRUE t hen
wr i t el n ( Gr af ul cont i ne ci cl ur i de l ungi me 4 ) el se
wr i t el n ( Gr af ul NU cont i ne ci cl ur i de l ungi me 4 ) ; r eadl nEND.
ATESTAT - 2005 - 21 - Pentru un graf orientat Gcu nvrfuri i marce (n i m numere naturalcitite la intrare) s se scrie un program care s determine matricea drumurilor. Matricea se va afipe ecran linie cu linie.
Barem:- declaraii corecte de variabile: 1 punct- reprezentarea corect a grafului prin matricea de adiacen: 3 puncte- determinarea matricii drumurilor prin algoritmullui Roy-Warshall: 3 puncte- afiarea matricii drumurilor: 2 puncte- din oficiu: 1 punct
Rezolvare:Reamintim cteva noiuni din teoria grafurilor orientate.Un lan ( L ) ntr-un graf orientat = un ir de arce L = [a1 , a2ak , , ap],cu proprietatea c oricare arc akare un nod comun cak-1i cellalt nod comun cu ak+1 , pentru orice kdin mulimea2, p-1}. NU ARE IMPORTAN ORIENTAREA ARCELORExemplu:Pentru graful din figura alturat, lanuri cu extremitiln nodurile 1 i 4 sunt:L1 = (a1, a2, a3), L2 = (a1, a4, a5, a3), L3 = (a5, a3) se observ c
nu are importan orientarea arcelor.
1 2
4 3
a1
a2
a4
a3
a5
5/19/2018 Probleme Rezolvate - 2005 - Pascal
46/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
48
Un lan ntr-un graf orientat se numete drum (notat D) dac toate arcele sale au ACEEAIORIENTARE, dat de sensul deplasrii de la x0(extremitatea iniial a lui a1) la xp (extremitateafinal a lui ap). Vrfurile x0 i xp = extremitile lanului. De observat c, n cazul drumului,ARE IMPORTAN ORIENTAREA ARCELOR
Altfel spus, un drumntr-un graf orientateste un ir de vrfuri. Un drum se poate scrie fieca o succesiune de arce, fie ca o succesiune de vrfuri. Pentru graful alturat, avem drumurile:D1 = (1, 2, 3), D2 = (1, 2, 1, 3).
Matricea drumurilorunui graf G este o matrice Bdefinit astfel:
Pentru graful anterior, avem:
Algoritmul Roy-Warshall determin matricea drumurilor plecnd de la matricea deadiacenastfel:
Un element A [i, j] = 0 din matricea de adiacendevine 1 n matricea drumurilordacexist un vrf kastfel nct
A [i, k] = 1 i A [k, j] = 1,adic atunci cnd exist drum de la xila xki drum de la xkla xj. Aceast condiie se poate exprimai astfel:
A [i, j] = MIN ( A[i, k], A [k, j] )sau
A [i, j] = A[i, k] * A [k, j].
Transformarea propriu-zis pe care o presupune algoritmul Roy-Warshall poate fiexprimat astfel:for k := 1 to ndo begin
for i := 1 to ndo begin
if i kthen begin for j := 1 to ndo
begin if j k then
beginIF A [i, j] = 0 then A [i, j] := A [i, k] * A [k, j]
end end
end end
end;
1, dac exist drum n GB [i, j]= de la nodul xi la nodul xj 0, n caz contrar.
Matricea de ADIACEN:
Nod 1 2 3 4 1 0 1 1 0 A = 2 1 0 1 0 3 0 0 0 0
4 0 0 1 0
Matricea DRUMURILOR:
Nod 1 2 3 4 1 1 1 1 0 B = 2 1 1 1 0 3 0 0 0 0
4 0 0 1 0
5/19/2018 Probleme Rezolvate - 2005 - Pascal
47/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
49
program ATESTAT_2005_21_MATRICEA_DRUMURILOR_ALGORITMUL_ROY_WARSHALL;uses CRT;CONST nmax = 100;
TYPE mat r i ce = ar r ay [ 1. . nmax, 1. . nmax] of i nt eger ;VAR n, m : i nt eger; {n = numar ul nodur i l or; m = numar ul de muchi i di n gr af } x, y : i nt eger ; {ext r emi t at i al e unei muchi i } A : mat r i ce; {matricea de adiacenta} B : mat r i ce; {matricea drumurilor} i , j , k : i nt eger ;function MIN ( al f a, bet a : i nt eger) : i nt eger; begi n i f al f a
5/19/2018 Probleme Rezolvate - 2005 - Pascal
48/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
50
{Transformarea propriu-zisa - Algoritmul Roy-Warshall} {VARIANTA 1}
f or k : = 1 t o n do begi n f or i : = 1 t o n do begi n i f i k t hen begi n f or j : = 1 t o n do begi n i f j k t hen begi n I F B [ i , j ] = 0 t hen B [i, j] := MIN (B [i, k], B [k, j]) end end end end end;
wri t el n ( 'Varianta 1 - Matricea drumurilor este: ' ) ; f or i : = 1 t o n do begi n
wr i t el n; f or j : = 1 t o n do begi n wri t e ( B [ i , j ] : 3 ) ; {se l asa 3 pozi t i i pent ru f i ecare } {el ement al mat r i ci i } end; end;
{Transformarea propriu-zisa - Algoritmul Roy-Warshall} {VARIANTA 2}
f or k : = 1 t o n do begi n
f or i : = 1 t o n do begi n f or j : = 1 t o n do begi n I F B [ i , j ] = 0 t hen B [i, j] := B [i, k] * B [k, j] end end end; wri t el n;
wri t el n ( 'Varianta 2 - Matricea drumurilor este: ' ) ; f or i : = 1 t o n do begi n wr i t el n; f or j : = 1 t o n do begi n wri t e ( B [ i , j ] : 3 ) ; {se l asa 3 pozi t i i pent ru f i ecare } {el ement al mat r i ci i } end; end; r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
49/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
51
ATESTAT - 2005 - 22 - Pentru un graf orientat G cu n vrfuri i m arce (n i m sunt numernaturale citite la intrare), s se scrie un program care s construiasc i s afieze listele de adiacenale succesorilor vrfurilorgrafului sub form de liste liniare simplu nlnuite.Barem:- declaraii corecte de variabile: 2 puncte- generarea listelor de adiacen: 4 puncte- afiarea listelor: 3 puncte- din oficiu: 1 punct
Rezolvare:Pentru reprezentarea grafurilor orientatese pot folosia matricea de adiacenb listele de adiacen.La reprezentarea prin liste de adiacen, pentru orice vrf x se construiete o list L ( x )succesorilor vrfului x. Liste de adiacen pot fi reprezentate folosind tablouri sau structurdinamice de date.Exemplu: pentru graful alturat, listele de adiacen Lvor fi:
La reprezentarea listelor de adiacen folosind structuri dinamice de date (liste liniarnlnuite), vom considera un vector L(LISTA) cu ncomponente de tip pointer(referin, adres).
O component L [ i ] va pointa lanceputul listei de adiacen a nodului i.Un arc (x, y) al grafului este reprezentat prin extremitile xi y,Fiecare element al listei va avea dou componente:
-
NodSuccesor= y= extremitatea final a nodului curent- URM= informaia de legtur ctre urmtorul element al listei de adiacen.Vom face urmtoarele declaraii:
TYPELISTA = ^ element;
element = RECORDNodSuccesor: 1 . . n;URM : LISTA
END;
VAR L : array [ 1 . . n ] of LISTA ;
P : LISTA ; {variabil pointer de lucru }n, m, i : integer ;Iniializm toate componentele listei Lcu pointerul NIL, scriind:for i := 1 to n do
L [i] := NIL;Prezena n graf a unui arc (x, y) presupune crearea unei locaii de memorie cu NEW (P), urmat dcalificarea celor dou cmpuri (NodSuccesor i URM) ale noii locaii. Vom scrie:P^. NodSuccesor := y ;P^.URM := L [ x ] ;
L [ x ] := P ;
1
2
4
3
5 1
23
4
5
2
34
1
5
5
NIL
NIL
NIL
NIL
NIL
Nod Succesori1 : 2
2 : 33 : 4, 5
4 : 1, 5
5 :
5/19/2018 Probleme Rezolvate - 2005 - Pascal
50/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
52
program ATESTAT_2005_22_LISTE_DE_ADIACENTA ;
uses CRT;CONST nmax = 100;
TYPE LI STA = ELEMENT; ELEMENT = RECORD NodSuccesor : i nt eger ; URM : LI STA {poi nt er de l egat ur a spr e ur mat or ul nod di n l i st a} END;VAR L : ar r ay [ 1. . nmax] of LI STA; m, n, i : i nt eger ; { n = nr . de NODURI ; m = nr . de ARCE } P : LI STA ; { P = poi nt er de l ucr u} x, y : i nt eger ; { x, y = ext r emi t at i l e unui ar c }
Begin { PROGRAM PRINCIPAL }
CLRSCR; wr i t e ( ' Dat i numar ul de nodur i , n = ' ) ; r eadl n ( n) ; wri t el n; wr i t e ( ' Dat i numar ul de muchi i , m = ' ) ; r eadl n ( m) ; wri t el n;
{ Initializam toate componentele listelor de ADIACENTA cu pointerul NIL } f or i : = 1 t o n do begi n L [i] := NIL; end; wri t el n; {Completarea LISTELOR de adiacenta}
For i := 1 to m do Begi n Wri t el n ( ' Dat i extremitatile muchiei i: ' ) ; Wri t e ( ' Dat i varf ul x = ' ) ;
r eadl n ( x) ; Wri t e ( ' Dat i varf ul y = ' ) ;
r eadl n ( y) ;
NEW (P); P^.NodSuccesor := y ;
P^.URM := L [x];
L [x] := P;
End; wri t el n;
{Afisarea listelor de adiacenta pentru cele n noduri}
f or i : = 1 t o n do begi n wr i t e ( ' Nodul ' , i , ' are urmat or i i succesori : ' ) ;
P := L [i]; {P indic initial spre inceputul listei nodului i } whi l e P NIL do begi n
wr i t e (p^.NodSuccesor, ' - > ' ) ; P := P^.URM
end; wr i te ( ' NI L' ) ; wr i t el n;
wr i t el n end; r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
51/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
53
ATESTAT - 2005 - 23 - Dat un graf orientat Gcu nvrfuri i marce, s se scrie un program pricare:a) s se calculeze gradul interior, respectiv exterioral fiecrui vrfb) s se verifice dac graful are vrfuri izolateDatele de intrare se preiau din fiierul text INPUT.TXTsub forma urmtoare :
pe prima linie: n - reprezentnd numrul de vrfuriale grafului ;pe linia a doua : m - reprezentnd numrul de arceale grafului ;pe urmtoarele m linii, cte o pereche de numere, separate printr-un spaiu, ce reprezint
extremitatea iniial, respectiv finala arcului.Rezultatele se vor afia pe ecran.
Barem:- declaraii corecte de variabile: 1 punct- citirea corect a datelor din fiier: 1 punct- reprezentarea corect a grafului prin matricea de adiacen: 2 puncte- realizarea punctului a): 2 puncte- realizarea punctului b): 2 puncte- afiarea rezultatelor: 1 punct- din oficiu: 1 punct
Rezolvare:Vom reprezenta graful prinlistele de adiacen(vezi problema anterioar ATESTAT_2005_22).Folosim 2 vectori GradExt, respectiv GradInt, fiecare cu cte ncomponente, n care vom memorgradul exterior i interior al fiecrui vrf. Dac pentru un vrf suma celor dou grade este zeroacel vrf este izolat.Exemplu: pentru graful alturat, fiierulGRAF.TXT, de pe discul C:, va aveaconinutul:6 {numrul de noduri}8 {numrul de arce}1 21 32 32 43 43 54 14 5De asemenea, se observ c vrful 6 este izolat.
program ATESTAT_2005_23_GRADE_INT_SI_EXT_CU_LISTE_DE_ADIACENTA ;
uses CRT;CONST nmax = 100;
TYPE LISTA = ^ELEMENT; ELEMENT = RECORD NodSuccesor : i nt eger; URM : LI STA {poi nt er de l egat ur a spr e ur mat or ul nod di n l i st a} END;VAR L : array [1..nmax] of LISTA; m, n, i : i nt eger ; { n = nr . de NODURI ; m = nr . de ARCE } P : LI STA ; { P = poi nt er de l ucr u} x, y : i nt eger ; { x, y = ext r emi t at i l e unui ar c } Gr adI nt , Gr adExt : ar r ay [ 1. . nmax] of i nt eger ; S : i nt eger ; { S = suma gr adel e i nt er i or si ext er i or pt . un var f }
1
2
4
3
5
6
NOD GradExt GradInt Suma grade
1 2 1 32 2 1 3
3 2 2 4
4 2 2 4
5 0 2 2
6 0 0 0
5/19/2018 Probleme Rezolvate - 2005 - Pascal
52/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
54
f : TEXT; {f i si er i n car e memor am i nf or mat i i l e despre GRAF } l i ni e : STRI NG ; { "l i ni e" = o l i ni e di n f i si er ul t ext GRAF. TXT } ER : i nt eger ; { var i abi l a er oar e di n apel ul pr ocedur i i VAL }
Begin { PROGRAM PRINCIPAL }
CLRSCR; wri t el n;
ASSI GN ( f , ' C: \ GRAF. TXT' ) ; RESET ( f ) ;
{ Citim din fisier prima componenta = numarul de noduri }
readln (f, n);
wr i t el n ( ' Numar ul de nodur i , n = ' , n) ; wri t el n;
{ Initializam toate componentele listelor de ADIACENTA cu pointerul NIL }
f or i : = 1 t o n do begi n L [ i ] : = NI L; end; { Citim din fisier a doua componenta = numarul de arce }
readln (f, m);
wr i t el n ( ' Numar ul de muchi i , m = ' , m) ;
wri t el n;
{ Citim din fisier urmatoarele "m" linii ce contin extremitatile arcelor. }
{ Cu aceste extremitati construim LISTELE de ADIACENTA }
For i : = 1 t o m do Begi n readln (f, linie);
VAL ( linie [1], x , ER ); {transformam sirul linie [1] in numarul x } Wri t el n ( ' Ext remi t at ea i ni t i al a a muchi ei ' , i , ' este x = ' , x) ;
VAL ( linie [3], y , ER ); {transformam sirul linie [3] in numarul y }
Wr i t el n ( ' Ext r emi t at ea f i nal a a muchi ei ' , i , ' est e y = ' , y) ;
{ Construirea LISTELOR DE ADIACENTA }
NEW ( P) ; P . NodSuccesor : = y ; P . URM : = L [ x] ; L [ x] : = P; End; wri t el n;
{Afisarea listelor de adiacenta pentru cele n noduri - OPTIONAL}
f or i : = 1 t o n do begi n wr i t e ( ' Nodul ' , i , ' are urmat or i i succesor i : ' ) ; P : = L [ i ] ;
whi l e P NI L do
begi n wr i t e ( p . NodSuccesor , ' - > ' ) ;
P : = P . URM end;
wr i te ( ' NI L' ) ; wr i t el n;
wr i t el n end; wri t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
53/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
55
{ Initializare elemente vectori GradExt si GradInt }
f or i : = 1 t o n do begi n Gr adExt [ i ] : = 0; Gr adI nt [ i ] : = 0; end;
{ Determinam gradele exterior si interior pt. fiecare nod }
f or i : = 1 t o n do begi n P : = L [ i ] ;
whi l e P NI L do begi n
INC ( GradExt [ i ] ) ; INC ( Gr adI nt [ P . NodSuccesor] ) ;
P : = P . URM end; wr i t el n
end; wr i t el n;
wr i t el n ( 'Gradele nodurilor sunt urmatoarele: ' ) ; wr i t el n; f or i : = 1 t o n do
begi n wr i tel n ( ' GradExt ( ' , i , ' ) = ' , GradExt [i] ) ; wr i tel n ( ' GradI nt ( ' , i , ' ) = ' , GradInt [i] ) ; S : = Gr adExt [ i ] + Gr adI nt [ i ] ; wri t el n; wri t el n ( 'Suma gradelor = ' , S ) ; wri t el n ; wri t el n;
i f GradExt [ i ] + GradInt [ i ] = 0 t hen wr i tel n ( ' Nodul ' , i , ' es te IZOLAT') ; end; r eadl nEND.
ATESTAT - 2005 - 24 - Se d un graf orientat Gcu nvrfuri i marce, reprezentat n memoriprin matricea de adiacen. S se scrie un program care, pornind de la matricea drumurilocorespunztoare grafului, s verifice dac:a). graful are vrfuri izolate;b). graful conine circuite(n i m sunt numere naturale citite la intrare).
Barem:
-
declaraii corecte de variabile: 1 punct-
reprezentarea corect a grafului prin matricea de adiacen: 2 puncte- determinarea matricii drumurilorprin algoritmullui Roy-Warshall: 2 puncte- realizarea punctului a): 2 puncte- realizarea punctului b): 2 puncte- din oficiu: 1 punct
5/19/2018 Probleme Rezolvate - 2005 - Pascal
54/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
56
Rezolvare:Considerm graful din figura alturat.Notm cu GradExt, respectiv GradInt, gradulexteriori interioral fiecrui vrf. Dac pentru un vrf suma celor dou grade
este zero, acel vrf este izolat. De asemenea, un vrf este izolatdac i
numai dac linia i i coloanai dinmatricea de ADIACENau toateelementeleNULE.
Un drum ntr-un graf orientat este un ir devrfuri. Un drum se poate scrie fie ca osuccesiune de arce, fie ca o succesiune devrfuri.Dac toate arceleunui drumsunt distincte, iar primuli ultimulnod coincid, drumul se numetecircuit.Dac toate vrfurile unui circuit, cu excepia primului i ultimului, sunt distincte, circuitul esteelementar.Pentru graful alturat, avem circuitele:C1 = (1, 2, 3, 4, 1, 3, 4, 1), C2 = (1, 3, 4, 1, 2, 3, 4, 1)precum i circuiteleelementare:C3 = (1, 2, 4, 1), C4 = (1, 3, 4, 1), C5 = (1, 2, 3, 4, 1)Pentru graful de mai sus, avem:
Pentru a verifica dac graful conine noduri izolate, declarm doi vectori zeropelinsi zeropecol incare memorm numarul de zero-uri de pe fiecare linie, respectiv fiecare coloan. Apoi, pentru fiecarelinie din matricea de ADIACEN, verificam dac este ndeplinit condiia
( zeropelin [ i ] = n) AND (zeropecol [ i ] = n)adic, simultan pe linia i i coloana i avem numai zero-uri (n zero-uri).Se observ c, n matricea de ADIACEN linia 6i coloana 6au toate elementele nule. Rezultc nodul 6este nod izolat.Pentru a verifica dac graful are circuite, se verific dac matricea drumurilor conine elementeegale cu 1pe diagonala principal. Din faptul c matricea drumurilor are numai elemente de 1pediagonala principal deducem doar c fiecare vrf aparine unui circuit; NU rezult c exist uncircuit care trece prin toate nodurile grafului.
program ATESTAT_2005_24_CIRCUITE_MATRICEA_DRUMURILOR_ALGORITMUL_ROY_WARSHALL;
uses CRT;CONST nmax = 100;
TYPE mat r i ce = ar r ay [ 1. . nmax, 1. . nmax] of i nt eger ;
1
2
4
3
5
6
NOD GradExt GradInt Suma grade
1 2 1 3
2 2 1 33 2 2 4
4 2 2 4
5 0 2 2
6 0 0 0
Matricea de ADIACEN:
Nod 1 2 3 4 5 6 1 0 1 1 0 0 0
A = 2 0 0 1 1 0 03 0 0 0 1 1 04 1 0 0 0 1 0
5 0 0 0 0 0 0 6 0 0 0 0 0 0
Matricea DRUMURILOR:
Nod 1 2 3 4 5 6 1 1 1 1 1 1 0
B = 2 1 1 1 1 1 03 1 1 1 1 1 0
4 1 1 1 1 1 0
5 0 0 0 0 0 0 6 0 0 0 0 0 0
5/19/2018 Probleme Rezolvate - 2005 - Pascal
55/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
57
VAR n : i nt eger ; {n = numar ul nodur i l or } m : i nt eger ; {numarul de muchi i di n gr af } x, y : i nt eger ; { ext r emi t at i al e unei muchi i } A : matr i ce; {matr i cea de adi acent a} B : mat r i ce; {mat r i cea dr umur i l or} i , j , k : i nt eger ; zer opel i n : ar r ay [ 1. . nmax] of i nt eger ; {vect or i n car e memor am numar ul zero- ur i l e gasi t e pe o l i ni e } zer opecol : ar r ay [ 1. . nmax] of i nt eger ; {vect or i n care memoramnumarul zero- ur i l e gasi t e pe o col oana } GASI T : bool ean ; {t est eaza daca exi st a ci r cui t e i n gr af }
function MIN ( al f a, bet a : i nt eger) : i nt eger; begi n i f al f a
5/19/2018 Probleme Rezolvate - 2005 - Pascal
56/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
58
{ Deoarece se pleaca de la matricea de ADIACENTA, se va face }
{ Initializarea matricii DRUMURILOR B cu matricea de ADIACENTA A }
f or i : = 1 t o n dobegi n f or j : = 1 t o n do begi n
B [ i , j ] : = A [ i , j ] ; end;
end;
{Transformarea propriu-zisa - Algoritmul Roy-Warshall}
f or k : = 1 t o n do begi n
f or i : = 1 t o n do begi n
i f i k t hen begi n f or j : = 1 t o n do begi n
i f j k t henbegi n I F B [ i , j ] = 0 t hen B [ i , j ] : = MI N ( B [ i , k] , B [ k, j ] )
end end
end end
end; wri t el n ( 'Matricea drumurilor este: ' ) ; f or i : = 1 t o n do
begi n wri t el n; f or j : = 1 t o n do begi n
wri t e ( B [ i , j ] : 3 ) ; {se l asa 3 pozi t i i pent ru f i ecare } {el ement al mat r i ci i }
end;end;
{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - }
{ Verificam, in matricea de ADIACENTA, daca exista varfuri IZOLATE }
f or i : = 1 t o n do begi n zer opel i n [ i ] : = 0; f or j : = 1 t o n do begi n i f A [ i , j ] = 0 t hen zer opel i n [ i ] : = zer opel i n [ i ] + 1; end
end;
f or j : = 1 t o n do begi n zer opecol [ j ] : = 0; f or i : = 1 t o n do begi n i f A [ i , j ] = 0 t hen zer opecol [ j ] : = zer opecol [ j ] + 1; end end; wr i t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
57/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
59
f or i : = 1 t o n do begi n wr i tel n ( ' zeropel i n [ ' , i , ' ] = ' , zeropel i n [ i ] ) ; wr i tel n ( ' zeropecol [ ' , i , ' ] = ' , zeropecol [ i ] ) ; wr i t el n end;
f or i : = 1 t o n do begi n i f ( zeropelin [ i ] = n) AND (zeropecol [ i ] = n) t hen wr i tel n ( ' Var f ul ' , i, ' es te izolat') ; wr i t el n end;
{ Verificam, in matricea de DRUMURILOR, daca exista 1 pe diagonala principala }
GASI T : = FALSE; {pr esupunemca nu exi st a ci r cui t e i n gr af } f or i : = 1 t o n do begi n i f B [ i , i ] = 1 t hen GASI T : = TRUE end; i f GASI T = TRUE t hen wri t el n ( ' Graf ul cont i ne ci r cui t e' )
el se wri t el n ( ' Graf ul NU cont i ne ci rcui t e' ) ; r eadl nEND.
FUNCII I PROCEDURI RECURSIVE
ATESTAT - 2005 - 25 - S se scrie un program care citete de la tastatur un numr natural napeleaz o funcie recursiv, care ntoarce valoarea produsului:
p (n) = 1 * 3 * 5 ** (2n+1).
Exemple: pentru n = 0, seva afia p (0) = 1, adic 2 * 0 + 1pentru n = 3, se va afia p (3) = 105, adic 1 * 3 * 5 * 7Barem:- corectitudinea definiiei recursive: 3 puncte- declaraie corect de funcie: 2 puncte- condiia de ieire din funcie: 2 puncte- corectitudine sintactic: 1 punct- din oficiu: 1 punct
Rezolvare: Algoritmul recursiv pentru calcularea produsului din enun este asemntor cu cel pentrcalcularea lui xn n variant recursiv.
program ATESTAT_2005_25_PRODUS_RECURSIV;var i , n, p : i nt eger ;function PRODUS ( m : i nt eger) : i nt eger ; begi n i f m = 0 t hen PRODUS : = 1 el se PRODUS : = (2*m + 1) * PRODUS (m - 1) end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
58/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
60
Begin { PROGRAM PRINCIPAL }
wri t e ( ' Dat i n = ' ) ; r eadl n ( n) ;
p : = PRODUS (n);
wr i tel n ( ' p ( ' , n, ' ) = ' , p) ; r eadl nEND.
ATESTAT - 2005 - 26 - S se scrie un program prin care se citete de la tastatur numrul natural n.Programul trebuie s apeleze o funcie recursiv, care s ntoarc valoarea sumei S (n), undeS (n) = 2 + 5 + 8 + ... + (2 + 3*n).Valoarea pentru numrul n este citit n programul principal. Valoarea calculat de funcie va fiafiat pe ecran tot n programul principal.
Exemplu: pentru n = 3, se va afia valoarea 26 ( S (3) = 2 + 5 + 8 + 11 ).Barem:- corectitudinea definiiei recursive: 3 puncte- declaraie corect de funcie: 2 puncte
-
condiia de ieire din funcie: 2 puncte- corectitudine sintactic: 1 punct- din oficiu: 1 punct
Rezolvare: Algoritmul recursiv pentru calcularea sumei din enun este asemntor cu cel pentrucalcularea, n variant recursiv, a sumei S = 1 + 2 + 3 + + n.
program ATESTAT_2005_26_SUMA_RECURSIVA;var i , n, s : i nteger ;
function SUMA ( m : i nt eger) : i nt eger ; begi n i f m = 0 t hen SUMA : = 2 el se SUMA : = ( 2 + 3 * m) + SUMA (m-1 ) end;
Begin { PROGRAM PRINCIPAL }
wri t e ( ' Dat i n = ' ) ; r eadl n ( n) ;
s : = SUMA (n);
wr i tel n ( ' S ( ' , n, ' ) = ' , s) ; s: =2; f or i : = 1 t o n do begi n wr i tel n ( ' SUMA ( ' , i , ' ) = ' , SUMA (i) ) ; s : = s + SUMA (i); end; r eadl nEND.
5/19/2018 Probleme Rezolvate - 2005 - Pascal
59/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
61
ATESTAT - 2005 - 27 - Se d un numr natural nintrodus de la tastatur. Scriei un program carcalculeaz suma cifrelor acestui numr. Programul trebuie s apeleze o funcie recursiv care sntoarc valoarea sumei.Barem:- corectitudinea definiiei recursive: 3 puncte- declaraie corect de funcie: 2 puncte- condiia de ieire din funcie: 2 puncte- corectitudine sintactic: 1 punct- din oficiu: 1 punct
Rezolvare: Pentru numrul x, trebuie s determinm, mai nti, numrul de cifre i apoi vomcalcula suma cifrelor. Vom defini dou funcii NRCIFREi SUMACIFRE, n acest scop
program ATESTAT_2005_27_SUMA_CIFRE_NUMAR_X;{Fol osi nd o f unct i e recur si va, sa se cal cul eze suma ci f r el or unui nr . nat ur al x}const nmax = 100;
TYPE vect or = ar r ay [ 1. . nmax] of i nt eger ;var s , x, x1, n, i : i nt eger ; y : vect or ; k : BOOLEAN;function NRCIFRE ( y : i nt eger ) : i nt eger; var m : i nt eger ; begi n i f y = 0 t hen m : = 1 el se begi n m : = 0; whi l e y 0 do begi n y : = y DI V 10;
m : = m + 1 end end; NRCI FRE : = m end;function SUMACIFRE ( nr : i nt eger) : i nt eger; var s1, i : i nt eger ; begi n s1 : = 0; f or i : = 1 t oNRCIFRE (nr) do begi n S1 : = s1 + y [ i ] ;
end; SUMACI FRE : = s1 end;
Begin { PROGRAM PRINCIPAL }
wr i t e ( ' I nt r oducet i un numar nat ur al x = ' ) ; r eadl n ( x) ;
n : =NRCIFRE (x); wr i tel n ( ' Numarul ' , x, ' are ' , n, ' ci f re' ) ; wri t el n;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
60/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
62
x1 : = x; {conser vam val oar ea numar ul ui i ni t i al x, f ol osi nd auxi l i ar ul x1} f or i : = 1 t o n do begi n y [ i ] : = x1 MOD 10; wr i t el n ( ' y [ ' , i , ' ] = ' , y [ i ] ) ; x1 : = x1 DI V 10; end; s : = SUMACIFRE (x); wri t el n ( ' Suma ci f rel or numarul ui ' , x, ' = ' , s) ; r eadl nEND.
ATESTAT - 2005 - 28 - Se d un numr natural nn baza 10i un numr natural b(2
5/19/2018 Probleme Rezolvate - 2005 - Pascal
61/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
63
wri t el n; wr i t e ( ' Numar ul bi nar echi val ent l ui ' , ZECI MAL, ' est e ' ) ; f or i : = n downto 1 do begi n wr i t e ( R[ i ] ) ; end; r eadl nEND.
program ATESTAT_2005_28_TRANSFORMARE_BAZA_10_IN_BAZA_B_VARIANTA_ITERATIVA_2;uses CRT;t ype vect or = ar r ay [ 1. . 100] of i nt eger ;VAR ZECI MAL, BI NAR, nr10 : i nt eger; {numarul zeci mal } nr 2i nver sat , nr2 : i nt eger ; {numar bi nar i nver sat r espect i v nr bi nar f i nal } R : vect or ; baza, n, i , j , k, res t : i nteger ;Begin { PROGRAM PRINCIPAL }
cl r scr ; wr i t e ( ' Dat i numar ul zeci mal nr 10 = ' ) ; r eadl n ( nr 10) ; wr i t e ( ' Dat i noua baza = ' ) ; r eadl n ( baza) ;
i : = 0; ZECI MAL : = nr 10; whi l e nr 10 0 do begi n r est : = nr10 MOD baza; i : = i + 1; R [ i ] : = rest ; nr10 : = nr10 DI V baza; end;
n := i;
wr i t e ( ' Numar ul i n baza ' , baza, ' echi val ent est e ' ) ; f or i : = n downto 1 do begi n wr i t e ( R[ i ] ) ; end; r eadl nEND.
program ATESTAT_2005_28_TRANSFORMARE_BAZA_10_IN_BAZA_2_VARIANTA_RECURSIVA;
varn: i nt eger ;
b: byte;
procedur e conversie ( x: i nt eger ; b: byt e) ; var r : byte; begi n i f x>0 t hen begi n r : =x mod b; conversie (x div b, b); wr i t e( r ) ; end; end;
5/19/2018 Probleme Rezolvate - 2005 - Pascal
62/77
Probleme rezolvate de programare Subiecte propuse la ATESTAT
64
Begin { PROGRAM PRINCIPAL }
wri t e ( ' Dat i n = ' ) ; r eadl n