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

  1. #1
    Nouveau Candidat au Club
    trouver une chaîne de caractères dans une chaîne de caractères
    Bonjour à tous, je suis étudiant en informatique (je vais entamer ma troisième année) et je suis en pleines révisions avant la rentrée. Je suis en train de bloquer sur un exercice, cela consiste à écrire une fonction indiquant si un mot est facteur d'un autre (exemple : "poly", "copi", et "polycop" sont des facteurs de "polycopié"). J'ai donc répondu à l'exercice en plusieurs fonctions, je vous montre les codes que j'ai fait ainsi que la structure d'un "mot " demandé dans l'exercice.
    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
     
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h> 
    #include <ctype.h>
    #include <assert.h>
    #define NMAX 300 
    typedef struct {
    	char m[NMAX];
    } mot;
     
    int est_facteur_gauche(mot facteur_g, mot src){
    	for(int i=0;facteur_g.m[i]!='\0';i++){
    		if(facteur_g.m[i]!=src.m[i]){
    			return 0;	
    		}
    	}		
    	return 1;	
    } 
     
    mot copyFromTo(int pos,int end, char tab[]){
    	assert(pos<=strlen(tab) && end<=strlen(tab) && pos<=end);
    	mot mnew;
    	int nb=0;
    	for(int k=pos;k<=end;k++){
    		nb++;	
    	}
    	mnew.m[nb];
    	for(int i=pos;i<=end;i++){
    		mnew.m[i]=tab[i];
    	}
    	return mnew;
    }
     
    int est_facteur(mot facteur, mot src){
    	for(int i=0;src.m[i]!='\0';i++){
    		mot m=copyFromTo(i,strlen(src.m),src.m);
    		printf("i = %d , s= %s\n",i,m.m);
    		if(est_facteur_gauche(facteur,m)){
    			return 1;
    		}	
    	}
    	return 0;	
    }

    Je vais donc vous expliquer comment j'ai résonné. La fonction est_facteur_gauche était pour la question précédente demandant de renvoyer un booléen (1 ou 0) selon que le mot facteur_g soit facteur de src ou non. J'ai par la suite décidé d'écrire une fonction renvoyant un mot qui copiait les caractères du mot donné en argument de la position pos à la position end, je me suis dis que ce serait un moyen de vérifier si chaque mot donné à partir de chaque position du mot de départ (src) avait pour facteur le mot "facteur" , si c'était le cas pour aucun des mots, la fonction est_facteur renvoyait 0 (faux) . J'ai donc testé les résultats dans un main que je vous montre ci-dessus :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    int main(){ 
            mot m1={"polycopié"};
    	mot m2={"copi"};
           printf("%d",est_facteur(m2,m1));
    	return 0;
    }


    Cette fonction n'a pas marché, après débogage j'ai remarqué que à l'itération 0, le mot m dont je me suis servi apparaissait, mais aux autres itérations, le mot m était vide. Je précise que dans cet exercice je n'ai pas le droit d'utiliser les fonctions strcpy , strcmp, strngcmp, seulement la fonction strlen(), c'est assez problématique car en C on a pas le droit de modifier des chaines de caractère.. . Pouvez vous s'il vous plait m'éclairer sur mon erreur ?
    En vous remerciant d'avances
    Bonne journée à vous !

  2. #2
    Membre confirmé
    c'est qu'il y a un problème dans la méthode copyFromTo

    1. elle fait quoi cette ligne ?
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    mnew.m[nb];


    2. ton pb vient de cette partie :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    for(int i=pos;i<=end;i++){
    		mnew.m[i]=tab[i];
    	}


    tu crées une nouvelle chaine (mnew) mais l'alimentation est mauvaise


    3. pas regardé s'il y avait d'autres pb

  3. #3
    Expert éminent
    Tu n'as pas besoin de faire 1 copie

    Il faut faire 1 double boucle.
    1 boucle for01 pour parcourir la première chaîne str01 moins la taille de la deuxième chaîne str02.
    Et à chaque lettre, tu testes avec la lettre la plus à gauche de la deuxième chaîne str02 : str01[i] == str02[0].
    Et si les 2 caractères sont égaux :
    2.1) Tu mémorises la position de la première chaîne pos
    2.2) Tu démarres 1 nouvelle boucle "tant que" les caractères sont égaux str01[pos + j] == str02[j].
    2.3) Si tu arrives à la fin de la deuxième chaîne str02, tu arrêtes ton algo - tu as trouvé la sous-chaîne. Sinon tu reprends ta boucle for01 à la position pos


    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    	int nb=0;
    	for(int k=pos;k<=end;k++){
    		nb++;	
    	}



    Et tu en penses quoi de nb = (end - pos); (<- à 1 près)

  4. #4
    Expert éminent sénior
    Bonjour
    Citation Envoyé par MugenTsukyomi Voir le message
    Je vais donc vous expliquer comment j'ai résonné. La fonction est_facteur_gauche était pour la question précédente demandant de renvoyer un booléen (1 ou 0) selon que le mot facteur_g soit facteur de src ou non. J'ai par la suite décidé d'écrire une fonction renvoyant un mot qui copiait les caractères du mot donné en argument de la position pos à la position end, je me suis dis que ce serait un moyen de vérifier si chaque mot donné à partir de chaque position du mot de départ (src) avait pour facteur le mot "facteur" , si c'était le cas pour aucun des mots, la fonction est_facteur renvoyait 0 (faux) .
    Inutile de faire tout ça. Ta fonction "facteur_g" suffit. Sauf qu'il faut boucler sur chaque caractère du mot de base (ici "polycopié") et faire le test à partir de la position en cours
    Exemple avec "copi"
    facteur_g("copi", "polycopié") => 0
    facteur_g("copi", "olycopié") => 0
    facteur_g("copi", "lycopié") => 0
    facteur_g("copi", "ycopié") => 0
    facteur_g("copi", "copié") => 1
    Accessoirement je ne suis pas certain qu'encapsuler ta chaine dans une structure soit une super idée. A moins que plus tard tu veuilles rajouter des éléments de gestion.

    Citation Envoyé par MugenTsukyomi Voir le message
    c'est assez problématique car en C on a pas le droit de modifier des chaines de caractère.
    Où as-tu rêvé cette assertion ? Tu n'as pas le droit de modifier une chaine statique en mémoire mais tu as parfaitement le droit de modifier une chaine que tu as stockée toi-même.
    Exemple
    Code c :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    char *s="Hello";                     # Pointeur vers une zone statique invariable
    s[0]='X';                            # Interdit car justement la zone est invariable
     
    char s[]="Hello";                    # Tableau qui récupère la chaine depuis la zone statique
    s[0]='X';                            # Ok

    Mais de toute façon tu n'as pas besoin de modifier ta chaine, juste de passer le bon pointeur à la fonction "facteur_g()".

    Citation Envoyé par MugenTsukyomi Voir le message
    Citation Envoyé par foetus Voir le message
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    	int nb=0;
    	for(int k=pos;k<=end;k++){
    		nb++;	
    	}



    Et tu en penses quoi de nb = (end - pos); (<- à 1 près)
    C'est vrai que là t'as franchement manqué d'à propos...

    Citation Envoyé par foetus Voir le message
    Et tu en penses quoi de nb = (end - pos); (<- à 1 près)
    T'es sûr de l'utilité des parenthèses ?
    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

  5. #5
    Nouveau Candidat au Club
    Citation Envoyé par Xelland Voir le message
    c'est qu'il y a un problème dans la méthode copyFromTo

    1. elle fait quoi cette ligne ?
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    mnew.m[nb];


    2. ton pb vient de cette partie :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    for(int i=pos;i<=end;i++){
    		mnew.m[i]=tab[i];
    	}


    tu crées une nouvelle chaine (mnew) mais l'alimentation est mauvaise


    3. pas regardé s'il y avait d'autres pb

    Coucou à tous, tout d'abord merci pour vos réponses et désolé si je réponds tardivement, ces derniers temps j'étais un peu pris ^^"
    Xelland :
    Dans la ligne que tu m'as cité, je voulais créer un tableau de caractères de taille nb (un peu comme on fait en java mais je sais pas si ca se fait pareil)


    Foetus :
    Merci beaucoup pour ta réponse, grâce à toi , j'ai trouvé la solution ! j'ai donc corrigé mon code, sans me servir des trucs que j'ai écris un peu inutiles J'ai testé la solution en essayant plusieurs cas et ca avait l'air de très bien fonctionner, je pense que ce que j'ai fais est bon. Voilà ce que j'ai corrigé ! :
    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
     
    int est_facteur(mot facteur, mot src){
    	int pos=0;
    	for(int i=0;src.m[i]!='\0';i++){
    		if(src.m[i]==facteur.m[0]){
    			pos=i;
    			int j=0;
    			while(src.m[pos+j]==facteur.m[j]){
    				if(j==strlen(facteur.m)-1 && src.m[pos+j]==facteur.m[j]){
    					return 1;				
    				}
    				j++;
    			}
    			i=pos+j;
    		}
    	}
    	return 0;
    }

    Merci encore une fois !! J'ai buté sur cette question pendant plusieurs jours à vrai dire !!

    Sve@r :
    A vrai dire j'y ai pensé ! J'ai essayé en utilisant la fonction facteur gauche mais ca ne marchait pas ^^" Je ne sais pas pourquoi à vrai dire . Si tu as une solution je suis preneur , sinon ne t'embêtes pas, j'ai résolu mon problème. Merci pour ta réponse également !!

    Passez une bonne soirée et merci pour tout !

  6. #6
    Expert éminent
    2-3 remarques sur ton code :
    • pas la peine d'initialiser des variables à zéro (ou autre valeur) lors de la définition si juste après, tu fais 1 affectation
    • dans mon explication, tu n'as pas besoin de sauvegarder pos, puisque tu ne réutilises pas le compteur de boucle (et on n'utilise pas 1 pointeur de chaîne)
    • il faut impérativement repartir de l'endroit où tu as commencé ta boucle while - 2ième boucle, afin d'éviter les motifs qui se répètent comme copcopcopicop avec copi (<- mais à vérifier pour l'exemple)
    • pas d'appel aux fonctions dans les tests de boucle (comme strlen)
    • utilise 1 type non signé comme size_t pour les compteurs
    • préfixe tes types avec t_ (<- mais ce n'est pas la seule convention de codage qu'il faut avoir)
    • petite optimisation dont je parlais : pas la peine de parcourir ta source en entier, puisqu'à la fin de ta chaîne, tu n'auras plus assez de lettres pour trouver factor (donc de 0 à strlen(src.m) - strlen(factor.m))




    Voici 1 code à l'arrache et crado avec des tests et du debug
    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
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
     
    /*****************************************************************************/
    /***********************************  Debug **********************************/
    /*****************************************************************************/
     
    // active debug : gcc -Wall XXX.c
    // or : gcc -Wall XXX.c -DD_VERBOSE=1
     
    // deactivate debug : gcc -Wall XXX.c -DD_VERBOSE=0
    #ifndef D_VERBOSE
        #define D_VERBOSE 1
    #endif
     
    #if (D_VERBOSE)
        #define DEBUG( XXX ) printf XXX ;
    #else
        #define DEBUG( XXX )
    #endif
     
     
    #define test__ok(TEST_NB, TEST_SRC, SRC_STR, FACTOR_STR) \
    { \
        t_word src    = { SRC_STR }; \
        t_word factor = { FACTOR_STR }; \
    \
        if ( is_factor(src, factor) ) { \
            printf("%02lu.%s : SUCCEED\n", TEST_NB, TEST_SRC); \
        } else { \
            printf("%02lu.%s : FAILED\n", TEST_NB, TEST_SRC); \
        } \
    }
     
     
    #define test_nok(TEST_NB, TEST_SRC, SRC_STR, FACTOR_STR) \
    { \
        t_word src    = { SRC_STR }; \
        t_word factor = { FACTOR_STR }; \
    \
        if ( !is_factor(src, factor) ) { \
            printf("%02lu.%s : SUCCEED\n", TEST_NB, TEST_SRC); \
        } else { \
            printf("%02lu.%s : FAILED\n", TEST_NB, TEST_SRC); \
        } \
    }
     
     
    /*****************************************************************************/
    /***********************************  Unit  **********************************/
    /*****************************************************************************/
     
    #define NMAX 300
     
     
    typedef struct {
        char m[NMAX];
    } t_word;
     
     
    int is_factor(t_word src, t_word factor) {
        size_t fact_len, src_len;
        size_t fact_pos, src_pos;
        unsigned char b_is_not_factor;
     
        fact_len =  strlen(factor.m);
        src_len  = (strlen(src.m) - fact_len);
     
    //  assert if (fact_len != 0) && (src_len != 0)
    //  assert if (fact_len < src_len)
     
        b_is_not_factor = 1;
     
        for(src_pos=0; (b_is_not_factor && (src_pos <= src_len)); ++src_pos){
            DEBUG( ("is_factor - debug: test 01 between %c and %c\n", src.m[src_pos], factor.m[0]) )
     
            if (src.m[src_pos] == factor.m[0]) {
                if (fact_len > 1) {
                    fact_pos = 1;
     
                    do {
                        if(src.m[src_pos + fact_pos] == factor.m[fact_pos]) {
                            DEBUG( ("is_factor - debug: test 02 between %c and %c\n", src.m[src_pos + fact_pos], factor.m[fact_pos]) )
     
                            ++fact_pos;
                        }
                    } while (b_is_not_factor && (fact_pos < (fact_len - 1)));
     
                    if ((fact_pos == (fact_len - 1)) && (src.m[src_pos + fact_pos] == factor.m[fact_pos])) {
                        DEBUG( ("is_factor - debug: test 03 between %c and %c (find)\n", src.m[src_pos + fact_pos], factor.m[fact_pos]) )
     
                        b_is_not_factor = 0;
                    } else {
                        DEBUG( ("is_factor - debug: test 03 between %c and %c (%lu <- %lu)\n", src.m[src_pos + fact_pos], factor.m[fact_pos], fact_pos, fact_len) )
                    }
                } else {
                    DEBUG( ("is_factor - debug: find\n") )
     
                    b_is_not_factor = 0;
                }
            }
        }
     
        return (!b_is_not_factor);
    }
     
     
    /*****************************************************************************/
    /***********************************  Main  **********************************/
    /*****************************************************************************/
     
    int main(int argc, char** argv)
    {
        size_t count;
     
        count = 0;
     
        count++; test__ok(count, "test true                   ", "polycopie",     "ycop")
        count++; test__ok(count, "test true  (first)          ", "polycopie",     "pol")
        count++; test__ok(count, "test true  (last)           ", "polycopie",     "copie")
        count++; test__ok(count, "test true, src == factor    ", "polycopie",     "polycopie")
        count++; test_nok(count, "test false                  ", "polycopie",     "copa")
        count++; test__ok(count, "test true,  len == 1        ", "polycopie",     "o")
        count++; test__ok(count, "test true,  len == 1 (first)", "polycopie",     "p")
        count++; test__ok(count, "test true,  len == 1 (last) ", "polycopie",     "e")
        count++; test_nok(count, "test false, len == 1        ", "polycopie",     "z")
        count++; test__ok(count, "test pattern true           ", "copcopcopicop", "copi")
        count++; test_nok(count, "test pattern false          ", "copcopcopicop", "copa")
     
     
        return EXIT_SUCCESS;
    }



    Citation Envoyé par Sve@r Voir le message
    T'es sûr de l'utilité des parenthèses ?
    nous avons plusieurs points de divergence (par exemple, 1 seul retour dans 1 fonction ou pas) et les parenthèses en font partie
    Je surparenthèse tout ... mais je ne suis jamais fait avoir par 1 test ou 1 affectation compliqué, mais des fois pour caler le truc c'est

  7. #7
    Expert éminent sénior
    Citation Envoyé par MugenTsukyomi Voir le message
    A vrai dire j'y ai pensé ! J'ai essayé en utilisant la fonction facteur gauche mais ca ne marchait pas ^^" Je ne sais pas pourquoi à vrai dire
    Moi je sais (enfin je n'ai pas de mérite, j'ai découvert le souci en faisant ce TP comme demandé).
    Le souci vient de ta fonction "est_facteur_gauche" qui prend en paramètre un mot, un mot entier qu'elle va traiter en entier. Impossible donc de faire en sorte que sur "polycopié" elle ne regade que "ycopié". Elle reçoit une structure contenant le mot, elle traite tout le mot => d'où ma remarque sur cette structure qui n'était pas vraiment nécessaire et ce qui a amené ta solution totalement foireuse un poil excessive où tu recopies dans une mémoire tampon ce que tu veux faire traiter
    Solution 1: lui rajouter un paramètre pour lui dire où démarrer dans le mot
    Solution 2: changer sa signature et lui faire traiter non pas deux type "mot" mais deux pointeurs sur strings, pointeurs qui eux pourront être positionnés par l'appelant selon ses désirs (je veux traiter "polycopié" je lui passe le pointeur sur "p", je veux traiter "ycopié" je lui passe le pointeur sur "y" et dans les deux cas la fonction part de là pour aller jusqu'à la fin de la string).

    C'est la solution 2 que j'ai privilégiée. Mais pour ne pas te déstabiliser, j'ai gardé ensuite cette structure "mot" dans la suite (ok je te dis pas que 2 fois j'ai failli la virer tellement elle me semble inutile)

    Citation Envoyé par MugenTsukyomi Voir le message
    Si tu as une solution je suis preneur
    Pas de souci. Généralement on ne donne pas de solution sauf si l'intervenant montre sa bonne foi ce que tu as fait avec ton exemple.

    Code c :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
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h> 
    #include <ctype.h>
    #define NMAX 300 
     
    typedef struct {
    	char m[NMAX];
    } mot;
     
    // Donc la fonction a été modifiée pour ne traiter que des pointeurs mais elle reste identique dans son code à la tienne
    int est_facteur_gauche(char *facteur_g, char *src){
    	for (int i=0; facteur_g[i] != '\0'; i++)
    		if (facteur_g[i] != src[i]) return 0;	
    	return 1;	
    } 
     
    int isFactor(mot test, mot src) {
    	size_t i;
    	size_t fin;
    	char *pt;
     
    	// Pour faire plaisir à foetus qui n'a pas tort quand il dit que si on arrive sur un mot plus petit que le mot à tester on peut s'arrêter)
    	fin=strlen(src.m) - strlen(test.m);
     
    	// La boucle va faire évoluer un pointeur sur la chaine de base
    	for (i=0, pt=src.m; i <= fin; i++, pt++)
    		if (est_facteur_gauche(test.m, pt)) return 1;		// Là je passe à la fonction juste les pointeurs sur la string
     
    	return 0;
    }
     
    int main(int argc, char *argv[]) {
    	mot src;
    	mot test;
    	strcpy(src.m, argv[1]);
     
    	size_t i;
    	for (i=2; i < argc; i++) {
    		strcpy(test.m, argv[i]);
    		printf("[%s] - [%s] - %d\n", src.m, test.m, isFactor(test, src));
    	}
    }


    Voilà. Tu peux tester ce programme en lui passant en premier paramètre le mot de base, puis ensuite tous les mots à tester. Exemple ./prog polycopié xxx yyy poly lyc copié. Le résultat
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    [polycopié] - [xxx] - 0
    [polycopié] - [yyy] - 0
    [polycopié] - [poly] - 1
    [polycopié] - [lyc] - 1
    [polycopié] - [copié] - 1
    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

  8. #8
    Expert éminent
    Ce message n'a pas pu être affiché car il comporte des erreurs.

###raw>template_hook.ano_emploi###