Inscription / Connexion Nouveau Sujet
Niveau exercices
Partager :

algorithme d'échange

Posté par
flight
16-12-24 à 18:59

Bonsoir

Je vous propose l'exercice suivant:

Un robot nommé "RA" possède 20 jetons , un autre robot nommé "RB" possède également 20 jetons , la partie commence de la façon suivante , le robot "RA" donne un nombre aléatoire de jetons à "RB" puis "RB" donne aléatoirement aussi un certain nombre de jetons à "RA"  jusqu'à ce que le premier d'entre eux n'ait plus de jetons.

En combien d'étapes en moyenne le jeu se termine?

Posté par
jandri Correcteur
re : algorithme d'échange 16-12-24 à 19:27

Bonsoir flight,
il y a une petite imprécision. Quand un joueur possède n jetons, est-ce qu'il peut donner 0 jeton à l'autre joueur?
La probabilité qu'il lui donne k jetons est alors égale à 1/(n+1).
S'il doit donner au moins 1 jeton à l'autre joueur la probabilité qu'il lui donne k jetons est alors égal à 1/n.

Posté par
flight
re : algorithme d'échange 16-12-24 à 21:00

Bonsoir Jandri , on va dire dire la chose suivante ; si le robot A est celui qui donne  , il pense à un nombre de jetons à donner à B ,( ce choix du nombre se fait au hasard), si il le peut par rapport à ce qu'il possède il remet alors ce nombre de jetons à B , par contre si ce choix est supérieur à ce qu'il possède en réserve, il renouvelle son choix , mais il doit toujours donner au moins un jeton sauf si il n'en a plus ...même raisonnement pour le robot B

Posté par
flight
re : algorithme d'échange 16-12-24 à 21:20

pour iluster cela

RA possède 20 jetons ,   il pense à 25 , impossible ...il refait son choix , il pense à 13 , c'est possible , il donne 13 jetons à RB , puis RB fait de même

Posté par
jandri Correcteur
re : algorithme d'échange 16-12-24 à 22:14

Merci pour ces précisions.
Si le robot qui joue possède n jetons, il choisit donc au hasard un entier k entre 1 et n puis il donne k jetons à l'autre robot.
J'ai cherché à généraliser mais je n'ai pas encore trouvé de formule générale.

Posté par
candide2
re : algorithme d'échange 17-12-24 à 09:35

Bonjour,

 Cliquez pour afficher

Posté par
jandri Correcteur
re : algorithme d'échange 17-12-24 à 12:00

Bonjour,
je ne pense pas qu'il existe une formule générale pour ce problème.
Quand il y a N jetons au total (ici N=40), j'obtiens un système linéaire de N-2 équations à N-2 inconnues qu'il faut résoudre. Heureusement qu'il existe des logiciels pour cela !
Pour N=40 et 20 jetons au départ pour chaque robot mon logiciel trouve que le jeu se termine en moyenne au bout de

 Cliquez pour afficher
étapes.
Ce n'est pas exactement ce que trouve candide2.

Posté par
candide2
re : algorithme d'échange 17-12-24 à 12:35

Bonjour,

 Cliquez pour afficher

Posté par
candide2
re : algorithme d'échange 17-12-24 à 13:27

Rebonjour,

 Cliquez pour afficher

Posté par
jandri Correcteur
re : algorithme d'échange 17-12-24 à 13:38

Bonjour,
je comprends pouquoi il y a une différence entre ce que je trouve et ce que trouve candide2 , c'est encore dû à une imprécision de flight. Dans sa question de il est écrit :
"jusqu'à ce que le premier d'entre eux n'ait plus de jetons".
J'ai compris que dès qu'un robot n'a plus de jeton cela s'arrête et donc cela peut s'arrêter quand le robot RA n'a plus de jeton. Pour moi une étape est "un robot donne un nombre aléatoire de jetons à l'autre".

candide2 a compris différemment l'énoncé, pour lui une étape est : "le robot RA donne un nombre aléatoire de jetons à RB puis le robot RB donne un nombre aléatoire de jetons à RA". Cela s'arrête donc uniquement quand RB n'a plus de jeton (quand RA n'a plus de jeton RB lui en donne au moins un dans la deuxième partie de l'étape).

Posté par
flight
re : algorithme d'échange 17-12-24 à 16:38

Un grand merci pour vos participations !
il n'y en effet pas de formule mathématique permettant de connaitre le nombre moyen d'echanges avant arrêt de l'expérience , vos approximations sont bonnes je trouve 22,29 essais en moyenne :


Sub echange()
Dim da, db  As Integer
Randomize
e = 0
q = 0
Do
e = e + 1
a = 20
b = 20
k = 0
Do
 k = k + 1
recom1:
   da = Int(Rnd * a) + 1
    If da <= a Then
   b = b + da
   a = a - da
       Else
       GoTo recom1
    End If
recom2:
   db = Int(Rnd * b) + 1
    If db <= b Then
     a = a + db
     b = b - db
      Else
        GoTo recom2
    End If
 Loop Until a = 0 Or b = 0
 q = q + k
Loop Until e = 1000000
MsgBox q / e '- retourne 22,29 essais
End Sub

Posté par
dpi
re : algorithme d'échange 17-12-24 à 17:48

Bonjour,
Mon bidule , sur 30 essais avec ALEA ,je trouve des passages à 0 (soit A soit B)
de 6 à 41 et en moyenne :20.03
Ce n'est pas trop loin de vos excellents calculs.
.

Posté par
jandri Correcteur
re : algorithme d'échange 17-12-24 à 18:38

Le programme de flight est très proche de celui de candide2.
Une remarque : le test "If da <= a" ne sert à rien puisque la ligne qui précède "da = Int(Rnd * a) + 1" fait que da est compris entre 1 et a. De même pour db.

D'autre part la ligne "Loop Until a = 0 Or b = 0" peut s'écrire plus simplement "Loop Until b = 0" car il n'est pas possible qu'on arrive à "a=0" (si a=0 après recom1 alors recom2 l'augmente de db qui vaut aumoins 1).

C'est pour cela que ce programme ne répond pas à la question initiale (comme celui de candide2) : l'énoncé du problème dit "jusqu'à ce que le premier d'entre eux n'ait plus de jetons" or ce programme ne s'arrête pas quand RA n'a plus de jeton (ce qui peut se produire après recom1 mais il ne faudrait pas effectuer recom2 après !).

Posté par
candide2
re : algorithme d'échange 17-12-24 à 19:34

Bonjour,

Oui Jandri, j'ai mentionné ce problème dans mon message du 17-12-24 à 13:27

En s'arrêtant dès qu'un des joueurs à 0 jeton (le J1 ou le J2), on a un tout autre résultat. La moyenne redescend vers 11 parties en moyennes pour arrêter le jeu.

Exemple de ce programme :

import random

for k in range (1,11):
  total = 0
  b=0
  c=0
  for j in range(1,100001):
    r1 = 20
    r2 = 20
    cmpt = 0
    while (r1 > 0 and r2 > 0):
      cmpt = cmpt + 1
      d = random.randint(1,r1)
      r1 = r1 - d
      r2 = r2 + d
      if r1 == 0 :
         r1=-45  #impose arret si J1 arrive à 0
         b = b+1
      d = random.randint(1,r2)
      r1 = r1 + d
      r2 = r2 - d
      if r2 == 0 :
         c = c+1
    total = total + cmpt
  print ("moyenne de coups (double) :" ,  total/100000)
****
résultats :

moyenne de coups (double) : 11.0248
moyenne de coups (double) : 11.02615
moyenne de coups (double) : 10.98209
moyenne de coups (double) : 10.97274
moyenne de coups (double) : 10.95721
moyenne de coups (double) : 11.01274
moyenne de coups (double) : 11.0232
moyenne de coups (double) : 10.95045
moyenne de coups (double) : 10.95801
moyenne de coups (double) : 10.97231

Posté par
candide2
re : algorithme d'échange 17-12-24 à 19:35

Zut, je recommence pour avoir un programme lisible

import random

for k in range (1,11):
  total = 0
  b=0
  c=0
  for j in range(1,100001):
    r1 = 20
    r2 = 20
    cmpt = 0
    while (r1 > 0 and r2 > 0):
      cmpt = cmpt + 1
      d = random.randint(1,r1)
      r1 = r1 - d
      r2 = r2 + d
      if r1 == 0 :
         r1=-45  #impose arret si J1 arrive à 0
         b = b+1
      d = random.randint(1,r2)
      r1 = r1 + d 
      r2 = r2 - d 
      if r2 == 0 :
         c = c+1
    total = total + cmpt
  print ("moyenne de coups (double) :" ,  total/100000)


moyenne de coups (double) : 11.0248
moyenne de coups (double) : 11.02615
moyenne de coups (double) : 10.98209
moyenne de coups (double) : 10.97274
moyenne de coups (double) : 10.95721
moyenne de coups (double) : 11.01274
moyenne de coups (double) : 11.0232
moyenne de coups (double) : 10.95045
moyenne de coups (double) : 10.95801
moyenne de coups (double) : 10.97231

Posté par
jandri Correcteur
re : algorithme d'échange 17-12-24 à 20:31

Bonsoir candide2,
dans ton programme les variables b et c ne servent à rien.
Seule la variable cmpt qui compte le nombre de coups doubles sert à quelque chose.
Mais dans le cas où c'est J1 qui arrive à 0 en premier tu comptes un coup double alors qu'il faudrait compter un coup simple.
C'est pour cela qu'en doublant ton nombre de coups doubles on trouve plus que ce que je trouve.

Posté par
candide2
re : algorithme d'échange 18-12-24 à 09:59

Bonjour jandri,

"dans ton programme les variables b et c ne servent à rien. "

Elles servaient dans une partie que j'ai ici supprimée...
Elles permettent (en ajoutant les lignes que j'ai supprimées) à voir quel est le pourcentage de victoires de chacun des 2 joueurs.

Quant à savoir si il faut compter les "coups simples" ou les "coups doubles", cela dépend de l'interprétation de l'énoncé.
Mais cela explique la différence d'un facteur 2 entre nos résultats.

Posté par
candide2
re : algorithme d'échange 18-12-24 à 10:50

Programme modifié pour inclure les 2 manières de compter (coups simple ou doubles) et le pourcentage de victoires de J1 et J2

import random

for k in range (1,11):
  total = 0
  b=0
  c=0
  coupsimple = 0
  for j in range(1,100001):
    r1 = 20
    r2 = 20
    cmpt = 0
    while (r1 > 0 and r2 > 0):
      cmpt = cmpt + 1
      d = random.randint(1,r1)
      r1 = r1 - d
      r2 = r2 + d
      if r1 == 0 :
         r1=-45 
         b = b+1
      d = random.randint(1,r2)
      r1 = r1 + d 
      r2 = r2 - d 
    total = total + cmpt
    coupsimple = total * 2 - b
  print ("coups (double) :" ,  total/100000, "   coups simples :" , coupsimple/100000 , "   perdus par J1:",  b/100000, 
  "   perdus par J2 :", (100000-b)/100000)


Résultats obtenus :

coups (double) : 10.99389    coups simples : 21.46471    perdus par J1: 0.52307    perdus par J2 : 0.47693
coups (double) : 10.97639    coups simples : 21.42997    perdus par J1: 0.52281    perdus par J2 : 0.47719
coups (double) : 11.02571    coups simples : 21.52804    perdus par J1: 0.52338    perdus par J2 : 0.47662
coups (double) : 10.99666    coups simples : 21.47092    perdus par J1: 0.5224    perdus par J2 : 0.4776
coups (double) : 10.96337    coups simples : 21.40418    perdus par J1: 0.52256    perdus par J2 : 0.47744
coups (double) : 10.94883    coups simples : 21.37417    perdus par J1: 0.52349    perdus par J2 : 0.47651
coups (double) : 10.99695    coups simples : 21.47224    perdus par J1: 0.52166    perdus par J2 : 0.47834
coups (double) : 10.99099    coups simples : 21.45737    perdus par J1: 0.52461    perdus par J2 : 0.47539
coups (double) : 10.95629    coups simples : 21.38746    perdus par J1: 0.52512    perdus par J2 : 0.47488
coups (double) : 10.94923    coups simples : 21.37726    perdus par J1: 0.5212    perdus par J2 : 0.4788

Posté par
jandri Correcteur
re : algorithme d'échange 18-12-24 à 11:14

D'accord, le nombre de coups simples correspond à peu près à ce que j'ai calculé : 21,446.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !