[C] Programma sui vettori

[ziomerio]

ciao a tutti mi servirebbe una mano con questo programma che non sono riuscito a fare

abbiamo due vettori uno di dimensione M uno di dimensione N in ordine crescente bisogna fare la differenza...(non mi ricordo il nome) e metterla in ordine crescente nel vettore c di dimensioni non piu di M+N

se per esempio abbiamo il vettore a {1,2,3,5,6} e il b{2,4,5,7}
il vettore c sara {1 ,3 ,4 ,6 ,7 } in ordine crescente ed i numeri uguali non si ripetono

grazie per l aiuto se non avete capito qualcosa del problema chiedete magari mi sono spiegato male in qualche punto

[tuccio`]

ti basta fare un merge (come quello del merge sort) con una leggera modifica per non mettere due numeri uguali nel nuovo vettore

[ziomerio]

grazie ho letto questo merce ma se io non l ho studiamo come mi faceva a venire in mente una cosa del genere ..
non cè un metodo alternativo a questo merce??'
mi sono scordato di dire che all inizio di questo problema non c era scritto algoritmo ricorsivo ma iterativo

[WarDuck]

La versione più semplice ti richiede di fare 2 cicli per controllare se un elemento è nell'altro vettore.

Se devi calcolare A - B ciò significa che vanno presi tutti gli elementi di A che non sono in B.

Quindi scorri il vettore A e per ogni elemento controlli se il vettore B non contiene quell'elemento.

Se B non lo contiene allora lo inserisci nel vettore di destinazione.

Nota bene:
Una versione un po' più sofisticata tiene conto del fatto che i vettori sono in ordine crescente, in particolare se stai testando {x, elemento di A, appartiene a B?} il ciclo interno si interromperà non appena trovi un y > x (x appartiene ad A e y appartiene a B).

Esempio:

A {1, 2, 3, 5, 6}
B {2, 4, 5, 7}

1 presente in B?
In B trovi 2, esci dal ciclo interno perché sai che sicuramente 1 non c'è, copi 1 in C.

2 presente in B?
Trovi 2, non fai nulla

3 presente in B?
Trovo 2, proseguo, trovo 4, esco dal ciclo, poiché 3 non c'è lo copio in C

(edit: nell'esempio sopra ho corretto l'errore)

E così via. Naturalmente gli elementi inseriti sono inseriti in ordine crescente, perché sei sicuro che ad ogni passo del ciclo ti trovi davanti ad un elemento maggiore del precedente.

Nota bene: si può ottimizzare ulteriormente tenendo traccia dell'ultimo elemento controllato in B e quindi usare l'indice salvato per ripartire da lì!!!

Così facendo fai pochissimi confronti nel ciclo interno, nell'ordine di O(n+m) anziché O(n*m).

[ziomerio]

il problema è che io ho capito come si risolve teoricamente il problema è la pratica perchè mi mettono in difficolta quelle dimensioni M ed N
quindi potrei chiamare l indice a[0] ma visto che non so M quanto sia se 5 o 6 non so dove fermarmi ... non so se mi hai capito .
io dichiaro il vettore a[M] e il vettore b[N] quindi dovrei avere un contatore tipo int i per a e uno per b j e magari trovare i loro valori con un for(i=0,i<M,i++)
{
e qui dentro metto un altro for per la N e poi metto a confronto a[i] con b[j]

diciamo questa era la mia idea ma probabilmente sbaglio

[WarDuck]

Ma i vettori devono essere letti da tastiera o da file?

Perché altrimenti ti basta metterli nel codice, avendo le dimensioni note a priori:


#include ...

#define N 6
#define M 5

int main(void)
{
int a[] = { ... }; // dichiari gli N elementi del vettore A
int b[] = { ... }; // dichiari gli M elementi del vettore B

for (int i=0; i<N; i++)
{
for (int j=0; j<M; j++)
{
...
}
}
return 0;
}


In ogni caso così facendo scansioni tutti gli elementi di B, e come ti ho fatto notare prima non è necessario, sfruttando proprio l'informazione che gli array sono già ordinati, che credo vi sia stata data appositamente per cercare di ragionarci sopra ;).

[ziomerio]

Ma i vettori devono essere letti da tastiera o da file?

Perché altrimenti ti basta metterli nel codice, avendo le dimensioni note a priori:


#include ...

#define N 6
#define M 5

int main(void)
{
int a[] = { ... }; // dichiari gli N elementi del vettore A
int b[] = { ... }; // dichiari gli M elementi del vettore B

for (int i=0; i<N; i++)
{
for (int j=0; j<M; j++)
{
...
}
}
return 0;
}


In ogni caso così facendo scansioni tutti gli elementi di B, e come ti ho fatto notare prima non è necessario, sfruttando proprio l'informazione che gli array sono già ordinati, che credo vi sia stata data appositamente per cercare di ragionarci sopra ;).
Quindi tu cosa consigli di fare ????
i vettori gia sono definiti non li devi inserire tu =D
ed il mio problem è che il vettore c gli do come grandezza M+N e non riesco a fare
a[i]=c[k] non riesco a fare il passaggio da i vettori a e b a il vettore c:S

[WarDuck]

Il vettore C sarà dichiarato come:


#include ...
#define N 6
#define M 5
...
int c[M+N];
...


A quel punto devi capire cosa devi mettere nella posizione c[k], dove k viene incrementato dopo ogni assegnazione, ovvero avrai una cosa del genere:


k=0;
for (..)
{
...
if ( condizione su a e b verificata )
{
c[k] = ...
k++;
}
}


Più di questo non posso dirti, dato che hai detto di aver compreso da solo cosa fare e comunque nei post precedenti ho scritto tutto quello che c'è da sapere :D.

Intanto fallo funzionare anche in maniera "semplice" (ovvero facendo tutti i controlli), poi guardiamo ad eventuali ottimizzazioni.

[clockover]

Voglio darti un piccolo consiglio.... Per facilitarti la situazione (molto semplice di per se e risolvibile nei modi in cui ti hanno già consigliato) potresti crearti una funzione che prende come parametri un array, la sua dimensione, e l'elemento da cercare. Una cosa del tipo
int funzione(array, dim, elem){
cerchi l'elemento in tutto l'array
se trovato return 1
al termine della scansione dell'array ritorni 0

ti verrebbe una cosa del genere
int funzione(array, dim, elem);

int main(int argv, char ** argp){
arrayA
arrayB
dimA
dimB
nuovoArrayC
per ogni c elem di arrA
se funzione(arrayB, dimA, c) == 1
aggiungi c in nuovoArrayC

questo pseudocodice dovrebbe aiutarti molto. Ovviamente se puoi proseguire per la strada vecchia che stavi seguendo, ma comunque sono equivalenti...

ps
come ha già detto warduck possono esserci degli accorgimenti per "lavorare" di meno dato che gli array sono ordinati, ma non ne ho tenuto conto

[ziomerio]

niente piu ci provo meno mi riesce non so che fare ....
e cmq per warduck non devo inserire i valori uguali ai due vettori ma quelli differenti

A {1, 2, 3, 5, 6}
B {2, 4, 5, 7}

1 presente in B?
In B trovi 2, esci dal ciclo interno perché sai che sicuramente 1 non c'è.

2 presente in B?
Trovi 2 e lo copi in C

3 presente in B?
Trovo 2, proseguo, trovo 4, esco
magari ho inteso male quello che hai scritto

[clockover]

Dato che ti vedo molto in difficoltà scrivi il codice di ricerca di un intero in un array di interi e postalo

[ziomerio]

scrivo solo la funzione
int ricerca(int array[],int key,int size) key sarebbe il numero che inserisco

{
int n=0;
for(n=0; n=< size - 1;n++)
if (array[n]==key)
return n;
return -1
}

[clockover]

perfetto e adesso basta fare un ciclo (nel main) che scorre l'altro array e per ogni suo elemento chiama la funzione e per ogni return diverso da -1 lo aggiunge nel nuovo array...

[clockover]

Ops chiedo scusa ho capito male il problema.. comunque è uguale... per ogni return uguale a -1 lo aggiungi nel vettore..

[WarDuck]

niente piu ci provo meno mi riesce non so che fare ....
e cmq per warduck non devo inserire i valori uguali ai due vettori ma quelli differenti

[...]
magari ho inteso male quello che hai scritto

Hai ragione, è il contrario, adesso correggo :D.

[clockover]

Effettivamente sono stato troppo frettoloso non avevo capito bene il problema... spero di non averlo confuso troppo!

[ziomerio]

quindi non mi conviene usare la ricerca nei vettori???:confused:

[WarDuck]

quindi non mi conviene usare la ricerca nei vettori???:confused:

No allora ricapitoliamo, ti serve la ricerca di un elemento in un vettore.

Scansioni tutto il vettore A cercando elemento per elemento se questo è contenuto nel vettore B.

Se non c'è lo copi in C, altrimenti passi avanti.

Intanto implementa questa cosa, poi penseremo a sfruttare l'informazione dell'array ordinato per ottimizzare la ricerca.

[ziomerio]

io non ci riesco

[WarDuck]

io non ci riesco

Posta il codice che hai scritto e vediamo cosa c'è che non va.