Reședință - Portal SEI Portalul educațional SEI  Admitere Admitere Bacalaureat Bacalaureat Titularizare Titularizare Euro 200 Euro 200 Bani de Liceu Bani de Liceu
Găzduire WEB pentru școli și licee Găzduire WEB pentru școli, licee și instituții educaționale Dictionare online Dicționare online Subiecte examene naționale "2007-2008" Subiecte examene naționale "2007-2008"
Subiecte examene naționale începând cu 2002 Subiecte examene naționale începând cu 2002 .campion .campion
SIVECO Romania  Ministerul Educației și Cercetării



  Răspunde la acest subiectSubiect nou Sondaj nou

> Problema informatica, Varianta bac
Ratzian
Trimis: 13 Jul 2008, 06:06 PM


Începător
*

Grup: Members
Mesaje: 2
Înscris: 13 Jul 08


Problema se afla in varianta 1 subiectul 2 punctul 2, info intensiv - pascal proba E (Bac 2008).

Cate grafuri neorientate, distincte, cu 4 varfuri se pot construi? Doua grafuri se considera distincte daca matricele lor de adiacenta sunt diferite.

a) 24
b) 4
c) 4^6
d) 2^6

Va rog sa-mi spuneti si o metoda de rezolvare. Multumesc.
Mesaj personal
Top
Sebastian C.
Trimis: 13 Jul 2008, 08:27 PM


Utilizator avansat
****

Grup: Members
Mesaje: 757
Înscris: 22 Jun 05


Matricea de adiacenta (o matrice patratica de diminesiune egala cu numarul de muchii) a unui graf neorientat este unic determinata de elementele de deasupra (sau de sub) diagonala principala, deoarece a[ i ][ j ] = a[ j ][ i ], pentru i <> j, iar a[ i ][ i ] = 0.
Astfel, problema se reduce la a numara in cate moduri se pot completa elementele de deasupra diagonalei principale. Pentru o matrice de dimnesiune n, numarul elementelor de deasupra diagonalei principale este n(n-1) / 2. In cazul de fata n = 4, iar deasupra diagonalei principale exista 6 elemente. Valorile pe care le poate lua un element din matricea de adiacenta sunt 0 si 1. Adica fiecare din cele 6 elemente poate lua 2 valori. Asta inseamna ca vor exista 2^6 moduri de completa matricea de adicenta (Se poate privi ca o functie f: {1, 2,..., 6} -> {0, 1}, unde multimea de definintie reprezinta elemetele deasupra diagonalei principale. Numarul de astfel de functii este card( B )^card(A) = 2^6). Acesta este si numarul de grafuri neorientate cu 4 noduri.

O alta solutie. Numarul maxim de muchii pe care il poate avea un graf neorientat (graf complet) este n(n-1)/2, in cazul nostru 6. Putem genera grafuri alegand din multimea de muchii zero, una sau mai multe muchii. Numarul de grafuri pe care le putem forma va fi egal cu numarul de submultimi ale multimii muchiilor. Cum multimea muchiilor are 6 elemente, vor exista 2^6 submultimi. Sau, dupa cum spuneam, alegem zero muchii - se poate alege in Comb(6, 0) moduri -, o muchie - se poate face in Comb(6, 1) moduri-, doua muchii - in Comb(6, 2) moduri-, ..., sase muchii - in Comb(6, 6) moduri- . Adunand aceste combinari se obtine 2^6.

Am obtinut acelasi rezultat. Asta e bine. Eu stiam ca la metode diferite se obtin rezultate... diferite. biggrin.gif

Varianta corecta este: d) 2^6.

if ( ai inteles ) smile.gif
else astept intrebari;

cool20.gif


--------------------
Când vezi că ai aceeași părere cu majoritatea,
e bine să mai reflectezi o dată.

-- Mark Twain
Mesaj personal
Top
Ratzian
Trimis: 13 Jul 2008, 11:38 PM


Începător
*

Grup: Members
Mesaje: 2
Înscris: 13 Jul 08


smile.gif

Multumesc mult, am inteles acum.

QUOTE
Matricea de adiacenta (o matrice patratica de diminesiune egala cu numarul de muchii)


Totusi am o nelamurire... Dimensiunea matricii nu e egala cu nr. de noduri?
Mesaj personal
Top
Sebastian C.
Trimis: 14 Jul 2008, 11:42 AM


Utilizator avansat
****

Grup: Members
Mesaje: 757
Înscris: 22 Jun 05


Da, asa este. Dimensiunea matricei de adiacenta este egala cu nr. de noduri.


--------------------
Când vezi că ai aceeași părere cu majoritatea,
e bine să mai reflectezi o dată.

-- Mark Twain
Mesaj personal
Top
A_A 20
Trimis: 31 Jan 2012, 08:40 PM


La prima intervenție


Grup: Members
Mesaje: 1
Înscris: 31 Jan 12


Varianta C++
a) Scrieti definitia completa a subprogramului cif, care primeste prin intermediul parametrului nr un numar natural de cel mult 9 cifre si furnizeaza prin intermediul parametrilor x si y prima cifra, respectiv ultima cifra a numarului primit prin parametrul nr.
b)Fisierul evaluare.in contine, pe o linie, un sir de maximum 1000 de nr naturale, fiecare avand maximum 9 cifre, separate prin cate un spatiu. Scrieti un program care cireste sirul de numere din fisierul evaluare.in construieste si afiseaza pe ecran cel mai mare numar ce poate fi format cu ajutorul celor mai mari doua cifre dintre cifrele cele mai semnificative ale numerelor din sir si a celor mai mici doua cifre dintre cifrele unitatilor numerelor din sir, folosind apeluri utile ale subprogramului cif.
Va rog cine ma poate ajuta?? Multumesc!!!

Acest mesaj a fost modificat de către A_A 20 la data 31 Jan 2012, 08:41 PM
Mesaj personal
Top
0 utilizator(i) citesc acest subiect (0 vizitatori și 0 utilizatori anonimi)
0 utilizator(i):

Opțiuni Răspunde la acest subiectSubiect nou Sondaj nou

 

 
  © 2002 SIVECO Romania SA. All Rights Reserved