FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

di il
16 risposte

FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

Salve. Sto riscontrando un problema con il programma che si evince dal titolo. Di seguito posto il codice e ne spiego il problema:
 #include <stdio.h>
/*Fusione di due array ordinati in un terzo vettore anch'esso ordinato*/
#define n 9 /*DIMENSIONE VETTORE 1*/
#define m 4 /*DIMENSIONE VETTORE 2*/

int main() {
    int v[n], u[m], w[n+m], i, j, aux, k;
    printf("\t\t\t\t\t\t FUSIONE DI DUE VETTORI ORDINATI IN UN TERZO ANCH'ESSO ORDINATO\n");
    /*IMMISSIONE VALORI VETTORI*/
    for(i=0;i<n;i++){
        printf("Inserire valore %d del vettore 1: \n", i+1);
        scanf("%d", &v[i]);
    }
    for(j=0;j<m;j++){
        printf("Inserire valore %d del vettore 2: \n", j+1);
        scanf("%d", &u[j]);
    }
    /*ORDINAMENTO DEI VETTORI (CRESCENTE)*/
    for(j=0;j<n-1;j++){
        for(i=0;i<n-1;i++){
            if(v[i]>v[i+1]) {
                aux = v[i + 1];
                v[i + 1] = v[i];
                v[i] = aux;
            }
        }
    }
    for(j=0;j<m-1;j++){
        for(i=0;i<m-1;i++){
            if(u[i]>u[i+1]) {
                aux = u[i + 1];
                u[i + 1] = u[i];
                u[i] = aux;
            }
        }
    } /*ORDINAMENTO VETTORI TERMINATO*/
    printf("\t\t\t\t\t\t\t\t\n I VETTORI SONO STATI ORDINATI E VERRANNO STAMPATI!\n");
    printf("\nVETTORE 1: ");
    for(i=0;i<n;i++){
    printf("%5d", v[i]);
    }
    printf("\nVETTORE 2: ");
    for(j=0;j<m;j++){
        printf("%5d", u[j]);
    }
    /*FUSIONE VETTORI*/
        for(i=0,j=0,k=0; k<m+n;i++,j++,k++){
                if (i == n && n<m) {
                    w[k] = u[j];
                } if(j==m && m<n){ /* DOVE MI SI PRESENTA IL PROBLEMA */
                    w[k] = v[i];
                }
            if(v[i]<u[j]){
                w[k]=v[i];
                j--;
            }else if(u[j]<v[i]){
                w[k]=u[j];
                i--;
            }else if(v[i]==u[j]){
                w[k]=v[i];
                w[k+1]=u[j];
                k++;
            }
        }
    printf("\nVETTORE FUSIONE ORDINATO: ");
    for(k=0;k<n+m;k++){
        printf("%5d", w[k]);
    }
}
Ricordando che con "n" indico la dimensione del primo vettore e con "m" la dimensione del secondo, dopo il commento "FUSIONE VETTORI", ho aggiunto due condizioni, ovvero la prima impone che se la dimensione del primo è vettore è minore della dimensione del secondo vettore e contemporaneamente si verifica che l'indice "i" del primo vettore assuma valore "n", allora tutti i restanti elementi del terzo vettore (vettore fusione) devono essere uguali agli elementi restanti del secondo vettore (dopo aver effettuato tutti i confronti del caso). Vi dirò, fin qui tutto a meraviglia, fintanto che il primo vettore è minore del secondo il codice è perfetto e funziona con qualsivoglia dimensione data ai due vettori, finché sia rispettata la condizione che la dimensione del primo sia minore del secondo. Automaticamente, ho imposto la stessa condizione anche nel caso in cui la dimensione del primo vettore sia maggiore della dimensione del secondo vettore. Adesso però nasce il problema, perché se faccio in modo che il primo vettore sia maggiore del secondo, arrivati alla condizione suddetta invece di salvarmi nel vettore fusione gli elementi rimasti del primo vettore, mi va a riempire il vettore fusione partendo di nuovo dai primi elementi del primo vettore. Il codice, cosi come l'ho postato, restituisce l'errore di cui parlo, se magari non fossi stato chiaro ci si può provare a compilarlo per capire. Ringrazio anticipatamente per un eventuale aiuto.

16 Risposte

  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Io, per non saper ne leggere ne scrivere, quindi senza entrare nel merito dell'algoritmo utilizzato, mi limiterei a trasferire la parte di "riordinamento" ad una funzione apposita, e nel main() richiamerei la funzione eventualmente scambiando gli argomenti....
    ammetto che è un metodo un po' brutale, ma da programmatore "giocattolo" è la strada più semplice che mi è venuta in mente...
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Ciao.

    - non hai ancora studiato le funzioni, vero?
    - puoi sostituire
    printf("%5d", v[i]);
    con un semplice
    printf("%d ", v[i]);
    - l'algoritmo di ordinamento, che dovrebbe essere un bubble sort, può essere ottimizzato cambiando la condizione del for più interno con i<n-1-j, in quanto ad ogni iterazione del ciclo più esterno, il massimo si troverà alla fine dell'array;
    - per quanto riguarda invece la fusione degli array, secondo me ti stai complicando troppo la vita. Io farei qualcosa del genere:
        i = 0;
        j = 0;
        for(k = 0; k < m + n; ++k)
        {
            if(j == m || i != n && v[i] < u[j])//ho qualche dubbio al riguardo, vedi P.S.
            {
                w[k] = v[i++];
            }
            else
            {
                w[k] = u[j++];
            }
        }
    La relazione tra m e n non ha nessuna importanza e sinceramente non capisco il motivo per cui li confronti.


    P.S.
    Avrei una domanda anche io, magari qualcuno può aiutarmi a chiarire questo dubbio. La condizione dell'if da me scritta è corretta o necessita di qualche parentesi?
    Secondo me è corretta perché il seguente codice
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int A = 1;
        int B = 0;
        int C = 0;
        cout << (A || ++B && C) << " " << B;
    }
    mi stampa
    1 0
    ma allora mi chiedo: in che senso && ha una precedenza maggiore rispetto a ||?
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Allora, grazie innanzitutto ad entrambi per la risposta. Nippolo, il tuo MERGE funziona perfettamente e pertanto la condizione nel tuo IF è corretta. Il libro di testo (Bellini con cui mi ci trovo abbastanza bene con le spiegazione) mi da un'alternativa diversa, che mi faceva restare perplesso perché non riuscivo a capire una cosa che spero adesso possa chiarirmi tu. Quando si inizializzano a ZERO delle variabili, come in questo caso tu hai fatto con i,j (anche con k, ma intendo fuori dal ciclo for), all'interno del for, tu hai eguagliato w[k] con v[i++] ed è proprio su v[i++] che mi sorge un dubbio. Io ho appreso che i++ è un incremento e che è equivalente a i+1, invece mi pare di capire che comunque, se la variabile i è inizializzata a ZERO, nel primo ciclo questa resta comunque a 0 per poi incrementarsi, è corretto?
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    All'ora sono qui a chiedervi un favore
    posto che la soluzione (una delle) è già stata postata
    dall'alto della vostra maggiore esperienza, mi fate la cortesia di spulciarmi questo programma?
    non sto scherzando, mi farebbe molto piacere avere indicazioni da persone più esperte (io sono ancora un programmatore "giocattolo")
    
    #include <stdio.h>
    int a[] = {110, 5, 2, 8, 0}; // e alla via così, numeri varii per prove
    int b[] = {6, 3, 7, 1}; // idem
    #define A (sizeof(a)/sizeof(a[0]))
    #define B (sizeof(b)/sizeof(b[0]))
    
    // prototipi
    void ordina(int a[], int sa);
    // ordina l'array 'a' di dimensione 'sa'
    
    void riversa(int a[], int sa, int b[], int sb, int c[]);
    // riversa il contenuto dei due array 'a' e 'b', di dimensione rispettivamente 'sa' e 'sb'
    // dentro nel terzo array 'c', per definizione di dimensione pari alla somma delle dimensioni dei due in ingresso
    
    int main(int argc, char **argv)
    {
       int c[A + B];// creo l'array di destinazione
       ordina(a, A); 
       ordina(b, B);
       riversa(a, A, b, B, c);
    
       for(int i = 0; i < (A + B); i++)
       {
          // stampo il valore
          printf("Elemento numero: %d Vale: %d\n", i, c[i]);
       }
    
       return 0;
    }
    
    void riversa(int a[], int sa, int b[], int sb, int c[])
    // riversa il contenuto dei due array 'a' e 'b', di dimensione rispettivamente sa e sb
    // dentro nel terzo array 'c', per definizione di dimensione pari alla somma delle dimensioni dei due in ingresso
    {
       int i = 0; // indice in a
       int j = 0; // indice in b
       int k = 0; // indice in c
    
       while(1)
       {
          // 4 possibili condizioni:
          // array a e array b finiti
          if(i >= sa && j >= sb)
          {
             // array finiti, esco dalla funzione
             return;
          }
    
          // finito solo il primo
          if(i >= sa)
          {
             // leggo dal secondo
             c[k++] = b[j++];
             continue;
          }
    
          // finito solo il secondo
          if(j >= sb)
          {
             // leggo dal primo
             c[k++] = a[i++];
             continue;
          }
    
          // nessuno dei due finiti
          // leggo l'elemento minore dei due
          if(a[i] < b[j])
          {
             // leggo dal primo
             c[k++] = a[i++];
          }
    
          else
          {
             // leggo dal secondo
             c[k++] = b[j++];
          }
       }
    }
    
    void ordina(int a[], int sa)
    // ordina l'array a di dimensione sa
    {
       int trigger = 0; // se non ha ordinato in un ciclo, non esegue i successivi
       int top = sa; // ultimo elemento da considerare, oltre è già ordinato
    
       do
       {
          top--;
          trigger = 0;
    
          for(int i = 0; i < top; i++)
          {
             if(a[i] > a[i + 1])
             {
                trigger = 1;
                int b = a[i];
                a[i] = a[i + 1];
                a[i + 1] = b;
             }
          }
       }
       while(trigger);
    }
    
    
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    mi fate la cortesia di spulciarmi questo programma?
    In generale va bene. Buona la scelta di utilizzare una variabile "trigger" per ottimizzare l'algoritmo di ordinamento. Per quanto riguarda invece la funzione riversa() trovo che sia un po' ridondante e poco elegante, ma in ogni caso svolge correttamente il proprio dovere.

    Il libro di testo (Bellini con cui mi ci trovo abbastanza bene con le spiegazione) mi da un'alternativa diversa
    Se puoi postala, sarei curioso di leggere la soluzione data dal libro.
    Io ho appreso che i++ è un incremento e che è equivalente a i+1, invece mi pare di capire che comunque, se la variabile i è inizializzata a ZERO, nel primo ciclo questa resta comunque a 0 per poi incrementarsi, è corretto?
    Questo comportamento non c'entra con lo ZERO; devi sapere che gli operatori di incremento (++) e decremento (--) possono esse utilizzati sia come prefisso (++i) che come suffisso (i++). Nel caso prefisso la variabile viene modificata prima che venga utilizzata nell'espressione, mentre nel caso suffisso avviene il contrario, ossia la variabile viene modificata dopo essere stata utilizzata per calcolare l'espressione in cui si trova.
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Per quanto riguarda gli incrementi, si, avevo risolto semplicemente tornando indietro col testo senza dare tutto per scontato (come spesso faccio e poi mi perdo in piccolezze), ma ti ringrazio comunque perché sei stato chiaro nella spiegazione.
    Per quanto riguarda la soluzione proposta dal libro (da tenere in considerazione che sto utilizzando la seconda edizione, ne sono seguite altre 3), ti allego direttamente i pdf del codice. La prima parte è l'allegato in basso e la seconda parte è quella in alto.
    Allegati:
    26852_647e81f49b59e80b82639de316e7c6c1.png
    26852_647e81f49b59e80b82639de316e7c6c1.png

    26852_cce9561810e8f154db591087da8d9499.png
    26852_cce9561810e8f154db591087da8d9499.png
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Grazie
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Nippolo ha scritto:


    ...
    - per quanto riguarda invece la fusione degli array, secondo me ti stai complicando troppo la vita. Io farei qualcosa del genere:
        i = 0;
        j = 0;
        for(k = 0; k < m + n; ++k)
        {
            if(j == m || i != n && v[i] < u[j])  //ho qualche dubbio al riguardo, vedi P.S.
            {
                w[k] = v[i++];
            }
            else
            {
                w[k] = u[j++];
            }
        }
    La relazione tra m e n non ha nessuna importanza e sinceramente non capisco il motivo per cui li confronti.


    P.S.
    Avrei una domanda anche io, magari qualcuno può aiutarmi a chiarire questo dubbio. La condizione dell'if da me scritta è corretta o necessita di qualche parentesi?
    Secondo me è corretta perché il seguente codice
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int A = 1;
        int B = 0;
        int C = 0;
        cout << (A || ++B && C) << " " << B;
    }
    mi stampa
    1 0
    ma allora mi chiedo: in che senso && ha una precedenza maggiore rispetto a ||?
    Qualcuno saprebbe chiarirmi questo dubbio?
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Nippolo ha scritto:


    Ciao..
    .
    .


    Secondo me è corretta perché il seguente codice
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int A = 1;
        int B = 0;
        int C = 0;
        cout << (A || ++B && C) << " " << B;
    }
    mi stampa
    1 0
    secondo me ti stamperebbe la stessa cosa anche se a valesse 2 3 o centomila (scusa la mezza citazione)
    perché non stampa a, ma il risultato del test.
    Che per la valutazione di corto circuito, essendo a vero, non prosegue valutando il resto del test
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Nippolo ha scritto:


    Nippolo ha scritto:


    ...
    - per quanto riguarda invece la fusione degli array, secondo me ti stai complicando troppo la vita. Io farei qualcosa del genere:
        i = 0;
        j = 0;
        for(k = 0; k < m + n; ++k)
        {
            if(j == m || i != n && v[i] < u[j])  //ho qualche dubbio al riguardo, vedi P.S.
            {
                w[k] = v[i++];
            }
            else
            {
                w[k] = u[j++];
            }
        }
    La relazione tra m e n non ha nessuna importanza e sinceramente non capisco il motivo per cui li confronti.


    P.S.
    Avrei una domanda anche io, magari qualcuno può aiutarmi a chiarire questo dubbio. La condizione dell'if da me scritta è corretta o necessita di qualche parentesi?
    Secondo me è corretta perché il seguente codice
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int A = 1;
        int B = 0;
        int C = 0;
        cout << (A || ++B && C) << " " << B;
    }
    mi stampa
    1 0
    ma allora mi chiedo: in che senso && ha una precedenza maggiore rispetto a ||?
    Qualcuno saprebbe chiarirmi questo dubbio?
    Il ++B è ininfluente nel codice perché (1 || 1 && 0) = (1 || 0 && 0)
    Il fatto che il risultato sia 1 mostra che && viene valutata prima di || nell'espressione, così come la moltiplicazione ha la precedenza sull'addizione in mancanza di parentesi
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Scusa se insisto, ma '++b' non viene proprio valutata, infatti stampa '1 0', se fosse valutata stamperebbe '1 1'
    Siccome già la prima parte della 'OR' vale 'vero' la seconda parte ( ++b && c) non viene proprio eseguita
    Peraltro come previsto dalla 'valutazione di corto circuito'
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    @standardoil

    Si hai ragione tu, mi ero confuso con gli operatori non short-circuit
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Cerco di spiegarmi meglio...

    La valutazione a corto circuito prevede che il secondo operando viene valutato soltanto se esso da solo non è sufficiente a determinare il risultato dell'espressione logica. Quindi in A&&B se A è falso B non viene valutato e in A||B se A è vero B non viene valutato.
    Si aggiunge però un'altra questione, ossia che stando alla teoria l'operatore && ha la precedenza sull'operatore ||.

    Consideriamo l'espressione:

    A || B && C

    Stando alla precedenza degli operatori dovrebbe essere valutata prima l'espressione B&&C (chiamiamo tale risultato D) e poi l'espressione A||D. Poi all'interno della valutazione delle due espressioni elementari si applica ovviamente il corto circuito.

    Consideriamo ora l'esempio che ho fatto in precedenza:
    int A = 1;
    int B = 0;
    int C = 0;
    cout << (A || ++B && C) << " " << B;
    stando a quanto detto prima l'output dovrebbe essere
    1 1
    Dal momento invece che l'output è
    1 0
    significa che viene valutata prima l'espressione A||++B e che per il corto circuito, essenso A vero, l'operando ++B non viene proprio valutato.

    La mia richiesta consisteva appunto nello spiegarmi questa apparente contraddizione tra teoria ed evidenza.
  • Re: FUSIONE DI DUE ARRAY ORDINATI IN UN TERZO ANCH'ESSO ORDINATO

    Bella domanda in effetti
    Credo che sia proprio per dare conto di queste eccezioni alle regole che sia stata introdotta la valutazione di corto circuito
Devi accedere o registrarti per scrivere nel forum
16 risposte