sunra
08-04-2006, 14:07
Ciao a tutti.
Sono nuovo di questo forum e non so se posso postare programmi interi. Nel caso ho riscontrato un problema curioso in questo programma in C. Brevemente, quello che fa è generare tutte le permutazioni di
{1,2,3,4,5,6,7,8,9,10} e verificare su ogni permutazione due condizioni: whist1 e whist2. Se la permutazione soddisfa entrambe la printa, altrimenti non fa nulla. Premetto che il programma per generare permutazioni l'ho scaricato da internet e funziona benissimo. Ho solo aggiunto i test da fare. Ora, il problema sorge nel passo della funzione perm
if( whist1(permutazione) && whist2(permutazione)) printf(permutazione);
else 'continua a generare la prossima permutazione';
L'espressione condizionale if si comporta in maniera strana: se la scrivo come sopra, ottengo anche permutazioni che soddifano whist1 ma non soddisfano whist2. Nota bene che whist1 e' sempre soddisfatta, ma a volte whist2 no e NON ottengo tutte le permutazioni che soddisfano la sola whist1, quindi qualche volta whist2 viene controllata.
Se invece inverto l'ordine di controllo nell'espressione condizionale, facendo testare prima whist2 di whist1:
if( whist2(permutazione) && whist1(permutazione)).....
ottengo permutazioni che in effetti soddisfano entrambe le condizioni. Com'è possibile?
Premetto che whist1 è il test più veloce da effettuare e quindi preferirei testarlo per primo, visto che poi avro' bisogno di far girare il programma su numeri grossi (e non su solo 10 numeri). Inoltre whist1 e whist2 funzionano a dovere se isolati dal ciclo che genera permutazioni, quindi il problema non dovrebbe essere li.
Vi posto il codice nella speranza che qualcuno abbia la pazienza di scoprire dove sta il problema. L'ho (forse troppo!) commentato per agevolare la lettura.
/*
* Un test sulle differenze fra gli elementi delle permutazioni di una stringa
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DIM 10
#define MOD 11
#define TWICEDIM 20
/*DEFINISCO I DUE TEST*/
/* mod (ausiliaria) fonisce il resto della divisione per MOD*/
int mod(int dividendo)
{
int risultato=dividendo%MOD;
if (risultato<0) risultato+= MOD;
return risultato;
} /*FINE MOD*/
/* whist1 effettua il PRIMO TEST di compatibilità fra stringa e test_stringa*/
int whist1(char stringa[DIM], char test_stringa[DIM])
{
int i;
char differenze[DIM]; /* un vettore ausiliario*/
/*Setto il vettore differenze*/
differenze[0]=(char) mod(stringa[0]-stringa[1])+33;
differenze[1]=(char) mod(stringa[1]-stringa[0])+33;
for(i=2; i<DIM;i++)
{
if((i+2)%4==0 || (i+2)%4==1) differenze[i]=(char) mod(stringa[i]-stringa[i+2])+33;
else differenze[i]=(char) mod(stringa[i]-stringa[i-2])+33;
}
/*Fine settaggio differenze*/
/* Effettuo il test: ogni elemento di test_stringa
* deve comparire nella stringa differenze
* strspn(A, B) restituisce la lunghezza del prefisso di A
* costituito da elementi di B.
*/
if (strspn(test_stringa, differenze)==DIM) return 1;
else return 0;
} /*FINE TEST WHIST1*/
/*whist2 effettua il SECONDO TEST di compatibilità fra stringa e test_stringa*/
int whist2(char stringa[DIM], char test_stringa[DIM])
{
int i, none=0;
char differenze[TWICEDIM]; /*un altro vettore ausiliario*/
/*Setto il vettore differenze*/
differenze[0]=(char) mod(stringa[0]-33)+33;
differenze[1]=(char) mod(33-stringa[1])+33;
for(i=2; i<DIM;i++)
{
if((i+2)%4!=3) differenze[i]=(char) mod(stringa[i]-stringa[i+1])+33;
else differenze[i]=(char) mod(stringa[i]-stringa[i-3])+33;
}
for(i=DIM; i<TWICEDIM;i++) differenze[i]=(char) mod(33-(int) differenze[i-DIM])+33;
/*fine settaggio differenze*/
/*Effettuo un primo controllo: ogni elemento di test_stringa deve
*comparire in differenze
*strspn(A, B) restituisce la lunghezza del prefisso di A
*costituito da elementi di B.
*/
if (strspn(test_stringa, differenze)==DIM)
{
/*Effettuo il secondo controllo: ogni elemento di test_stringa
*deve comparire almeno due volte in differenze
*/
for(i=0; none==0 && i<DIM; i++)
{
/* La prima occorrenza dell'elemento in differenze
* deve essere diversa dall'ultima
*/
if (strchr(differenze,(char) 34+i)==strrchr(differenze, (char) 34+i)) none++;
}
if (none==0) return 1;
else return 0;
}
else return 0;
} /*FINE WHIST2*/
/* HO FINITO DI DEFINIRE I DUE TEST*/
/*DEFINISCO LA FUNZIONE RICORSIVA CHE GENERA LE PERMUTAZIONI*/
/* remchr (ausiliaria) rimuove un carattere da una stringa.
* Il carattere eliminato viene restituito al chiamante.
*/
char remchr (char *str, int c)
{
int i;
int length = strlen (str);
/*strlen calcola la lunghezza di una stringa */
char lost = str[c];
for (i = c; i < length; i++)
str[i] = str[i + 1];
return lost;
} /*FINE REMCHAR*/
/*perm genera tutte le permutazioni di una stringa di DIM
* elementi e di ciascuna controlla che verifichi whist1 e whist2
*/
int perm (char *tlock, char *tfree, char test_stringa[DIM])
{
int i, contatore;
char *nLock;
char *nFree;
char tmp[2];
tmp[1] = '\0';
if (strlen (tfree) == 0)
/* Se tfree ha lunghezza nulla, allora abbiamo generato una
* permutazione completa della stringa iniziale, contenuta
* in tlock.Verifichiamo whist1 e whist2 e se soddisfa entrambe,
* la visualizziamo
*/
{ /*QUI C'E' IL PROBLEMA DI CUI SOPRA?*/
if ( whist1(tlock,test_stringa) && whist2(tlock,test_stringa) )
{
for(i=0; i<DIM; i++) printf("%3d", (int) tlock[i]-33);
printf("\n");
}
}
else
{
/* Se tfree ha lunghezza maggiore di zero, allora tlock contiene
* una permutazione di alcune lettere della stringa iniziale.
* Allora, per ciascuna lettera non ancora inserita nella permutazione,
* possiamo generare una nuova tlock, aggiungendo questa lettera in
* coda, e quindi formare una nuova coppia tlock-tfree, che ci avvicina
* alla costruzione delle permutazioni.
*/
for (i = 0; i < strlen (tfree); i++)
{
/* strdup crea un duplicato di una stringa
* La usiamo per lavorare sui parametri senza modificarli
*/
nFree = strdup (tfree);
nLock = strdup (tlock);
/* Rimuoviamo l'i-esimo carattere dalla stringa nFree */
tmp[0] = remchr (nFree, i);
/* strcat concatena due stringhe
* La usiamo per creare una parte della permutazione
* fissata con la nuova lettera estratta dall'insieme di
* quelle disponibili in tfree.
*/
strcat (nLock, tmp);
/* Richiamiamo perm sulla nuova coppia nLock-nFree, con
* strlen(nLock)==strlen(tlock)+1, e
* strlen(nFree)==strlen(tfree)-1.
*/
perm (nLock, nFree, test_stringa);
/* Distruggiamo le stringhe nLock ed nFree, che non ci
* useremo ulteriormente.
*/
free (nLock);
free (nFree);
}
}
return 0;
} /*FINE PERM*/
/*HO FINITO DI DEFINIRE LE FUNZIONI*/
int main ()
{
int i;
char test_stringa[DIM], sfree[DIM], slock[DIM];
slock[0] = '\0';
for(i=0; i<DIM;i++)
{
sfree[i]=(char) 34+i;
test_stringa[i]=(char) 34+i;
}
printf ("\nLe permutazioni che soddisfano le condizioni di compatibilità sono:\n");
perm (slock, sfree, test_stringa);
return 1;
}
Sono nuovo di questo forum e non so se posso postare programmi interi. Nel caso ho riscontrato un problema curioso in questo programma in C. Brevemente, quello che fa è generare tutte le permutazioni di
{1,2,3,4,5,6,7,8,9,10} e verificare su ogni permutazione due condizioni: whist1 e whist2. Se la permutazione soddisfa entrambe la printa, altrimenti non fa nulla. Premetto che il programma per generare permutazioni l'ho scaricato da internet e funziona benissimo. Ho solo aggiunto i test da fare. Ora, il problema sorge nel passo della funzione perm
if( whist1(permutazione) && whist2(permutazione)) printf(permutazione);
else 'continua a generare la prossima permutazione';
L'espressione condizionale if si comporta in maniera strana: se la scrivo come sopra, ottengo anche permutazioni che soddifano whist1 ma non soddisfano whist2. Nota bene che whist1 e' sempre soddisfatta, ma a volte whist2 no e NON ottengo tutte le permutazioni che soddisfano la sola whist1, quindi qualche volta whist2 viene controllata.
Se invece inverto l'ordine di controllo nell'espressione condizionale, facendo testare prima whist2 di whist1:
if( whist2(permutazione) && whist1(permutazione)).....
ottengo permutazioni che in effetti soddisfano entrambe le condizioni. Com'è possibile?
Premetto che whist1 è il test più veloce da effettuare e quindi preferirei testarlo per primo, visto che poi avro' bisogno di far girare il programma su numeri grossi (e non su solo 10 numeri). Inoltre whist1 e whist2 funzionano a dovere se isolati dal ciclo che genera permutazioni, quindi il problema non dovrebbe essere li.
Vi posto il codice nella speranza che qualcuno abbia la pazienza di scoprire dove sta il problema. L'ho (forse troppo!) commentato per agevolare la lettura.
/*
* Un test sulle differenze fra gli elementi delle permutazioni di una stringa
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define DIM 10
#define MOD 11
#define TWICEDIM 20
/*DEFINISCO I DUE TEST*/
/* mod (ausiliaria) fonisce il resto della divisione per MOD*/
int mod(int dividendo)
{
int risultato=dividendo%MOD;
if (risultato<0) risultato+= MOD;
return risultato;
} /*FINE MOD*/
/* whist1 effettua il PRIMO TEST di compatibilità fra stringa e test_stringa*/
int whist1(char stringa[DIM], char test_stringa[DIM])
{
int i;
char differenze[DIM]; /* un vettore ausiliario*/
/*Setto il vettore differenze*/
differenze[0]=(char) mod(stringa[0]-stringa[1])+33;
differenze[1]=(char) mod(stringa[1]-stringa[0])+33;
for(i=2; i<DIM;i++)
{
if((i+2)%4==0 || (i+2)%4==1) differenze[i]=(char) mod(stringa[i]-stringa[i+2])+33;
else differenze[i]=(char) mod(stringa[i]-stringa[i-2])+33;
}
/*Fine settaggio differenze*/
/* Effettuo il test: ogni elemento di test_stringa
* deve comparire nella stringa differenze
* strspn(A, B) restituisce la lunghezza del prefisso di A
* costituito da elementi di B.
*/
if (strspn(test_stringa, differenze)==DIM) return 1;
else return 0;
} /*FINE TEST WHIST1*/
/*whist2 effettua il SECONDO TEST di compatibilità fra stringa e test_stringa*/
int whist2(char stringa[DIM], char test_stringa[DIM])
{
int i, none=0;
char differenze[TWICEDIM]; /*un altro vettore ausiliario*/
/*Setto il vettore differenze*/
differenze[0]=(char) mod(stringa[0]-33)+33;
differenze[1]=(char) mod(33-stringa[1])+33;
for(i=2; i<DIM;i++)
{
if((i+2)%4!=3) differenze[i]=(char) mod(stringa[i]-stringa[i+1])+33;
else differenze[i]=(char) mod(stringa[i]-stringa[i-3])+33;
}
for(i=DIM; i<TWICEDIM;i++) differenze[i]=(char) mod(33-(int) differenze[i-DIM])+33;
/*fine settaggio differenze*/
/*Effettuo un primo controllo: ogni elemento di test_stringa deve
*comparire in differenze
*strspn(A, B) restituisce la lunghezza del prefisso di A
*costituito da elementi di B.
*/
if (strspn(test_stringa, differenze)==DIM)
{
/*Effettuo il secondo controllo: ogni elemento di test_stringa
*deve comparire almeno due volte in differenze
*/
for(i=0; none==0 && i<DIM; i++)
{
/* La prima occorrenza dell'elemento in differenze
* deve essere diversa dall'ultima
*/
if (strchr(differenze,(char) 34+i)==strrchr(differenze, (char) 34+i)) none++;
}
if (none==0) return 1;
else return 0;
}
else return 0;
} /*FINE WHIST2*/
/* HO FINITO DI DEFINIRE I DUE TEST*/
/*DEFINISCO LA FUNZIONE RICORSIVA CHE GENERA LE PERMUTAZIONI*/
/* remchr (ausiliaria) rimuove un carattere da una stringa.
* Il carattere eliminato viene restituito al chiamante.
*/
char remchr (char *str, int c)
{
int i;
int length = strlen (str);
/*strlen calcola la lunghezza di una stringa */
char lost = str[c];
for (i = c; i < length; i++)
str[i] = str[i + 1];
return lost;
} /*FINE REMCHAR*/
/*perm genera tutte le permutazioni di una stringa di DIM
* elementi e di ciascuna controlla che verifichi whist1 e whist2
*/
int perm (char *tlock, char *tfree, char test_stringa[DIM])
{
int i, contatore;
char *nLock;
char *nFree;
char tmp[2];
tmp[1] = '\0';
if (strlen (tfree) == 0)
/* Se tfree ha lunghezza nulla, allora abbiamo generato una
* permutazione completa della stringa iniziale, contenuta
* in tlock.Verifichiamo whist1 e whist2 e se soddisfa entrambe,
* la visualizziamo
*/
{ /*QUI C'E' IL PROBLEMA DI CUI SOPRA?*/
if ( whist1(tlock,test_stringa) && whist2(tlock,test_stringa) )
{
for(i=0; i<DIM; i++) printf("%3d", (int) tlock[i]-33);
printf("\n");
}
}
else
{
/* Se tfree ha lunghezza maggiore di zero, allora tlock contiene
* una permutazione di alcune lettere della stringa iniziale.
* Allora, per ciascuna lettera non ancora inserita nella permutazione,
* possiamo generare una nuova tlock, aggiungendo questa lettera in
* coda, e quindi formare una nuova coppia tlock-tfree, che ci avvicina
* alla costruzione delle permutazioni.
*/
for (i = 0; i < strlen (tfree); i++)
{
/* strdup crea un duplicato di una stringa
* La usiamo per lavorare sui parametri senza modificarli
*/
nFree = strdup (tfree);
nLock = strdup (tlock);
/* Rimuoviamo l'i-esimo carattere dalla stringa nFree */
tmp[0] = remchr (nFree, i);
/* strcat concatena due stringhe
* La usiamo per creare una parte della permutazione
* fissata con la nuova lettera estratta dall'insieme di
* quelle disponibili in tfree.
*/
strcat (nLock, tmp);
/* Richiamiamo perm sulla nuova coppia nLock-nFree, con
* strlen(nLock)==strlen(tlock)+1, e
* strlen(nFree)==strlen(tfree)-1.
*/
perm (nLock, nFree, test_stringa);
/* Distruggiamo le stringhe nLock ed nFree, che non ci
* useremo ulteriormente.
*/
free (nLock);
free (nFree);
}
}
return 0;
} /*FINE PERM*/
/*HO FINITO DI DEFINIRE LE FUNZIONI*/
int main ()
{
int i;
char test_stringa[DIM], sfree[DIM], slock[DIM];
slock[0] = '\0';
for(i=0; i<DIM;i++)
{
sfree[i]=(char) 34+i;
test_stringa[i]=(char) 34+i;
}
printf ("\nLe permutazioni che soddisfano le condizioni di compatibilità sono:\n");
perm (slock, sfree, test_stringa);
return 1;
}