Misez p'tit, optimisez n°62: Les boules

[tyann]

Bonjour à tous

Aller je me lance, c'est mon premier.

Dans un sac vous avez une boule blanche et une boule noire.
A: vous piochez une boule à l'aveugle et vous rajoutez dans ce sac une boule de la couleur de celle que vous venez de piocher.
Vous avez maintenant 3 boules dans le sac et vous recommencer la manip (A).

Le programme devra simuler un nombre de tirages variable et vous retourner à la fin le nombre de boules
blanches et noires contenues dans le sac.

A vos machines.

Sommaire MPO

[zpalm]

Chouette un MPO

Sur WP 34S en 13 pas et en n'utilisant que les 4 registres de la pile: on entre le nombre de tirages, on lance le programme, on obtient en X le nombre de boules blanches et en Y le nombre de boules noires.

Par exemple avec [5] [A] (5 tirages) on peut obtenir 2 boules noires et 5 boules blanches (avec YDON on voit les deux en même temps):

Code : Tout sélectionner

001 LBL A
002 #001
003 #002
004 RAN#
005 RCLx Y
006 x<=? Z
007 INC Z
008 INC Y
009 DROP
010 DSZ Z
011 BACK 007
012 RCL- Y
013 RTN

[bernouilli92]

Voici ma version pour hp 48 :

Code : Tout sélectionner

<< { 1 1 } 1 ROT 
  START
    DUP 1 GET OVER LIST-> DROP 
    + RAND *
    FLOOR 1 + < 
    1 + DUP2 
    GET 1 + PUT
  NEXT
>>

On entre le nombre d'itérations et on lance le programme. Le résultat est une liste de 2 nombres (nb boules blanches et nb de boules noires).

[Marge]

Je vais tenter de me lancer sur HP-29c. Sympa ce MPO !

[Woodstock]

Ah, enfin un MPO dont je comprends l'énoncé...

Basic Sharp, 9 instructions sans label ni end (64 octets + 5 variables sur PC-1247) :

Code : Tout sélectionner

1:"=" AREAD V:B=1,R=1: FOR T=1 TO V:P= RND 2:B=B+(P=1),R=R+(P=2): NEXT T: PRINT "B";B;"R";R: END

Nombre de tirages voulus puis DEF =

Mais au fait, pourquoi faire réellement les tirages ?
Basic, 3 instructions (34 octets + 2 variables sur PC-1247) :

Code : Tout sélectionner

1:"=" AREAD T:P=RND T: PRINT "B":P+1;"R";T-P+1: END

Même utilisation

Et là, même les Casio pourront le faire (en remplaçant AREAD par INP ou INPUT, RND £ INT (£*RAN#) et PRINT par PRT le cas échéant, dialecte oblige)

Nota pour les vrais économiseurs d'octets : on peut gratter 4 octets dans la première version en remplçant B=B+(P=1),R=R+(P=2) par B=B+P-1,R=R-P+2 mais c'est moins compréhensible ; on peut supprimer 3 octets en remplaçant "=" AREAD T par INPUT T mais c'est moins pratique, et récupérer 8 octets en remplaçant PRINT "B";B;"R";R par PRINT B;R, ou PRINT "B";P+1;"R";T-P+1 par PRINT P+1;T-P+1 mais c'est moins lisible. Et s'il n'y a pas d'autre programme, autant supprimer le : END, ça fera encore deux octets de gagnés.

Bref, Basic 3 instructions, 2 variables, 21 octets sur Sharp PC-1247:

Code : Tout sélectionner

1:INPUT T:P= RND T: PRINT P+1;T-P+1

Mais c'est moins joli...

[bernouilli92]

Basic Sharp, 9 instructions sans label ni end (64 octets + 5 variables sur PC-1247) :

Code : Tout sélectionner

1:"=" AREAD V:B=1,R=1: FOR T=1 TO V:P= RND 2:B=B+(P=1),R=R+(P=2): NEXT T: PRINT "B";B;"R";R: END

Ce n'est pas conforme à l'énoncé, ici à chaque tirage, tu as autant de chances de tirer une boule noire qu'une boule blanche et ce quelque soit la proportion de boules noires (RND 2).

Mais au fait, pourquoi faire réellement les tirages ?
...
[/i]Bref, Basic 3 instructions, 2 variables, 21 octets sur Sharp PC-1247:

Code : Tout sélectionner

1:INPUT T:P= RND T: PRINT P+1;T-P+1

Mais c'est moins joli...

Mais au final, tu as raison. Les résultats ont l'air d'être équiprobables. J'ai lancé 10000 fois la fonction avec 99 itérations -> le premier nombre autant de chances d'être un 1 ou un 2 ou ... ou un 100.

[Woodstock]

Ce n'est pas conforme à l'énoncé, ici à chaque tirage, tu as autant de chances de tirer une boule noire qu'une boule blanche et ce quelque soit la proportion de boules noires (RND 2).

Très juste, ami Bernouilli

Donc je modifie ma première phrase : "Ah, enfin un MPO que je croyais avoir compris..."

Ceci dit; on peut rattraper le coup, en influençant un peu le tirage... Donc au plus court (9 instructions, 68 octets, 5 variables) :

Code : Tout sélectionner

1: INPUT V:B=1,R=1: FOR T=1 TO V:P= INT (2*( RND B + RND R)/(B+R)), B=B+P-1,R=R-P+2: NEXT V: PRINT B;R

Par contre, mes seconde et troisième version deviennent complètement fausses, et je ne me souviens plus assez de mes cours de proba d'il y a trente ans pour tenter de reconstruire une formule tenant compte de cette particularité...

J'aurais dû m'en douter : 61 MPO qui me passaient par-dessus la tête, le soixante-deuxième ne pouvait faire exception...

[zpalm]

Voici ma version pour hp 48 :

Code : Tout sélectionner

<< { 1 1 } 1 ROT 
  START
    DUP 1 GET OVER LIST-> DROP 
    + RAND *
    FLOOR 1 + < 
    1 + DUP2 
    GET 1 + PUT
  NEXT
>>

Un peu plus court:

Code : Tout sélectionner

<< { 1 1 } 1 ROT
  START
    DUP LIST-> DROP OVER  
    + RAND * >=
    DUP NOT 2 ->LIST ADD
  NEXT
>>

[bernouilli92]

Voici ma version pour hp 48 :

Code : Tout sélectionner

<< { 1 1 } 1 ROT 
  START
    DUP 1 GET OVER LIST-> DROP 
    + RAND *
    FLOOR 1 + < 
    1 + DUP2 
    GET 1 + PUT
  NEXT
>>

Un peu plus court:

Code : Tout sélectionner

<< { 1 1 } 1 ROT
  START
    DUP LIST-> DROP OVER  
    + RAND * >=
    DUP NOT 2 ->LIST ADD
  NEXT
>>

C'est vrai que je peux virer le "FLOOR 1 +".
Par contre ta version est une version pour 48g(x), elle ne fonctionne pas sur hp48s(x) à cause de l'instruction ADD

[zpalm]

Par contre ta version est une version pour 48g(x), elle ne fonctionne pas sur hp48s(x) à cause de l'instruction ADD

C'est vrai mais ça doit marcher sur une 48s(x) avec Gx Library.

[bernouilli92]

Pas mal, je ne connaissais pas.

[C.Ret]

Ce n'est pas conforme à l'énoncé, ici à chaque tirage, tu as autant de chances de tirer une boule noire qu'une boule blanche et ce quelque soit la proportion de boules noires (RND 2).

Très juste, ami Bernouilli

Donc je modifie ma première phrase : "Ah, enfin un MPO que je croyais avoir compris..."

Pas sûr que nos amis Bernouilli92 et Woodstock soient dans le faux ou le vrai.

En effet, en cherchant à étudier cet interressant problème, je me rends compte que les choses suivent le diagramme suivant.
Les boules blanches et noires sont représentées respectivement par o et *.

Code : Tout sélectionner

   1           2                  3                     4                          5                           6 ... 
TIRAGES                                                                                                         /
                                                                                     oooooo* (120/720)
                                                                                   /                           \
                                                          ooooo* (24/120)
                                                        /                          \                           /
                                    oooo* (6/24)                                     ooooo** (24/720 + 96/720)
                                  /                     \                          /                           \
                 ooo* (2/6)                               oooo** (6/120 + 18/120)
               /                  \                     /                          \                           /
     oo* (1/2)                      ooo** (2/24 + 4/24)                              ooo**** (48/720 + 72/720)
   /           \                  /                     \                          /                           \
 o*              oo** (1/6 + 1/6)                         ooo*** (12/120 + 12/120)
   \           /                  \                     /                          \                           /
     o** (1/2)                      oo*** (4/24 + 2/24)                              oo***** (72/720 + 48/720) 
               \                  /                     \                          /                           \
                 o*** (2/6)                               oo**** (12/120 + 6/120)            
                                  \                     /                          \                           /
                                    o**** (6/24)                                     oo***** (96/720 + 48/720)
                                                        \                          /                           \
                                                          o***** (24/120)
                                                                                   \                           /
                                                                                     o****** (120/720)
                                                                                                               \
Proba     (1/2)        (1/3)              (1/4)                  (1/5)                       (1/6)               ...

Au bout de n tirages, on obtient un combinaison de (n+2) boules qui contient au minimum une boule blanche et une boule noire.


Entre parenthèses, j'ai mis la probabilité de chacune des combinaisons de boules blanches et noires.



Les combinaisons "extrêmes" qui contiennent le nombre minimal soit d'une boule blanche, soit d'une noire, ne peuvent être obtenues que par une seule voie. Pour chaque tirage, elles sont dessinées en haut et en bas de la colone que forment les combinaisons. Leur probabilité s'obtient donc par une suite de multiplications.

Par exemple, depuis la combinaison o*, il y a une chance sur deux de tirer la boule blanche pour obtenir oo*.
Si on continue, ooo* s'obtient en tirant successivement deux boules blanches, une première fois dans la combinaison initiale contenant une boule blanche et une noire puis une seconde fois depuis une combinaison de trois boules contenant deux boules blanches 1/2 * 2/3 = 2/6. C'est à dire 1/3.

Pour les combinaisons intermédiaires les choses sont différentes, mais pas particulièrement plus compliquées; il y a toujours uniquement deux façons d'obtenir une combinaison.
Par exemple, oooo** ne peut être obtenue que depuis oooo* (en tirant une boule noire) et ooo** (en tirant une boule blanche).
Dans ce cas, la probabilité d'obtention de la combinaison est à chaque fois la somme des probabilités des deux événements générateurs indépendants.
Dans notre exemple la probabilité s'obtient à partir de la fréquence de l'événement "tirer la boule noire de la combinaison oooo* sachant que celle-ci existe dans 6/24 des cas, soit ( 1/5 * 6/24 = 6/120 ) et de l'évenement "tirer l'une des trois boules blanches de la combinaison ooo** qui elle aussi existe dans 6/24 des cas, soit ( 3/5 * 6/24 = 18/120).
On obtient alors bien pour la combinaison oooo** la probablité (1/5*6/24 + 3/5*6/24 = 6/120 + 18/120 = 24/120 = 1/5)


On se rend alors compte que pour chaque tirage, les combinaisons sont équiprobables:
les deux combinaisons à trois boulles (1/2), trois combinaisons à quatre boules (1/3), à cinq boules (1/4), à six boules (1/5), etc.


D'où ma proposition de "simulation" qui suit en fait un algorithme très diffèrent des votres,
- Entrer le nombre de tirages t
- Déterminer aléatoirement le nombre de boule(s) blanche(s) b qui pour n tirages est compris dans l'intervalle [ 1 1+t ]
- Déduire à partir du nombre b de boules blanches le nombre n de boules noires qui est alors en fait 2+t-b
- Afficher la combinaison (b,n) resultant de la simulation

D'où l' code pour HP-28S/C:

Code : Tout sélectionner

« DUP                      @@  Mémorise t
  1 + RAND * CEIL          @@  Tirage aléatoire de b dans [1 1+t]
  2 OVER - ROT +           @@  Détermine n
  R->C »                   @@  Met en forme le résultat (b,n)

Et celui pour SHARP PC-1360

Code : Tout sélectionner

1 " " AREAD T : B= RND (T+1) : PRINT B,2+T-B : END

Et celui pour SHARP PC-1210 ou PC-1211

Code : Tout sélectionner

1 " " AREAD T:X=9821X-.211327,X=X-INT X,B=1+INT (X+XT:PRINT B,2+T-B:END

où X est la semence pour la génération des nombres pseudo-aléatoires.

[caloubugs]

Mais au final, tu as raison. Les résultats ont l'air d'être équiprobables. J'ai lancé 10000 fois la fonction avec 99 itérations -> le premier nombre autant de chances d'être un 1 ou un 2 ou ... ou un 100.

Je confirme, j'ai fait le test sur une HP39GII en surchargeant le programme graphique statistique à une variable...
J'obtiens ça sur 10000 séries de 1000 tirages (fait sur l'émulateur, ça va quand même plus vite !!! Environ 70 fois plus vite sur mon ordi, sinon près d'une heure 30 pour la HP39...) :

En répartissant les résultats dans des déciles (de 1 à 100, de 101 à 200, etc) histoire de voir s'il y a une tendance qui se dégage... Du coup, c'est bien équiprobable : moyenne de 504 boules blanches et un écart type de 286 (proche de l'idéal de 1/√12*1000).

avec le programme suivant (j'ai honte, il n'est pas optimisé, mais le langage s'y prête moyen).

Code : Tout sélectionner

START()
BEGIN {}►D1;{}►D2;5►H1Type; END;
VIEWS "Tirage",LISTWAIT()
BEGIN
INPUT(N);
MAKELIST(0,X,1,10,1)►D1;MAKELIST(0,X,1,4,1)►D2;
FOR K FROM 1 TO N DO
  1►A;1►B;
  FOR L FROM 1 TO 1000 DO
    IF RANDOM<A/(A+B) THEN A+1►A ELSE B+1►B END; 
    END;
  D2(1)+A►D2(1);  D2(2)+(A−1)²►D2(2);
  IF A=1 THEN 2►A END;  FLOOR((A−2)/100)+1►A;
  D1(A)+1►D1(A);
  END;
D2(1)/N►D2(3);√(D2(2)/N-D2(3)²)►D2(4);
0►Xmin;10►Xmax;0►Ymin;MAX(D1)►Ymax;
STARTVIEW(1,1);
END;

[charognard]

Code : Tout sélectionner

10 INPUT N
20 P=0.5
30 FOR I=1 TO N
40 S=1 - 2*(RND 0<P)
50 P=P+P/1/(I+2)*S
60 NEXT I
70 PRINT INT((P+1E-8)*(N+2)),N+2-INT((P+1E-8)*(N+2))

[badaze]

En fait je ne comprends pas vos solutions. Pour pouvoir simuler un sac contenant des billes il faut qu'à chaque tirage on puisse tirer une boule blanche ou noire. Donc la structure qui les contient doit les contenir de manière unitaire. Comme ce serait le cas avec un vrai sac.
Or de ce que je comprends, vous vous basez tous sur des probabilités alors que d'un tirage à l'autre il peut y avoir de sacrés écarts.

J'ai écrit le code en php car j'ai ce langage sous la main.

Code : Tout sélectionner

<?php
 function sac() {
  mt_srand(); // initialisation du générateur de nombre aléatoire
  $array = array(0,1);
  $iter  = 998;
  for ($i=1;$i<=$iter;$i++) {
	 $tirage  = mt_rand(0,count($array)-1);
	 $array[] = $array[$tirage];
	 shuffle($array); // secoue le sac
  }
  return array_count_values($array);
 }	
 
 $nb_blanches = 0;
 $nb_noires   = 0;
 for ($i=1;$i<=100;$i++) {
  $aaa = sac();
	print "Boules blanches = ".$aaa[0]." - Boules noires = ".$aaa[1];
	print "<br/>";
	$nb_blanches += $aaa[0];
	$nb_noires   += $aaa[1];
 } 
 	print "Total boules blanches = ".$nb_blanches." - Total boules noires = ".$nb_noires ;
?>

Au bout de 100 tirages de 1000 boules. J'obtiens ceci

Code : Tout sélectionner

Boules blanches = 261 - Boules noires = 739 | Boules blanches = 531 - Boules noires = 469
Boules blanches = 603 - Boules noires = 397 | Boules blanches = 606 - Boules noires = 394
Boules blanches = 665 - Boules noires = 335 | Boules blanches = 196 - Boules noires = 804
Boules blanches = 609 - Boules noires = 391 | Boules blanches = 788 - Boules noires = 212
Boules blanches = 192 - Boules noires = 808 | Boules blanches = 445 - Boules noires = 555
Boules blanches = 228 - Boules noires = 772 | Boules blanches = 244 - Boules noires = 756
Boules blanches = 266 - Boules noires = 734 | Boules blanches = 911 - Boules noires =  89
Boules blanches = 513 - Boules noires = 487 | Boules blanches = 257 - Boules noires = 743
Boules blanches = 328 - Boules noires = 672 | Boules blanches = 445 - Boules noires = 555
Boules blanches = 269 - Boules noires = 731 | Boules blanches = 182 - Boules noires = 818
Boules blanches = 716 - Boules noires = 284 | Boules blanches = 178 - Boules noires = 822
Boules blanches = 721 - Boules noires = 279 | Boules blanches = 912 - Boules noires =  88
Boules blanches = 298 - Boules noires = 702 | Boules blanches = 864 - Boules noires = 136
Boules blanches =  21 - Boules noires = 979 | Boules blanches = 232 - Boules noires = 768
Boules blanches = 313 - Boules noires = 687 | Boules blanches = 324 - Boules noires = 676
Boules blanches = 625 - Boules noires = 375 | Boules blanches = 312 - Boules noires = 688
Boules blanches = 259 - Boules noires = 741 | Boules blanches = 726 - Boules noires = 274
Boules blanches = 963 - Boules noires =  37 | Boules blanches = 542 - Boules noires = 458
Boules blanches = 648 - Boules noires = 352 | Boules blanches = 497 - Boules noires = 503
Boules blanches =  82 - Boules noires = 918 | Boules blanches =  51 - Boules noires = 949
Boules blanches =   2 - Boules noires = 998 | Boules blanches = 698 - Boules noires = 302
Boules blanches = 186 - Boules noires = 814 | Boules blanches = 403 - Boules noires = 597
Boules blanches =  29 - Boules noires = 971 | Boules blanches = 789 - Boules noires = 211
Boules blanches = 840 - Boules noires = 160 | Boules blanches = 645 - Boules noires = 355
Boules blanches = 329 - Boules noires = 671 | Boules blanches = 689 - Boules noires = 311
Boules blanches = 908 - Boules noires =  92 | Boules blanches = 647 - Boules noires = 353
Boules blanches = 365 - Boules noires = 635 | Boules blanches = 962 - Boules noires =  38
Boules blanches = 525 - Boules noires = 475 | Boules blanches = 473 - Boules noires = 527
Boules blanches =  96 - Boules noires = 904 | Boules blanches = 363 - Boules noires = 637
Boules blanches = 586 - Boules noires = 414 | Boules blanches = 507 - Boules noires = 493
Boules blanches = 639 - Boules noires = 361 | Boules blanches = 627 - Boules noires = 373
Boules blanches = 893 - Boules noires = 107 | Boules blanches = 598 - Boules noires = 402
Boules blanches = 478 - Boules noires = 522 | Boules blanches = 487 - Boules noires = 513
Boules blanches = 920 - Boules noires =  80 | Boules blanches =  34 - Boules noires = 966
Boules blanches = 855 - Boules noires = 145 | Boules blanches = 442 - Boules noires = 558
Boules blanches = 254 - Boules noires = 746 | Boules blanches = 689 - Boules noires = 311
Boules blanches =  54 - Boules noires = 946 | Boules blanches =  44 - Boules noires = 956
Boules blanches = 883 - Boules noires = 117 | Boules blanches = 975 - Boules noires =  25
Boules blanches = 808 - Boules noires = 192 | Boules blanches = 847 - Boules noires = 153
Boules blanches = 995 - Boules noires =   5 | Boules blanches =  26 - Boules noires = 974
Boules blanches = 245 - Boules noires = 755 | Boules blanches =  36 - Boules noires = 964
Boules blanches = 994 - Boules noires =   6 | Boules blanches = 304 - Boules noires = 696
Boules blanches = 337 - Boules noires = 663 | Boules blanches = 451 - Boules noires = 549
Boules blanches = 575 - Boules noires = 425 | Boules blanches = 304 - Boules noires = 696
Boules blanches = 294 - Boules noires = 706 | Boules blanches = 542 - Boules noires = 458
Boules blanches =  55 - Boules noires = 945 | Boules blanches = 477 - Boules noires = 523
Boules blanches = 720 - Boules noires = 280 | Boules blanches = 966 - Boules noires =  34
Boules blanches = 774 - Boules noires = 226 | Boules blanches = 822 - Boules noires = 178
Boules blanches = 249 - Boules noires = 751 | Boules blanches = 761 - Boules noires = 239
Boules blanches = 842 - Boules noires = 158 | Boules blanches =  82 - Boules noires = 918

=========================================================================================
Total boules blanches = 49243 - Total boules noires = 50757

Si au bout de 100 tirages la probabilité de tirer une boule pour chaque couleur tend vers 0,50. Pour un seul tirage la variabilité est énorme.