[c]Merge aiuto!

[djdavi96c]

Salve ragazzi ho bisogno di un aiuto, in classe con la prof abbiamo creato un algoritmo per fare la fusione di due vettori ordinati considerando che se in entrambi ci fosse stato un numero uguale bisognava copiarne solamente uno..ma eseguendo il programma ciò non avviene.. questo è il codice,mi potete dire dove ho sbagliato?

#include <iostream>
#include <stdlib.h>
#define NMAX 100
using namespace std;
void ordinamento(int v[], int n);
int main()
{
int i,j,k,l,vet1[NMAX],vet2[NMAX],vet3[NMAX],m,n;
cout<<"Inseirsci la grandezza del primo vettore: ";
cin>>n;
cout<<"Inseirsci la grandezza del secondo vettore: ";
cin>>m;
for(i=0; i<n; i++){
cout<<"Inserisci il "<<i+1<<" numero del primo vettore: ";
cin>>vet1[i];
}
for(j=0; j<m; j++){
cout<<"Inserisci il "<<j+1<<" numero del secondo vettore: ";
cin>>vet2[j];
}
ordinamento(vet1,n);

ordinamento(vet2,m);

system("PAUSE");

i=0;
j=0;
k=0;
do{
if(vet1[i]>vet2[j]){
vet3[k]=vet2[j];
j++;
}else{
if(vet1[i]==vet2[j]){
vet3[k]=vet1[i];
j=j+1;
i=i+1;
}else{
vet3[k]=vet2[i];
i++;
}
}
k++;
}while(i<n && i<m);

if(i==n){
for(l=j; l<m; l++){
vet3[k]=vet2[l];
k++;
}
}else{
for(l=i; l<i; l++){
vet3[k]=vet1[l];
k++;
}
}


for(k=0; k<(n+m); k++){
cout<<"il "<<i+1<<" numero del 3 vettore: ";
cout<<vet3[k];
cout<<endl;
}


return 0;
}

void ordinamento(int v[], int n) {
int i,k;
int temp;
for(i = 0; i<n-1; i++) {
for(k = 0; k<n-1-i; k++) {
if(v[k] > v[k+1]) {
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
}
}
}

[Xfree]

Prima reinserisco il codice opportunamente formattato e poi ti rispondo

#include <iostream>
#include <stdlib.h>
#define NMAX 100
using namespace std;
void ordinamento(int v[], int n);
int main()
{
	int i, j, k, l, vet1[NMAX], vet2[NMAX], vet3[NMAX], m, n;
	cout << "Inseirsci la grandezza del primo vettore: ";
	cin >> n;
	cout << "Inseirsci la grandezza del secondo vettore: ";
	cin >> m;
	for (i = 0; i < n; i++){
		cout << "Inserisci il " << i + 1 << " numero del primo vettore: ";
		cin >> vet1[i];
	}
	for (j = 0; j<m; j++){
		cout << "Inserisci il " << j + 1 << " numero del secondo vettore: ";
		cin >> vet2[j];
	}
	ordinamento(vet1, n);

	ordinamento(vet2, m);

	system("PAUSE");

	i = 0;
	j = 0;
	k = 0;
	do{
		if (vet1[i]>vet2[j]){
			vet3[k] = vet2[j];
			j++;
		}
		else{
			if (vet1[i] == vet2[j]){
				vet3[k] = vet1[i];
				j = j + 1;
				i = i + 1;
			}
			else{
				vet3[k] = vet2[i];
				i++;
			}
		}
		k++;
	} while (i < n && i < m);

	if (i == n){
		for (l = j; l < m; l++){
			vet3[k] = vet2[l];
			k++;
		}
	}
	else{
		for (l = i; l < i; l++){
			vet3[k] = vet1[l];
			k++;
		}
	}


	for (k = 0; k < (n + m); k++){
		cout << "il " << i + 1 << " numero del 3 vettore: ";
		cout << vet3[k];
		cout << endl;
	}


	return 0;
}

void ordinamento(int v[], int n) {
	int i, k;
	int temp;
	for (i = 0; i < n - 1; i++) {
		for (k = 0; k<n - 1 - i; k++) {
			if (v[k] > v[k + 1]) {
				temp = v[k];
				v[k] = v[k + 1];
				v[k + 1] = temp;
			}
		}
	}
}

C'è un errore nella riga

vet3[k] = vet2[i];

che invece deve essere

vet3[k] = vet1[i];

e nella condizione del while che deve essere

i < n && j < m

Errori che potrebbero essere dovuti alla disattenzione.
Detto questo, alla fine del merge rimangono pendenti gli ultimi elementi dai rispettivi vettori di provenienza da copiare nel vettore di merge e quello lo fai banalmente con due cicli while.

Rivedi meglio tutto il seguente blocco e ragionaci.
Se ti do la soluzione pronta non impari nulla.

if (i == n){
	for (l = j; l < m; l++){
		vet3[k] = vet2[l];
		k++;
	}
}
else{
	for (l = i; l < i; l++){
		vet3[k] = vet1[l];
		k++;
	}
}


for (k = 0; k < (n + m); k++){
	cout << "il " << i + 1 << " numero del 3 vettore: ";
	cout << vet3[k];
	cout << endl;
}

L'ouput corretto è il seguente.

c:\hwu>merge
Inseirsci la grandezza del primo vettore: 4
Inseirsci la grandezza del secondo vettore: 4
===== PRIMO VETTORE =====
Inserisci il 1 numero del primo vettore: 7
Inserisci il 2 numero del primo vettore: 4
Inserisci il 3 numero del primo vettore: 2
Inserisci il 4 numero del primo vettore: 5
===== SECONDO VETTORE =====
Inserisci il 1 numero del secondo vettore: 2
Inserisci il 2 numero del secondo vettore: 3
Inserisci il 3 numero del secondo vettore: 1
Inserisci il 4 numero del secondo vettore: 6

Premere un tasto per continuare . . .

===== VETTORE FUSO=====
1
2
3
4
5
6
7

[gianmpu]

Oltre a quanto già detto, faccio notare anche un'altro punto che potrebbe essere fonte di errore.
Se vet1 e vet2 sono due vettori di dimensione NMAX da unire e il vettore vet3 è quello in cui verranno inseriti i due vettori, la dimensione di v3 non dovrebbe essere NMAX, perchè se in vet1 e vet2 ci sono solo valori diversi, ci sarà un overflow inserendo i dati in vet3.
Ovviamente, in questo caso il problema non si pone perchè è un semplice esercizio scolastico e difficilmente si arriverà a 100 elementi, ma in una implementazione reale bisognerebbe tenerne conto.

[Xfree]

Sì hai ragione, nel worst case dovrebbe essere 2*NMAX.

[djdavi96c]

Originariamente inviato da Xfree

Prima reinserisco il codice opportunamente formattato e poi ti rispondo

#include <iostream>
#include <stdlib.h>
#define NMAX 100
using namespace std;
void ordinamento(int v[], int n);
int main()
{
	int i, j, k, l, vet1[NMAX], vet2[NMAX], vet3[NMAX], m, n;
	cout << "Inseirsci la grandezza del primo vettore: ";
	cin >> n;
	cout << "Inseirsci la grandezza del secondo vettore: ";
	cin >> m;
	for (i = 0; i < n; i++){
		cout << "Inserisci il " << i + 1 << " numero del primo vettore: ";
		cin >> vet1[i];
	}
	for (j = 0; j<m; j++){
		cout << "Inserisci il " << j + 1 << " numero del secondo vettore: ";
		cin >> vet2[j];
	}
	ordinamento(vet1, n);

	ordinamento(vet2, m);

	system("PAUSE");

	i = 0;
	j = 0;
	k = 0;
	do{
		if (vet1[i]>vet2[j]){
			vet3[k] = vet2[j];
			j++;
		}
		else{
			if (vet1[i] == vet2[j]){
				vet3[k] = vet1[i];
				j = j + 1;
				i = i + 1;
			}
			else{
				vet3[k] = vet2[i];
				i++;
			}
		}
		k++;
	} while (i < n && i < m);

	if (i == n){
		for (l = j; l < m; l++){
			vet3[k] = vet2[l];
			k++;
		}
	}
	else{
		for (l = i; l < i; l++){
			vet3[k] = vet1[l];
			k++;
		}
	}


	for (k = 0; k < (n + m); k++){
		cout << "il " << i + 1 << " numero del 3 vettore: ";
		cout << vet3[k];
		cout << endl;
	}


	return 0;
}

void ordinamento(int v[], int n) {
	int i, k;
	int temp;
	for (i = 0; i < n - 1; i++) {
		for (k = 0; k<n - 1 - i; k++) {
			if (v[k] > v[k + 1]) {
				temp = v[k];
				v[k] = v[k + 1];
				v[k + 1] = temp;
			}
		}
	}
}

C'è un errore nella riga

vet3[k] = vet2[i];

che invece deve essere

vet3[k] = vet1[i];

e nella condizione del while che deve essere

i < n && j < m

Errori che potrebbero essere dovuti alla disattenzione.
Detto questo, alla fine del merge rimangono pendenti gli ultimi elementi dai rispettivi vettori di provenienza da copiare nel vettore di merge e quello lo fai banalmente con due cicli while.

Rivedi meglio tutto il seguente blocco e ragionaci.
Se ti do la soluzione pronta non impari nulla.

if (i == n){
	for (l = j; l < m; l++){
		vet3[k] = vet2[l];
		k++;
	}
}
else{
	for (l = i; l < i; l++){
		vet3[k] = vet1[l];
		k++;
	}
}


for (k = 0; k < (n + m); k++){
	cout << "il " << i + 1 << " numero del 3 vettore: ";
	cout << vet3[k];
	cout << endl;
}

L'ouput corretto è il seguente.

c:\hwu>merge
Inseirsci la grandezza del primo vettore: 4
Inseirsci la grandezza del secondo vettore: 4
===== PRIMO VETTORE =====
Inserisci il 1 numero del primo vettore: 7
Inserisci il 2 numero del primo vettore: 4
Inserisci il 3 numero del primo vettore: 2
Inserisci il 4 numero del primo vettore: 5
===== SECONDO VETTORE =====
Inserisci il 1 numero del secondo vettore: 2
Inserisci il 2 numero del secondo vettore: 3
Inserisci il 3 numero del secondo vettore: 1
Inserisci il 4 numero del secondo vettore: 6

Premere un tasto per continuare . . .

===== VETTORE FUSO=====
1
2
3
4
5
6
7

Grazie mille a tutti voi,ho risolto anche quel problemi dei cicli che come dicevi era inutile tutto quel codice bastavano due cicli for e ho risolto la stampa.