Discussion :

[leonardoo]

Bonjour. Je suis entrain de realiser un programme qui , a partir d'une chaine de caractere saisie, genere toutes les combinaisons possibles avec les caracteres de la chaine, les combinaisons, ont des longueurs qui vont de 1 a strlen(chaine_depart). le choix fut porté sur l'utilisation d'une fonction recursive. Selon different tests fait sur le programme, il s'es revelé operationnel pour 7 carctere, au dela de cette limite , la fenetre de la console se ferme automatiquement, en mod debogague , on constate un essai d'acceder a l'adresse nulle , ce qui me laisse supposer un debordement de la pile. j'etale mon code ici (excusez les erreurs d'orthographes )

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
 
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
 
int *toutlemondemeconnais ;
char *filtrer (char *chaine, char car)
    { 
      int longueur = strlen(chaine);        
      int true = 1;
      char *res = (char*) malloc ((longueur+1)*sizeof(char));
      int j=0;
      int i = 0;
      while ((i<= longueur) && chaine[i])
        { if ((chaine[i] == car) && true ) 
           {             i++;
                         true = 0;
                         continue ;
           }        
          res[j] = chaine[i];
            i++;
            j++;
        }
            res[j] = 0;
            return (res);
    }
void recursive (char *pile,char *reserve , int taille, int taillei)
  { 
    char *piles;
    char *reserves;
 
    int i;
    int L = taille - taillei;
     if (pile[0])  printf("%s \n",pile); 
 
 
 
    if (taille == 0) return ;
      for (i = 0; i < taille ; i++)
 
             {    
                  piles = (char*)malloc ( (taillei - taille +1) * sizeof (char));
 
                  reserves =(char*) malloc ( (taille +1) * sizeof (char));                 
                   if (piles== NULL) return;
                   if (reserves ==NULL) return ;
                  strcpy ( piles, pile);
                  strcpy (reserves , reserve);
                  piles[taillei- taille]= reserve [i];
                  piles[taillei - taille +1] = 0;
                  recursive (piles,filtrer (reserves,reserves[i]), taille - 1,taillei);
                  (*toutlemondemeconnais)++;  
                 free (piles);
                 free (reserves);
              }  
        return;
 
 
    }
 
 
 
 
 
int main ()
   { 
     int i; 
     char atraiter[100];
     toutlemondemeconnais = (int*) malloc (sizeof (int));
     (*toutlemondemeconnais) = 0;  
     char *magasin;   
     char *depot;
     printf ("\n saisir une chaine de caractere ");
        scanf ("%s", atraiter);
        printf("les combinaisons possibles sont : \n");
     int metre = strlen (atraiter);
     magasin = (char *) malloc ((metre+1) * sizeof (char));
      depot = (char *) malloc ((metre+1)* sizeof (char));
        magasin[0]=0;
 
        strcpy (depot, atraiter);
        recursive (magasin, depot, strlen(depot),metre);
        printf (" \n le nbre de combinaisons est %d \n", *toutlemondemeconnais);
        system ("pause");
 
        return 0;
}

je precise que la fonction filtrer qui a pour argument une chaineQLQ de caractere et un caractere, rend un pointeur sur la chaine ChaineQLQ - { caractere} .

Si on peut eclairer ma lanternne, si effectivement la deffaillance quand on lui fournit 8 caractere reviens a une erreur involontaire de programation, ou vraiment a un depassement de la pile, et si il y a moyen de remedier a cela. Cordialement.

ps : si quelqu'un a des questions concernant le code , qu'il n'hesite pas
ps2 : si le moyen de remedier au probleme est une refonte de l'algorithme, merci de me signaler seulement la partie qui cause probleme.

[loufoque]

On ne caste pas malloc en C.
Je constate aussi qu'il y a beaucoup de mémoire allouée qui n'est pas libérée.

Il est inutile de multiplier par sizeof(char), cela vaut toujours 1.
Je ne vois pas l'intérêt d'avoir un int* en global, autant utiliser un int.
Les variables i (main) et L ne sont pas utilisées.
Je ne vois pas l'intérêt non plus de la chaîne dépôt, autant utiliser atraiter directement.

Voici une version sans fuite mémoire et avec moins d'allocations.

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
char *filtrer(char *chaine, char car)
{
	int i;
 
	for(i=0; chaine[i] && chaine[i] != car; i++);
 
	for(; chaine[i]; i++)
	{
		chaine[i] = chaine[i+1];
	}
 
	return chaine;
}
 
int recursive(char *pile, char *reserve, int taille, int taillei)
{
	static int combinaisons = 0;
	char *reserves;
	int i;
 
	if(pile[0]) printf("%s\n", pile);
 
 
	if(taille == 0) return -1;
	for(i = 0; i < taille ; i++)
	{   
		reserves = malloc (taille +1);
		if(reserves == NULL) return -1;
 
		memcpy(reserves, reserve, taille+1);
 
		pile[taillei - taille]= reserve[i];
		pile[taillei - taille +1] = 0;
 
		recursive(pile, filtrer(reserves, reserves[i]), taille-1, taillei);
		combinaisons++; 
 
		free(reserves);
	}
 
	return combinaisons;
 
}
 
int main ()
{
	char atraiter[100];
	char *magasin;
	int metre;
 
	printf ("\nSaisir une chaine de caractere : ");
	scanf ("%s", atraiter);
	printf("Les combinaisons possibles sont : \n");
 
	metre = strlen(atraiter);
	magasin = malloc(metre+1);
	if(magasin == NULL) perror("magasin\n");
	magasin[0] = 0;
 
	printf ("\nLe nbre de combinaisons est %d\n", recursive(magasin, atraiter, metre, metre));
 
	free(magasin);
 
	return 0;
}

J'ai testé la taille jusqu'à 12 et je n'ai pas eu de problème.
(Si ce n'est que ça prend trois plombes - 1302061344 combinaisons)

[Emmanuel Delahaye]

Voici une version sans fuite mémoire et avec moins d'allocations.

Pas mal. On peut éviter cette horrible statique...

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
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
static char *filtrer(char *chaine, int car)
{
   size_t i;
 
   for (i = 0; chaine[i] && chaine[i] != car; i++)
   {
   }
 
   for (; chaine[i]; i++)
   {
      chaine[i] = chaine[i + 1];
   }
 
   return chaine;
}
 
static long recursive (char *pile
                       , char *reserve
                       , size_t taille
                       , size_t taillei
                       , long combinaisons)
{
 
   if (pile[0] != 0)
   {
      printf("%s\n", pile);
   }
 
   if (taille != 0)
   {
      size_t i;
      for (i = 0; i < taille ; i++)
      {
         char *reserves = malloc (taille + 1);
         if (reserves != NULL)
         {
            memcpy(reserves, reserve, taille + 1);
            pile[taillei - taille] = reserve[i];
            pile[taillei - taille + 1] = 0;
            combinaisons = recursive(pile
                                     , filtrer(reserves, reserves[i])
                                     , taille - 1
                                     , taillei
                                     , combinaisons + 1);
            free(reserves);
         }
         else
         {
            combinaisons = -1;
         }
      }
   }
   return combinaisons;
}
 
int main (void)
{
   char atraiter[100];
 
   printf ("\nSaisir une chaine de caractere : ");
   fgets (atraiter, sizeof atraiter, stdin);
   {
      char *p = strchr(atraiter, '\n');
      {
         if (p != NULL)
         {
            *p = 0;
         }
      }
   }
 
   {
      size_t metre = strlen(atraiter);
      if (metre != 0)
      {
         char *magasin = malloc(metre + 1);
         if (magasin == NULL)
         {
            fprintf(stderr, "memory error: magasin\n");
         }
         else
         {
            long combinaisons = 0;
            magasin[0] = 0;
            printf("Les combinaisons possibles sont : \n");
            combinaisons = recursive(magasin, atraiter, metre, metre, combinaisons);
            if (combinaisons != -1)
            {
               printf ("\nLe nbre de combinaisons est %lu\n", (unsigned long) combinaisons);
            }
            free(magasin), magasin = NULL ;
         }
      }
   }
   return 0;
}

Mais une solution récursive se heurtera toujours au risque de consommation excessive de la mémoire automatique qui est indétectable de manière standard.

[leonardoo]

Merci infiniment pour vos deux interventions, mais ce que je souhaiterai, c'est de me mentionner a quel niveau la fuite de memoire dans mon programme se situe, je pensais que la consommation de la pile d'execution est due aux variables crées par la fonction recursive elle meme. mais apparement c'est aussi de ma faute j'ai utilisé les variables piles et reserves pour justement ne pas modifier les variables passé a la fonction recursive a chaque iteration, puisque dans le cas de passage de chaine de caractere, comme je le conçois, c'est automatiquement un passage de pointeur sur le contenu, enfin bon, j'aimerai bien detecter l'espace alloué non liberé. Cordialement.

[Emmanuel Delahaye]

j'aimerai bien detecter l'espace alloué non liberé. Cordialement.

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
 
FRMWRK.DBG_SYSALLOC=1
SYSALLOC Overload (85 rec)
SYSALLOC Successful initialization: 85 records available
 
 saisir une chaine de caractere 123
les combinaisons possibles sont :
1
12
123
13
132
2
21
213
23
231
3
31
312
32
321
 
 le nbre de combinaisons est 15
Appuyez sur une touche pour continuer...
SYSALLOC min=4294967295 max=4294967295 delta=0
SYSALLOC Err: Not-matched list:
SYSALLOC Bloc 003D2478 (4 bytes) malloc'ed at line 69 of 'main.c' not freed
SYSALLOC Bloc 003D2468 (4 bytes) malloc'ed at line 77 of 'main.c' not freed
SYSALLOC Bloc 003D24E8 (4 bytes) malloc'ed at line 78 of 'main.c' not freed
SYSALLOC Bloc 003D2518 (4 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2588 (4 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D25D8 (4 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2548 (3 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2568 (3 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2578 (2 byte) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2508 (3 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2598 (2 byte) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D25B8 (3 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D25C8 (2 byte) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2538 (3 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D25E8 (2 byte) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2608 (3 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2618 (2 byte) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2638 (2 byte) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Released Memory
FRMWRK.Terminated
 
Press ENTER to continue.

[leonardoo]

Bonjour, je viens de changer les malloc niveau fonction recursive par :

Code :

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

1
2
3
4
5
 
 
                  piles = (char*)alloca  ( (taillei - taille +1) * sizeof (char));
 
                  reserves =(char*) alloca  ( (taille +1) * sizeof (char));

ce qui a donné du tonus au code , je presume que les fuites de memoire dont mon programme souffre, c'est l'espace aloué qui attendai le depilement, ce qui rendait l'implementation trop lourde, enfin bon, j'aimerai bien comprendre d'avantage.

ps : pour les deux codes au dessus, est ce que vous pouvez avoir l'amabilité de savoir pourquoi changer void recursive par long recursive, est ce que ça aide a allouer plus d'espace au valeurs retournés par recursive,merci d'avance.

[leonardoo]

a , c'est donc le malloc de :

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
 
char *filtrer (char *chaine, char car)
    {
      int longueur = strlen(chaine);       
      int true = 1;
      char *res = (char*) malloc ((longueur+1)*sizeof(char));
      int j=0;
      int i = 0;
      while ((i<= longueur) && chaine[i])
        { if ((chaine[i] == car) && true )
           {             i++;
                         true = 0;
                         continue ;
           }       
          res[j] = chaine[i];
            i++;
            j++;
        }
            res[j] = 0;
            return (res);
    }

qui est en cause, donc le return(res) ne suffit remplace pas un free, y a t il un moyen de contourner un free en dehors de la fonction apres recuperation, enfin bon, apres que les alloca ont resou le probleme en partie, me voila en case depart.

[loufoque]

Pourquoi n'utilises-tu pas le code fourni par moi ou Emmanuel ?
On a déjà résolu les problèmes de fuites mémoire et Emmanuel l'a un peu arrangé (même s'il a oublié de passer la variable i en size_t dans filtrer)

Comme tu peux le constater, j'ai préféré pour filtrer modifier directement la chaîne passée, et par conséquent passer une copie, déplaçant la gestion mémoire à l'extérieur de la fonction.

Plutôt que d'utiliser alloca() tu pourrais utiliser les tableaux C99.

[Emmanuel Delahaye]

Emmanuel l'a un peu arrangé (même s'il a oublié de passer la variable i en size_t dans filtrer)

Corrigé, merci.

[leonardoo]

Salut, c'est pas que je veux pas utiliser votre code, d'ailleurs le programme etant d'interet minime, c'est surtout mes connaissances en allocation de memoire que je mets en epreuve, par contre, j'avais pas vu pour le free en filtrer, la prochaine fois, je serais plus prudent. cordialement.

ps : pouvez vous m'expliquer pour les tableaux en c99 ?

[loufoque]

En C99 on peut utiliser des variables pour déclarer la taille des tableaux.

[Emmanuel Delahaye]

En C99 on peut utiliser des variables pour déclarer la taille des tableaux.

Pour être plus précis, la norme prévoit l'existence de tableaux locaux dont la taille peut être définie à l'exécution (VLA).

A ma connaissance, il n'y a pas d'implémentation libre de C99 qui offre cette possibilité de façon fiable.

gcc 4.x : VLA : 'broken'

http://gcc.gnu.org/c99status.html

D'autre part, il n'y a aucun moyen de savoir si le tableau a été correctement crée, et comme pour un tableau local fixe, son adresse ne peut être utilisée en dehors de la fonction.

Je recommande l'usage de malloc() / free().