Discussion :

[Zavonen]

La cause est entendue.
Sous réserve qu'on s'interdise de verser dans un récipient une quantité ARBITRAIRE.
J'ai déjà vu des pbs du genre ou l'arbitraire s'élimine à la fin, s'isole dans un récipient, alors que l'autre contient la quantité voulue.
Mais je n'y crois pas trop ici.
Bravo pour tes prouesses en ASCII-ART.
On propose la discipline pour les prochains J.O.?

[Trap D]

Pour ceux que ça intéresse, voici un programme SWI-Prolog qui donne la solution la plus courte.

Le programme est en deux parties,
La première partie est un module de parcours de graphe en largeur, on peut en lire le détail ici : paragraphe II-C. 'probleme.pl' : le module de parcours d'un arbre en largeur.
La seconde partie est spécifique au problème, voici le code prolog :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
:- module('zavonen.pl',[etat_initial/1,etat_final/1,etats_suivants/2]).
% les mesures sont vides
etat_initial([mesure(50,0), mesure(30,0)]).
% la mesure de 50 contient 40
etat_final([mesure(50,40), mesure(30,_)]).
 
 
etats_suivants([mesure(50, X), mesure(30,Y)], L):-
	% on vide la mesure de 50, puis la mesure de 30
	L1 = [[mesure(50,0), mesure(30, Y)], [mesure(50,X), mesure(30, 0)]],
	%  on remplit la mesure de 50, puis la mesure de 30
	L2 = [[mesure(50,50), mesure(30, Y)], [mesure(50,X), mesure(30, 30)]],
	% on tranvase le contenu de X dans Y
	(   verse1([mesure(50, X), mesure(30,Y)], L3); L3 = []),
	(   verse2([mesure(50, X), mesure(30,Y)], L4); L4 = []),
	append(L1, L2, L5),
	append(L3,L4,L6),
	append(L5,L6,L).
 
 
verse1([mesure(50,X), mesure(30,Y)], [[mesure(50,X1), mesure(30,Y1)]]) :-
	Y < 30, X > 0,
	Y2 is 30 - Y,
	Delta is min(X, Y2),
	X1 is X - Delta,
	Y1 is Y + Delta.
 
verse2([mesure(50,X), mesure(30,Y)], [[mesure(50,X1), mesure(30,Y1)]]) :-
	X < 50, Y > 0,
	X2 is 50 - X,
	Delta is min(X2, Y),
	X1 is X + Delta,
	Y1 is Y - Delta.

Au fait, le résultat :

[mesure(50, 0), mesure(30, 0)]
[mesure(50, 50), mesure(30, 0)]
[mesure(50, 20), mesure(30, 30)]
[mesure(50, 20), mesure(30, 0)]
[mesure(50, 0), mesure(30, 20)]
[mesure(50, 50), mesure(30, 20)]
[mesure(50, 40), mesure(30, 30)]

@Zavonen : solution instantanée

[Zavonen]

Mais à l'étape 4, on vide la mesure 30 ce qui est interdit!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
[mesure(50, 20), mesure(30, 30)]
[mesure(50, 20), mesure(30, 0)]

Pour la solution ci-dessus, pas besoin de déranger Prolog. Je crois que tout le monde l'avait.

[Trap D]

Pour la solution ci-dessus, pas besoin de déranger Prolog. Je crois que tout le monde l'avait.

Tout à fait, c'est toi qui à parlé de Prolog et du fait que ça bouclait.
Comme le dit pseudocode, je ne vois pas trop comment on peut faire sans vider une mesure.

[Zavonen]

Tout à fait, c'est toi qui à parlé de Prolog et du fait que ça bouclait.
Comme le dit pseudocode, je ne vois pas trop comment on peut faire sans vider une mesure.

Oui, ce qui m'intéresse, c'est du Prolog qui ne boucle pas dans le cas du non vidage. C'est à dire en gros le mien, relooké de séquences cut- fail aux bons endroits.
Je ne suis pas assez motivé pour m'y remettre (à Prolog), surtout sur ce cas, somme toute pas très intéressant, mais quelqu'un qui pratique régulièrement (toi peut être?) pourrait arranger cela illico.
Je voudrais cependant réaffirmer que nous n'avons rien démontré.
Ni Pseudocode avec son arbre, ni moi avec mon 'mauvais' prolog, parce que nous refusons des mouvements possibles, par exemple remplir partiellement un récipient.
Exemple: Si on trouvait un truc pour remplir un récipient exactement à moitié.
Il suffirait de le faire pour chacun des deux et de réunir.

[pseudocode]

Je voudrais cependant réaffirmer que nous n'avons rien démontré.
Ni Pseudocode avec son arbre, ni moi avec mon 'mauvais' prolog, parce que nous refusons des mouvements possibles, par exemple remplir partiellement un récipient.

??

Bah si. On a prouvé qu'avec les axiomes et prédicats dont on dispose, le theoreme n'est pas demontrable. On l'a prouvé par une exploration exhaustive: moi en forward-chaining, toi en backward-chaining.

[Zavonen]

Bah si. On a prouvé qu'avec les axiomes et prédicats dont on dispose, le theoreme n'est pas demontrable.

Ensemble volontairement et artificiellement restreint par toi et par moi.
Les données du pb n'interdisent pas qu'on remplisse partiellement un réservoir, et cela PERSONNE ne l'envisage.
Je répète si qq'un trouve un truc pour remplir à moitié c'est résolu en 3 étapes.
Qu'est ce qui te permet de décider a priori qu'il est impossible de remplir un récipient à moitié quand on dispose de deux récipients de tailles connues?
Qu'est ce qui te permet de décider que quand il y a 1 litre dans le petit et 5 litres dans le grand il n'est pas possible de reverser dans le petit exactement la même quantité que celle qui y est déjà présente ?

[pseudocode]

Qu'est ce qui te permet de décider a priori qu'il est impossible de remplir un récipient à moitié quand on dispose de deux récipients de tailles connues?
Qu'est ce qui te permet de décider que quand il y a 1 litre dans le petit et 5 litres dans le grand il n'est pas possible de reverser dans le petit exactement la même quantité que celle qui y est déjà présente ?

... ou de présupposer que la bouteille d'huile ne contient que 40cl.

Mouais... vu la maniere dont etait posé le probleme, les hypotheses usuelles ont ete sous-entendue... D'ou notre surprise quand on nous dit qu'on ne peut pas vider un des flacons !

[Zavonen]

La solution suppose que les réservoirs ont des formes géométriques simples
(cylindres droits, par exemple, au sens math le plus général).
Remplir le réservoir de 3 litres et le vider dans celui de 5
Remplir à nouveau le petit réservoir et finir de remplir le grand avec.
On a donc 1 litre d'un côté et 5 de l'autre
Reportons une fois la hauteur du liquide dans le petit réservoir (pas besoin de la connaitre). Remplir le petit réservoir jusqu'au trait. Il contient alors deux litres.
Finir de le remplir avec le grand, il reste exactement 4 litres dans le grand.
Et il n'y a pas une goutte d'eau par terre.

[Trap D]

Il n'est dit nulle part que les bidons sont transparents, ni qu' il y ait besoin d'un stylo pour marquer les bidons.

[Nemerle]

sacré tripatouillage de nouilles ici! On peut continuer à étendre le spectre du problème, style "j'ai un partitionneur quantique à boucles afin de pouvoir répartir les molécules d'huiles précisément"... Cela a plus de classe que le stylo marqueur (d'ailleurs, quel est l'épaisseur de la pointe du stylo, mmhhh? )

Ceci dit, la réponse de l'initiateur

C'est ça le problème je ne peut rien vider .

ne me semble pas très crédible: le problème vient d'un exo d'algo, la solution de TrapD me semble exactement ce qu'attend le prof.