Clasa a IX-a lecția 27

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Interclasarea a doi vectori (merge)

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate crescător. Să se construiască un al treilea şir, c, care să conţină, în ordine crescătoare, elementele din şirurile a şi b.

O soluție ar fi să copiem toate elementele în cel de-al treilea vector și apoi să îl ordonăm. Există însă o soluție mai bună, bazată pe faptul că vectorii sînt deja ordonați. Să observăm că primul element din vectorul final este minimul dintre primele elemente din vectorii inițiali. Îl putem deci copia și apoi îl eliminăm din vectorul din care face parte. Apoi reluăm procedura. La un moment dat unul din vectori se va goli. În acel moment copiem ceea ce a rămas din vectorul nevid. Vom folosi trei indici i1, i2 și i3 care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

#include <stdio.h>

int a[100000], b[100000], c[200000];

int main(){
    int i, j, k, n1, n2;
    FILE *fin = fopen( "interclasare.in", "r" );
    FILE *fout = fopen( "interclasare.out", "w" );

    fscanf( fin, "%d", &n1 );
    for( i = 0; i < n1; i++ )
        fscanf(fin, "%d", &a[i]);
    
    fscanf(fin, "%d", &n2);
    for( i = 0; i < n2; i++ )
        fscanf(fin, "%d", &b[i]);

    i = j = k = 0;
    while( i < n1 && j < n2 ){      // cate vreme mai avem elemente in ambii vectori
        if( a[i] < b[j] )           // daca in a avem elementul mai mic
            c[k++] = a[i++];        // il copiem in vectorul c; avansam in vectorul a si in vectorul c
        else                        // altfel b are elementul cel mai mic
            c[k++] = b[j++];        // il copiem in vectorul c; avansam in vectorul b si in vectorul c

    }
    // in acest moment unul din vectorii a, b este sigur vid,
    while ( i < n1 )                // incercam sa copiem elementele ramase in a, daca exista
        c[k++] = a[i++];

    while ( j < n2 )                // incercam sa copiem elementele ramase in b, daca exista
        c[k++] = b[j++];

    for( i = 0; i < k; i++ ){       // k va fi n1 + n2
        fprintf ( fout, "%d ",  c[i] );        
    }
    fclose( fin );
    fclose( fout );
    return 0;
}

Laborator

#251 Interclasare2

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate strict crescător. Să se afişeze, în ordine strict crescătoare, valorile existente în ambele şiruri.

#284 Interclasare3

Se dau două şiruri, cu n, respectiv m, elemente, numere naturale. Primul şir este ordonat crescător, iar al doilea element este ordonat descrescător. Să se afişeze, în ordine crescătoare, valorile pare din cele două şiruri.

#530 Multimi1

Se dau două mulțimi de numere naturale. Să se afișeze reuniunea și intersecția lor.

#242 InterclasM

Se dă un număr natural x și două șiruri a și b, cu n, respectiv m elemente, numere naturale, ordonate strict crescător. Să se afișeze, în ordine crescătoare, multiplii lui x care se află doar în unul dintre cele două șiruri.

Tema Teorie

Interclasare1, Interclasare

#241 Interclasare

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate crescător. Să se construiască un al treilea şir, c, care să conţină, în ordine crescătoare, elementele din şirurile a şi b.

#include <stdio.h>

int a[100000], b[100000], c[200000];

int main(){
    int i, j, k, n1, n2, n;
    FILE *fin = fopen( "interclasare.in", "r" );
    FILE *fout = fopen( "interclasare.out", "w" );
    fscanf( fin, "%d", &n1 );
    for( i = 0; i < n1; i++ )
        fscanf(fin, "%d", &a[i]);
    fscanf(fin, "%d", &n2);
    for( i = 0; i < n2; i++ )
        fscanf(fin, "%d", &b[i]);

    i = j = k = 0;
    while( i < n1 && j < n2 ){      /// cate vreme mai avem elemente in ambii vectori
        if( a[i] < b[j] )           /// daca in a avem elementul mai mic
            c[k++] = a[i++];        /// il copiem in vectorul c; avansam in vectorul a si in vectorul c
        else                        /// altfel b are elementul cel mai mic
            c[k++] = b[j++];        /// il copiem in vectorul c; avansam in vectorul b si in vectorul c

    }
    /// in acest moment unul din vectorii a, b este sigur vid,
    while ( i < n1 )                /// incercam sa copiem elementele ramase in a, daca exista
        c[k++] = a[i++];

    while ( j < n2 )                /// incercam sa copiem elementele ramase in b, daca exista
        c[k++] = b[j++];

    n = n1 + n2;
    for( i = 0; i < n; i++ ){
        fprintf ( fout, "%d ",  c[i] );
        if( ( i + 1 ) % 10 == 0 )  /// dupa ce am printat al 10-lea element dau enter
            fprintf ( fout, "\n" );
    }

    return 0;
}

#250 Interclasare1

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate strict crescător. Să se afişeze, în ordine strict crescătoare, valorile existente în cel puţin unul dintre cele două şiruri.

#include <stdio.h>

int a[100000], b[100000], c[200000];

int main(){
  int i, j, k, n1, n2, n;
  FILE *fin = fopen( "interclasare1.in", "r" );
  FILE *fout = fopen( "interclasare1.out", "w" );
  
  fscanf( fin, "%d", &n1 );
  for( i = 0; i < n1; i++ )
    fscanf(fin, "%d", &a[i]);
  
  fscanf(fin, "%d", &n2);
  for( i = 0; i < n2; i++ )
    fscanf(fin, "%d", &b[i]);

  i = j = k = 0;
  while( i < n1 && j < n2 ){      /// cate vreme mai avem elemente in ambii vectori
    if( a[i] < b[j] ) {
      if ( a[i] != c[k-1] )
        c[k++] = a[i];
      i++;
    }        /// il copiem in vectorul c; avansam in vectorul a si in vectorul c
    else {
      if ( b[j] != c[k-1] )
        c[k++] = b[j];
      j++;
    }
  }

  while ( i < n1 ){
    if ( a[i] != c[k-1] )
      c[k++] = a[i];
    i++;
  }

  while ( j < n2 ){
    if ( b[j] != c[k-1] )
      c[k++] = b[j];
    j++;
  }

  for( i = 0; i < k; i++ ){
    fprintf ( fout, "%d ",  c[i] );
    if( ( i + 1 ) % 10 == 0 )   /// dupa ce am printat al 10-lea element dau enter
      fprintf ( fout, "\n" );
  }

  return 0;
}

Tema Laborator

Interclasare2, Interclasare3, Multimi1, InterclasM