Probleme de informatică
  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

   Home Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2018
Bacalaureat 2018 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2018
Subiecte si rezolvări 2010-2018
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Olimpiada
Clasele V-VI
Clasele VII-VIII
Clasa a IX-a
Clasa a X-a
Clasele XI-XII
Noţiuni teoretice
Metode de sortare
Metoda backtracking


Metode de sortare  

Sortare stabilind poziţia definitivă prin numărare
Această metodă constă în cons­tru­irea unui nou tablou B care are aceeaşi dimensiune ca şi tabloul A în care depunem ele­mentele din A, ordonate crescător.
Vom lua fiecare element şi îl vom compara cu fiecare alt element din şir pentru a putea reţine în variabila k numărul elementelor care sunt mai mici decât ele­men­tul considerat. Astfel, vom afla poziţia pe care trebuie să-l punem pe acesta în şirul B. Da­că în problemă avem nevoie de şirul ordonat tot în tabloul A, vom copia în A întreg tabloul B.


Subalgoritm Numărare(n,A)
1: pentru i=1,n execută
2:     k = 0
3:     pentru j=1,n execută
4:         dacă (A[i] > A[j]) atunci
5:             k = k + 1            { numărăm câte elemente sunt mai mici decât A[i] }
6:     B[k+1] = A[i]            { pe A[i] îl punem pe poziţia corespunzătoare din B }
7: A = B         { copiem peste şirul A întreg şirul B }
Exemplu

     Fie tabloul A cu 4 elemente: 7, 2, 3, –1.

i

j

Relaţia

k

bk + 1

1

1

i = j

0

 

1

2

7 > 2

1

 

1

3

7 > 3

2

 

1

4

7 > –1

3

b4 = 7

2

1

2 < 7

0

 

2

2

i = j

0

 

2

3

2 < 3

0

 

2

4

2 > –1

1

b2 = 2

3

1

3 < 7

0

 

3

2

3 > 2

1

 

3

3

i = j

1

 

3

4

3 > –1

2

b3 = 3

4

1

–1 < 7

0

 

4

2

–1 < 2

0

 

4

3

–1 < 3

0

 

4

4

i = j

0

b1 = –1

Algoritmul funcţionează în această formă dacă elementele tabloului A sunt distincte, altfel în B vor rămâne elemente necopiate din A, deoarece două elemente egale se vor copia în B pe aceeaşi poziţie. De exemplu, pentru un tabloul A cu 4 elemente: 7, 2, 3, 3 se va obţine 2, 3, 0, 7 dacă în B am avut iniţial doar elemente nule. 
Această situaţie se poate remedia în 2 moduri:
1. mai parcurgem o dată şirul final şi toate elementele care nu respectă relaţia de ordine le modificăm atribuindu-le valoarea din stânga. Astfel, din şirul 2, 3, 0, 7 vom obţine 2, 3, 3, 7.
Algoritmul modificat este următorul:


Subalgoritm Numărare(n,a)
1: pentru i=1,n execută
2:    k = 0
3:    pentru j=1,n execută
4:        dacă (a[i] > a[j]) atunci
5:            k = k + 1                                                                                                
6:    b[k+1] = a[i]                                                                                                  
7: a = b          
8: pentru i=1,n-1 execută
9:     dacă  a[i] >= a[i+1] atunci
10:        a[i+1] = a[i]

2.  înainte de atribuirea b[k+1] = a[i] verificăm dacă b[k+1] ¹ a[i] şi cât timp e fals mărim pe k. Rezultatul este acelaşi.
Algoritmul modificat este următorul:


Subalgoritm Numărare(n,a)
1: pentru i=1,n execută
2:       k = 0
3:       pentru j=1,n execută
4:           dacă (a[i] > a[j]) şi (i <> j) atunci
5:               k = k + 1                                                                                             
6:      câttimp  b[k+1] = a[i] execută  {cat timp în B a fost deja pus un element cu aceeasi valoare}
8:                 k = k + 1
9:      b[k+1] = a[i]                                                                                                
10: a = b        

Pentru acest algoritm de sortare nu putem spune că există caz favorabil, nefavorabil sau mediu, deoarece numărul de paşi efectuaţi este n2 indiferent de structura datelor de intrare. Aşadar, ordinul de complexitate este Θ(n2).




  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (106)
6. Probleme diverse (13)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (47)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (18)

Calculatoare si accesorii second hand
Copyright 2009-2017 Muresan Vasile Ciprian - mcip.ro