10 2018 Lectia24

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.

#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;
}

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.

#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;
}

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 )