Discussion :

[abdelhamidem]

Bonjour,

Je cherche à faire un programme qui à partir d'un alphabet {a, b}, genere tous les mots possibles de taille inferieure ou egale à un entier "n".
Par exemple pour n=2 :

a; b; aa; ab; ba; bb.

Pour cela, j'ai procédé de la maniere suivante:

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void generer(char* mot, int n)
{
    char* mot_a;
    char* mot_b;
 
    // J'ai essayé de mettre des malloc, mais ca ne ne donne rien :o).
    mot_a = (char*) malloc(n*sizeof(char));
    mot_b = (char*) malloc(n*sizeof(char));
 
    //on copie mot dans deux variables chaine de caractere. L'une pour
    //la concatener avec "a", l'autre avec "b".
    mot_a = mot;
    mot_b = mot;
 
    //condition d'arret du programme.
    if (n==0)
        exit(0);
 
//debugage amateur
printf("avant probleme\n");
 
    // On concatene la lettre "a" à mot_a, puis on l'affiche
    strcat(mot_a, "a");
 
//debugage amateur
printf("apres probleme\n");
 
    puts(mot_a);
 
    // on fait de meme avec mot_b et "b"
    strcat(mot_b, "b");
    puts(mot_b);
 
    //Appels recursifs pour generer les autres mots
    //On decremente n pour que le programme s'arrete quand n = 0
    generer(mot_a, n-1);
    generer(mot_b, n-1);
}
 
int main()
{
    int n;
 
    printf("programme de generation de mots a partir de l'alphabet {a, b}\n");
    printf("Entrez N\n");
    scanf("%d", &n);
 
    // on donne un mot "vide" au depart.
    generer("", n);
 
    return 0;
}

Comme vous pourrez le constater dans le code (ou en executant le programme), ca plante juste apres le 1er strcat. En lancant le debuggeur (que je ne maitrise pas du tout) j'ai cru comprendre qu'il s'agissait d'une "segmentation fault".

Voila voila. Alors si vous pouviez m'aider... Merci d'avance.

[Médinoc]

Hum...

C'est un beau bordel.

1. Premièrement, on ne "copie" pas une chaîne avec = : = ne copie que le pointeur. Il faut utiliser strcpy() pour copier la chaîne.
2. Ensuite, pense à mettre des const pour les pointeurs pointant vers quelque chose qui ne doit pas être modifié.
3. Tu dois absolument définir ce que tu cherches à faire avant de l'implémenter en C. Écris l'algorithme de ce que tu veux faire et poste-le ici.
4. Et supprime les casts du retour de malloc() : Ils sont inutiles et déconseillés en C.

[Sve@r]

Bonjour,

Je cherche à faire un programme qui à partir d'un alphabet {a, b}, genere tous les mots possibles de taille inferieure ou egale à un entier "n".
Par exemple pour n=2 :

a; b; aa; ab; ba; bb.

Pour cela, j'ai procédé de la maniere suivante:

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void generer(char* mot, int n)
{
    char* mot_a;
    char* mot_b;
 
    // J'ai essayé de mettre des malloc, mais ca ne ne donne rien :o).
    mot_a = (char*) malloc(n*sizeof(char));
    mot_b = (char*) malloc(n*sizeof(char));
 
    //on copie mot dans deux variables chaine de caractere. L'une pour
    //la concatener avec "a", l'autre avec "b".
    mot_a = mot;
    mot_b = mot;
 
    //condition d'arret du programme.
    if (n==0)
        exit(0);
 
//debugage amateur
printf("avant probleme\n");
 
    // On concatene la lettre "a" à mot_a, puis on l'affiche
    strcat(mot_a, "a");
 
//debugage amateur
printf("apres probleme\n");
 
    puts(mot_a);
 
    // on fait de meme avec mot_b et "b"
    strcat(mot_b, "b");
    puts(mot_b);
 
    //Appels recursifs pour generer les autres mots
    //On decremente n pour que le programme s'arrete quand n = 0
    generer(mot_a, n-1);
    generer(mot_b, n-1);
}
 
int main()
{
    int n;
 
    printf("programme de generation de mots a partir de l'alphabet {a, b}\n");
    printf("Entrez N\n");
    scanf("%d", &n);
 
    // on donne un mot "vide" au depart.
    generer("", n);
 
    return 0;
}

Comme vous pourrez le constater dans le code (ou en executant le programme), ca plante juste apres le 1er strcat. En lancant le debuggeur (que je ne maitrise pas du tout) j'ai cru comprendre qu'il s'agissait d'une "segmentation fault".

Ouahou... ça part en torche là. Déjà premier truc => jamais de "exit" dans une fonction. On part du main pour aller dans la fonction => on quitte la fonction pour revenir au main (comme les poupées russes)

Sinon j'ai pas trop le temps de suite mais plus tard dans la soirée je regarderai mieux l'algo...

[*]Et supprime les casts du retour de malloc() : Ils sont inutiles et déconseillés en C.

Inutiles certainement. Mais pourquoi "déconseillés" ???

[Médinoc]

Inutiles certainement. Mais pourquoi "déconseillés" ???

Dangereux en cas d'oubli d'inclusion de stdlib.h, qu'ils masquent (le cast masque le warning de conversion d'entier en pointeur) :

• Sur une architecture M68k, pointeurs et entiers ne sont pas retournés dans le même registre : Si le compilo croit que malloc() retourne un int parce qu'on n'a pas inclut stdlib.h, on aura n'importe quoi.
• Sous Windows 64 bits, un int et un pointeur n'ont pas la même taille : On perdra donc les 32 bits supérieurs du pointeur.

[Sve@r]

Dangereux en cas d'oubli d'inclusion de stdlib.h, qu'ils masquent (le cast masque le warning de conversion d'entier en pointeur) :

• Sur une architecture M68k, pointeurs et entiers ne sont pas retournés dans le même registre : Si le compilo croit que malloc() retourne un int parce qu'on n'a pas inclut stdlib.h, on aura n'importe quoi.
• Sous Windows 64 bits, un int et un pointeur n'ont pas la même taille : On perdra donc les 32 bits supérieurs du pointeur.

Jolie réponse très bien explicitée !!!

[abdelhamidem]

Hum...

C'est un beau bordel.

1. Premièrement, on ne "copie" pas une chaîne avec = : = ne copie que le pointeur. Il faut utiliser strcpy() pour copier la chaîne.
2. Ensuite, pense à mettre des const pour les pointeurs pointant vers quelque chose qui ne doit pas être modifié.
3. Tu dois absolument définir ce que tu cherches à faire avant de l'implémenter en C. Écris l'algorithme de ce que tu veux faire et poste-le ici.
4. Et supprime les casts du retour de malloc() : Ils sont inutiles et déconseillés en C.

Merci pour ton aide.

Alors en fait l'algorithme tourne à peu pres comme ca pour generer des mots de taille <= 3 , toujours sur l'alphabet {a, b}
le premier appel de generer se fait avec un mot vide, et n=3.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
 
                                generer("", 3)
                              /              \
                generer("a", 2)               generer("b", 2)
               /           \                      /        \
generer("aa", 1)  generer("ab", 1)    generer("ba", 1)   generer("bb", 1)

etc...

Ce qui se passe dans generer("b", 2) c'est d'abord l'impression à l'ecran des deux mots "ba" puis "bb"...
et ensuite il y a deux appels de generer(,):
_ L'un pour afficher les mots qui viennent apres "ba", c'est à dire : "baa" puis "bab" ... puis faire les 2 appels de generer(,) qui font la suite de l'abrbre.
_ L'autre pour afficher les mots qui viennent apres "ba", c'est à dire : "bba" puis "bbb"... puis faire les 2 appels de generer(,) qui font la suite de l'abrbre.

J'utilise la concatenation car quand on appelle generer("b", 2) je concatene le mot "b" à la lettre "a", puis le mot "b" à la lettre "b", et je les affiche tous les 2. (ca donne "ba" puis "bb")

J'espere que c'est plus clair maintenant.

[Médinoc]

OK.
Donc, les mots générés sont immédiatement affichés et n'ont pas à être mémorisés.

On sait aussi que la chaîne passée en paramètres est invariable : Le pointeur doit donc être const.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void generer_et_afficher(char const * mot, int n);

Pour l'instant, on va se soucier de l'efficacité plutôt que de la performance : On va donc systématiquement utiliser malloc(), pour que le code marche avec des tailles arbitraires de mots. Mais dans la fonction, on n'utilisera qu'un seul buffer, par soucis de simplicité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
void generer_et_afficher(char const * const mot, int const n)
{
	/* Ici, le const est à droite de l'étoile: 
	   C'est le pointeur lui-même qui est constant. */
	char * const buf = malloc( sizeof(*buf) * (strlen(mot)+2) ); /* n caractères + 0 terminal */
	if(buf != NULL)
	{
		/* Faire ce qu'il faut */
		/* ... */
 
		free(buf);
	}
}

[Médinoc]

Ensuite, il suffit de remplir avec le traitement correct :

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
void generer_et_afficher(char const * const mot, int const n)
{
	/* Ici, le const est à droite de l'étoile: 
	   C'est le pointeur lui-même qui est constant. */
	char * const buf = malloc( sizeof(*buf) * (strlen(mot)+2) ); /* longueur de mot + 1 + 0 terminal */
	if(buf != NULL)
	{
		/* Faire ce qu'il faut */
		strcpy(buf, mot);
		strcat(buf, "a");
		puts(buf);
		generer_et_afficher(buf, n-1);
 
		strcpy(buf, mot);
		strcat(buf, "b");
		puts(buf);
		generer_et_afficher(buf, n-1);
 
		free(buf);
	}
}

Ce code suit l'arborescence, donc affichera ainsi:

a
aa
ab
b
ba
bb

[Emmanuel Delahaye]

Inutiles certainement. Mais pourquoi "déconseillés" ???

http://emmanuel-delahaye.developpez....tes.htm#malloc

[abdelhamidem]

Ensuite, il suffit de remplir avec le traitement correct :

...

Ce code suit l'arborescence, donc affichera ainsi:

a
aa
ab
b
ba
bb

Merci beaucoup pour ton aide! J'ai appliqué tes conseils, et ca marche à la perfection :o)