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
    Membre confirmé
    Inscrit en
    Octobre 2005
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2005
    Messages : 61
    Par défaut Nombre Secret (Probleme de Proba)
    Bonsoir,

    Voila, je suis en train de faire un algorithme, le but est est de trouve un "Nombre secret" ce nombre secret est generé par un Random:

    Float: Rand: Random()

    Random donne un nombre (float) compris entre 0 et 1

    les borne pour trouver le chiffre son demandé au joueur (genre de 0 à 100..)

    Pour l'example on va dire de : 0 à 10

    Le probleme maintenant c'est qu'il faut que CHAQUE CHIFFRE EST LA MEME PROBABILITE D?ETRE CHOISIT...

    la premiere chose qui me vien a l'esprit c'est de faire:

    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...

    example de 0 à 2

    de 0 à 0.4 = 0 ( la y a en 5)
    de 0.5 à 1.4 = 1 (la 10)
    de 1.5 à 2 = 2 (et la 6)

    j'ai donc fait un ca (par ex de 0 à 10):

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

    avec ceci chaque chiffre a la meme probabilité detre choisit (car la on a agrandi la borne (de 10 a 11) et le mod(10+1) agrandi la borne (0)

    de 0 à 0.4 = 0 ( la y a en 5)
    de 0.5 à 1.4 = 1 (la 10)
    de 1.5 à 2.4 = 2 (et la 10)
    de 2.5 à 3 = 3 (et la 6)

    en faite le mod sert en GROS a mettre tout les '3' dans les 0... (car 3 mod 3 = 0..)

    Mais je n'ai pas le droit d'utilise Mod,
    Il me faut donc une autre Equation..

    et la je bloque

    si quelqu'un pourrai me donné quelque indice?

    d'avance merci

  2. #2
    Membre Expert
    Avatar de afrikha
    Profil pro
    Étudiant
    Inscrit en
    Août 2005
    Messages
    1 600
    Détails du profil
    Informations personnelles :
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2005
    Messages : 1 600
    Par défaut
    je pense que cette solution marche mais j'ai restreint rand à [0,1[.
    j'espere que c'est pas trop grave.mais je pense qu'avec ça tous les nombres auront la mème probabilité.

    supposons que l'utilisateur choisisse un intervalle [0,n-1].
    comme c'est un intervalle entier,il est equivalent à [0,n[.
    on divise [0,1] par n, on a donc n morceaux dans [0,1]

    exemple:
    si n=4,on a 0--0.25--0.5--0.75--1

    aprés on fait une boucle pour comme suit:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    faire
    a=Rand;
    jusqu'à (a!=1)
     
    pour i=1 jusqu'à n faire
    {si (a<((1/n)*i)
      alors nombresecret=i-1;}


    Mes publications
    Lisez
    Les régles du forum
    Pensez au bouton

  3. #3
    Membre émérite
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Par défaut
    Il y a + simple en tout cas avec borland delphi ou C++

    1er comencer par appeler
    randomize();

    2eme
    plutôt que d'utiliser rand() qui retourne un float pseudo alléatoire dans [0..1[
    utiliser
    i random(N); qui retoutne un entier pseudo alléatoire i>=0, i < N

  4. #4
    Membre confirmé
    Inscrit en
    Octobre 2005
    Messages
    61
    Détails du profil
    Informations forums :
    Inscription : Octobre 2005
    Messages : 61
    Par défaut
    hmm, afrikha

    merci d'avoir répondu, mais le 1 est compris

    le rand sort un nombre float [0- 1]

  5. #5
    Membre Expert
    Avatar de afrikha
    Profil pro
    Étudiant
    Inscrit en
    Août 2005
    Messages
    1 600
    Détails du profil
    Informations personnelles :
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2005
    Messages : 1 600
    Par défaut
    Citation Envoyé par BoBy9
    hmm, afrikha

    merci d'avoir répondu, mais le 1 est compris

    le rand sort un nombre float [0- 1]
    dans ce cas;ma methode ne marche pas,car je pense que ce n'est pas possible de diviser [0,1] en n intervalles de mème "cardinal".


    Mes publications
    Lisez
    Les régles du forum
    Pensez au bouton

  6. #6
    doccpu
    Invité(e)
    Par défaut Re: Nombre Secret (Probleme de Proba)
    Citation Envoyé par BoBy9
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    NbSecret := ((10 +1)*Rand) mod (10 + 1));
    ne sert pas a grand chose au contraire il desequilibre ton algo en excentrant tes stats. fait plutot :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    NbSecret := (Integer)((11)*Rand);
    il faut savoir que les fonctions Rand renvoient un nombre réel [0;1[ en les multipliant metont par 10 on obtient [0;9] ([0;10[) en rajoutant + 1 on décale les résultats d'un crant soit toujours avec un coef 10 : [1;10] ([1;11[)donc si on veux alle de 0 a n il faut donner au programme (n+1) comme coef et ne pas rajouter +1 apres le calcul. le generateur de nombres aleatoire doit logiquement donner autant de chance a tout les nombres mais certains generateurs sont plus aboutis que d'autres.

    si par maleur ta calculatrice ne sortait jammais le 0 avec le code que je t'ai donné essaye :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    NbSecret := (Integer)(((12)*Rand) - 1);
    Ca voudrais dire que ton Rand ne sort tes intervales que dans ]0:1[ ce qui est bizare mais que j'ai déjà vu ailleur

  7. #7
    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
    NbSecret := ((10 +1)*Rand) mod (10 + 1));

    Me parait correcte si le resultat est comme tu l'as dis arrondi
    Le nombre est tiré dans l'intervalle 0..11 puis arrondis
    => donc 0 et 11 ont deux fois moins de chances d'etre tirés
    le module corrige ce probleme car lorque l'on tire 11 il est transformé en 1


    Avec ceci tu devrais obtenir le meme resultat
    NbSecret = ((11.0*Rand)-0.5)
    le nombre est tiré entre -0.5 et 10.5
    => donc après arrondi on obtient bien un nombre entre 0 et 10 avec quasiment le même probabilité de tiré chauqe nombred'être tirés

  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
    Il vaut mieux diviser par 11 que faire un modulo 11.

  9. #9
    Membre Expert
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Par défaut
    oui, c'est logique.

    pour le rand, je ne vois pas pourquoi le 0 à moins de chance que les autres si tu fait un rand*11 puisque (vu que tu fait un integer) ses chances sont celles de tous les nombres compris sur [0,1[
    par contre, évite le round.(arrondi)
    je me demande si le 11 peut vraiment être sorti?
    théoriquement non, puisque même en integer sa chance est de 1 sur l'infini soit 0
    mais comme il y as des arrondis...

    salut

  10. #10
    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 ne vois pas trop ce que veut dire Miles :
    >>Il vaut mieux diviser par 11 que faire un modulo 11.
    Pourrais tu préciser tes pensées ?

    méphistopheles les extremité ont deux foix moins de chance d'être tirés à cause de l'arrondi :
    0..0,5 => 0
    0,5..1,5 => 1
    ...
    10.5 à 11 => 11

  11. #11
    Membre Expert
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Par défaut
    non, car il faut utiliser comme je l'ai dis l'a fonction partie entière (int en vb) pour que ta probabilité soit vallable.

    il est évident que la fonction arrondi ne marche pas.

    regarde, je ne connais pas ton langage de programmation mais il y à forcément une fonction partie entière qui est basique, indispensable et plus facile à programmer que la fonction arrondi.



    salut

  12. #12
    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
    Non Non et Non

    Boby9 à écrit:
    PS: dans le language que j'utilise (Integer) ARRONDI, donc 1.5 -> 2
    J'essaie seulement de répondre au problème mais c'est sûr qu'en prenant la partie entière c'est plus simple !

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    NbSecret = Arrondi((11.0*Rand)-0.5)
    devient

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    NbSecret := Int((11)*Rand);
    ou plutot

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    NbSecret := Int((10.99999)*Rand);
    pour être sûr que le 11 ne sorte jamais

  13. #13
    Membre Expert
    Avatar de méphistopheles
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    1 551
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France

    Informations forums :
    Inscription : Janvier 2005
    Messages : 1 551
    Par défaut
    Citation Envoyé par scr
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    NbSecret := Int((10.99999)*Rand);
    pour être sûr que le 11 ne sorte jamais
    oui, mais ça fausse les statistique
    en fait, il faudrais cnaitre le degrés de précision de ta variable et mettre autemps de décimales.

    salut

  14. #14
    Membre éclairé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    277
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 277
    Par défaut
    Une chose est sûre : pour avoir 11 valeurs équiprobables 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, il faudra multiplier rand par 11.

    Le problème du 11 maintenant :

    En fait, dans la mesure où la probabilité que rand renvoie 1 est pratiquement nulle (elle serait nulle si il y avait un précision infinie, ce qui n'est pas le cas), on pourrait tout à fait dire que si 10*rand+1 renvoit 11 alors le résultat est 10, on ne sentirait pas la différence.

    Maintenant, si ça vous embête tant que ça (mais déjà vous chipoteriez ), vous n'avez qu'à refaire un tirage jusqu'à ce que rand ne renvoit pas 1 (sachant que la probabilité que rand renvoit 1 deux fois de suite est à hurler de rire tellement elle est faible).

  15. #15
    doccpu
    Invité(e)
    Par défaut
    vous ne lisez pas ce que l'on ecrit !
    ya pas de chance que le 11 sorte avec int((11)*rand) puisque le resultat sera compris entre 0 INCLU et 11 EXCLU
    int(10.999999) = 10 !

    si il n'y a pas de "int", "Int", "INT" ou "INTEGER" utilise "Trunc" ou "Truncate" qui renvoi la partie entière sur certaines calculatrices !

  16. #16
    Membre éclairé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    277
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 277
    Par défaut
    Citation Envoyé par BoBy9
    hmm, afrikha

    merci d'avoir répondu, mais le 1 est compris

    le rand sort un nombre float [0- 1]
    Je sais pas de quel langage il s'agit. En C, je sais que c'est [0;1[, mais dans d'autres langages...

  17. #17
    Membre éclairé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    277
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 277
    Par défaut
    Je crois que j'avais mal compris le sens de ta remarque.

    alors je corrige : j'essaie d'éviter ton 10.99999 qui est malvenu pour plusieurs raisons. La première étant que le langage va traduire ton 10.999999 dans son système de codage des nombres à virgules, et que si ça se trouve, en faisant ça, il va arrondir à 11 (demande aux programmeurs en C le nombre de fois qu'un float initialisé à 10 s'est en fait révélé égal à 10.0002).

    De plus, tu biaises (un tout petit peu, mais quand même, sur 100000000 de lancers ça se verra ) les fréquences d'appartition de chaque nombre.

  18. #18
    doccpu
    Invité(e)
    Par défaut
    La fonction rand renvoie un nombre entre [0;1[ dans tout les languages que j'ai pratiqué (ZX81basic,Qbasic, VBA, VB, VB.NET, C/C++/C#) et sur toutes les calculatrices que j'ai utilisé (Casio et TI) c'est pour cela que l'on rajoute +1 pour un tir de dé (pour décaler d'un chiffre le resultat)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    //code d'un dé
    int tir = int((Rand*(6))+1)

  19. #19
    Membre éclairé
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    277
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 277
    Par défaut
    Je suis tout à fait d'accord, j'avais moi-même été surpris de la remarque de Boby9, mais puisque ça avait l'air de poser problème, je postais pour dire que même dans ce cas ça ne pose pas problème.

    Comme on dit en math, [0;1[et [0;1] ont même mesure

  20. #20
    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 Re: Nombre Secret (Probleme de Proba)
    Citation Envoyé par BoBy9
    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 ne faut pas arrondir le résultat mais récupérer sa partie entière :

    Pour un nombre aléatoire entre 0 et n : trunc(random * (n + 1))

    avec : 0 <= random < 1
    et : trunc(0,99999999) = 0

    Bloon

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