Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 06-02-2015 18:52:13

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Il faut économiser les ipoches...

C'est une bonne performance. Je n'en étais pas encore là (aux essais). Peux tu nous dire comment tu as réglé ton algo ?
Je vois que, bien entendu, tu adaptes le seuil n+1 en fonction du jeton n, ce qui est normal.

#0 Pub

 #27 - 07-02-2015 11:06:12

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Il ffaut économiser les pioches...

Voici mon raisonnement :

On note T(j,n,i,k) le nombre de jetons piochés en moyenne pour parvenir à en piocher j dans l'ordre croissant, à partir d'un sac en contenant n, sachant qu'un jeton faisant partie des i plus petits doit obligatoirement être remis dans le sac (jetons interdits pour cause de tirages antérieurs) et en suivant la tactique qui consiste à garder le premier jeton s'il fait partie des k plus petits (mais pas des jetons interdits), puis pour les jetons suivants à suivre la meilleure tactique possible.

On note T(j,n,i) le min des T(j,n,i,k)  (pour k variant entre i+1 et n-j+1)
et K(j,n,i) le k correspondant à ce minimum.

Notre but est de déterminer T(10,1000,0) ainsi que les différents K(j,990+j,i)

En raisonnant comme en #17, on établit que :

T(j,n,i,k) = 1 + (i+n-k)/n*T(j,n,i,k) + 1/n*Somme{pour ii=i+1 à k}de T(j-1,n-1,ii-1)

On en tire la relation de récurrence (sur j) suivante :

T(j,n,i,k) = 1/(k-i) * [n + Somme{pour ii=i+1 à k}de T(j-1,n-1,ii-1)]

Évidemment, T(0,n,i)=0, ce qui initialise la récurrence.

Voici un programme en Python (pas optimisé) :

Code:

nb_jetons_total = 10
nb_jetons_ordre = 4
T = [[0]*nb_jetons_total for j in range(nb_jetons_ordre+1)]
K = [[0]*nb_jetons_total for j in range(nb_jetons_ordre+1)]
for j in range(1,nb_jetons_ordre+1):    
    n = nb_jetons_total+j-nb_jetons_ordre
    for i in range(n-j+1):
        t_min = j*(2*n+1-j)/2+1        
        s = 0
        for k in range(i+1, n-j+2):
            s += T[j-1][k-1]
            t = (s+n)/(k-i)
            if t < t_min :
                t_min = t
                k_min = k
        T[j][i] = t_min
        K[j][i] = k_min+nb_jetons_ordre-j
print("Nombre de jetons piochés en moyenne :", T[nb_jetons_ordre][0])
print("Seuil n°1 :",K[nb_jetons_ordre][0])
k = K[nb_jetons_ordre][0]
for j in range(nb_jetons_ordre-1, 1, -1):
    print("Seuil n°",nb_jetons_ordre-j+1," en fonction du jeton n°",nb_jetons_ordre-j," (entre ",nb_jetons_ordre-j," et ",k,") : ",K[j][:k-nb_jetons_ordre+j+1],sep="")
    k = K[j][k+j-nb_jetons_ordre]

 #28 - 07-02-2015 18:01:02

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

lI faut économiser les pioches...

Je viens de terminer le calcul théorique pour 10 jetons. On appelle J(k-1) le nombre de jetons nécessaires pour tomber sur la plage cherchée. On appelle xk le coefficient à appliquer à l'intervalle qui reste pour jouer le coup suivant. Les k sont dans l'ordre inverse, le 1er sert pour jouer les 2 derniers jetons.

La formule que j'ai appliquée est la suivante:
Pour k+1 jetons:
J0=1
xk est défini par cette égalité: J(k-1)(xk/(1-xk)+ln(1-kk))=1
Et Jk=(1-ln(1-xk)*J(k-1))/xk

Les résultats sont les suivants
............x .........................J
0        1
1    0,682155567    3,146193221
2    0,505407033    6,361176622
3    0,401221955    10,62359697
4    0,332792704    15,92248321
5    0,284417051    22,2510657
6    0,248394849    29,60472752
7    0,220520232    37,98011023
8    0,198303222    47,37465745
9    0,18017573    57,78635642

C'est très très proche de tes résultats !

En revanche, j'aurais pensé qu'on pouvait faire mieux par l'ajustement de l'intervalle restant à chaque itération....

 #29 - 07-02-2015 18:52:18

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Il faut économiser les pioches..

Une singularité à signaler: pour obtenir 1 jeton ordonné, il ne faut piocher qu'un jeton.
Pour 2 jetons ordonnés, il en faudra 2 de plus (avec qq chose après la virgule)
Pour 3 jetons ordonnés, il en faudra 3 de plus.
Pour n jetons ordonnés, il en faudra n de plus.

En réalité, ça dépasse légèrement, mais on n'est pas loin du n(n+1)/2.
Pour 10: 55. L'écart s'accroit mais très très lentement et en diminuant en pourcentage. 

Finalement, Gwen et Fix33 n'étaient pas tombés si loin du bon résultat !

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete