Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 01-05-2013 19:29:54
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
[Python]A propos de Jeu d'eau de Yassine (cf énigmes)
Bonsoir,
Sujet : http://www.bibmath.net/forums/viewtopic.php?id=6040
Voilà une version "factorisée"
#!/usr/bin/python
# -*- coding: Latin-1 -*-
def transfer(T,cr):
a,b=T[0],T[1]
q,r=max(a,b)//min(a,b),(max(a,b)%min(a,b))*cr
if r==0:
if q%2==0:
T[1-cr],T[2]=T[1-cr]*2,T[2]-T[1-cr]
print T
else:
T[1-cr],T[cr]=T[1-cr]*2,T[cr]-T[1-cr]
print T
elif cr:
T[0],T[1]=T[0]*2,T[1]-T[0]
print T
return T
N=sorted([7,11,29])
print N
while not (N[0]==N[1] or N[0]==N[2] or N[1]==N[2]):
if N[1]>N[0]:
N=transfer(N,1)
elif N[0]>N[1] :
if N[0]>N[2]:
N[2],N[0]=N[2]*2,N[0]-N[2]
print N
else:
N=transfer(N,0)
nb=10*(N[0]==N[1])+20*(N[0]==N[2])+21*(N[1]==N[2])
if nb==51:nb=10
print
print"** Fin **"
N[nb%10],N[nb//10]=0,N[nb//10]*2
print N
Sortie :
[7, 11, 29]
[14, 4, 29]
[10, 8, 29]
[2, 16, 29]
[4, 16, 27]
[8, 16, 23]
[16, 16, 15]** Fin **
[0, 32, 15]
Pour optimiser dans le cas soulevé par arfr, il me faudrait rajouter une dizaine de lignes de code...
C'est fait, mais elles ne figurent pas ci-dessus : j'ai estimé que ça ne valait pas le coup !
@+
Dernière modification par yoshi (02-05-2013 12:18:39)
Hors ligne
#2 05-05-2013 18:55:25
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python]A propos de Jeu d'eau de Yassine (cf énigmes)
Bonsoir,
Hélas, totomm a montré que cet algorithme n'est pas infaillible : il boucle parfois sans fin...
Donc après explications, j'ai recodé "propre" en incluant deux cas particuliers :
* [3,11,14] ou 14 - 11 = 3 et 14 - 3 = 11
[c,b,a] avec c < b <a et a - c = b
Je ne fais qu'un test : si a-b = c alors a - c = b
* Cas du triple.
[3,11,33] ou [5,11,15]
[c,b,a] avec c < b <a et a = 3c ou a = 3b
Le sous-cas b = 3a est résolu par l'algorithme...
def vidage(L):
print L
while not (L[0]==0 or L[1]==0):
M=L
L=sorted(L)
if M!=L:
print L
fg=(L[2]==L[0]*3)+10*(L[2]==L[1]*3)
if L[2]-L[1]==L[0]:
L[0],L[2]=L[0]*2,L[2]-L[0]
print L
L[2],L[1]=L[2]*2,0
print L
elif fg > 0:
L[fg//10],L[2]=L[fg//10]*2,L[2]-L[fg//10]
print L
L[2],L[fg//10]=L[2]*2,0
print L
else:
q=L[1]//L[0]
lg=len(bin(q))-2
for i in range(lg):
L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]
print L
Sorties
>>> vidage([3, 11, 14])
[3, 11, 14]
[6, 11, 11]
[6, 0, 22]
>>> vidage([3, 17, 51])
[3, 17, 51]
[3, 34, 34]
[3, 0, 68]
>>> vidage([3, 7, 35])
[3, 7, 35]
[6, 7, 32]
[12, 1, 32]
[1, 12, 32]
[2, 12, 31]
[4, 12, 29]
[8, 8, 29]
[16, 0, 29]
Explications (pour qui ne saurait pas)
>>> bin(5)
'0b101'
>>> type(bin(5))
<type 'str'>
Confirmation : python convertit un nombre en binaire et restitue une chaîne...
>>> bin(9)
'0b1001'
>>> bin(9)[2:]
'1001'
q=L[1]//L[0]
Alors, j'obtiens le nombre de bits significatifs de q avec longueur de chaîne -2 : lg=len(bin(q))-2
Puis je boucle sur cette longueur...
(q>>i) & 1 :
j'obtiens le ieme bit par décalage vers la droite de i (>>) avec un & 1 logique...
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
* Si le résultat de ce calcul vaut 1 (valeur du ieme bit), alors L[2-((q>>i) & 1)] donne L[1] et c'est R2 que je vide
* Si le résultat de ce calcul vaut 0 (valeur du ieme bit), alors L[2-((q>>i) & 1)] donne L[2] et c'est R3 que je vide
@+
Hors ligne
#3 06-05-2013 20:41:46
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python]A propos de Jeu d'eau de Yassine (cf énigmes)
Bonsoir,
J'ai gagné 2 lignes...
def vidage(L):
print L
while not (L[0]==0 or L[1]==0):
if L!=sorted(L):
L.sort()
print L
fg=(L[2]==L[0]*3)+10*(L[2]==L[1]*3)
if L[2]-L[1]==L[0]:
for i in range(2):
L[2*i],L[2-i]=L[2*i]*2,L[2-i]-L[i]
print L
elif fg > 0:
L[fg//10],L[2]=L[fg//10]*2,L[2]-L[fg//10]
print L
L[2],L[fg//10]=L[2]*2,0
print L
else:
q=L[1]//L[0]
lg=len(bin(q))-2
for i in range(lg):
L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]
print L
Je ne désespère pas d'en gagner encore au moins une...
@+
Hors ligne
#4 07-05-2013 19:48:14
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python]A propos de Jeu d'eau de Yassine (cf énigmes)
bonsoir,
J'ai gagné ma ligne...
Tout ça pour ça ?
Ce n'est pas tant le fait de gagner une ligne que de ne plus écrire 2 fois de suite print L : l'intérêt est là
def vidage(L):
print L
while not (L[0]==0 or L[1]==0):
if L!=sorted(L):
L.sort()
print L
fg=(L[2]==L[0]*3)+10*(L[2]==L[1]*3)
if L[2]-L[1]==L[0]:
for i in range(2):
L[2*i],L[2-i]=L[2*i]*2,L[2-i]-L[i]
print L
elif fg > 0:
for i in range(2):
L[(fg//10)*(1-i)+2*i],L[(fg//10)*i+2*(1-i)]=L[(fg//10)*(1-i)+2*i]*2,(L[2]-L[fg//10])*(1-i)
print L
else:
q=L[1]//L[0]
lg=len(bin(q))-2
for i in range(lg):
L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]
print L
C'est plus rationnel comme ça.
@+
Hors ligne
#5 08-05-2013 08:30:45
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python]A propos de Jeu d'eau de Yassine (cf énigmes)
Bonjour,
La nuit portant conseil, j'ai modifié la ligne 7, pour obtenir respectivement 2 et 1 au lieu de 1 et 10...
Ce qui m'a permis de simplifier considérablement les calculs de la ligne 14.
def vidage(L):
print L
while not (L[0]==0 or L[1]==0):
if L!=sorted(L):
L.sort()
print L
f=2*(L[2]==L[0]*3)+(L[2]==L[1]*3)
if L[2]-L[1]==L[0]:
for i in range(2):
L[2*i],L[2-i]=L[2*i]*2,L[2-i]-L[i]
print L
elif f > 0:
for i in range(2):
L[f%2+f*i],L[2-f*i]=L[f%2+f*i]*2,L[2]-L[f%2+f*i]
print L
else:
q=L[1]//L[0]
lg=len(bin(q))-2
for i in range(lg):
L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]
print L
Et là, je ne pense pas qu'il n'y aura pas d'autres "mises à jour"...
@+
Hors ligne