Problème de récursivité

Version imprimable

Voir 40 message(s) de cette discussion en une page

salut les amis
je dois faire un programme qui lit un mot est affiche son miroir ("yous" -> "suoy") en utilisant l'algorithmes suivant :
en découpe le mot en 2 facteurs a et b alors le miroir de ab = la concatenation de 2 mots : le 1èr est le miroir de b le 2ème est le miroir de a
et cela de manière recursif . miroir(ab) = concatenation( miroir(b) , miroir(a) )
voila mon code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define N 100
 
char* con(char mot[] , char Mot[] );   
char* mir(char mot[]);
 
int main()
{
 
      char A[N] ;
 
      printf("Saisir un mot : ");
      fgets(A,N,stdin); 
      A[strlen(A)-1] = '\0' ; //supprimer le '\n'
      printf("%s", mir(A) ) ; 
 
      getch();
      return(0);
}
 
 
char* con(char mot[] , char Mot[] )
{
     int i , j , m = strlen(mot) , n = strlen(Mot) ;
 
     for(i=0 ; i < n+1 ; i++)
     mot[ m + i ] = Mot[i] ;
 
     return mot ;
 
}
char* mir(char mot[])
{
     int i , j , m = strlen(mot)  ;
     char tab1[N] , tab2[N] ;   
     if( m  != 1 ) // le test d'arret quand le mot contient un seul caractère
     {
         for(i=0;i<m/2;i++) // je divise en deux voici la 1ér facteur
         tab1[i]=mot[i];
 
         tab1[i]='\0';
 
         for(i=m/2;i<=m;i++) // le 2ème
         tab2[i-(m/2)]=mot[i];
 
         return con(mir(tab2),mir(tab1)); // la recursivité
     }
     else
     return mot ;
 
}

mais à l'execution il y a ce probléme :

Code:

1
2
3
Saisir un mot : abcd

dcdcdعّ|°2ْ|↑

alors que quand je tape juste 3 caractere ça marche :

Code:

1
2
3
Saisir un mot : wxc

cxw

Citation:
Envoyé par yous18
salut les amis
je dois faire un programme qui lit un mot est affiche son miroir ("yous" -> "suoy") en utilisant l'algorithmes suivant :
en découpe le mot en 2 facteurs a et b alors le miroir de ab = la concatenation de 2 mots : le 1èr est le miroir de b le 2ème est le miroir de a
et cela de manière recursif .
voila mon code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 100 char* con(char mot[] , char Mot[] ); char* mir(char mot[]); int main() { char A[N] ; printf("Saisir un mot : "); fgets(A,N,stdin); A[strlen(A)-1] = '\0' ;//supprimer le '\n' printf("\n%s", mir(A) ) ; getch(); return(0); } char* con(char mot[] , char Mot[] ) { int i , j , m = strlen(mot) , n = strlen(Mot) ; for(i=0 ; i < n+1 ; i++) mot[ m + i ] = Mot[i] ; return mot ; } char* mir(char mot[]) { int i , j , m = strlen(mot) ; char tab1[N] , tab2[N] ; if( m != 1 ) { for(i=0;i<m/2;i++) tab1[i]=mot[i]; tab1[i]='\0'; // Ici for(i=m/2;i<=m;i++) tab2[i-(m/2)]=mot[i]; // Et là ??? //printf("\n%s\n%s",tab1,tab2); return con(mir(tab2),mir(tab1)); } else { //printf(" %s",mot); return mot ; } }
mais à l'execution il y a ce probléme :
Code:

1 2 3 Saisir un mot : abcd dcdcdعّ|°2ْ|↑
alors que quand je tape juste 3 caractere ça marche :
Code:

1 2 3 Saisir un mot : wxc cxw
J'ai pas trop examiné le code en détail... mais je vois que t'as une première partie for (i=0; i < m/2; i++) que tu termines avec un '\0' (j'ai mis "Ici" en rouge) et une seconde partie for (i=m/2; i < m; i++) où ce '\0' n'est pas mis (là où j'ai mis "Là").
Te faut pas terminer aussi le second mot ???

11/03/2008, 20h33
yous18
non pas la peine pour le 2ème
Code:

1 2 for(i=m/2;i<=m;i++) // ici i<=m et non i<m tab2[i-(m/2)]=mot[i];
car je parcours jusqu'à m (i<=m) donc j'arrive au '\0'
c'est pas juste ?

Salut,

J'ai essayé de comprendre ton code puisque moi aussi je viens d'avoir de gros problèmes avec cette récursivitée ;) ...voici deux remarques concernant ton code :

-> il ne faut pas passer par d'autres tableaux ( tab1 et tab2 ) c'est ta chaine de caractère lus qu'il faut modifier directement ( utilisation de pointeur+envoie de la taille des chaînes aux fonctions "pas de strlen" )

-> 'con' d'après ce que j'ai compris c'est une concaténantion hors je pense que tu voulais plutôt permuter les deux sous-chaînes passée...

Voici ma version, j'ai réécrit un autre bout de code, mais tout en essayons de pas trop m'éloigner de la tienne :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX_SIZE 128 char* permuter( char mot1[] , char mot2[] ,int taille1 , int taille2) { char tmp[MAX_SIZE]; strncpy(tmp,mot1,taille1); strncpy(mot1,mot2,taille2); strncpy(mot1+taille2,tmp, taille1); return mot1; } char *mir( char mot[] , int taille1 ) { if( taille1>=2 ) { int taille2=taille1/2; taille1=taille1-taille2; char *mot1=mot; char *mot2=mot+taille1; return permuter(mir( mot1 ,taille1 ),\ mir( mot2 ,taille2 ),\ taille1,taille2); } else { return mot; } } int main() { char mot[MAX_SIZE]; char *nl=NULL; fgets(mot,128,stdin); if( (nl=strchr(mot,'\n'))!=NULL ) { *nl='\0'; printf("%s",mir( mot , strlen(mot) )); } return 0; }
Code:

1 2 Hello World! !dlroW olleH
@++

Lorsque l'on écrit un code récursif, il faut toujours (toujours) un moyen d'arrêter la récusirvité... Sinon, c'est la boucle infinie assurée !

Or, dans ton code, tu n'avais aucun moyen de l'arrêter (sacré souci), en revanche, dans celui qu'a proposé ssmario2, on voit apparaître un test, permettant d'arrêter l'appel récursif à un moment donné.

Maintenant, si j'y mets mon grain de sel aussi, j'aurais plutot permuté deux caractères opposés, en m'arrêtant lorsque la longueur de la chaine est <= 1. Et sachant qu'on bosse avec des chaines (donc terminée par 0), pas vraiment la peine de rajouter la taille ;-)

Allez zou, je colle ma petite mienne (je vous avoue que c'est pas revenu très naturellement !)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 /* str : la chaine a permuter start : l'offset de depart end : l'offset de fin */ void perm(char * str, int start, int end); void perm(char * str, int start, int end) { if ( (end - start) > 0 ) /* Si il y a des caracteres a permuter ET qu'on n'a pas encore parcouru plus de la moitie de la chaine */ { /* Echanger lesdits caracteres */ char c = str[start]; str[start] = str[end]; str[end] = c; perm(str, start + 1, end - 1); /* Continuer de permuter */ } /* sinon, ne rien faire */ }
Et voilà, tout bêtement ;-)

Allez, moi aussi je propose ma version !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define NBCHAR 100
 
void inverserMot(char *mot) {
    char temp[NBCHAR];
    char lettre[2];
 
    if ( strlen(mot) > 1 ) {
        lettre[0] = mot[0];
        lettre[1] = '\0';
        strcpy(temp,&mot[1]);
        inverserMot(temp);
        strcat(temp,lettre);
        strcpy(mot,temp);
    }
}
 
int main(void) {
    char mot[NBCHAR];
 
    printf("Veuillez rentrer un mot : ");
    fgets(mot,NBCHAR,stdin);
    mot[strlen(mot)-1] = '\0';
 
    printf("le mot est \"%s\"\n",mot);
    inverserMot(mot);
    printf("son miroir est \"%s\"\n",mot);
 
    return 0;
}

voici une version plus optimisée

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
void inverserMot2(char *mot,size_t L,size_t i) {
    char lettre[2];
 
    if ( i < L ) {
        lettre[0] = mot[i];
        lettre[1] = '\0';
        i++;
        inverserMot2(mot,L,i);
        strcat(mot,lettre);
    } else {
        mot[0] = '\0';
    }
}

L'appel de la fonction se fait alors par

Code:

inverserMot2(mot,strlen(mot),0);

12/03/2008, 12h31
corentin59

mais en fait, je pense que la version de groscask est encore plus simple !
12/03/2008, 14h21
yous18

merci bcp les amis je vais bien observer vos poste et si j'ai des probléme je vais vous dire ...
12/03/2008, 19h14
yous18

Citation:

Envoyé par ssmario2

-> il ne faut pas passer par d'autres tableaux ( tab1 et tab2 ) c'est ta chaine de caractère lus qu'il faut modifier directement ( utilisation de pointeur+envoie de la taille des chaînes aux fonctions "pas de strlen" )

oui ... mais il faut que je découpe ma chaine lu ... alors comment faire ?
et je sais pas ou vous decouper votre chaine ?
le decoupage c'est la base de l'exercice ensuite la concatenation et non la pérmutation (sans utiliser string.h) ?

vous pouvez me dire pourquoi mon code ne marche pas ?
12/03/2008, 20h08
groscask

Pourquoi ton code ne marche pas ? Le mien ne s'est pas fait du premier coup. La technique : rajouter des printf par-ci par là, et voir effectivement où ca ne marche pas !
Euh... C'est pas LA technique ultime hein, mais pour ce genre de soft, ça fait bien l'affaire :)

Ensuite, avant de te lancer dans un quelconque code, pose d'abord l'algorithme ! Comment fais-tu, toi, pauvre humain, pour écrire une chaîne à l'envers ?

Mmmh...

Canard

Je prends C et d. Je les inverse.
Ensuite je prends a et r, et je les inverse.
Je prends n et a et je les inverse.
J'ai plus rien !
dranaC

Cas impair :
Chien
Je prends C et n...
je prends h et e...
Il me reste qu'un seul caractère ! Je m'arrete.
neihC

Maintenant, essaye de généraliser ça, et ça viendra tout seul :)

Comme dirait l'autre :

Citation:

Rien ne sert de courir, il faut partir à point.
12/03/2008, 21h30
yous18

merci groscask ... mnt j'ai compri vos code source et vraiment c'est une méthode facile et pratique .... mais moi je dois faire l'exercice comme ça :
miroir(ab) = concatenation( miroir(b) , miroir(a) )
toujours découper la chaine jusqu'à strlen(chaine) = 1 ;
et t'a raison pour l'usage des printf pour localiser les erreures

j'ai ajouter un printf pour détécter le probléme

Code:

1
2
printf( "\n%s  %s" , mir(tab2),mir(tab1) );
return con(mir(tab2),mir(tab1)); // vous pouvez remplacer ma fonction con  avec strcat

Code:

1
2
3
4
5
6
7
8
Saisir un mot : azer

z  a
r  e
re  re // je crois que ici c'est l'erreur mais je sais pas comment la corrigé
z  a
r  e
rererÒæ|°2Æ|↑ // quand j'utilise strcat il m'affiche "rere"

Salut,

en fait, tu écrases le contenu du tableau pendant l'appel récursif.
Voici un exemple pour procéder différement.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define N 100
 
char* con(char mot[] , char Mot[] );
char* mir(char mot[]);
 
 
char* con(char mot[] , char Mot[] )
{
	int i , m = strlen(mot) , n = strlen(Mot) ;
	for(i=0 ; i < n ; i++)
		mot[ m + i ] = Mot[i] ;
	return mot ;
 
}
char* mir(char *mot)
{
 	int m = strlen(mot)  ;
	char *c1,*c2;
	c1=malloc(N);
	c2=malloc(N);
	if( m  != 1 ) // le test d'arret quand le mot contient un seul caractère
	{
		strncpy(c1,mot,m/2);
		strcpy(c2,mot+m/2);
		return con(mir(c2),mir(c1)); // la recursivité
	}
	else
	return mot ;
 
}
 
 
int main(int argc, char *argv[])
{
      if(argc!=2)
      {
	      printf("Utilisation ./yous mot\n") ; 
	      exit(1);
      }
      printf("%s\n", mir(argv[1])) ; 
 
      return(0);
}

Si tu as des questions, n'hésites pas.
bonne après-midi

je pense qu'il faut ajouter les lignes que j'ai mis en rouge

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define N 100
 
char* con(char mot[] , char Mot[] );
char* mir(char mot[]);


char* con(char mot[] , char Mot[] )
{
	int i , m = strlen(mot) , n = strlen(Mot) ;
	for(i=0 ; i < n ; i++)
		mot[ m + i ] = Mot[i] ;

	mot[m+i] = '\0';
	return mot ;
  
}
char* mir(char *mot)
{
 	int m = strlen(mot)  ;
	char *c1,*c2;
	c1=malloc(N);
	c2=malloc(N);
	if( m  != 1 ) // le test d'arret quand le mot contient un seul caractère
	{
		strncpy(c1,mot,m/2);
		c1[m/2] = '\0';
		strcpy(c2,mot+m/2);
		return con(mir(c2),mir(c1)); // la recursivité
	}
	else
	return mot ;
 
}
 

int main(int argc, char *argv[])
{
      if(argc!=2)
      {
	      printf("Utilisation ./yous mot\n") ; 
	      exit(1);
      }
      printf("%s\n", mir(argv[1])) ; 

      return(0);
}

Ceci dit, il y a un problème de fuite de mémoire, les malloc() n'étant pas accompagnés de free()

13/03/2008, 19h09
je®ome

Citation:

Envoyé par corentin59

je pense qu'il faut ajouter les lignes que j'ai mis en rouge

Suis d'accord.

Citation:

Envoyé par corentin59

Ceci dit, il y a un problème de fuite de mémoire, les malloc() n'étant pas accompagnés de free()

Bien sûr, mais je pense que pour ce type de programme, cela n'est pas considérable, enfin c'est mon avis.

salut ... mais j'ai rien compri à votre main
Code:

1 2 3 4 5 6 7 8 9 10 11 int main(int argc, char *argv[]) { if(argc!=2) { printf("Utilisation ./yous mot\n") ; exit(1); } printf("%s\n", mir(argv[1])) ; return(0); }
c'est quoi argc et argv ? moi j'utilise main sans parametres (void)

et pourquoi le if ? et quand j'execute votre code rien n'est affiché je crois à cause de exit(1)
et ou est le scanf ou le fgets pour saisir le mot ?

13/03/2008, 20h55
yous18

ça marche quand j'ai remplacé ton main avec mon main :yaisse2:
et pourquoi ta fonction n'écrase pas ton tableau ?
13/03/2008, 23h40
yous18

j'ai consataté que quand toi t'a utilisé les pointeurs ça marche et moi non quand j'ai utilisé les tableau !!!
pourquoi ?

En fait, dans ta version, tu déclares les tableaux par

Code:

char tab1[N], tab2[N];

les espaces mémoire vers lesquels pointent tab1 et tab2 sont alloués dès que tu appelles la fonction. Dans la solution de je®ome, les espaces mémoire sont alloués dynamiquement.

Si tu regardes quelle est la valeur des pointeurs dans ton implémentation, par exemple en faisant ceci
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 char *con(char mot[],char Mot[]) { int i, m=strlen(mot), n=strlen(Mot); printf("con : %s(%p) + %s(%p) = ",mot,mot,Mot,Mot); for(i=0;i<n;i++) { mot[m+i] = Mot[i]; } mot[m+i] = '\0'; printf("%s(%p)\n",mot,mot); return mot; } char *mir(char mot[]) { int i, m=strlen(mot); char tab1[N], tab2[N]; if( m != 1 ) {// le test d'arret quand le mot contient un seul caractère for (i=0;i<m/2;i++) {// je divise en deux voici la 1ér facteur tab1[i]=mot[i]; } tab1[i]='\0'; for (i=m/2;i<=m;i++) {// le 2ème tab2[i-(m/2)]=mot[i]; } printf("mir : %s(%p) = %s(%p) + %s(%p)\n",mot,mot,tab1,tab1,tab2,tab2); return con(mir(tab2),mir(tab1)); // la recursivité } else { printf("mir : %s = %s(%p)\n",mot,mot,mot); return mot; } }
tu te rends compte qu'il y a des pointeurs qui sont conservés et donc des espaces mémoires qui sont écrasés. Par exemple, si tu traites la chaine "abcd", il t'affiches :
Code:

1 2 3 4 5 6 7 8 9 10 mir : abcd(0022FF00) = ab(0022FE50) + cd(0022FDE0) mir : ab(0022FE50) = a(0022FD30) + b(0022FCC0) mir : a = a(0022FD30) mir : b = b(0022FCC0) con : b(0022FCC0) + a(0022FD30) = ba(0022FCC0) mir : cd(0022FDE0) = c(0022FD30) + d(0022FCC0) mir : c = c(0022FD30) mir : d = d(0022FCC0) con : d(0022FCC0) + c(0022FD30) = dc(0022FCC0) con : dc(0022FCC0) + dc(0022FCC0) = dcdc(0022FCC0)
On voit ainsi, sur la première ligne (décomposition de "abcd"), que la fonction mir donne a tab1 et tab2 les valeurs 0022FE50 et 0022FDE0. Pour la décomposition de "ab" et de "cd", la fonction donne à tab1 et tab2 les mêmes valeurs (0022FD30 et 0022FCC0) alors qu'il y a deux appels différents.

Je ne sais pas si l'absence d'allocation dynamique est la cause de ce problème, il faut peut-être attendre la réponse d'experts.

Voir 40 message(s) de cette discussion en une page