[C++] funzione ricorsiva che verifica sovrapponibilità

[mistergks]

ho un esercizio:
dato un array v[] con dimensione N, si verifichi se l'array è ripiegabile su se stesso con passo pari a 3.
Per ripiegatura si intende: i primi tre numeri devono essere uguali ai secondi 3 numeri capovolti(cioè leggendoli in modo inverso..in modo palindromo diciamo: ad esempio 123 è uguale a 321).
ad esempio avendo l'array: 1,2,3,3,2,1,2,4,6,12,8,4 di dimensione 12
la ripiegatura è possibile perchè 123 è uguale a 321. Dalla loro sovrapposizione si creerà una nuova terna sommando 1+1,2+2 e 3+3 e si forma la nuova terna cioè 6,4,2
quindi ora la ripiegatura va fatta con la nuova terna e l'array diventa:
6,4,2,2,4,6,12,8,4.. stesso discorso di prima....
quando si arriva ad avere solo 3 numeri non è possibile piu ripiegatura e quindi la funzione termina stampando questi ultimi 3 numeri.

A me non funzione, ma non capisco il perchè:


#include <iostream>
using namespace std;

bool ricorsiva(int v[], int dim, int i, int k, int sommaA, int sommaB, int sommaC);

int main(){
const int dim=12;
int i=0,k=0, sommaA=0, sommaB=0, sommaC=0;
int v[dim]={1,2,3,3,2,1,2,4,6,12,8,4};

if(ricorsiva(v,dim,i,k,sommaA,sommaB,sommaC))
for(int i=0; i<dim; i++)
cout<<v[i]<<endl;
else
cout<<"non sovrapponibile"<<endl;

system("pause");
return 0;
}

bool ricorsiva(int v[], int dim, int i, int k, int sommaA, int sommaB, int sommaC){

if(i%3!=0)
return false;

if(i==dim-3)
return true;

sommaA=v[i], sommaB=v[i+1], sommaC=v[i+2];

if(sommaA != v[k] || sommaB != v[k-1] || sommaC != v[k-2])

ricorsiva(v,dim,i+3,k+3,v[i],v[i+1],v[i+2]);
}

[mistergks]

ho un esercizio:
dato un array v[] con dimensione N, si verifichi se l'array è ripiegabile su se stesso con passo pari a 3.
Per ripiegatura si intende: i primi tre numeri devono essere uguali ai secondi 3 numeri capovolti(cioè leggendoli in modo inverso..in modo palindromo diciamo: ad esempio 123 è uguale a 321).
ad esempio avendo l'array: 1,2,3,3,2,1,2,4,6,12,8,4 di dimensione 12
la ripiegatura è possibile perchè 123 è uguale a 321. Dalla loro sovrapposizione si creerà una nuova terna sommando 1+1,2+2 e 3+3 e si forma la nuova terna cioè 6,4,2
quindi ora la ripiegatura va fatta con la nuova terna e l'array diventa:
6,4,2,2,4,6,12,8,4.. stesso discorso di prima....
quando si arriva ad avere solo 3 numeri non è possibile piu ripiegatura e quindi la funzione termina stampando questi ultimi 3 numeri.

A me non funzione, ma non capisco il perchè:


#include <iostream>
using namespace std;

bool ricorsiva(int v[], int dim, int i, int k, int sommaA, int sommaB, int sommaC);

int main(){
const int dim=12;
int i=0,k=0, sommaA=0, sommaB=0, sommaC=0;
int v[dim]={1,2,3,3,2,1,2,4,6,12,8,4};

if(ricorsiva(v,dim,i,k,sommaA,sommaB,sommaC))
for(int i=0; i<dim; i++)
cout<<v[i]<<endl;
else
cout<<"non sovrapponibile"<<endl;

system("pause");
return 0;
}

bool ricorsiva(int v[], int dim, int i, int k, int sommaA, int sommaB, int sommaC){

if(i%3!=0)
return false;

if(i==dim-3)
return true;

sommaA=v[i], sommaB=v[i+1], sommaC=v[i+2];

if(sommaA != v[k] || sommaB != v[k-1] || sommaC != v[k-2])

ricorsiva(v,dim,i+3,k+3,v[i],v[i+1],v[i+2]);
}


up

[Mommolo]

Premessa: è un po' non lavoro in C quindi spero di non dire castronerie :)

La logica della funzione ricorsiva, da quello che vedo, mi sembra piuttosto sballata.
Cosa volevi fare?
Vedo che le tre variabili sommaA..C le passi come parametro ma non le controlli mai, perché vengono assegnate prima della chiamata ricorsiva.
forse nelle intenzioni servivano ad altro :confused:

Poi invochi la ricorsione se
sommaA != v[k]
oppure uno degli altri 2 casi.
Ma non dovrebbe essere il contrario? Controlli i primi 3 numeri con i successivi e se il controllo è corretto prosegui con la ricorsione?

Io farei un po' diversamente...:rolleyes:

[mistergks]

Premessa: è un po' non lavoro in C quindi spero di non dire castronerie :)

La logica della funzione ricorsiva, da quello che vedo, mi sembra piuttosto sballata.
Cosa volevi fare?
Vedo che le tre variabili sommaA..C le passi come parametro ma non le controlli mai, perché vengono assegnate prima della chiamata ricorsiva.
forse nelle intenzioni servivano ad altro :confused:

Poi invochi la ricorsione se
sommaA != v[k]
oppure uno degli altri 2 casi.
Ma non dovrebbe essere il contrario? Controlli i primi 3 numeri con i successivi e se il controllo è corretto prosegui con la ricorsione?

Io farei un po' diversamente...:rolleyes:

ops...ho sbagliato a trascrivere il codice!
manca il return false a quell'if! :


if(sommaA != v[k] || sommaB != v[k-1] || sommaC != v[k-2])
return false;


Il mio ragionamento è:
se la condizione di sopra non viene rispettata, restituisco subito falso
altrimenti continuo con la ricorsione al passo successivo e se tutto va bene, cioè arrivo al caso if(i==dim-3) e non ho ancora restituito false, restituisco true!

[wingman87]

Il problema principale è che non fai le somme.
A parte questo io l'avrei strutturato in due funzioni, la prima che nasconde la logica interna (e che quindi non prende come parametri i, k, sommaA, ...) e la seconda che viene richiamata dalla prima.
In questo modo nella prima puoi anche fare i check più generici una sola volta, ad esempio controllare che dim sia un multiplo di 3.

[Mommolo]

converrai con me che scrivere:

sommaA=v[i], sommaB=v[i+1], sommaC=v[i+2];

if(sommaA != v[k] || sommaB != v[k-1] || sommaC != v[k-2])

equivale a scrivere

if(v[i] != v[k] || v[i+1]!= v[k-1] || v[i+2] != v[k-2])

quindi, a che servono sommaA|B|C?

EDIT: ti ha risposto wingman87 ;)

Ti faccio anche notare che hai dichiarato le stesse variabili sia nel main che nella funzione, col rischio di confonderti... :)

[mistergks]

ops...ho trascritto sbagliato di nuovo..il fatto è che invece di ricopiarla dal foglio in cui avevo scritto la funzione, l'ho rifatta a memoria dimenticando alcune cose importanti:

nel main k lo inizializzo a 5! quindi k=5!

bool ricorsiva(int v[], int dim, int i, int k, int sommaA, int sommaB, int sommaC);

int main(){
const int dim=12;
int i=0,k=5, sommaA=0, sommaB=0, sommaC=0;
int v[dim]={1,2,3,3,2,1,2,4,6,12,8,4};

if(ricorsiva(v,dim,i,k,sommaA,sommaB,sommaC))
for(int i=0; i<dim; i++)
cout<<v[i]<<endl;
else
cout<<"non sovrapponibile"<<endl;

system("pause");
return 0;
}
bool ricorsiva(int v[], int dim, int i, int k, int sommaA, int sommaB, int sommaC){

if(i%3!=0)
return false;

if(i==dim-3)
return true;

sommaA=v[i], sommaB=v[i+1], sommaC=v[i+2];

if(sommaA != v[k] || sommaB != v[k-1] || sommaC != v[k-2])
return false;

ricorsiva(v, dim, i+3, k+3, v[i]+v[k], v[i+1]+v[k-1], v[i+2]+v[k-2]);
}

Ho messo in corsivo le cose che ho modificato...ho deciso di inserire le variabili sommaA,B e C per passare di volta in volta la somma... però al primo passo devono essere inizializzate con v[i], v[i+1] e v[i+2] rispettivamente.

[wingman87]

if(i%3!=0)
return false;
i parte da zero e ogni volta lo incrementi di 3: la condizione di questo if non sarà mai vera. Piuttosto dovresti controllare che la dimensione del vettore sia un multiplo di 3.

if(i==dim-3)
return true;
Se c'è la possibilità che il vettore abbia zero elementi questa condizione non basta.

sommaA=v[i], sommaB=v[i+1], sommaC=v[i+2];
Così sovrascrivi le variabili somma che ti sono state passate come argomento (e quindi di fatto non fai le somme).

ricorsiva(v, dim, i+3, k+3, v[i]+v[k], v[i+1]+v[k-1], v[i+2]+v[k-2]);
Manca un return davanti a questa istruzione, inoltre non passi le somme accumulate ma solo le somme di due elementi (ad esempio v[i]+v[k] dovrebbe essere sommaA+v[k]).

[mistergks]

if(i%3!=0)
return false;
i parte da zero e ogni volta lo incrementi di 3: la condizione di questo if non sarà mai vera. Piuttosto dovresti controllare che la dimensione del vettore sia un multiplo di 3.

if(i==dim-3)
return true;
Se c'è la possibilità che il vettore abbia zero elementi questa condizione non basta.

sommaA=v[i], sommaB=v[i+1], sommaC=v[i+2];
Così sovrascrivi le variabili somma che ti sono state passate come argomento (e quindi di fatto non fai le somme).

ricorsiva(v, dim, i+3, k+3, v[i]+v[k], v[i+1]+v[k-1], v[i+2]+v[k-2]);
Manca un return davanti a questa istruzione, inoltre non passi le somme accumulate ma solo le somme di due elementi (ad esempio v[i]+v[k] dovrebbe essere sommaA+v[k]).

per passare le somme cumulate invece come faccio?!
ma a me le inizializzazioni che dò a sommaA,B e C mi servono solo per il primo passo! Poi sovrascrivo con le somme..

[wingman87]

per passare le somme cumulate invece come faccio?!
Ad esempio come ho scritto in rosso nel precedente post.
ma a me le inizializzazioni che dò a sommaA,B e C mi servono solo per il primo passo! Poi sovrascrivo con le somme..
Ora però lo fai ad ogni passo, non solo al primo passo.

[goldorak]

Supponi di trovarti sull'elemento i-esimo dell'array. Prima di effettuare la chiamata ricorsiva devi verificare che una certa condizione valga tra gli elementi
v[i], v[i+1],v[i+2],v[i+3], v[i+4] e v[i+5].

Devono valere queste tre condizioni : (*)

v[i] == v[i+5]
v[i+1] == v[i+4]
v[i+2] == v[i+3]

A questo punto prima di effettuare la chiamata ricorsiva sulla posizione i+3 basta aggiornare i valori di v[i+3], v[i+4] e v[i+5] (e' una operazione banalissima questa e quindi non te la scrivo). Cosi' quando arrivi al caso base della ricorsione (ti trovi sul terzo-ultimo elemento dell'array) gli ultimi 3 elementi conterrano i valori corretti da stampare. Ovviamente se le condizioni (*) non sono soddisafatte durante l'esecuzione esci restituendo false.