[C] Aiuto!! uno strano comportamento per una istruzione condizionale

[sunra]

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; 
}

[andbin]

Ciao, innanzitutto non credo che ci siano problemi a postare sorgenti interi, purché, penso, non siano delle cose di lunghezza spropositata! Inoltre, per rendere il sorgente più leggibile, ti conviene indentare correttamente il codice e postarlo all'interno del marcatore [CODE][/code].

Veniamo al tuo sorgente. Io lo sto verificando adesso e pur non conoscendo nei dettagli il funzionamento e il suo obiettivo finale, ho già trovato una cosa che non va.
Nel sorgente usi degli array di char di lunghezza DIM (costante che vale 10). Tu usi tutti i 10 caratteri dell'array. In alcuni punti del sorgente, usi la funzione strlen per ottenere la lunghezza di una stringa. Occhio!! Perché facendo così le tue stringhe non sono terminate dal carattere nullo!!!

Sto debuggando il tuo programma e, ad esempio, nella funzione remchr la lunghezza di str mi risulta di 41. Ma potrebbe essere qualunque altro valore perché le tue stringhe non sono correttamente terminate!!!

[sunra]

Ciao e grazie per la risposta innanzitutto.
Probabilmente il problema sta tutto in quello che dici tu, in effetti forse sarebbe meglio lavorare con stringhe di lunghezza fissata, mettiamo di 50 char e ogni volta settare un '\0' al punto giusto. Il problema e' che il codice che genera le permutazioni non lo capisco tanto bene, non sono un programmatore di lungo corso ed e' la prima volta che uso funzioni ricorsive. In particolare ero tentato di riscrivere il programma in una forma piu' adatta ai miei gusti, usando stringhe di lunghezza fissata invece di puntatori. Solo mi preoccupa un po' la funzione free( ), che non conosco anche se ne intuisco la funzione. Provero' a fare degli esperimenti, vediamo cosa succede...

Ciao

[Qu@ker]

A proposito, ma sei sicuro che il codice per le permutazioni funzioni?
Tempo fa, ho utilizzato il codice presentato qui.
Un possibile esempio con l'algoritmo di Bogomolyn:

#include <stdio.h>
#include <string.h>

#define DIM 10

int Indici[DIM];
char Stringa[DIM+1];

void print()
{
	char tmp[DIM+1];
	int i;

	for (i = 0; i < DIM; ++i)
		tmp[i] = Stringa[Indici[i]-1];
	tmp[DIM] = '\0';
	puts(tmp);
}

void visit(int k)
{
	static int level = -1;
	Indici[k] = ++level;

	if (level == DIM)
		print();
	else {
		int i;
		for (i = 0; i < DIM; i++)
			if (Indici[i] == 0)
				visit(i);
	}

	--level;
	Indici[k] = 0;
}

int main(void)
{
	int i;

	strcpy(Stringa, "prosciutto");
	for (i = 0; i < DIM; i++) {
		Indici[i] = 0;
	}
	visit(0);

	return 0;
}