Date post: | 11-Mar-2016 |
Category: |
Documents |
Upload: | alin-fanase |
View: | 228 times |
Download: | 3 times |
Algoritm:Algoritm:Este un algoritm simplu, menit a transforma
doua secvente ordonate intr-una singura, tot ordonata, care contine toate elementele celor doua secvente de pornire.
Presupunem că dorim să interclasăm tablourile unidimensionale A şi B, ordonate crescător, şi să obţinem secvenţa rezultat C, ordonată tot crescător.
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A:
C:
Presupunem că avem câte un indicator pentru fiecare din vectorii A şi B, care pornesc de pe prima poziţie a fiecăruia.
La fiecare pas se compară cele două elemente corespunzătoare indicatorilor.
Minimul dintre cele două elemente este adăugat la elementele vectorului C şi indicatorul corespunzător este mutat o poziţie spre dreapta (indicatorul din celălalt vector rămâne neschimbat).
Dacă vreunul din indicatori depăşeşte limita dreaptă a vectorului asociat, se copiază elementele rămase în celălat vector la sfârşitul vectorului C, în ordinea în care apar.
Algoritmul se încheie în momentul în care ambii indicatri au depăşit limita dreaptă a vectorilor asociaţi (A şi B).
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 4 < 6, trece 4
4C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 5 < 6, trece 5
4 5C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 6 < 7, trece 6
4 5 6C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 7 < 8, trece 7
4 5 6 7C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 8 < 10, trece 8
4 5 6 7 8C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 9 < 10, trece 9
4 5 6 7 8 9C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 10 < 12, trece 10
4 5 6 7 8 9 10C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 11 < 12, trece 11
4 5 6 7 8 9 10 11C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 12 < 14, trece 12
4 5 6 7 8 9 10 11 12C:
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 14 < 16, trece 14
4 5 6 7 8 9 10 11 12C:
14
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 16 < 19, trece 16
4 5 6 7 8 9 10 11 12C:
14 16
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 19 < 28, trece 19
4 5 6 7 8 9 10 11 12C:
14 16 19
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 24 < 28, trece 24
4 5 6 7 8 9 10 11 12C:
14 16 19 24
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 28 < 36, trece 28
4 5 6 7 8 9 10 11 12C:
14 16 19 24 28
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 31 < 36, trece 31
4 5 6 7 8 9 10 11 12C:
14 16 19 24 28 31
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 32 < 36, trece 32
4 5 6 7 8 9 10 11 12C:
14 16 19 24 28 31 32
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: 35 < 36, trece 35
4 5 6 7 8 9 10 11 12C:
14 16 19 24 28 31 32 35
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A: trece 36
4 5 6 7 8 9 10 11 12C:
3614 16 19 24 28 31 32 35
6 8 9 12 16 28 31 32 35
4 5 7 10 11 14 19 24 36B:
A:
4 5 6 7 8 9 10 11 12C:
3614 16 19 24 28 31 32 35
Ambele indicatoare au depăşit limita din dreapta a vectorilor asociaţi, deci algoritmul se opreşte aici.
ProblemăProblemă::Se citesc de la tastatura doi vectori A şi B de numere întregi ordonate. Să se creeze un vector C cu elementele din cei doi vectori A şi B, sortat şi să se afişeze vectorul C (INTERCLASARE).
ProProgram:gram:# include <iostream.h># include <iostream.h># include <conio.h># include <conio.h>int A[50], B[50], C[100], i, j, m, n, k;int A[50], B[50], C[100], i, j, m, n, k;void main() {void main() {
clrscr();clrscr();cout << “m=” ;cout << “m=” ;cin >> m ;cin >> m ;for( i = 0 ; i < m ; i++ ){for( i = 0 ; i < m ; i++ ){
cout << “A[“ << i << “]=” ;cout << “A[“ << i << “]=” ;cin >> A[i] ;cin >> A[i] ;
}}cout << “n=” ;cout << “n=” ;cin >> n ;cin >> n ;for( i = 0 ; i < n ; i++ ){for( i = 0 ; i < n ; i++ ){
cout << “B[” << i << “]=” ;cout << “B[” << i << “]=” ;cin >> B[i] ;cin >> B[i] ;
}}i = 0 ; j = 0 ; k = 0;i = 0 ; j = 0 ; k = 0;while ( i < m && j < n ){while ( i < m && j < n ){
if ( A[i] < B[j] ){if ( A[i] < B[j] ){C[k] = A[i] ;C[k] = A[i] ;
k++ ; i++ ;k++ ; i++ ;}}else {else {
C[k] = B[j] ;C[k] = B[j] ;k++ ; j++ ;k++ ; j++ ;
}}}}while ( i < m ){while ( i < m ){
C[k] = A[i] ;C[k] = A[i] ;k++ ; i++ ;k++ ; i++ ;
}}while ( j < n ){while ( j < n ){
C[k] = B[j] ;C[k] = B[j] ;k++ ; j++ ;k++ ; j++ ;
}}for( i = 0 ; i < k ; i++)for( i = 0 ; i < k ; i++)
cout << C[i] <<‘ ‘ ;cout << C[i] <<‘ ‘ ;getch();getch();
} }