IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Problème de récursivité


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre très actif
    Inscrit en
    Août 2007
    Messages
    260
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 260
    Par défaut Problème de récursivité
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    Saisir un mot : abcd
    
    dcdcdعّ|°2ْ|↑
    alors que quand je tape juste 3 caractere ça marche :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    Saisir un mot : wxc
    
    cxw

  2. #2
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 832
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 832
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par yous18 Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    Saisir un mot : abcd
    
    dcdcdعّ|°2ْ|↑
    alors que quand je tape juste 3 caractere ça marche :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ???
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  3. #3
    Membre très actif
    Inscrit en
    Août 2007
    Messages
    260
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 260
    Par défaut
    non pas la peine pour le 2ème
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ?

  4. #4
    Membre émérite Avatar de orfix
    Homme Profil pro
    Inscrit en
    Avril 2007
    Messages
    707
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : Avril 2007
    Messages : 707
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 en sortie : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    Hello World!
    !dlroW olleH
    @++

  5. #5
    Membre averti
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    25
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 25
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ;-)

  6. #6
    Membre chevronné Avatar de corentin59
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    462
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 462
    Par défaut
    Allez, moi aussi je propose ma version !

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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;
    }

  7. #7
    Membre très actif
    Inscrit en
    Août 2007
    Messages
    260
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 260
    Par défaut
    Citation Envoyé par ssmario2 Voir le message
    -> 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 ?

  8. #8
    Membre averti
    Profil pro
    Inscrit en
    Mars 2008
    Messages
    25
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : Mars 2008
    Messages : 25
    Par défaut
    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 :
    Rien ne sert de courir, il faut partir à point.

  9. #9
    Membre très actif
    Inscrit en
    Août 2007
    Messages
    260
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 260
    Par défaut
    j'ai ajouter un printf pour détécter le probléme

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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" 

  10. #10
    Membre éclairé Avatar de je®ome
    Inscrit en
    Octobre 2005
    Messages
    285
    Détails du profil
    Informations forums :
    Inscription : Octobre 2005
    Messages : 285
    Par défaut
    Salut,

    en fait, tu écrases le contenu du tableau pendant l'appel récursif.
    Voici un exemple pour procéder différement.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  11. #11
    Membre chevronné Avatar de corentin59
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    462
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 462
    Par défaut
    je pense qu'il faut ajouter les lignes que j'ai mis en rouge

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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()

  12. #12
    Membre éclairé Avatar de je®ome
    Inscrit en
    Octobre 2005
    Messages
    285
    Détails du profil
    Informations forums :
    Inscription : Octobre 2005
    Messages : 285
    Par défaut
    Citation Envoyé par corentin59 Voir le message
    je pense qu'il faut ajouter les lignes que j'ai mis en rouge
    Suis d'accord.
    Citation Envoyé par corentin59 Voir le message
    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.

  13. #13
    Membre très actif
    Inscrit en
    Août 2007
    Messages
    260
    Détails du profil
    Informations forums :
    Inscription : Août 2007
    Messages : 260
    Par défaut
    salut ... mais j'ai rien compri à votre main
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 ?

Discussions similaires

  1. Problème Arnaud <> récursivité
    Par Kanter dans le forum Delphi
    Réponses: 13
    Dernier message: 20/02/2007, 16h54
  2. Problème de récursivité
    Par nmathon dans le forum Delphi
    Réponses: 5
    Dernier message: 12/01/2007, 16h40
  3. Problème de récursivité en Prolog
    Par poooky dans le forum Prolog
    Réponses: 5
    Dernier message: 04/01/2007, 17h35
  4. Problème de récursivité
    Par mehdi.berra dans le forum C
    Réponses: 8
    Dernier message: 14/12/2006, 17h42
  5. Problème de récursivité
    Par tazmania dans le forum C
    Réponses: 24
    Dernier message: 14/12/2005, 14h34

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo