L’algorithme teste les différents choix possibles (remplir A, vider B, verser A dans B etc.). Tant qu’il obtient de nouvelles combinaisons, par exemples [0,0],[2,5],[3,0]… il continue. Quand il trouve une combinaison déjà existante, il remonte d’un niveau (indiqué par “Annuler”) et teste un autre choix.
arbre = [[0,0]] pos = [0] rang = 0 choix = ['viderA', 'viderB', 'AversB', 'BversA', 'remplirA', 'remplirB'] # Capacites recipients et volume voulu A, B, V = 3, 5, 4 def tester(txt): print(txt,etat) def viderA(): etat[0] = 0 def remplirA(): etat[0] = A def viderB(): etat[1] = 0 def remplirB(): etat[1] = B def AversB(): # Possible si qq chose dans A et de la place dans B if etat[0] > 0 and etat[1] < B: qte = min(etat[0], B - etat[1]) etat[1] += qte etat[0] -= qte def BversA(): if etat[1] > 0 and etat[1] < A: qte = min(etat[1], A - etat[0]) etat[0] += qte etat[1] -= qte while True: etat = list(arbre[rang]) # A ou B arrive au volume voulu ? if etat[0] == V or etat[1] == V: break test = pos[rang] # plus de choix possible if test == 6: # mission impossible ? if len(pos) == 1: print("??") break # on enleve la derniere branche pos.pop() arbre.pop() rang -= 1 # Choix suivant pr branche inferieure pos[rang] += 1 print("Annuler") else: # Choix numero 'test' decision = choix[test] eval(decision+'()') # nouvel etat ? if etat not in arbre: # nouvelle branche # avec test = 0 arbre.append(etat) pos.append(0) # Affichage de la decision tester(decision) rang += 1 else: # on passe au choix suivant pos[rang] += 1