Bella: /* Tema Teorie */

2018-04-22T07:43:06Z

Tema Teorie

New page

== 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 <tt>i1</tt>, <tt>i2</tt> și <tt>i3</tt> care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

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

= 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.
<syntaxhighlight></syntaxhighlight>
=== #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.
<syntaxhighlight></syntaxhighlight>
===#530 Multimi1===
Se dau două mulțimi de numere naturale. Să se afișeze reuniunea și intersecția lor.
<syntaxhighlight></syntaxhighlight>
=== #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.
<syntaxhighlight></syntaxhighlight>

= 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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

=== #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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

= Tema Laborator =
Interclasare2, Interclasare3, Multimi1, InterclasM

Clasa a IX-a lecția 27 - Revision history

Bella: /* Tema Teorie */