[C++]Funzione ricorsiva: incastro stringhe

[mistergks]

Ho fatto questo esercizio ma non riesco a farlo funzionare, mi date una mano?

Si scriva in C++ una funzione RICORSIVA che, ricevuti come parametri (almeno) tre array di caratteri, A B e C, e la loro dimensione, riempia C incastrando ad incrocio i caratteri presenti in A e B come descritto di seguito. Ogni coppia di elementi consecutivi in C deve essere formata da un carattere di A e da uno di B; gli elementi di A vanno usati da sinistra verso destra( cioè prima il primo, poi il secondo e così via) mentre gli elementi di B devono essere usati da destra verso sinistra (ossia, prima l’ultimo, poi penultimo, ecc.). Pertanto, la prima coppia di elementi in C sarà formata dal primo carattere di A e dall’ultimo in B, la seconda coppia in C, conterrà, il secondo elemento di A ed il penultimo di B e così via, finché tutti i caratteri di A e di B saranno stati considerati.
Si noti che, perché l’incastro sia fattibile, gli array A e B devono avere la stessa dimensione n, mentre la dimensione di C deve essere 2*n. Se la funzione riceve come parametri array le cui dimensioni non rispettano queste condizioni, l’incastro non deve essere effettuato e la funzione deve terminare restituendo false.

 
  A                     B                    C
VERDE             ROSSO              VOESRSDOER
                                                                          
        
ESEMPIO: Dati gli array A e B riportati sopra, la funzione dovrà 
riempire l’array C come illustrato in figura e terminerà restituendo true.

La mia soluzione:

bool incastro(char A[], int dim, char B[], int dim, char C[],  int dimC, int i){
       if(dimC!=dim*2)
       return false;
       
       if(A[i]==dim)
       return true;
       C[i]=A[i];
       C[i]=B[i];

incastro(A, dim, B, dim-1, C, dimC, i+1);
}

[wingman87]

bool incastro(char A[], int dim, char B[], int dim, char C[],  int dimC, int i){
       if(dimC!=dim*2)
       return false;
       
       if(A[i]==dim)
       return true;
       C[i]=A[i];
       C[i]=B[i];

incastro(A, dim, B, dim-1, C, dimC, i+1);
}

Ti ho evidenziato le parti che secondo me sono da correggere.
Intanto non puoi chiamare con lo stesso nome due parametri diversi (mi riferisco a dim che hai usato sia per la dimensione di A sia per quella di B).
Poi nella condizione di terminazione true dovresti confrontare l'indice i con dim, non A[i].
Le assegnazioni non vanno bene per via degli indici, devi considerare che, mentre in A e in B avanzi di uno per volta a leggere i valori, in C devi inserire 2 valori per volta. Riguardo a questo inoltre tu hai scritto consecutivamente due valori diversi nella stessa posizione C[i].
Infine ci sono dei problemi nella chiamata finale: perché diminuisci dim di 1? Tieni poi sempre conto che devi usare due nomi di parametri distinti per le dimensioni.

[mistergks]

ho risolto spero.... ora va bene il codice migliorato??

bool incastro(char A[],int sizeA, char B[],int sizeB, char C[], int sizeC, int i){
     
     if(sizeA != sizeB && sizeC != 2*sizeA) //per terminare subito
     return false;
     
     if(i==sizeC) //caso base
     return true;
     
     C[i]=A[i];
     C[i+1]=B[sizeB];
     
     incastro(A, sizeA, B, --sizeB, C, sizeC, i+1);        
}

[wingman87]

Originariamente inviato da mistergks

ho risolto spero.... ora va bene il codice migliorato??

bool incastro(char A[],int sizeA, char B[],int sizeB, char C[], int sizeC, int i){
     
     if(sizeA != sizeB && sizeC != 2*sizeA) //per terminare subito
     return false;
     
     if(i==sizeC) //caso base
     return true;
     
     C[i]=A[i];
     C[i+1]=B[sizeB];
     
     incastro(A, sizeA, B, --sizeB, C, sizeC, i+1);        
}

Quel && deve diventare un || Perché se una qualsiasi di quelle condizioni si verifica non puoi andare avanti.
Gli indici di C non vanno bene, facciamo un esempio:
alla prima iterazione i=0 -> scrivi in C[0] e C[1]
alla seconda i=1 -> scrivi in C[1] e C[2]
In pratica ogni volta sovrascrivi uno dei valori che hai scritto prima.
Non puoi usare sizeB per indicizzare B perché quando effettui la chiamata ricorsiva devi decrementare sizeB e questo lo rende diverso da sizeA facendoti entrare nel primo if.

[mistergks]

Ops...che disastro ... ora dovrebbe andare...

bool incastro(char A[],int sizeA, char B[],int sizeB, char C[], int sizeC, int i){
     
     if(sizeA != sizeB || sizeC != 2*sizeA) //per terminare subito
     return false;
     
     if(i==sizeC) //caso base
     return true;
     
     C[i]=A[i];
     C[i+1]=B[j];
     
     incastro(A, sizeA, B, sizeB, C, sizeC, i+2, --j);        
}

come mai il compilatore mi da questo errore?

error: too few arguments to function `bool incastro(char*, int, char*, int, char*, int, int, int)'

Significa che la funzione ha troppi argomenti? c'è un numero massimo? non lo sapevo...e come si fa quindi?

[wingman87]

Originariamente inviato da mistergks

Ops...che disastro ... ora dovrebbe andare...

bool incastro(char A[],int sizeA, char B[],int sizeB, char C[], int sizeC, int i){
     
     if(sizeA != sizeB || sizeC != 2*sizeA) //per terminare subito
     return false;
     
     if(i==sizeC) //caso base
     return true;
     
     C[i]=A[i];
     C[i+1]=B[j];
     
     incastro(A, sizeA, B, sizeB, C, sizeC, i+2, --j);        
}

come mai il compilatore mi da questo errore?

error: too few arguments to function `bool incastro(char*, int, char*, int, char*, int, int, int)'

Significa che la funzione ha troppi argomenti? c'è un numero massimo? non lo sapevo...e come si fa quindi?

j dove è dichiarato? Inoltre se i avanza di 2 in 2 quando leggi il valore A[i] salterai tutti i valori in posizione dispari (leggerai A[0], A[2], A[4], A[6] ...)

[mistergks]

oh cavolo.....come posso risolvere sta cosa???

[wingman87]

Io userei solo l'indice i, quindi farei a meno di j. Inoltre i lo incrementerei di 1 per volta, invece di 2.
Quindi per i=0:
C[0]=A[0]
C[1]=B[sizeB-1]
per i=1
C[2]=A[1]
C[3]=B[sizeB-2]
per i=2
C[4]=A[2]
C[5]=B[sizeB-3]
...
Devi capire qual è la relazione tra questi indici e i.

[mistergks]

Ho usato un nuovo indice per l'array A..mi sembra l'unica soluzione... la j è vero...c'era l'errore che andava inizializzata a dimB per scorrere dall'ultimo elemento al primo...comunque ora ho usato direttamente l'indice di dimensione...

bool incastro(char A[],int sizeA, char B[],int sizeB, char C[], int sizeC, int i, int k){
     
     if(sizeA != sizeB || sizeC != 2*sizeA) //per terminare subito
     return false;
     
     if(i==sizeC) //caso base
     return true;
     
     C[i]=A[k];
     C[i+1]=B[sizeB-k];
     
     incastro(A, sizeA, B, sizeB, C, sizeC, i+2, ++k);        
}

[mistergks]

Mi è sorto un dubbio sul caso base... incrementando i di 2... se ad esempio non ci fosse stato il vincolo, che il vettore C deve essere grande quando la somma di A e B ed essi devono essere uguali...quindi C avrà size pari sicuramente, quale sarebbe stato il caso base?

[wingman87]

Ciao, ora il tuo codice mi sembra quasi corretto, manca solo un -1 lì dove l'ho aggiunto nel codice sotto e un return

bool incastro(char A[],int sizeA, char B[],int sizeB, char C[], int sizeC, int i, int k){
     
     if(sizeA != sizeB || sizeC != 2*sizeA) //per terminare subito
     return false;
     
     if(i==sizeC) //caso base
     return true;
     
     C[i]=A[k];
     C[i+1]=B[sizeB-k-1];
     
     return incastro(A, sizeA, B, sizeB, C, sizeC, i+2, ++k);        
}

Quel -1 serve perché altrimenti per k=0 sfori oltre il limite dell'array B, e in più non andrai mai a considerare B[0].
Per il resto va tutto bene. Non ho capito molto la tua domanda quindi evito di rispondere in modo errato.

Ti aggiungo il codice dell'esercizio svolto usando solo l'indice i (quindi senza k) e con una piccola ulteriore ottimizzazione/miglioria.

bool incastro(char A[], int sizeA, char B[], int sizeB, char C[], int sizeC){

     if(sizeA != sizeB || sizeC != 2*sizeA)
          return false;
     return incastro_int(A,B,sizeA,C,0);

}

bool incastro_int(char A[], char B[], int sizeAB, char C[], int i){

     if(i==sizeAB)
     return true;
     
     C[2*i]=A[i];
     C[2*i+1]=B[sizeAB-i-1];
     
     return incastro_int(A, B, sizeAB, C, i+1);     
   
}

Non l'ho provato ma dovrebbe andare.