[C] Tirage de lettre et probabilité

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [C] Tirage de lettre et probabilité

yeskinokay

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

Publicité

Farian

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 !

yeskinokay

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 :

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

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

yeskinokay

Code :

switch(nbAleatoire){
case (nbAleatoire<225947):
return 'e';
break;
default: "Erreur Tirage";
}

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

Farian

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 :

char getLettreRandom(int nombreAleatoire)
{
int occurrences[] = {225947, 121895, 117110, ...., 84, 7};
char lettres[] = "esa...ïë";
int i, total;
char retour = ' '; /* Valeur par défaut au cas où */
for (i=0, total = 0; i < 36; i++)
{
if ( (nombreAleatoire >= total) && (nombreAleatoire < total + occurences[i]))
{
retour = lettres[i];
break;
}
total += occurrences[i];
}
return retour;
}

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

yeskinokay

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

Farian

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

yeskinokay

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 :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
int rand_a_b(int min,int max){
return rand()%(max-min)+min;
}
char getLettreRandom(int nombreAleatoire)
{
int occurrences[] = {225947, 121895, 117110,115465,111103,108812,100500,96785,83668,
82762,56269,50003,46335,45521,29206,24975,20889,16351,13822,11298,
8351,7449,5928,4725,4160,3445,2093,1747,1306,890,745,695,283,84,7, 84, 7};
char lettres[] = "esaitnrulodcpmévqfbghjàxyèêzwçùkîœïë";
int i, total;
char retour = ' '; /* Valeur par défaut au cas où */
for (i=0, total = 0; i < 36; i++)
{
if ( (nombreAleatoire > total) && (nombreAleatoire < total + occurrences[i]))
{
retour = lettres[i];
break;
}
total += occurrences[i];
}
return retour;
}
int main(){
int nbAleatoire;
nbAleatoire = rand_a_b(0,1533628);
printf("%d\n",nbAleatoire);
getLettreRandom(nbAleatoire);
getchar();
}

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

gilou

Modérateur
Modosaurus Rex

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! -- Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- No jab ? No job ! -- (╯°□°)╯︵ ┻━┻

Farian

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

Publicité

gilou

Modérateur
Modosaurus Rex

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! -- Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- No jab ? No job ! -- (╯°□°)╯︵ ┻━┻

Farian

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"

yeskinokay

Code :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
int rand_a_b(int min,int max){
return rand()%(max-min)+min;
}
char getLettreRandom(int nombreAleatoire)
{
// Tirage de lettre en fonction de sa probabilité d'apparaitre dans un corpus donné de 1 533 629 lettres
// Source wiki.
// On fait correspondre les occurrences avec les lettres.
int occurrences[] = {225947, 121895, 117110,115465,111103,108812,100500,96785,83668,
82762,56269,50003,46335,45521,24975,20889,16351,13822,11298,
8351,5928,4725,2093,1747,745,695,283,};
char lettres[] = "esaitnrulodcpmvqfbghjxyzwk";
int i, total;
char retour = ' '; /* Valeur par défaut au cas où */
for (i=0, total = 0; i < 36; i++)
{
if ( (nombreAleatoire > total) && (nombreAleatoire < total + occurrences[i]))
{
retour = lettres[i];
break;
}
total += occurrences[i];
}
return retour;
}
int main(){
int nbAleatoire1=rand_a_b(0,1533628);
int nbAleatoire2=rand_a_b(0,1533628);
int nbAleatoire3=rand_a_b(0,1533628);
//nbAleatoire=rand()%1533628;
printf("%d , %d , %d \n",nbAleatoire1,nbAleatoire2,nbAleatoire3);
char c = ' ';
c= getLettreRandom(nbAleatoire1);
printf("%c\n",c);
srand(time(NULL));
getchar();
}

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>f:\cours\etudedecas\consoleapplication1\source.c(53): error C2143: erreur de syntaxe : absence de ';' avant 'type'
1>f:\cours\etudedecas\consoleapplication1\source.c(54): error C2065: 'c' : identificateur non déclaré
1>f:\cours\etudedecas\consoleapplication1\source.c(55): error C2065: 'c' : identificateur non déclaré
1>f:\cours\etudedecas\consoleapplication1\source.c(58): warning C4244: 'fonction' : conversion de 'time_t' en 'unsigned int', perte possible de données
========== 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

Farian

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

yeskinokay

A je pensais que c’était comme libéré une mémoire alloué [:michelnet1]

EDIT: mon compilateur n'est pas d'accord ...

Code :

int main(){
srand(time(NULL));
int nbAleatoire1=rand_a_b(0,1533628);
int nbAleatoire2=rand_a_b(0,1533628);
int nbAleatoire3=rand_a_b(0,1533628);
//nbAleatoire=rand()%1533628;
printf("%d , %d , %d \n",nbAleatoire1,nbAleatoire2,nbAleatoire3);
//char c = ' ';
//c= getLettreRandom(nbAleatoire1);
//printf("%c\n",c);
getchar();
}

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

Farian

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

yeskinokay

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

Farian

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 !

yeskinokay

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

Farian

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 !

yeskinokay

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

gilou

Modérateur
Modosaurus Rex

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 :

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

A+,

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

---------------
There's more than what can be linked! -- Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- No jab ? No job ! -- (╯°□°)╯︵ ┻━┻

yeskinokay

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

Publicité

FORUM HardWare.fr

Programmation

[C] Tirage de lettre et probabilité

Sujets relatifs
[C] Calculer la Normale d'un vecteur en C	[C#]grand débutant restriction
Reload automatique toute les 10sec - C#	C sous unix => synchronisation avec les signaux
envoyer tout un vecteur comme un paramètre de Java en C + +	Aide Programmation en C
Structure Polynome( probleme d'affichage) en C	[C] Besoin d'aide pour le Jeux de la Vie
mini serveur en C: setsockopt() == -1	Langage C - Pointeurs (Quelques explications)
Plus de sujets relatifs à : [C] Tirage de lettre et probabilité

Page générée en 0.145 secondes