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 (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
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 (12)

   Home Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2017
Bacalaureat 2017 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2017
Subiecte si rezolvări 2010-2017
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
Teme proiect
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Subiecte atestat 2014 CNLR
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  

Ordonare pe baza cifrelor
Ordonarea pe baza cifrelor este algoritmul folosit de către maşinile de sortare a cartelelor, care se mai găsesc la ora actuală numai în muzeele de calculatoare. Cartelele sunt organizate în 80 de coloane, şi fiecare coloana poate fi perforata în 12 poziţii. Sortatorul poate fi “programat” mecanic să examineze o coloana data a fiecărei cartele dintr-un pachet şi să distribuie fiecare cartela într-una dintre cele 12 cutii, în funcţie de poziţia perforata. Un operator poate apoi să strângă cartelele cutie cu cutie, astfel încât cartelele care au prima poziţie perforata să fie deasupra cartelelor care au a doua poziţie perforata s.a.m.d.
Pentru cifre zecimale sunt folosite numai 10 poziţii în fiecare coloana. (Celelalte două poziţii sunt folosite pentru codificarea caracterelor nenumerice). Un număr având d cifre ar ocupa un câmp format din d coloane. Întrucât sortatorul de cartele poate analiza numai o singura coloana la un moment dat, problema sortării a n cartele în funcţie de un număr având d cifre necesita un algoritm de sortare.
Intuitiv, am putea dori să sortam numere în funcţie de cea mai semnificativa cifra, să sortam recursiv fiecare dintre cutiile ce se obţin, şi apoi să combinam pachetele în ordine. Din nefericire, întrucât cartelele din 9 dintre cele 10 cutii trebuie să fie păstrate pentru a putea sorta fiecare dintre cutii, aceasta procedura generează teancuri intermediare de cartele care trebuie urmărite.
Ordonarea pe baza cifrelor rezolva problema sortării cartelelor într-un mod care contrazice intuiţia, sortând întâi în funcţie de cea mai puţin semnificativa cifra. Cartelele sunt apoi combinate într-un singur pachet, cele din cutia 0 precedând cartelele din cutia 1, iar acestea din urma precedând pe cele din cutia 2 şi aşa mai departe. Apoi întregul pachet este sortat din nou în funcţie de a doua cifra cea mai puţin semnificativa şi recombinat apoi într-o maniera asemănătoare. Procesul continua până când cartelele au fost sortate pe baza tuturor celor d cifre.
De remarcat că în acel moment cartelele sunt complet sortate în funcţie de numărul având d cifre. Astfel, pentru sortare sunt necesare numai d treceri prin lista de numere. În figura 1.16 este ilustrat modul de operare al algoritmului de ordonare pe baza cifrelor pe un “pachet” de şapte numere de câte trei cifre.
Este esenţial ca sortarea cifrelor în acest algoritm să fie stabila. Sortarea realizata de către un sortator de cartele este stabila, dar operatorul trebuie să fie atent să nu schimbe ordinea cartelelor pe măsura ce acestea ies dintr-o cutie, chiar daca toate cartelele dintr-o cutie au aceeaşi cifra în coloana aleasa.
Într-un calculator care funcţionează pe baza de acces secvenţial aleator, ordonarea pe baza cifrelor este uneori utilizata pentru a sorta înregistrările de informaţii care sunt indexate cu chei având câmpuri multiple. De exemplu, am putea dori să sortam date în funcţie de trei parametri: an, luna, zi. Am putea executa un algoritm de sortare cu o funcţie de comparare care, considerând doua date calendaristice, compara anii, şi daca exista o legătură, compara lunile, iar daca apare din nou o legătură, compara zilele. Alternativ, am putea sorta informaţia de trei ori cu o sortare stabila: prima dupa zi, următoarea dupa luna, şi ultima dupa an.

Figura 1.16 Modul de funcţionare al algoritmului de ordonare pe baza cifrelor pe o lista de şapte numere a câte 3 cifre. Prima coloana este intrarea. Celelalte coloane prezintă lista dupa sortări succesive în funcţie de poziţiile cifrelor în ordinea crescătoare a semnificaţiei. Săgeţile verticale indica poziţia cifrei dupa care s-a sortat pentru a produce fiecare lista din cea precedenta.

Pseudocodul pentru algoritmul de ordonare pe baza cifrelor este evident. Următoarea procedura presupune că într-un tablou A având n elemente, fiecare element are d cifre, cifra 1 este cifra cu ordinul cel mai mic, iar cifra d este cifra cu ordinul cel mai mare.


Subalgoritm Ordonare-Pe-Baza-Cifrelor(A, d)
1: pentru i ← 1, d executa
2:       foloseşte o sortare stabila pentru a sorta tabloul A dupa cifra i

Corectitudinea algoritmului de ordonare pe baza cifrelor poate fi demonstrata prin inducţie dupa coloanele care sunt sortate. Analiza timpului de execuţie depinde de sortarea stabila folosita ca algoritm intermediar de sortare. Când fiecare cifra este în intervalul [1, k], iar k nu este prea mare, sortarea prin numărare este opţiunea evidenta. Fiecare trecere printr-o mulţime de n numere a câte d cifre se face în timpul Θ(n + k). Se fac d treceri, astfel încât timpul total necesar pentru algoritmul de ordonare pe baza cifrelor este Θ(dn + kd). Când d este constant şi k = Θ(n), algoritmul de ordonare pe baza cifrelor se executa în timp liniar.
Unii informaticieni considera că numărul biţilor într-un cuvânt calculator este Θ(log2 n). Pentru exemplificare, să presupunem că d log2 n este numărul de biţi, unde d este o constantă pozitivă.
Atunci, daca fiecare număr care va fi sortat încape într-un cuvânt al calculatorului, îl vom putea trata ca pe un număr având d cifre reprezentat în baza n. De exemplu, să consideram sortarea a 1 milion de numere având 64 de biţi. Tratând aceste numere ca numere de patru cifre în baza 216, putem să le sortam pe baza cifrelor doar prin patru treceri, comparativ cu o sortare clasica prin comparaţii de timp Θ(n log2 n) care necesita aproximativ log2 n = 20 de operaţii pentru fiecare număr sortat. Din păcate, versiunea algoritmului de ordonare pe baza cifrelor care foloseşte sortarea prin numărare ca sortare intermediara stabila nu sortează pe loc, lucru care se întâmpla în cazul multora din sortările prin comparaţii de timp Θ(n log2 n). Astfel, daca se doreşte ca necesarul de memorie să fie mic, atunci este preferabil algoritmul de sortare rapidă.




  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 (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
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 (12)

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