Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 12-01-2011 12:21:17
- gprbx
- Membre
- Inscription : 17-12-2010
- Messages : 134
[Python] 4 verres vides et 4 verres pleins
Bonjour,
Pour répondre à l'invitation de yoshi, voici mon code en Python, libre de tous droits
Il imprime la solution en une seconde à peine....
La fonction Deplacer est un exemple de fonction récursive. J'espère que ce code est suffisamment documenté
Parmi les avantages de Python (que j'ai découvert récemment) il y a la concision dans la disposition du code !
mais je peux aussi le donner en VBasic
#**************************************************************
# gprbx 11/01/2011 Ce code est libre pour toute diffusion
# Placer 8 verres 00001111. Les alterner 10101010
# en déplaçant 2 verres adjacents. en 4 mouvements au maximum.
#***************************************************************
verres = [5,5,1,2,3,4,6,7,8,9] # les espaces sont des 5
#Les 4 verres vides sont 1234 et les 4 verres pleins 6789
espaces =[0,0,0,0,0]
#repère la position du premier des 2 espaces
#pour la position de départ et chacun des 4 mouvements
def Echanger(i,j):
verres[i], verres[j] = verres[j], verres[i]
verres[i+1], verres[j+1] = verres[j+1], verres[i+1]
def Verifier():
# trouver le premier verre (différent de 5)
nb = 0 #Compte le nombre de verres successifs
alterne = 1 #pour différencier les verres pleins des verres vides
for n in range(0,len(verres)-2):
if nb == 0:
if verres[n] != 5:
nb += 1
if verres[n] < 5:
alterne = -1
else:
if verres[n] != 5:
nb += 1
alterne = -alterne
if (alterne>0 and verres[n]<5) or (alterne<0 and verres[n]>5):
return 0
if nb == 8:
return 1
else:
return 0
def Imprimer():
print "le premier des 2 espaces adjacents a pour positions successives :"
print espaces[0], espaces[1], espaces[2], espaces[3], espaces[4],
print "(index au départ, puis après chaque mouvement)."
for n in range(4,0,-1):
Echanger(espaces[n],espaces[n-1])
for n in range(0,5):
ch=" "
for i in range(0,len(verres)):
if verres[i] == 5:
ch += '_'
elif verres[i] > 5:
ch += '1'
else:
ch += '0'
print "Mouvement N° %s :%s" %(n,ch)
if n <4:
Echanger(espaces[n],espaces[n+1])
def Deplacer(nmouv): #appelée avec nMouv de 0 à 3
espace = espaces[nmouv]
for i in range(0, 9):
if (i <= espace - 2) or (i >= espace + 2):
Echanger(i,espace) #avant de passer au mouvement suivant
espaces[nmouv + 1] = i
if nmouv < 3:
Deplacer(nmouv + 1) #appel récursif
else:
if Verifier() == 1:
Imprimer()
Echanger(i,espace) #défaire avant que i ne progresse
Deplacer(0) # Pour commencer
print "Fin de recherche"
A+ cordialement : gprbx
Hors ligne
#2 12-01-2011 12:26:22
- gprbx
- Membre
- Inscription : 17-12-2010
- Messages : 134
Re : [Python] 4 verres vides et 4 verres pleins
re,
je n'ai pas posté dans le bon forum, car j'étais revenu du "café mathématiques" à ce forum et je n'ai pas prêté attention au titre du forum
Un modérateur pourra peut-être transférer ? A+ cordialement : gprbx
Hors ligne
#4 12-01-2011 14:18:07
- gprbx
- Membre
- Inscription : 17-12-2010
- Messages : 134
Re : [Python] 4 verres vides et 4 verres pleins
Re,
Sur la récursivité :
Quand les appels récursifs portent sur des fonctions assez courtes, certains compilateurs les transforment en itérations pour gagner en vitesse et ménager la pile...C'est plus la rapidité d'exécution qui est visée car les ordinateurs ont maintenant tellement de mémoire vive disponible...
Les appels récursifs sont surtout intéressants quand on raisonne pour écrire le programme correctement.
A+ cordialement : gprbx
Dernière modification par gprbx (13-01-2011 10:54:30)
Hors ligne