Bella: /* TEMA */

2019-03-27T14:40:06Z

TEMA

New page

= Tema Rezolvari =
= Lectie =
== Merge Sort ==

Sortarea prin interclasare este un exemplu tipic de algoritm divide et impera :

* se sortează o secvență delimitată de indicii st și dr:
* dacă st <= dr, problema este elementară, secvența fiind deja sortată
* dacă st < dr:
** se împarte problema în subprobleme, identificând mijlocul secvenței, m = (st + dr) / 2;
** se rezolvă subproblemele, sortând secvența delimitată de st și m, respectiv secvența delimitată de m+1 și dr – apeluri recursive;
** se combină soluțiile, interclasând cele două secvențe; în acest fel, secvența delimitată de st și dr este sortată.

'''Observații''':

complexitatea sortării prin interclasare este O(n⋅logn);
pentru interclasare este este necesar un spațiu de memorie suplimentar, de dimensiunea tabloului care se sortează;
în secvența de mai sus tabloul tmp a fost declarat global; declararea sa locală poate duce la depășirea stivei; o soluție pentru această situație poate fi alocarea dinamică a tabloului auxiliar.

[[Image:mergesort.gif]]

<syntaxhighlight>
#include <iostream>

using namespace std;

int tmp[100000], v[100000];

void MergeSort( int v[], int st, int dr ) {
if( st < dr ){
int m = (st + dr) / 2;

MergeSort ( v, st , m ); // ordonam prima jumatate
MergeSort( v, m + 1 , dr ); // ordonam a doua jumatate

int i = st, j = m + 1, k = 0; // interclasam cele doua jumatati
while( i <= m && j <= dr ) // cata vreme mai am elemente in cele doua jumatati
if( v[i] < v[j] ) // compar primele elemente
tmp[k++] = v[i++]; // punem intr-un vector temporar valorile interclasate
else
tmp[k++] = v[j++];
while( i <= m ) // daca mi-au mai ramas valori in prima jumatate, le transfer in tmp
tmp[k++] = v[i++];
while( j <= dr ) // daca mi-au ramas valori in a doua jumatate, le transfer in tmp
tmp[k++] = v[j++];

j = 0 ;
for(i = st; i <= dr ; i ++ ) // punem valorile din tmp in v;
v[i] = tmp[j++];
}
}

int main(){
int n ;

cin >> n;
for( int i = 0; i < n; ++i )
cin >> v[ i ];

MergeSort( v, 0, n - 1 );

for( int i = 0; i < n; ++i )
cout << v[ i ] << " ";

return 0;
}
</syntaxhighlight>
== Turnurile din Hanoi ==
Fie tijele a, b, c, iar pe tija a n discuri. Sa se muta discurile de pe tija a pe tija b folosind tija intermediara c. Respectand regurile:
1. la fiecare pas se muta un singur disc
2.nu se poate muta un disc mare peste unul mic

* Daca n = 1 se muta discul de pe a pe b; H(n,a,b,c)= ab
* Daca n = 2 mutam discul de pe : a pe c, a pe b, c pe b
Pentru n discuri:
Trebuie sa mut n-1 discuri de pe tija a pe tija c si discul n de pe tija a pe tija b. Se muta a,b (discul care a ramas pe a), si mut n-1 discuri de pe c pe b prin tija intermediara a.

<syntaxhighlight>
#include <iostream>
using namespace std;
void hanoi(int n,char a, char b, char c){
if( n == 1 )
cout << a<< b << endl; // mut de pe tija a pe tija b singurul disc
else{
hanoi( n - 1, a, c, b ); // mut n-1 discuri de pe tija a pe tija c, prin intermediul tijei b
cout << a << b << endl; // mut de pe tija a pe tija b singurul disc ramas
hanoi( n - 1, c, b, a ); // mut n-1 discuri de pe tija c pe tija b, prin intermediul tijei a
}
}
int main(){
int n;
char a = 'a', b = 'b', c ='c';
cin >> n;
hanoi( n, a, b, c );
return 0;
}
</syntaxhighlight>

= TEMA =
usor
* https://www.pbinfo.ro/?pagina=probleme&id=1025 ( teorie )
mediu
* https://www.infoarena.ro/problema/mergesort
* https://infoarena.ro/problema/swap
* https://infoarena.ro/problema/password2
* http://varena.ro/problema/hanoi
grea
* http://cs.org.mk/jboi2013/en/tasks.html "Counting inversions" ( Propunere Tibi )

10 2018 Lectia24 - Revision history

Bella: /* TEMA */