Discussion :

[safsafmedraed]

salut à tous ,je suis un débutant en programmation .
j'ai un tableau de chaine de caractères deja rempli de mots et alors je veut savoir comment prendre le 1er mot de ma chaine et le mettre etant aléatoire
exemple : dimanche ======> "n"a"m"d"i""m""e"c""h"
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
 
void dictionnaire(int NM,char *Tdict)
 
{ int i,j;
 
    char dict[30][12]={"dimanche \n","presenter \n","attitude\n","projet\n","codeblocks\n","message\n","communication\n","chiffres\n","lettres\n","electronique\n","programmation\n"};
 printf("%s",dict);
for (i=0;i<NM;i++)
 {
     for (j=0;j<NM;j++)
     {
         dict[rand()][rand()];
         printf("%c",dict);
     }
 }
   Tdict=malloc(50);
 
free(Tdict);
}

[picodev]

Bonjour,
tu peux implémenter l'algorithme de Fisher-Yates (→ cf page wikipedia) pour mélanger ta chaîne. C'est un algorithme simple à mettre en oeuvre et très efficace.

[dalfab]

Bonjour,
j ← entier aléatoire entre 0 et i peut s'écrire int j = rand() % (i+1); avec une bonne approximation.
échanger a_j et a_i peut s'écrire char tmp=dict[m][i]; dict[m][i]=dict[m][j]; dict[m][j] = tmp;.

[safsafmedraed]

mais est ce que c'est efficace pour une chaine de caractére la méthode de fesher ??

[picodev]

Je te réponds une bonne heure plus tard … temps qui t'aurais permis d'implémenter l'algo, de le tester et de constater que oui sans avoir à poser la question. Tu t'imagines bien aussi que si je te l'ai conseillé c'est que je pense que c'est ce qu'il te faut je ne vais pas t'orienter vers une fausse solution.

[foetus]

C'est surtout un algo du genre classique "glouton" en info si tu avais regardé

On coupe le tableau en 2 parties: 1 qui va grossir jusqu'à avoir tout le tableau, l'autre qui va se réduire jusqu'à n'avoir plus aucun élément.

Dans cet algo, on va prendre une lettre dans la partie qui réduit (donc on va prendre toutes les lettres sans répétition) et on va la ranger dans la partie qui grossit, la fin du tableau (dans une case qu'on ne touche plus après puisqu'on gère cette partie en pile)

[Sve@r]

Bonjour

mais est ce que c'est efficace pour une chaine de caractére la méthode de fesher ??

C'est une méthode qui mélange un tableau. Une chaine de caractères étant un tableau, je ne comprends même pas que tu poses la question...

On coupe le tableau en 2 parties: 1 qui va grossir jusqu'à avoir tout le tableau, l'autre qui va se réduire jusqu'à n'avoir plus aucun élément.

Dans cet algo, on va prendre une lettre dans la partie qui réduit (donc on va prendre toutes les lettres sans répétition) et on va la ranger dans la partie qui grossit, la fin du tableau (dans une case qu'on ne touche plus après puisqu'on gère cette partie en pile)

Euh je ne crois pas que tu parles du même. Dans l'algo proposé par picodev, les éléments sont échangés mais restent dans le même tableau...

[sambia39]

Bonsoir,

C'est surtout un algo du genre classique "glouton" en info si tu avais regardé

On coupe le tableau en 2 parties: 1 qui va grossir jusqu'à avoir tout le tableau, l'autre qui va se réduire jusqu'à n'avoir plus aucun élément.

Dans cet algo, on va prendre une lettre dans la partie qui réduit (donc on va prendre toutes les lettres sans répétition) et on va la ranger dans la partie qui grossit, la fin du tableau (dans une case qu'on ne touche plus après puisqu'on gère cette partie en pile)

Les algorithmes gloutons sont des algorithmes utilisés le plus souvent dans la résolution de problèmes fondés sur des choix de solutions locales optimales, dans le but que ce choix mène à une solution globalement optimale. Mais attention tout de même, les algorithmes gloutons dans certains cas, ne peuvent fournir ou aboutir à aucune solution optimale.
Et ici ce n'est pas le cas.

Sans vouloir vous offusquer, vous confondez et interprétez mal la permutation par trie de donner aléatoire, qui est si je peux le dire une autre façon d’écrire l’algorithme de knuth et qui consiste à donner un ordre de priorité de traitement aléatoire à un ensemble fini Y(d’où la création d’un nouveau tableau), puis de trier les éléments du tableau d’origine selon les priorités de Y.

Algorithme:
FUNC_PERMUT_TRIE( SIZE, T):
Y[ 1,..., n] //un nouveau tableau de taille finis (SIZE)
pour i = 1 à SIZE:
Y[i] = RAND(1,SIZE³) // Augmentation des chances d’unicité avec une fonction random
Trier T en utilisant Y comme clé de tris //Implémenter une variante du tris par insertion.

Ce qui donne l’implémentation suivante comme 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
/*
 ============================================================================
 Name        : Untitled 7.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 2016 SAMBIA39
 Description : Ansi-style
 ============================================================================
 */
#define MAX 5
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
 
//Func random
int f_get_random_opti( int x , int y){
 
    static int seed;
    if( !seed ){
        seed = 1;
        srand( (unsigned int)time(NULL) );
    }
    return (rand() % (y - x + 1));
}
 
void f_shuffle_tris_permut_data( size_t size, int ptr[] ){
 
    int tmp[size];
    unsigned int i = 0;
    unsigned int j = 0;
    unsigned int k = 0;
    unsigned int r = 0;
 
    /*  Augmente la probabilité  && remplis le tableau*/
    for( i = 0; i < size; i++ )
        tmp[i] = (int)f_get_random_opti( 1, 
            pow((double)size,(double)3));
 
   /*  tris par insertion en utilisant tmp[i] 
       comme clé de permutation */
    for( i = 0; i< size; i++ ){
        k = tmp[i];
        r = ptr[i];
        for( j = i; j > 0 && 
            ((unsigned int)tmp[ j - 1] > k); j-- )
            ptr[j] = ptr[j-1];    //permutation de ptr
        ptr[j] = r;
    }
}
 
int main( void ){
 
    int tmp[] = {
        1,2,3,4
    };
    unsigned int i = 0;
    f_shuffle_tris_permut_data( 4, tmp );
    for( i = 0; i < 4; i++ )    
        fprintf( stdout, "- %d ", tmp[i] );
    fprintf( stdout, "\n" );
 
    return EXIT_SUCCESS;
}

salut à tous ,je suis un débutant en programmation .
j'ai un tableau de chaine de caractères deja rempli de mots et alors je veut savoir comment prendre le 1er mot de ma chaine et le mettre etant aléatoire
exemple : dimanche ======> "n"a"m"d"i""m""e"c""h"
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
void dictionnaire(int NM,char *Tdict)

{ int i,j;

    char dict[30][12]={"dimanche \n","presenter \n","attitude\n","projet\n","codeblocks\n","message\n","communication\n","chiffres\n","lettres\n","electronique\n","programmation\n"};
 printf("%s",dict);
for (i=0;i<NM;i++)
 {
     for (j=0;j<NM;j++)
     {
         dict[rand()][rand()];
         printf("%c",dict);
     }
 }
   Tdict=malloc(50);

free(Tdict);
}

• Les "\n" n’ont aucune utilité ici ; dans la limite vous pouvez utiliser "\0" pour délimiter la fin de chaîne.

• Bonjour,
  tu peux implémenter l'algorithme de Fisher-Yates (→ cf page wikipedia) pour mélanger ta chaîne. C'est un algorithme simple à mettre en oeuvre et très efficace.

  Encore faut-il qu'il adapte l’implémentation afin d’avoir le résultat souhaité.
  
  @safsafmedraed, l'algorithme en question fonctionne avec un ensemble fini c’est-à-dire, que l'on connais d’avance le nombre d'éléments ( exemple 5) mais il faut également comprendre qu’il est indispensable de fournir la taille maximum pour un résultat correcte. En clair la taille du mot le plus long de l’un des ensembles finit donc pour votre tableau le max est 30 par exemple
  

  Code C :

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

  1
  2
  3
  4
  5
  6
  ......
   for (j=0;j<NM;j++)
       {
           dict[rand()][rand()];
           printf("%c",dict);
       }

  Ici, vous avez essayé de faire directement une permutation uniforme des valeurs aléatoires d’un ensemble fini. Ce qui revient à faire de façon indirect l’algorithme de knuth sous cette forme.
  
  Algorithme:
  FUNC_ALEA_FAST_PERMUT( SIZE, T)
  pour i = 1 à SIZE:
  SWAP(T[i], T[RAND(i,SIZE) )
  
  Ce qui donne l’implémentation suivante comme 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
  44
  45
  46
   
  /*
   ============================================================================
   Name        : Untitled 7.c
   Author      : SAMBIA39
   Version     : 0.1
   Copyright   : Copyright (c) 2016 SAMBIA39
   Description : Ansi-style
   ============================================================================
   */
   
   
  #define MAX 5
  #include <math.h>
  #include <time.h>
  #include <stdio.h>
  #include <stdlib.h>
   
  void f_swap( int *ptr_x, int *ptr_y ){
   
      int x = 0;
      x = *ptr_x;
      *ptr_x = *ptr_y;
      *ptr_y = x;
  }
   
  void f_algo_shuffle_direct( size_t size, int ptr[] ){
   
      unsigned int i = 0;
      for( i = 0; i < size; i++ )
          f_swap( &ptr[i], &ptr[f_get_random_opti(i,size)]);
  }
   
  int main( void ){
   
     int tmp[] = {
          1,2,3,4
      };
   
      unsigned int i = 0;
   
      f_algo_shuffle_direct( 4, tmp );
      for( i = 0; i < 4; i++ )    
          fprintf( stdout, "- %d ", tmp[i] );
      return EXIT_SUCCESS;
  }

mais est ce que c'est efficace pour une chaine de caractére la méthode de fesher ??

Oui cette algorithme est efficaces voici un exemple adapté:

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
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
 
/*
 ============================================================================
 Name        : Untitled 7.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 2016 SAMBIA39
 Description : Ansi-style 
 Le code source et algorithme que j'ai posté peuvent contenir des erreurs.
 ============================================================================
 */
 
 
#define MAX 5
 
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
 
int f_get_random_opti( int x , int y){
 
    static int seed;
    if( !seed ){
        seed = 1;
        srand( (unsigned int)time(NULL) );
    }
    return (rand() % (y - x + 1));
}
 
void f_print_data( size_t size, char t_data[][size] ){
 
    unsigned int i = 0;
    unsigned int j = 0;
 
    for( i = 0; i < size; i++ ){
        for( j = 0; j < size; j++ )
            fprintf( stdout, "%c", t_data[i][j] );
        fprintf( stdout, "\n" );
    }
}
 
void f_shuffle_opti_knuth( size_t size, char ptr[] ){
 
    char c_str = '\0';
    unsigned int i = 0;
    unsigned int r = 0;
    for( i = 0; i < size; i++ ){
        r = (unsigned int)f_get_random_opti( i, 1 );
        c_str = ptr[r];
        ptr[r] = ptr[i];
        ptr[i] = c_str;
    }
}
 
void f_algo_shuffle_knuth( size_t size, char ptr[][size] ){
 
    unsigned int i = 0;
    unsigned int j = 0;
    for( i = 0; i < size; i++ ){
        for( j = 0; j < size; j++ )
            f_shuffle_opti_knuth( size, &(*ptr[j]) );
    }
}
 
 
int main( void ){
 
    char t_data[MAX][MAX] ={
        {"BONGH"},
        {"RDE"},
        {"RETRE"}, 
        {"RTYTE"},
        {"RERTY" }
    };
 
    f_print_data( MAX, t_data );
    fprintf( stdout, "\n====\n" );
    f_algo_shuffle_knuth( MAX, t_data );
    f_print_data( MAX, t_data );
 
    return EXIT_SUCCESS;
}

/!\:Les exemples de code source et algorithme que j'ai posté peuvent contenir des erreurs.

à bientôt