[C++] problema cardinalità crescente simmetrica (ricorsiva)

[mistergks]

Ciao a tutti..
ho provato a svolgere questo esercizio ma non ci riesco... posso spiegarvi cosa non so fare e magari mi date un consiglio su come farlo?:
allego la traccia dell'esercizio..ho dovuto ridurre le dimensioni per questioni di spazio qui sul forum... ingranditela..

Riesco a trovare la cardinalità centrale...cioè parto dal centro (n/2-1) e se i numeri a sinistra e a destra sono uguali a n/2-1 incremento un contatore (sarebbe la cardinalità);
mi blocco qua..come faccio a vedere la cardinalità di s2 e s4 (sarebbero l'insieme di sinistra e destra rispetto a quello al centro)?
poi vabbè alla fine devo confrontare le cardinalità di s2 e s4 e se sono diverse restituisco false.

http://img407.imageshack.us/img407/1326/img00421.jpg

[mistergks]

Ho caricato la traccia su:
http://depositfiles.com/files/ngs9fs60o">http://depositfiles.com/files/ngs9fs60o

Inviato dal mio GT-I9003 usando Tapatalk

[sottovento]

Ho caricato la traccia su:
http://depositfiles.com/files/ngs9fs60o">http://depositfiles.com/files/ngs9fs60o

Inviato dal mio GT-I9003 usando Tapatalk

Perdonami ma con tutta la buona volonta' che uno ci puo' mettere non si riesce a leggere nulla, o quasi. Magari puoi provare a descrivere la traccia, o scannerizzarla con una risoluzione migliore.....

[mistergks]

Delete

[mistergks]

Traccia:
http://img407.imageshack.us/img407/1326/img00421.jpg

[mistergks]

Up

Inviato dal mio GT-I9003 usando Tapatalk

[sottovento]

Una soluzione potrebbe essere la seguente (ovviamente l'entry point e' la funzione doCheck()):


bool getMiddleCount(int *vect, int n, int &lowIndex, int &highIndex)
{
if (lowIndex <= 0)
return true;
if (vect[lowIndex] != vect[highIndex])
{
lowIndex++;
highIndex--;
return lowIndex <= highIndex;
}
return getMiddleCount(vect, n, --lowIndex, ++highIndex);
}

bool checkEquals(int *vect, int startIndex, int endIndex)
{
if (startIndex == endIndex)
return true;
return (vect[startIndex] == vect[endIndex]) && checkEquals(vect, startIndex+1, endIndex);
}

bool doCheckLeftIncreasingCount(int *vect, int count, int startIndex, int endIndex)
{
if (endIndex <= startIndex) /* Base of recursion */
return true;
if (!checkEquals(vect, endIndex-count, endIndex))
return false;
count++;
return doCheckLeftIncreasingCount(vect, count, startIndex, endIndex-count);
}

bool doCheckRightIncreasingCount(int *vect, int count, int startIndex, int endIndex)
{
if (endIndex <= startIndex) /* Base of recursion */
return true;
if (!checkEquals(vect, startIndex, startIndex+count))
return false;
count++;
return doCheckRightIncreasingCount(vect, count, startIndex+count, endIndex);
}

bool doCheck(int *vect, int n)
{
int lowIndex, highIndex;
lowIndex = highIndex = n/2;
if (!getMiddleCount(vect, n, lowIndex, highIndex)) return false;
if (lowIndex <= 0)
return true; /* The whole array is filled up with the same number */
if (doCheckLeftIncreasingCount(vect, highIndex-lowIndex+1, 0, lowIndex-1))
return doCheckRightIncreasingCount(vect, highIndex-lowIndex+1, highIndex+1, n-1);
return false;
}


int main()
{
int vect[21] = { 1,1,1,1,1,2,2,2,2,3,3,3,4,4,4,4,5,5,5,5,5 };
bool res = doCheck(vect, (int)(sizeof(vect)/sizeof(int)));
printf ("Result: %s\n", res ? "OK" : "ERROR");

return 0;
}

[mistergks]

Una soluzione potrebbe essere la seguente (ovviamente l'entry point e' la funzione doCheck()):


bool getMiddleCount(int *vect, int n, int &lowIndex, int &highIndex)
{
if (lowIndex <= 0)
return true;
if (vect[lowIndex] != vect[highIndex])
{
lowIndex++;
highIndex--;
return lowIndex <= highIndex;
}
return getMiddleCount(vect, n, --lowIndex, ++highIndex);
}

bool checkEquals(int *vect, int startIndex, int endIndex)
{
if (startIndex == endIndex)
return true;
return (vect[startIndex] == vect[endIndex]) && checkEquals(vect, startIndex+1, endIndex);
}

bool doCheckLeftIncreasingCount(int *vect, int count, int startIndex, int endIndex)
{
if (endIndex <= startIndex) /* Base of recursion */
return true;
if (!checkEquals(vect, endIndex-count, endIndex))
return false;
count++;
return doCheckLeftIncreasingCount(vect, count, startIndex, endIndex-count);
}

bool doCheckRightIncreasingCount(int *vect, int count, int startIndex, int endIndex)
{
if (endIndex <= startIndex) /* Base of recursion */
return true;
if (!checkEquals(vect, startIndex, startIndex+count))
return false;
count++;
return doCheckRightIncreasingCount(vect, count, startIndex+count, endIndex);
}

bool doCheck(int *vect, int n)
{
int lowIndex, highIndex;
lowIndex = highIndex = n/2;
if (!getMiddleCount(vect, n, lowIndex, highIndex)) return false;
if (lowIndex <= 0)
return true; /* The whole array is filled up with the same number */
if (doCheckLeftIncreasingCount(vect, highIndex-lowIndex+1, 0, lowIndex-1))
return doCheckRightIncreasingCount(vect, highIndex-lowIndex+1, highIndex+1, n-1);
return false;
}


int main()
{
int vect[21] = { 1,1,1,1,1,2,2,2,2,3,3,3,4,4,4,4,5,5,5,5,5 };
bool res = doCheck(vect, (int)(sizeof(vect)/sizeof(int)));
printf ("Result: %s\n", res ? "OK" : "ERROR");

return 0;
}


Non riesco a capire il codice..forse perchè è proprio in stile c..
Puoi spiegarmi passo per passo? Pero il tutto deve essere fatto in una sola funzione!

Inviato dal mio GT-I9003 usando Tapatalk

[sottovento]

Certo che posso spiegarti. Pero' dal testo non ho dedotto che il tutto debba essere fatto in una sola funzione. Anche perche', quand'anche possibile, sarebbe davvero un'impresa non da poco.
Secondo me il fatto che abbiano scritto "scrivere una funzione che..." non esclude il fatto che possa crearne altre, da essa chiamate, per semplificarmi il lavoro, no? Specialmente quanto si parla di ricorsivita'!

Ad ogni modo:
- bool getMiddleCount(int *vect, int n, int &lowIndex, int &highIndex);
dato il vettore e la sua lunghezza, determina l'ampiezza della sequenza centrale, che deve essere simmetrica rispetto al centro. Se tale simmetria viene a mancare, ritorna false. Altrimenti ritorna true e lowIndex, highIndex contengono i due indici che delimitano detta zona. Ovviamente l'implementazione e' ricorsiva.

- bool checkEquals(int *vect, int startIndex, int endIndex)
Controlla che tutti gli elementi del vettore vect da startIndex a endIndex siano uguali e ritorna true se lo sono. L'implementazione e' ricorsiva, anche se quella iterativa sarebbe stata banale.

- bool doCheckLeftIncreasingCount(int *vect, int count, int startIndex, int endIndex)
Controlla che gli intervalli a sinistra dell'intervallo centrale siano di dimensione crescente, come richiesto. Implementazione ricorsiva.

- bool doCheckRightIncreasingCount(int *vect, int count, int startIndex, int endIndex)
Come sopra, ma si muove a destra.

doCheck() e' la funzione principale, che deve solo chiamare le funzioni di cui sopra per fare il "dirty job" :D

Prova a rileggerle sapendo cosa devono fare. Ovviamente se ti servono piu' informazioni saro' felice di provvedere; preferirei delle domande precise su un particolare dell'implementazione....