Question

Salutare am facut aceasta problema si nu stiu daca e destul de eficient algoritmul.
Subprogramul sub primeşte prin intermediul parametrilor:
– n şi m două numere naturale (1 – a şi b două tablouri unidimensionale, fiecare având componente numere naturale de maximum patru cifre, ordonate crescător; tabloul a conţine n numere pare, iar tabloul b conţine m numere impare. Subprogramul va afişa pe ecran, în ordine crescătoare, separate prin câte un spaţiu, un şir format dintr-un număr maxim de elemente care aparţin cel puţin unuia dintre tablouri, astfel încât orice două elemente aflate pe poziţii consecutive să fie de paritate diferită. Exemplu: pentru n=5, m=3 şi tablourile a=(2,4,8,10,14) şi b=(3,5,11), subprogramul va afişa 2 3 4 5 8 11 14 sau 2 3 4 5 10 11 14.
a) Scrieţi definiţia completă a subprogramului sub, alegând pentru rezolvare un algoritm eficient din punctul de vedere al timpului de executare. (6p.)
b) Descrieţi succint, în limbaj natural, algoritmul pe baza căruia a fost scris subprogramul de la punctul a), explicând în ce constă eficienţa metodei utilizate. (4p.)


#include
using namespace std;


void sub(int n, int m, int a[100], int b[100])
{
int i = 1, j = 1, k;

if (a[1] < b[1])
{
cout << a[i] << " ";
k = 2, i++;
}
else
{
cout << b[j] << " ";
k = 1, j++;
}

while (i <= n && j <= m)
{
if (k == 1)
{
while (a[i] < b[j - 1])
i++;
cout << a[i] << " ";
k = 2, i++;
}
else
{
while (a[i - 1] > b[j])
j++;
cout << b[j] << " ";
k = 1, j++;
}
}

if (k == 1)
{
if (k == 1)
{
while (a[i] < b[j - 1])
i++;
cout << a[i] << " ";
}
}
else
{
while (a[i - 1] > b[j])
j++;
cout << b[j] << " ";
}


}

int main()
{
int n, i, m, a[100], b[100];
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];

cin >> m;
for (i = 1; i <= m; i++)
cin >> b[i];

sub(n, m, a, b);



return 0;
}

Answer 1

Orice algoritm care parcurge pe fiecare dintre cei doi vectori o singura data este optim.  Sa te inspri din algoritmul de interclasare a doi vectori sortati crescator - o idee utila. In acest caz, complexitatea timp a algoritmului: O(m+n).