[C] Tirage de lettre et probabilité

Tirage de lettre et probabilité [C] - C - Programmation

Marsh Posté le 11-11-2013 à 14:00:07    

Bonjour a tous, j'ai une petite fonction à faire ou j'ai un peu de mal.
 
Je m'explique :  
 
Ma fonction doit retourner une lettre (parmi les 26 de l’alphabet) en fonction de la probabilité qu'elle a d'apparaitre dans la langue française.
 
J'ai trouver les probabilité ici : http://fr.wikipedia.org/wiki/Fr%C3 [...] n%C3%A7ais
 
Mais je ne sais pas vraiment comment procéder...  
 
En vous remerciant d'avance :jap:


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 14:00:07   

Reply

Marsh Posté le 11-11-2013 à 14:04:18    

Bonjour !
 
En vous basant sur les chiffres donnés dans l'article en lien, vous tirez un nombre aléatoire entre 1 et 1533629.
 
Si il est inférieur à 225947, vous choisissez la lettre e
Si il est entre 225948 et 225947+121895, vous choisissez un s
..
 
...
Si il est entre 1533623 1533629, vous choisissez ë.
 
Cela me paraît le plus simple en prenant en compte les données dont vous disposez.
 
Bonne continuation !

Reply

Marsh Posté le 11-11-2013 à 14:32:08    

Merci de l'indication, j'en suis la, je ne connais pas bien le switch (j'utilise des if generalement) mais la vu qu'il va pas y en avoir 1 ou 2 le switch sera plus propre.
 
Comment donc lui dire que si il tire entre A ou B il effectue tel ou tel action ... (CASE????)
 
 

Code :
  1. int main(){
  3. //Fonction de tirage de lettre en fonction de la probabilité d'apparition  
  4. //dans un corpus donnés de  1 533 629 Lettres (Source wiki).
  6. int Nbmin = 1 ;
  7. int Nbmax = 1533629 ; //nombre max de lettres dans le corpus
  8. int nbAleatoire ;
  10. nbAleatoire = rand()%(Nbmax-Nbmin)+Nbmax;  //Tirage du nombres entre 1 et 1533629  
  12. switch(nbAleatoire){
  13.  case????
  15. default: "Erreur Tirage";
  16. }
  19. getchar();
  20. return 0;
  21. }


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 14:44:31    

Code :
  1. switch(nbAleatoire){
  2. case (nbAleatoire<225947):
  3.   return 'e';
  4.   break;
  8. default: "Erreur Tirage";
  9. }


 
Si je met ceci le compilateur me signal une erreur (nbAleatoire doit avoir une valeur constante) ... ><


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 14:50:17    

Cela ne marchera pas car vous devez "prévoir tous les cas dans le switch".
 
Puisque vous devez vous limiter à du C, je construirais rapidement un truc du genre, sans trop chercher à optimiser (je ne compile pas le code, il est possible qu'il y ait quelques petites erreurs :) ) :  
 
(Note : au lieu de mettre directement le caractère accentué, vous pouvez aussi modifier directement dans le tableau en utilisant les codes ASCII, selon l'éditeur et de son encodage.
 

Code :
  1. char getLettreRandom(int nombreAleatoire)
  2. {
  3.    int occurrences[] = {225947, 121895, 117110, ...., 84, 7};
  4.    char lettres[] = "esa...ïë";
  5.    int i, total;
  6.  
  7.    char retour = ' '; /* Valeur par défaut au cas où */
  9.    for (i=0, total = 0; i < 36; i++)
  10.    {
  11.        if ( (nombreAleatoire >= total) && (nombreAleatoire < total + occurences[i]))
  12.        {
  13.              retour = lettres[i];
  14.              break;
  15.        }
  16.        total += occurrences[i];
  17.    }
  19.    return retour;
  20. }


 
Edit : ">=" au lieu de ">" dans le "if", sinon cela marche beaucoup moins bien ! [:sachaguitry:2]


Message édité par Farian le 11-11-2013 à 15:22:44
Reply

Marsh Posté le 11-11-2013 à 14:52:36    

J'essaye !
 
(je viens de m'apercevoir également que mon nbAleatoire ne fonctionne pas, cela me renvoi la valeur de nbMax a chaque fois ... ><
 
Moi aussi je prefere le c++ mais le projet et en C (des gens de ma promo ne font pas de c++ ...)


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 15:06:38    

Je ne vois pas d'erreur sur le calcul du nombre aléatoire qui permettrait de renvoyer nbMax à chaque fois (en revanche, il faudrait faire rand()%(...)+nbMin au lieu de +nbMax :) )
 
Pour le code que j'ai posté, le nombre doit être entre 0 et 1533628.
 
Bonne continuation !


Message édité par Farian le 11-11-2013 à 15:07:20
Reply

Marsh Posté le 11-11-2013 à 15:22:43    

Ma fonction rand, me renvoi toujours 42 (avec min a 1) et me renvoi toujours 41 (avec min a 0)..
Et la fonction getLettreRandom(int nombreAleatoire)  ne retourne rien :/.
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  8. int rand_a_b(int min,int max){
  9.     return rand()%(max-min)+min;
  10. }
  13. char getLettreRandom(int nombreAleatoire)
  14.     {
  17.        int occurrences[] = {225947, 121895, 117110,115465,111103,108812,100500,96785,83668,
  18.       82762,56269,50003,46335,45521,29206,24975,20889,16351,13822,11298,
  19.       8351,7449,5928,4725,4160,3445,2093,1747,1306,890,745,695,283,84,7, 84, 7};
  20.        char lettres[] = "esaitnrulodcpmévqfbghjàxyèêzwçùkîœïë";
  21.        int i, total;
  22.    
  23.        char retour = ' '; /* Valeur par défaut au cas où */
  24.        for (i=0, total = 0; i < 36; i++)
  25.        {
  26.            if ( (nombreAleatoire > total) && (nombreAleatoire < total + occurrences[i]))
  27.            {
  28.                  retour = lettres[i];
  29.                  break;
  30.            }
  31.            total += occurrences[i];
  32.        }
  33.        return retour;
  34.     }
  38. int main(){
  40. int nbAleatoire;
  41. nbAleatoire = rand_a_b(0,1533628);
  42. printf("%d\n",nbAleatoire);
  43. getLettreRandom(nbAleatoire);
  44. getchar();
  46. }


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 15:25:32    

C'est pas a faire avec des switches je pense.
Tu fais un tableau de 26 cases auquel tu associes les fréquences sommées multipliées  par un facteur 100 ou 1000 afin d'avoir des entiers.
Par exemple avec juste les 4 premières lettres et les valeurs données dans la page wikipedia:
Je fais un tableau a 4 cases, int freq[4]
a -> 7,636 je range 7636 dans la première case
b -> 0,901 je range 7636 + 901 = 8537 dans la 2e case
c -> 3,260 je range 8537 + 3260 = 11797 dans la 3e case
d -> 3,669 je range 11797 + 3699 = 15496 dans la 4e case
(on peut écrire une procédure d'initialisation de freq a partir d'un tableau qui contient directement les fréquences pour chaque lettre)
Je fais un tirage aléatoire entre 0 et 15495 avec rand () % 15496 , par exemple 9735
Je fais une recherche par dichotomie dans freq pour trouver la plus petite valeur i telle que mon tirage 9735 soit strictement inférieur à freq[i]
Et je tire comme lettre aléatoire 'a' + i  (ça a un sens en C)
(a généraliser a 26 lettres ou 36 si on tient compte des caractères spéciaux)
EDIT: le temps que je réponde, le topic avait pas mal progressé
A+,


Message édité par gilou le 11-11-2013 à 15:34:34

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 11-11-2013 à 15:27:14    

Je viens de comprendre !
 
C'est normal que la fonction renvoie toujours la même valeur, c'est dû au fonctionnement de rand : elle utilise une valeur de départ ("seed" ) qui vaut 1 au démarrage de tout programme, puis c'est à partir de cette valeur qu'est générée la série des tirages aléatoires.
 
Si vous faites plusieurs tirages dans le même programme, vous aurez des valeurs différentes.
 
Si vous voulez ne faire qu'un seul tirage aléatoire dans votre programme, et que les valeurs changent, vous devez réinitialiser la "seed" avec la fonction srand, en lui passant à chaque fois une valeur différente.
 
La manière classique de le faire est d'appeler "srand(time(NULL))", qui vous donnera à chaque fois une valeur différente à moins de lancer deux fois le programme dans la même seconde.
 
La fonction vous renvoie a priori un caractère, mais vous ne l'affichez pas :)
 
Bonne continuation !
 
Edit : Attention, sous Windows, rand() renvoie un nombre entre 0 et 32767, ce qui va fausser nos résultats et renvoyer 'e' à chaque fois ... Si nécessaire, pour le contourner, utilisez rand()*32768+rand() pour faire le modulo (là encore, truc simple et rapide, pas optimisé au niveau de la distribution ...) afin que le nombre dans un intervalle bien plus grand que celui des valeurs que l'on souhaite obtenir.


Message édité par Farian le 11-11-2013 à 15:32:02
Reply

Marsh Posté le 11-11-2013 à 15:27:14   

Reply

Marsh Posté le 11-11-2013 à 15:37:55    

char lettres[] = "esaitnrulodcpmévqfbghjàxyèêzwçùkîœïë";
Comme le œ n'est ni ascii, ni même isolatin1, la portabilité de ce truc est un poil compromise...
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 11-11-2013 à 15:45:12    

C'est même plus que compromis, et il vaudrait mieux se limiter aux caractères ASCII dans un premier temps (je ne suis pas certain que l'exercice en question porte sur ces aspects-là ...), voire aux 26 lettres, ce qui doit suffire à montrer que l'on a produit un algo qui tourne et que l'on est conscient des difficultés à gérer des caractères plus "exotiques" :)

Reply

Marsh Posté le 11-11-2013 à 15:47:10    

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  8. int rand_a_b(int min,int max){
  9.     return rand()%(max-min)+min;
  10. }
  13. char getLettreRandom(int nombreAleatoire)
  14.     {
  15.  // Tirage de lettre en fonction de sa probabilité d'apparaitre dans un corpus donné de 1 533 629 lettres
  16.  // Source wiki.
  20.  // On fait correspondre les occurrences avec les lettres.
  21.        int occurrences[] = {225947, 121895, 117110,115465,111103,108812,100500,96785,83668,
  22.       82762,56269,50003,46335,45521,24975,20889,16351,13822,11298,
  23.       8351,5928,4725,2093,1747,745,695,283,};
  24.        char lettres[] = "esaitnrulodcpmvqfbghjxyzwk";
  27.        int i, total;
  28.    
  29.        char retour = ' '; /* Valeur par défaut au cas où */
  30.        for (i=0, total = 0; i < 36; i++)
  31.        {
  32.            if ( (nombreAleatoire > total) && (nombreAleatoire < total + occurrences[i]))
  33.            {
  34.                  retour = lettres[i];
  35.                  break;
  36.            }
  37.            total += occurrences[i];
  38.        }
  39.        return retour;
  40.     }
  44. int main(){
  46. int nbAleatoire1=rand_a_b(0,1533628);
  47. int nbAleatoire2=rand_a_b(0,1533628);
  48. int nbAleatoire3=rand_a_b(0,1533628);
  49. //nbAleatoire=rand()%1533628;
  50. printf("%d  , %d , %d \n",nbAleatoire1,nbAleatoire2,nbAleatoire3);
  53. char c = ' '; 
  54. c= getLettreRandom(nbAleatoire1);
  55. printf("%c\n",c);
  58. srand(time(NULL));
  59. getchar();
  61. }


 
 
Effectivement j'ai bien 3 valeurs différentes maintenant par contre  srand(time(NULL)); ne les réinitialise pas chez moi ...  
 
J'ai enlever les caractères spécifique ainsi que leur valeur dans le tableau "occurrences" et je n'arrive toujours pas a retourner de lettre, le compilateur me dit ceci :
 

Code :
  1. 1>f:\cours\etudedecas\consoleapplication1\source.c(53): error C2143: erreur de syntaxe : absence de ';' avant 'type'
  2. 1>f:\cours\etudedecas\consoleapplication1\source.c(54): error C2065: 'c' : identificateur non déclaré
  3. 1>f:\cours\etudedecas\consoleapplication1\source.c(55): error C2065: 'c' : identificateur non déclaré
  4. 1>f:\cours\etudedecas\consoleapplication1\source.c(58): warning C4244: 'fonction' : conversion de 'time_t' en 'unsigned int', perte possible de données
  5. ========== Régénération globale : 0 a réussi, 1 a échoué, 0 a été ignoré ==========


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 15:51:33    

C'est normal, il faut faire le srand AVANT les rand :)

Reply

Marsh Posté le 11-11-2013 à 15:54:17    

A je pensais que c’était comme libéré une mémoire alloué  [:michelnet1]
 
EDIT: mon compilateur n'est pas d'accord ...  
 

Code :
  1. int main(){
  4. srand(time(NULL));
  5. int nbAleatoire1=rand_a_b(0,1533628);
  6. int nbAleatoire2=rand_a_b(0,1533628);
  7. int nbAleatoire3=rand_a_b(0,1533628);
  8. //nbAleatoire=rand()%1533628;
  9. printf("%d  , %d , %d \n",nbAleatoire1,nbAleatoire2,nbAleatoire3);
  12. //char c = ' ';   
  13. //c= getLettreRandom(nbAleatoire1);
  14. //printf("%c\n",c);
  18. getchar();
  20. }


 
si je le met dans la fonction rand_a_b() biensur il me tire 3x le meme nombre le malin !!


Message édité par yeskinokay le 11-11-2013 à 15:58:24

---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 16:06:06    

Remarque : si vous n'utilisez que les 26 lettres, il vous faudra réduire l'intervalle du rand à la somme des occurrences du tableau et aussi modifier le for, afin de n'aller que jusqu'à 26 :)

Reply

Marsh Posté le 11-11-2013 à 16:18:40    

C'est bon c'est modifié par contre j'ai pas compris comment avoir des tirages au dessus de 32XXX
 
Voici le programme sur un compilateur en ligne : http://ideone.com/eH4CAM
 
lui il tire correctement ... je comprend pas mon soucis


Message édité par yeskinokay le 11-11-2013 à 16:20:01

---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 16:29:52    

Par conception, rand() renvoie toujours un nombre entre 0 et RAND_MAX.
 
Selon la plate-forme / le compilateur la valeur de RAND_MAX est différente : Visual Studio utilise un RAND_MAX à 32767, tandis que linux/gcc utilise 2^32 -1.
 
Si le site compile sous Linux (et cela a de bonnes chances d'être le cas), le code fonctionnera bien mieux.
 
Pour aller au delà, il faut construire un nombre aléatoire, par exemple comme je l'ai indiqué plus haut, où un construit un nombre sur 30 bits (maximum égal à un peu plus qu'un milliard) en faisant un premier rand() pour les 15 premiers bits, puis un autre pour les 15 bits de poids fort (que l'on multiplie par 32768).
 
Bonne continuation !

Reply

Marsh Posté le 11-11-2013 à 16:32:35    

Ne serait t'il pas plus simple d'utiliser le pourcentage multiplié par 1000 plutôt que le nombre ?  
 
http://fr.wikipedia.org/wiki/Fr%C3 [...] n%C3%A7ais


Message édité par yeskinokay le 11-11-2013 à 16:32:49

---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 16:41:57    

Si mais,
 
- C'est moins précis,
- Vous devrez vérifier tous les arrondis pour être sûr que la somme fait bien 10000 tout rond,
- Cela aurait pu poser problème pour la lettre "ë",
 
D'une manière plus générale, cela revient à dégrader les données pour pallier un problème d'implémentation (de la fonction rand en l'occurrence), ce qui n'est pas très satisfaisant intellectuellement.
 
Mais cela va marcher et il va falloir en faire, des tirages, pour mettre en lumière un écart entre les résultats obtenus et les résultats théoriques :)
 
Après, c'est comme tout, tant qu'on le fait en comprenant les enjeux et après avoir pesé le pour et le contre, c'est une question de choix !
 
Bonne continuation !

Reply

Marsh Posté le 11-11-2013 à 16:58:27    

:) Bon j'ai continuer comme sa enfaite.
 
Sur le compilateur en ligne le code fonctionne : http://ideone.com/sgyatO
 
Moi je suis sous windaube, mes collègues sont sous linux, j'essayerai sur leur machine.
 
Je vous posterais la fin du projet :)  
 
Nous avons fais une fenêtre en sdl avec des boules (contenant des lettres) qui tombe (gestion de collision avec Chipmunk) ensuite une fois la fenêtre rempli de boule on trace un trait avec la souris, toute les boules qui sont couper par le trait, on récupères les lettres et on sort les mots qui sont compatible (depuis un fichier de dictionnaire).


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le 11-11-2013 à 22:54:16    

Noter que si tu es pas limité au C mais que tu peux utiliser le C++11, tu peux alors disposer de std::discrete_distribution<int> qui fait le boulot pour toi...
 

Code :
  1. #include <array>
  2. #include <chrono>
  3. #include <functional>
  4. #include <iostream>
  5. #include <random>
  6. #include <string>
  8. int main()
  9. {
  10.     // rand initialisé avec une seed à time(), C++11 style
  11.     std::default_random_engine generateur(std::chrono::system_clock::now().time_since_epoch().count());
  12.     // l'alphabet
  13.     std::string const alphabet = "abcdefghijklmnopqrstuvwxyz";
  14.     // un array des occurences de chaque lettre cf http://www.lexique.org/listes/liste_lettres.php
  15.     std::array<int, 26> occurences = {36874333, 4627074, 15085754, 17905604, 71889538,
  16.                                       5146739, 4716482, 4350377, 35137433, 2828752,
  17.                                       146188, 27563346, 14641296, 33720188, 25910113,
  18.                                       13436762, 5596700, 31772475, 39185354, 33688246,
  19.                                       29974507, 7692339, 88479, 2025673, 1400656, 753886
  20.                                      };
  21.     // La est ce qui facilite les choses: on construit une distribution de 0 à 25
  22.     // avec comme poids associés les occurences
  23.     std::discrete_distribution<int> distribution(occurences.begin(), occurences.end());
  24.     // et on va generer avec le générateur des valeurs de la distribution
  25.     // avec une fréquence en rapport au poids: valeur = distribution(generator)
  26.     // et sous forme de fonction pour réutilisations multiples
  27.     auto nextval = std::bind(distribution, generateur);
  29.     // utilisation: on genere 25 suites de 8 lettres
  30.     for (auto i = 0; i < 25; ++i) {
  31.         for (auto j = 0; j < 8; ++j) {
  32.             std::cout << alphabet.at(nextval());
  33.         }
  34.         std::cout << std::endl;
  35.     }
  36.     std::cout << std::endl;
  38.     return 0;
  39. }


 
A+,


Message édité par gilou le 11-11-2013 à 22:56:36

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 13-11-2013 à 23:54:46    

Non malheureusement le projet ne peux pas être fais en c++, seulement en C. Mais c'est gentil a toi d'avoir posté ce bout de code !


---------------
                          Mon FEED-BACK : http://forum.hardware.fr/hfr/Achat [...] 8658_1.htm
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed