Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 15-04-2013 12:37:44
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Jeu d'eau
Bonjour,
J'espère que le petit exercice suivant n'a pas déjà été posé dans ce forum; Mes excuses à l'avance si c'est le cas.
Vous avez 3 récipents, chacun contenant un nombre entier de litres d'eau. Vous pouvez baisser le contenu d'un récipient en doublant le contenu d'un autre moins rempli (passer de [tex]N_1 \leq N_2[/tex] à [tex]2 \times N_1[/tex] et [tex] N_2 - N_1[/tex]. On suppose que chaque récipent est assez grand pour contenir toute l'eau mise en jeu.
Trouver un algorithme pour vider l'un des récipients au bout d'un nombre fini d'opérations.
Dernière modification par Yassine (15-04-2013 14:57:48)
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#3 16-04-2013 08:01:03
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
Re,
Pffffou...
Pas de la petite bière !
J'ai commencé quelques tests avec 7, 5 et 3 qui m'ont montré que j'allais devoir réfléchir pour dégager une loi...Joli pb...
@+
Je l'avais pas mal apprécié aussi.
Ce qui est intéressant, c'est que pour un exemple numérique donné, on est tous capables en peu de tentatives de vider un récipent (pour des exemples "raisonnables"), il est néanmoins difficile (du moins pour moi à l'époque) de formaliser ces tentatives.
A+
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#7 21-04-2013 20:25:27
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
Petite indication pour ceux qui veulent :
[EDIT] : Petite correction (pas très importante) de mon indication
Dernière modification par Yassine (22-04-2013 08:02:33)
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#8 24-04-2013 21:47:53
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
Une solution (il peut y en avoir d'autres)
Je trouve celle-ci très belle, mais à vous de juger :
[EDIT] Modif pour plus de rigueur.
Dernière modification par Yassine (25-04-2013 09:38:31)
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#9 28-04-2013 10:59:27
- arfr
- Invité
Re : Jeu d'eau
Bonjour,
@Yassine : oui, solution belle, et brillante : Bravo
il ne faut pas se laisser piéger par la facilité ! Exemple :
3 11 14 on trouve facilement 6 11 11 d'où 6 0 22 !
Mais l'algorithme de Yassine veut :
6 8 14
12 2 14 on pourrait être tenté par 12 4 12 mais l'algorithme Yassine fait :
2 12 14 puis
4 12 12 on peut regarder 12 et 12 mais l'algorithme Yassine continue :
8 8 12 soit enfin
16 0 12 à coup sûr !!!
#10 28-04-2013 14:02:01
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
@arfr : Je vais chipoter, mais j'avais indiqué en début de ma solution que je m'arrêtais dès lors que deux des récipients contenaient la même quantité. Je me serai donc arrêté à 4 12 12. Néanmoins, comme tu l'indiques, l'algorithme brut (sans la vérification que je mentionne) aurais suivi le parcours que tu indiques et n'est donc clairement pas optimal. Un challenge serait d'identifier tous les cas où mon algorithme est sous optimal (tu donnes l'exemple [tex]n_1+n_2=n_3[/tex] qui se résout plus "optimalement" en R3 vers R1, puis R3 vers R2).
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#11 29-04-2013 12:29:58
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Jeu d'eau
Bonjour,
@Yassine : oui, solution belle, et brillante : Bravo
il ne faut pas se laisser piéger par la facilité ! Exemple :
3 11 14 on trouve facilement 6 11 11 d'où 6 0 22 !
Mais l'algorithme de Yassine veut :
6 8 14
12 2 14 on pourrait être tenté par 12 4 12 mais l'algorithme Yassine fait :2 12 14 puis
4 12 12 on peut regarder 12 et 12 mais l'algorithme Yassine continue :
8 8 12 soit enfin
16 0 12 à coup sûr !!!
Salut,
on a une maxime pour décrire la cécité de l'intelligence artificielle : "science sans conscience ...." Je laisse yoshi sama compléter !
De la considération des obstacles vient l’échec, des moyens, la réussite.
Hors ligne
#12 29-04-2013 13:26:42
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Jeu d'eau
Bonjour,
@Yassine : oui, solution belle, et brillante : Bravo
Pour éviter tout commentaire hors de propos, voici un exemple modifié
qui met en œuvre l'algorithme Yassine sans laisser aucune possibilité d'en abréger le déroulement :
3 11 99999
6 8 99999
12 2 99999
2 12 99999 (q=6 en base 10 soit 110 en base 2, donc appel à R3 pour le 0 de 110)
4 12 99997
8 8 99997
16 0 99997 à coup sûr !!!
Hors ligne
#13 30-04-2013 18:59:05
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 946
Re : Jeu d'eau
Bonjour,
Mais l'algorithme de Yassine veut :
6 8 14
12 2 14 on pourrait être tenté par 12 4 12 mais l'algorithme Yassine fait :2 12 14 puis
4 12 12 on peut regarder 12 et 12 mais l'algorithme Yassine continue :
8 8 12 soit enfin
16 0 12 à coup sûr !!!
Non, l'algo de Yassine ne fait pas ça...
Je viens de "pythonner" la méthode brute, voilà le résultat :
[3, 11, 14]
[6, 8, 14]
[12, 2, 14]
[12, 4, 12]
[0, 4, 24]
Exemple de totomm :
[3, 11, 9999]
[6, 8, 9999]
[12, 2, 9999]
[12, 4, 9997]
[8, 8, 9997]
[0, 16, 9997]
Autres tests :
[4, 5, 6]
[8, 1, 6]
[2, 1, 12]
[2, 2, 11]
[0, 4, 11][4, 5, 7]
[8, 1, 7]
[1, 1, 14]
[0, 2, 14]
Maintenant, je vais travailler à optimiser le code (remarque de arfr) et le rendre plus "présentable"...
@+
Arx Tarpeia Capitoli proxima...
En ligne
#14 30-04-2013 19:25:54
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
@yoshi : normalement, la méthode brute devrait faire 2,12,14 -> 4,12,12 -> 8,8,12 -> 16,0,12 ([tex]12=\bar{110}_22[/tex]), comme indiqué par arfr ?
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#15 30-04-2013 20:05:50
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 946
Re : Jeu d'eau
Re,
Alors, c'est ce que j'ai dû l'améliorer (?) légèrement sans le vouloir..
Il faut dire que tes notations sur le sujet m'ont paru absconses (apparemment, je suis le seul... problème de compréhension ?), alors je me suis inspiré de ta méthode à partir de plusieurs résolutions à la main...
Ton histoire de bit de poids faible à 0 dans l'écriture binaire du quotient (traduction informatique du phénomène) et de son traitement, notamment, je n'étais pas très sûr de m'y retrouver dans ton écriture LaTeX
N2 est un multiple de N1 ssi le reste de leur division euclidienne est nul.
Et dans ce cas je teste si le quotient est pair ou impair : ça doit revenir au même...
2 --> [tex]\overline{10}^2[/tex], 4 --> [tex]\overline{100}^2[/tex], 6 --> [tex]\overline{110}^2[/tex]... et quotients pairs
Et
3 --> [tex]\overline{11}^2[/tex], 5 --> [tex]\overline{101}^2[/tex], 7 --> [tex]\overline{111}^2[/tex]... et quotients impairs
J'ai donc shunté ton écriture binaire et testé la parité du quotient avec un simple modulo 2...
Autre modif peut-être, si N1 devient plus grand que N3, je double N3 à partir de N1.
En tout état de cause, mon prog a l'air de fonctionner : il a même résolu certaines configurations en moins de manipes que moi à la main...
Cela dit je ne me hasarderais pas à affirmer qu'il est sans faille : pour l'instant, je ne l'ai pas planté...
Autres exemples:
[6, 9, 16] [8, 9, 21] [8, 19, 21] [17, 22, 43]
[12, 3, 16] [16, 1, 21] [16, 11, 21] [34, 5, 43]
[12, 6, 13] [16, 2, 20] [5, 22, 21] [34, 10, 38]
[12, 12, 7] [16, 4, 18] [10, 17, 21] [24, 20, 38]
[0, 24, 7] [16, 8, 14] [20, 7, 21] [4, 40, 38]
[2, 8, 28] [20, 14, 14] [8, 40, 34]
[4, 8, 26] [20, 0, 28] [16, 32, 34]
[8, 8, 22] [32, 32, 18]
[0, 16, 22] [0, 64, 18]
16 lignes pour [17,21,49]...
Remarques ?
@+
Arx Tarpeia Capitoli proxima...
En ligne
#16 01-05-2013 09:26:25
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
@yoshi: Re,
Moi non plus je ne comprends pas l'histoire du bit de poids faible. Normalement, je regarde TOUS les bits de l'écriture binaire du quotient en démarrant du bit de poids faible (avec ma notation [tex]\delta_0[/tex]). Si le bit de rang i que je suis en train de regarder est nul, j'utilise R3, sinon, j'utilise R2. Avec un programme C++, il faudrait une boucle de type
do {
if ( (q & 1) == 0) { // test du bit de poids faible
r3 -= r1;
} else {
r2 -= r1;
}
r1 *= 2;
q = (q >> 1); // décalage binaire à droite de q
} while ( q > 0);
Quant à ton algorithme, je ne suis pas sûr d'avoir tout suivi, met éventuellement le code Python en ligne, ça nous permettra de comprendre. J'ai l'impression que ça ne respecte pas l'idée de base de mon algo, à savoir arriver à rendre encore plus petit le min des trois récipient (méthode de descente infinie du grand Fermat).
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#17 01-05-2013 10:34:59
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 946
Re : Jeu d'eau
Re,
A dire vrai, je n'avais pas très bien compris ta formule LateX avec des sommes, des indices "étranges", le paragraphe commençant par :
Donc, on écrit q en base 2 ....
Décalage à droite... Joli, mais je ne vois pas comment tu t'en sers ni à quoi cela sert.
Désolé...
Voilà le 1er jet qui fonctionne.
Je travaille à créer une fonction qui permettrait de supprimer la quasi-répétition de bloc if r==0...
N=[17,21,49]
print N
while not (N[0]==N[1] or N[0]==N[2] or N[1]==N[2]):
if N[1]>N[0]:
q,r=N[1]//N[0],N[1]%N[0]
if r==0:
if q%2==0:
N[0],N[2]=N[0]*2,N[2]-N[0]
print N
else:
N[0],N[1]=N[0]*2,N[1]-N[0]
print N
else:
N[0],N[1]=N[0]*2,N[1]-N[0]
print N
elif N[1]==N[0]:
pass
else:
if N[0]>N[2]:
N[2],N[0]=N[2]*2,N[0]-N[2]
print N
else:
q,r=N[0]//N[1],N[01]%N[1]
if r==0:
if q%2==0:
N[1],N[2]=N[1]*2,N[2]-N[1]
print N
else:
N[0],N[1]=N[0]-N[1],N[1]*2
print N
# Identification des 2 conteneurs à contenance égale
nb=10*(N[0]==N[1])+20*(N[0]==N[2])+21*(N[1]==N[2])
# Vidage du n° le plus petit et doublage de l'autre
N[nb%10],N[nb//10]=0,N[nb//10]*2
print N
Pour l'adapter en 3.x, écrire print(N) puisque print dans ces versions est devenue une fonction...
méthode de descente infinie du grand Fermat
Wouah... Il en sait des choses...
Il était si grand que ça, Fermat ? ;-)
Moi, je connaissais la grande descente avec "Yves Montand", chacun sa culture ("la caque sent toujours le hareng", dit l'aphorisme populaire)... ^_^
En tous cas, ce que j'ai fait fonctionne sauf si tu me trouves un bug que je me ferai un plaisir de corriger...
Je gagne même parfois des étapes par rapport à ta méthode pure et dure.
Je reposterai un script plus propre quand j'aurai trouvé ce que je cherche...
@+
Dernière modification par yoshi (01-05-2013 10:53:01)
Arx Tarpeia Capitoli proxima...
En ligne
#18 01-05-2013 11:02:04
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
@yoshi
Tu ne veux pas rajouter un tri de ton tableau au départ pour éviter les nombreux 'if' qui rendent la lecture assez difficile.
Tu as par exemple un boucle où ne rentre que si tous les entiers sont différents, puis tu as un elif qui porte sur l'égalité de deux entiers, alors que rien ne s'est passé entre le test de la boucle et ce test !
Il était si grand que ça, Fermat ? ;-)
Si les marges des livres avaient été plus grandes, il aurait été encore plus grand ;-)
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#19 01-05-2013 11:14:14
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Jeu d'eau
@yoshi:
Un exemple qui à mon avis fait planter ton prog :
[2,4,1] : tu te retrouves avec N[2] négatif.
Dernière modification par Yassine (01-05-2013 11:14:36)
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#20 01-05-2013 11:34:10
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Jeu d'eau
Bonjour,
Je n'ai pas réussi à faire marcher le code de yoshi. le programme boucle indéfiniment...
Mais j'avais habillé l'algorithme Yassine et fait divers essais :
def vider(n):
while True:
n.sort(),print(n," après tri")
if n[0]<=0:
print("**************")
break
if n[0]==n[1]:n[0],n[1]=n[0]+n[0],0
elif n[1]==n[2]:n[1],n[2]=n[1]+n[1],0
else:
q,r=n[1]//n[0],n[1]%n[0]
while q>0:
if (q&1):n[1]-=n[0]
else:n[2]-=n[0]
n[0]+=n[0]
print(n," q =",q," r =",r)
q=q//2
if r==0:
print("**************")
break
#vider([3,2,1])
#vider([6,35,1000])
#vider([6,9,16])
#vider([8,9,21])
#vider([8,19,21])
vider([17,21,49])
Hors ligne
#21 01-05-2013 13:16:26
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 946
Re : Jeu d'eau
Re,
@ Yassine
Tu ne veux pas rajouter un tri de ton tableau au départ pour éviter les nombreux 'if' qui rendent la lecture assez difficile.
Tu as par exemple un boucle où ne rentre que si tous les entiers sont différents, puis tu as un elif qui porte sur l'égalité de deux entiers, alors que rien ne s'est passé entre le test de la boucle et ce test !
"rien ne s'est passé entre le test de la boucle et ce test" : oui, à l'entrée. Mais non, dès le 2e tour
J'ai dit que c'était un premier jet et que je travaillais à faire propre...
D'autre part, j'ai rajouté le tri demandé au départ, même si, Yassine, tu avais écrit post #7:
Montrer qu'on peut toujours partir d'une configuration [tex]0<n_1≤n_2≤n_3[/tex] : j'avais pris l'ordre croissant comme situation de départ.
Mais ce tri ne retire aucun if, tu n'as pas compris le code...
Par contre, j'ai dû rajouter une ligne à la fin : là, il y avait un bug si les 3 conteneurs étaient de quantités contenues égales...
Pour répondre à tes objections :
[1, 2, 4] [1, 2, 3]
[2, 2, 3] [2, 2, 2]
** Fin ** ** Fin **
[0, 4, 3] [0, 4, 2]
Désolé encore, d'étaler ma compréhension limitée : j'ai procédé ainsi, parce que moi, je n'ai rien compris aux explications de yassine.
Je sais, d'autres, si !
Je vous l'avais dit : mes facultés intellectuelles étant limitées, ne m'en demandez pas trop...
@totomm
Si mon prog boucle indéfiniment, merci de me donner la situation de départ...
Vos tests faits chez moi :
[17, 21, 49] [6, 35, 1000] [8, 9, 21] [8, 19, 21] [6, 9, 16]
[34, 4, 49] [12, 29, 1000] [16, 1, 21] [16, 11, 21] [12, 3, 16]
[34, 8, 45] [24, 17, 1000] [16, 2, 20] [5, 22, 21] [12, 6, 13]
[34, 16, 37] [7, 34, 1000] [16, 4, 18] [10, 17, 21] [12, 12, 7]
[34, 32, 21] [14, 27, 1000] [16, 8, 14] [20, 7, 21]
[13, 32, 42] [28, 13, 1000] [2, 8, 28] [20, 14, 14] **Fin **
[26, 19, 42] [28, 26, 987] [4, 8, 26] [0, 24, 7]
[7, 38, 42] [2, 52, 987] [8, 8, 22] **Fin **
[14, 31, 42] [4, 52, 985] [20, 0, 28]
[28, 17, 42] [8, 48, 985] **Fin **
[11, 34, 42] [16, 48, 977] [0, 16, 22]
[22, 23, 42] [32, 32, 977]
[44, 1, 42]
[2, 1, 84] **Fin **
[2, 2, 83] [0, 64, 977]
** Fin **
[0, 4, 83]
S'il s'agit du prog lui-même, je ne vois pas pourquoi, il planterait en 3.2...
La seule différence est l'instruction print devenue fonction print().
Après CTRL + C, quel est le message ?
Votre prog fonctionne chez moi à deux conditions :
1. J'enlève les parenthèses à print
2. Je retouche la ligne n.sort(),print(n," après tri") en supprimant la virgule et en renvoyant le print à la ligne
Pour [17,21,49] vous affichez 19 états de liste, moi 15...
Listing tenant compte du souhait de tri initial et du correctif du bug :
N=sorted([3,2,1])
print N
while not (N[0]==N[1] or N[0]==N[2] or N[1]==N[2]):
if N[1]>N[0]:
q,r=N[1]//N[0],N[1]%N[0]
if r==0:
if q%2==0:
N[0],N[2]=N[0]*2,N[2]-N[0]
print N
else:
N[0],N[1]=N[0]*2,N[1]-N[0]
print N
else:
N[0],N[1]=N[0]*2,N[1]-N[0]
print N
elif N[1]==N[0]:
pass
else:
if N[0]>N[2]:
N[2],N[0]=N[2]*2,N[0]-N[2]
print N
else:
q,r=N[0]//N[1],N[01]%N[1]
if r==0:
if q%2==0:
N[1],N[2]=N[1]*2,N[2]-N[1]
print N
else:
N[0],N[1]=N[0]-N[1],N[1]*2
print N
# Identification des 2 conteneurs à contenance égale
nb=10*(N[0]==N[1])+20*(N[0]==N[2])+21*(N[1]==N[2])
if nb==51:nb=10
# Vidage du n° le plus petit et doublage de l'autre
N[nb%10],N[nb//10]=0,N[nb//10]*2
print
print "** Fin **"
print N
@+
Arx Tarpeia Capitoli proxima...
En ligne
#22 01-05-2013 14:05:57
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Jeu d'eau
Rebonjour,
@yoshi : Je reprends votre code post #17 avec N=[17,21,49]
les lignes 14,15 et 16 impriment [34,4,49]
et on revient ligne 3 sur le while not, puis sur la ligne 19, puis sur la ligne 24
sur cette ligne 24 j'ai corrigé le 01 de q,r=N[0]//N[1],N[01]%N[1] en 0 sinon Python 3.2 se met en erreur. Comme alors r=2 on reboucle indéfiniment via la ligne 3......??
Hors ligne
#23 01-05-2013 14:29:13
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 946
Re : Jeu d'eau
Re,
Alors, il y a là un heureux hasard ou j'ai oublié ce que j'ai imaginé...
Et le 01 est une faute de frappe non détectée : Python 2.6 est donc plus laxiste que les v. 3.x
Donc, après examen, j'en ai conclu que ça ne marche qu'avec 1 au lieu de 01 : en foi de quoi le calcul de r est inutile, il est automatiquement égal à 0, et le if r==0 est inutile aussi. Donc code expurgé :
N=sorted([17,21,49])
print N
while not (N[0]==N[1] or N[0]==N[2] or N[1]==N[2]):
if N[1]>N[0]:
q,r=N[1]//N[0],N[1]%N[0]
if r==0:
if q%2==0:
N[0],N[2]=N[0]*2,N[2]-N[0]
print N
else:
N[0],N[1]=N[0]*2,N[1]-N[0]
print N
else:
N[0],N[1]=N[0]*2,N[1]-N[0]
print N
elif N[1]==N[0]:
pass
else:
if N[0]>N[2]:
N[2],N[0]=N[2]*2,N[0]-N[2]
print N
else:
q=N[0]//N[1]
if q%2==0:
N[1],N[2]=N[1]*2,N[2]-N[1]
print N
else:
N[0],N[1]=N[0]-N[1],N[1]*2
print N
# Identification des 2 conteneurs à contenance égale
nb=10*(N[0]==N[1])+20*(N[0]==N[2])+21*(N[1]==N[2])
if nb==51:nb=10
# Vidage du n° le plus petit et doublement de l'autre
N[nb%10],N[nb//10]=0,N[nb//10]*2
print
print "** Fin **"
print N
Ça fonctionne... chez moi !
@+
[EDIT]
Version "factorisée" dans le forum programmation...
Dernière modification par yoshi (01-05-2013 19:50:30)
Arx Tarpeia Capitoli proxima...
En ligne
#24 02-05-2013 13:08:27
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Jeu d'eau
Bonjour,
Correction faite, le programme donne un résultat sur les différentes valeurs initiales utilisées : Python 3.2.2 dit "Invalid token" pour N[01] (il prend cependant correctement N[00] !)
Comparé à l'algorithme Yassine implémenté post #20, le programme donné au post #23 donne un résultat "récipient vide" plus rapidement, vraisemblablement en économisant les tris, puisqu'il n'y en a plus qu'un seul au début.
L'algorithme implémenté post #23 par yoshi correspond à un automate dont les états sont finis, puisque la somme des contenus des 3 récipients est constante.
Mais en suivant la succession d'états : la "descente" qui est la base de la démonstration de Yassine n'est pas utilisée !
Un état correspondant à deux récipients égaux sera donc inéluctablement atteint pour tout triplet initial si l'algorithme ne boucle pas auparavant : est-ce démontrable au vu du programme ?
Hors ligne
#25 02-05-2013 15:49:31
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 946
Re : Jeu d'eau
Bonjour,
Une façon de prouver que ma méthode -inspirée largement de Yassine - est incorrecte théoriquement serait de trouver des contre-exemples...
Pour l'instant, je n'en ai pas.
Je suis parti de deux principes différents cependant :
- A bien lire Yassine, même si son emploi du binaire me laisse toujours perplexe (je retrouve ici mon adage favori : savoir pour soi, c'est une chose, savoir pour les autres c'en est une autre ô combien plus "délicate". Donc j'attends toujours une explication dénué e d'une procédure elliptique), une chose m'a frappée, le récipient R3 sert de variable d(ajustement, il est très important qu'il contienne une quantité conséquente... Donc, je me suis efforcé de faire en sorte de le remplir de nouveau dès que le contenu de R1 lui était supérieur...
- En regardant votre exemple avec :
3 11 99999
6 8 99999
12 2 99999
2 12 99999 (q=6 en base 10 soit 110 en base 2, donc appel à R3 pour le 0 de 110)
4 12 99997
8 8 99997
16 0 99997 à coup sûr !!!
je suis tombé en arrêt devant les deux lignes :
2 2 99999
2 12 99999 (q=6 en base 10 soit 110 en base 2, donc appel à R3 pour le 0 de 110)
et une question s'est posée à moi : pourquoi faire ?
Si N1 > N2 alors les rôles de R1 et R2 sont inversés...
Donc, mon algorithme est tel que si N1 > N2 alors, je ne trie pas pour que N1>N2 pour pouvoir remplir R1 avec R2, mais je remplis tout simplement R2 avec R1.
Je ne remplis R2 avec R1 (ou R1 avec R2) que si (N1//N2)%2 = 1 respectivement (N2//N1)%2=1 et r=0, sinon je fais appel à R3...
N-B : "q=6 en base 10 soit 110 en base 2, donc appel à R3 pour le 0 de 110". Très bien, va pour le 0 ... et les deux 1, on en fait quoi ?
C'est pourquoi j'ai cru pouvoir tester si le quotient était pair ou impair.
J'ai pris aussi comme option de toujours vider le récipient de n° le plus faible.
D'autre part dans la version #23, je savais que le test elif N[0]==N[1]: était inutile, d'abord parce que l'instruction était "pass" et que le cas était traité dans le while...
Donc dans la version factorisée (forum programmation j'ai supprimé ce test et écrit la suite (un peu) différemment...
@+
Arx Tarpeia Capitoli proxima...
En ligne