[C] Algoritmo non corretto

[claudio19488]

Ciao a tutti

ecco il mio problema (tutto il giorno che ci provo ma.. )

Chiedo perdono per la mia scrittura che a voi programmatori esperti sembrerà uno "stupro" del compiler da parte mia.

Il problema è spiegato nel programma, è un tema d'esame che sto svolgendo in preparazione all'appello che farò venerdi 18/06.

Chiedo qualche consiglio in quanto l'algoritmo pare corretto, ma come potete vedere le ultime due cifre non sono quelle esatte

PS: ringrazio che risponderà

PPS: sono alle prime armi, conosco poco il C e la sua libreria

Codice:

#include <stdio.h>

int main () {

/*
8. Si sviluppi un programma in linguaggio C che riceva in ingresso due vettori di interi,
ciascuno di 10 elementi. Supponendo che i due vettori siano già ordinati in modo crescente,
il programma deve creare e stampare un terzo vettore che rappresenti la “fusione†dei due
vettori acquisiti, ovvero che contenga tutti i 20 elementi ordinati tra loro in modo crescente.
Ad esempio, se il primo vettore contiene gli elementi
2 5 9 14 15 20 25 27 30 32
e il secondo vettore contiene gli elementi
3 5 10 11 12 22 23 24 26 27
Il programma crea e stampa un vettore contenente i seguenti elementi:
2 3 5 5 9 10 11 12 14 15 20 22 23 24 25 26 27 27 30 32 

*/

   int  v1[10] , v2[10], v3[20] , i , i1, i2, i3;

   printf("Inserisci una sequenza di 10 interi, in ordine crescente.\n");

   for (i = 0 ; i < 10 ; i++ ) {
        scanf("%d", &v1[i]);   
   }

   printf("Inserisci ora un' altra sequenza di 10 interi, in ordine crescente.\n");

   for (i = 0 ; i < 10 ; i++ ) {
       scanf("%d", &v2[i]);   
   }



   i1= 0;
   i2= 0;
   i3= 0;    
   while ( i3 < 20 ) {

       if (v1[i1] > v2[i2] ) 
       { 
           v3[i3] = v2[i2] ; 
           printf("%d ",v3[i3]);
               i3++; 
               i2++;     

           }

       else
                      {
           v3[i3] = v1[i1]; 
           printf("%d ",v3[i3]);
           i3++;
               i1++; 
                     }


       }

   return 0 ;
} 

Qui la finestra--

Inserisci una sequenza di 10 interi, in ordine crescente.
1
2
3
4
5
6
12
15
22
31
Inserisci ora un' altra sequenza di 10 interi, in ordine crescente.
1
2
3
9
12
14
22
29
40
42
1 1 2 2 3 3 4 5 6 9 12 12 14 15 22 22 29 31 [color=Red][b]10 11[/b][/color] logout

[Processo completato]

Ecco i due errori..

[canne1087]

Devi controllare che il contatore per ogni vettore non superi la lunghezza del vettore corrispondente.

Nel tuo caso quando arrivi a 31 il contatore i1 si aggiorna a 10 e al ciclo successivo controlla se v1[10] > v2[i2] ma il vettore v1 è già stato completato il ciclo precedente. In tal caso devi copiare i rimanenti elementi di v2 nel vettore v3.

[DaD]

Ma fai le cose con calma... Fondi prima gli array nel terzo e solo dopo applica l'ordinamento al terzo, è meno performante ma da quanto vedo è un esame di base, il prof apprezzerà il ragionamento

[ignazioc]

Ma fai le cose con calma... Fondi prima gli array nel terzo e solo dopo applica l'ordinamento al terzo, è meno performante ma da quanto vedo è un esame di base, il prof apprezzerà il ragionamento

verametne se fossi io il professore lo manderei a casa.

passare da un programma banale che ha complessità lineare O(n) ad uno che ha complessità O(nlogn)...

la soluzione proposta da canne1087 è corretta, devi verificare che non sei "uscito fuori" dal vettore

qui c'è una soluzione.

#include <stdio.h>
#include <stdlib.h>
#define N 5

int main(int argc, char **argv)
{
int v1[N],v2[N],v3[2 * N];
int i,i1,i2,i3;

printf("Inserisci una sequenza di %d interi, in ordine crescente.\n",N);

   for (i = 0 ; i < N ; i++ ) {
	scanf("%d", &v1[i]);   
   }

   printf("Inserisci ora un' altra sequenza di %d interi, in ordine crescente.\n",N);

   for (i = 0 ; i < N ; i++ ) {
       scanf("%d", &v2[i]);   
   }
i1 = i2 = i3 = 0;

while (i1 < 20 && i2 < 20) {
	if (v1[i1] <= v2[i2]) {
		v3[i3] = v1[i1];
		i1++;
	}
	else {
		v3[i3] = v2[i2];
		i2++;
	}
	i3++;
}
while (i1 < 20) {
	v3[i3] = v1[i1];
	i3++;
	i1++;
}
while (i1 < 20) {
	v3[i3] = v2[i2];
	i3++;
	i2++;
}
for (i = 0; i < 2 * N; i++) {
	printf(" %d ",v3[i]);
}
printf("\n");
}

ps: questo algoritmo viene utilizzato all'interno dell'algoritmo di ordinamento Mergesort e viene chiamato "merge".

[DaD]

L'algoritmo di merge-sort non è di certo un algoritmo che viene insegnato in un corso base, o lameno io l'ho studiato in un corso succesivo a questo, quindi secondo me con la mia soluzione e prendendo la suo post per buono, non lo boccia per niente ;D

[ignazioc]

L'algoritmo di merge-sort non è di certo un algoritmo che viene insegnato in un corso base, o lameno io l'ho studiato in un corso succesivo a questo, quindi secondo me con la mia soluzione e prendendo la suo post per buono, non lo boccia per niente ;D

e quando dici "applica l'ordinamento al terzo" che algoritmo intendi? se già è un problema fare il merge di due array che algoritmo di ordinamento può usare?

ps: cmq non ha risposto, chissà com'è finita.

[DaD]

Mhh ma può anche fare un insertion e gli passa la paura, comunque forse è stato scomunicato dall'università :°D

[stevemb]

io metterei i 2 vettori nel 3° vettore e poi con un ciclo for più un if li ordinerei con

if(n>n[i+1])

{x=n;

y=n[i+1];

n=y;

n[i+1]=x;

}

più base di così si muore

[ignazioc]

io metterei i 2 vettori nel 3° vettore e poi con un ciclo for più un if li ordinerei con

if(n>n[i+1])

{x=n;

y=n[i+1];

n=y;

n[i+1]=x;

}

più base di così si muore

quello che hai scritto mi pare che si chiami bubblesort. Quell' IF va fatto n per n-1 volte (diciamo quindi due clicli for) perchè ad ogni iterazione metti in valore più grande nell'ultima posizione dell'array.

[stevemb]

quello che hai scritto mi pare che si chiami bubblesort. Quell' IF va fatto n per n-1 volte (diciamo quindi due clicli for) perchè ad ogni iterazione metti in valore più grande nell'ultima posizione dell'array.

Sisi giusto hai ragione tu