IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Nombre Secret (Probleme de Proba)


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    je suis d'accord mephisto sauf mais pour ce qui est de fausser les statistiques je pense que c'est negligeable si l'on ajoute autant de décimales que le type de donnée le permet...


    En ce qui concerne la remarque de docpu sur l'interval [0,1[ , j'ai bien lu mais tout ce qui est ecrit ici n'est pas parole d'évangile ! Est ce vraiment un standard pour tous les language ?
    En C le rand sort une valeur entre 0 et RAND_MAX (defined as the value 0x7fff)
    Il faut ensuite diviser la valeur par RAND_MAX pour obtenir un chiffre tiré dans l'intervalle [0..1] (RAND_MAX peut être tiré)
    Bien sur on doit pouvoir diviser par RAND_MAX+1 quoi que ? je ne suis pas sur que cela soit si simple car il me semble que RAND_MAX est la valeur maximum d'un 32 bit signé ... Il doit donc falloir passer par un type de donnée ayant assez de précision pour donner un calcul exacte.

  2. #2
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    En C, par exemple, le générateur tire un entier entre 0 et RAND_MAX - 1. Si on fait un modulo, on va légèrement biaiser le générateur vers les valeurs faibles, ce qui ne sera pas le cas de la division.

    Si l'arrondi se fait entre [-0.5; 0.5[, il suffit de décaler les données, donc faire Rand()*11-0.5, c'est pourtant pas compliqué !

  3. #3
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    En C, par exemple, le générateur tire un entier entre 0 et RAND_MAX - 1
    Es tu sur de ça, la MSDN parle d'un nombre tiré entre 0 et RAND_MAX sans préciser que RAND_MAX ne fait pas partie de l'interval !



    Si on fait un modulo, on va légèrement biaiser le générateur vers les valeurs faibles
    Personnelement je ne vois pas trop ce que tu veux dire, pourrais tu preciser ...


    ce qui ne sera pas le cas de la division
    Je ne vois pas non plus comment utiliser une division pour remplacer le modulo, aurais tu un example ?

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Par défaut
    Citation Envoyé par scr
    [Je ne vois pas non plus comment utiliser une division pour remplacer le modulo, aurais tu un example ?
    Réponse sur cette page
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  5. #5
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    Merci Trap D mais cette page parle de division de rand() par RAND_MAX en C
    et non de l'utilisation d'une division pour remplacer un modulo comme le disiat Miles


    Rappel:

    J'ai écrit
    NbSecret := ((10 +1)*Rand) mod (10 + 1));
    Miles a répondu:
    Il vaut mieux diviser par 11 que faire un modulo 11.

    Alors a moins que je ne sois passé a coté de qqc cela ne répond pas a ma question !

    [/quote]

  6. #6
    Membre éclairé Avatar de Biosox
    Profil pro
    Inscrit en
    Mai 2005
    Messages
    298
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations forums :
    Inscription : Mai 2005
    Messages : 298
    Par défaut
    Pourquoi se fatiguer?
    PS: dans le language que j'utilise (Integer) ARRONDI, donc 1.5 -> 2
    NbSecret = (Integer)Rand * 10

    donc la j'aurai un chiffre qui se trouvera entre 0 et 10 (Compris)

    mais le probleme c'est que les borne (0 et 10) on 2fois moi de chance d'etre choisi...
    Il n'y a qu'à prendre
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    NbSecret = (Integer)Rand *11
    a ce moment les bornes (0 et 11) on 2fois moi de chance d'etre choisi. On ajoute un petit:
    IF NbSecret==11 then NbSecret = 0
    et le tour est joué: La borne 11 n'apparait jamais (c'est ce qu'on voulait) et la borne 0 a 2 fois la moitié de chances d'etre choisie, donc c bon.
    Pas de divisions, pas de modulo (que de la bricole )

    (ou pur etre générique: If NbSecret == borneSup, then NBSecret = borneInf)

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Par défaut
    Citation Envoyé par scr
    Alors a moins que je ne sois passé a coté de qqc cela ne répond pas a ma question !
    Comme tu dis
    Si tu avais bien regarder, on divise rand() par RAND_MAX, on obtient donc un réel compris entre 0 et 1, je le multiplie ensuite par 3, donc le réel obtenu est compris entre 0 et 3. je prends la partie entière de ce réel et j'ai un entier compris entre 0 et 2 inclus, soit bien un modulo 3 !
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  8. #8
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Et qui a des chances égales de sortir !

    Mais bon, on répond aux questions, on répond aux questions et les gens ne lisent même pas.

  9. #9
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    Merci Trap D pour ton explication mais j'avais bien compris

    Tu parles de division par RAND_MAX

    Or lorsque j'ai écrit :

    NbSecret := ((10 +1)*Rand) mod (10 + 1));
    On ne parlait pas du Rand en C qui genere un nombre entre 0 et RAND_MAX mais du Rand standard qui tire un nombre dans l'interval 0..1
    Dans ce cas on a pas besoin de diviser par RAND_MAX puisque la valeur tirée est déjà dans l'interval 0..1

    Et c'est la que Miles à écrit :
    Il vaut mieux diviser par 11 que faire un modulo 11.
    Voila pourquoi ma question:
    Comment peut on remplacer un modulo par une division ?


    Pour répondre à Miles je dirai que j'ai bien lu tes réponses mais j'ai un peut de mal à te comprendre et je ne dois pas être le seul !
    Ce que tu dis avais l'air très intéressant :

    Il vaut mieux diviser par 11 que faire un modulo 11.
    Si on fait un modulo, on va légèrement biaiser le générateur vers les valeurs faibles, ce qui ne sera pas le cas de la division.
    Mais sans example, j'ai du mal à voir de quoi tu parles.

    Comment peut on remplacer le modulo par une division dans la formule ?
    NbSecret := ((10 +1)*Rand) mod (10 + 1));
    par ce que si je fais ca, ca donne pas exacetement ce qu'on attendait
    NbSecret := ((10 +1)*Rand) / (10 + 1));
    et cette remarque ?
    Si on fait un modulo, on va légèrement biaiser le générateur vers les valeurs faibles, ce qui ne sera pas le cas de la division.
    Pourrais tu s'il te plait argumenter un petit peu !
    Merci d'avance

  10. #10
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    OK, si RAND génère un nombre entre 0 et 1, il n'y a pas de modulo à faire, le nombre reste entre 0 et 11. Maintenant si tu génères un nombre entier entre 0 et RAND_MAX, en utilisant un modulo, tu biaises.

    Exemple avec RAND_MAX = 12
    Tu fais donc Rand() % 11.
    Tu as 0 et 1 qui ont 2 fois plus de chances d'être tirés que les autres nombres.
    Maintenant, si tu fais 11 * (Rand() / 11), ça redeviens équitable. Pour des grands nombres.

  11. #11
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    Ca y est compris ce que tu voulais dire Miles Merci pour ton explication

    Mais si on reprend le cas dont on parlait avec la fonction rand qui tire un nombre de 0..1
    Alors je réaffirme que :

    NbSecret := (Arrondi((10 +1)*Rand)) mod (10 + 1));

    Me paraît correcte pour tirer un nombre entre 0 et 10 avec autant de chance de tiré chaque nombre.

    Car:
    Rand tire entre 0 et 1
    multiplié par 11 cela donne entre 0 et 11
    l'arrondi donne une valeur entre entre 0 et 11 mais avec deux fois moins de chance pour le zero et pour le 11
    le modulo transforme les tirages de 11 en zero ce qui corrige le tout pour avoir un nombre entre 0 et 10 avec autant de chance de tiré chacun de nombre.


    Mais alors la si tu me dis encore qu'il vaut mieux diviser par 11 que faire un modulo 11 je comprend plus rien !

  12. #12
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Si ton arrondi est fait entre -0.5 et +0.5, tu ne fais pas un mod 11, tu fais une soustraction avec 0.5, comme je l'ai proposé plus tôt - j'aurai dû le mettre en rouge ? -.
    Le modulo coûte plus cher qu'une soustraction.

  13. #13
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Par défaut
    Citation Envoyé par scr
    Ca y est compris ce que tu voulais dire Miles Merci pour ton explication
    Donc maintenant tu as compris mon intervention
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  14. #14
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    Oui Miles mais si tu lisais un peu ce qu'on écrit, tu verrais que j'avais deja dit ca dans le 7e post sur ce sujet, juste avant ton premier post.

    NbSecret = ((11.0*Rand)-0.5)

    Peut être est ce plus clair comme ceci :

    NbSecret = Arrondi((11.0*Rand)-0.5)

    Mais c'est bien vu quand même...


    Trap D ma question était comment remplacer un modulo par une division
    dans le calcul :

    NbSecret := Arrondi((10 +1)*Rand) mod (10 + 1));

    Avec Rand tirant un nombre entre 0 et 1.
    Donc la page sur laquelle tu m'a renvoyé ne répond pas du tout à la question, d'ailleur on ne parle pas de modulo sur cette page.
    Mais merci quand même d'avoir participer...



    Sinon question de rattrapage, vu que vous avez l'air de connaitre le C:
    Rand en C cette fois ci sort il un nombre entre
    [0..RAND_MAX]
    ]0..RAND_MAX[
    [0..RAND_MAX[

    En gros les extremités sont elles comprises, la MSDN reste flou a ce sujet:

    The rand function returns a pseudorandom integer in the range 0 to RAND_MAX

    Sans préciser si les extrémités peuvent être tirées ou pas ?

  15. #15
    Membre chevronné Avatar de xxiemeciel
    Inscrit en
    Juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 371
    Par défaut
    Salut,

    Pourquoi ne pas utiliser une valeur beaucoup plus grande, divisible en nombre de partie souhaitee pour rendre la difference de statistique negligeable ?


    dans le cas ou le nombre secret est entre 0 et 2 ca fais une grosse difference mais entre 0 et 3000 ca ne se verra pas ou alors j'ai rien compris lol

    et ensuite y'a plus qu'a definir que 0 = valeur entre 0 et 1000
    1 = valeur entre 1000 et 2000
    2 = valeur entre 2000 et 3000

    XXiemeciel

  16. #16
    Membre émérite
    Avatar de Bloon
    Homme Profil pro
    Consultant Freelance
    Inscrit en
    Avril 2002
    Messages
    467
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Consultant Freelance
    Secteur : Conseil

    Informations forums :
    Inscription : Avril 2002
    Messages : 467
    Par défaut


    Vous pouvez discuter longtemps comme ça, mais comme je le dis plus haut, il faut utiliser la partie entière du nombre et non une bidouille avec l'arrondi :

    partieEntiere(random * (n + 1)) 0 <= nombre aléatoire <= n

    Bloon

  17. #17
    scr
    scr est déconnecté
    Membre éprouvé
    Inscrit en
    Juin 2005
    Messages
    127
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 127
    Par défaut
    Oui Bloon bien sur et je pense que tout le monde est d'accord
    Mais dans les hypothèses de la question initiale, Boby9 ne disposait pas de la fonction partie entiere. Mais peut être l'a t il trouvé depuis...


    Salut xxiemeciel,
    Je vois ce que tu veux dire, tu parles du problème soulevé par Miles me semble t'il ? (ou j'ai rien compris !)
    Cela pourrait être une solution s'il y avait un problème mais il ne me semble pas qu'il y ait de problème statistique si on utilise les bonnes formules...

    NbSecret := Int((11)*Rand);

    NbSecret = Arrondi((11.0*Rand)-0.5)

    NbSecret := Arrondi((10 +1)*Rand) mod (10 + 1));

    Sont a mon avis des bonnes formules sauf si doccpu veut bien nous expliquer ce qu'il entend par :
    NbSecret := ((10 +1)*Rand) mod (10 + 1));
    ne sert pas a grand chose au contraire il desequilibre ton algo en excentrant tes stats.

  18. #18
    Membre chevronné Avatar de xxiemeciel
    Inscrit en
    Juin 2005
    Messages
    371
    Détails du profil
    Informations forums :
    Inscription : Juin 2005
    Messages : 371
    Par défaut
    dites je crois que la personne qui a posté la question de depart n'est pas revenu depuis le 4ieme post de la premiere page

    XXiemeciel

Discussions similaires

  1. [SGBD] MySQL:Probleme lorsque je evux afficher des nombres
    Par pierrot10 dans le forum SQL Procédural
    Réponses: 2
    Dernier message: 16/10/2005, 00h59
  2. Réponses: 24
    Dernier message: 27/09/2005, 21h16
  3. Probleme de compte le nombre de Recordset
    Par nemesys971 dans le forum Access
    Réponses: 5
    Dernier message: 27/10/2004, 15h23
  4. [VB6] Problème d'addition de dates et de nombres
    Par pepper dans le forum VB 6 et antérieur
    Réponses: 8
    Dernier message: 28/11/2002, 21h12
  5. [Kylix] Probleme de nombre flottant!!
    Par yopziggy dans le forum EDI
    Réponses: 5
    Dernier message: 02/05/2002, 10h13

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo