Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#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

#2 15-04-2013 14:51:57

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

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...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#3 16-04-2013 08:01:03

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Jeu d'eau

yoshi a écrit :

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

#4 16-04-2013 10:18:53

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : Jeu d'eau

Salut,

j'ai un peu regardé, c'est raide ...


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#5 16-04-2013 10:26:41

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 946

Re : Jeu d'eau

Re,

Loi permettant de vider un tonneau

Il faut arriver à égaliser les contenu de 2 tonneaux. Après il suffit de vider l'un des deux dans l'autre...

Je vais y retourner, mais d'abord faut que je corrige le tableau dans l'autre discussion...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#6 16-04-2013 10:37:33

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Jeu d'eau

@yoshi

C'est une effet obligatoirement l'avant dernier état des récipients. Il reste encore du chemin !


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 :

Indication

Montrer qu'on peut toujours partir d'une configuration [tex]0 < n_1 \leq n_2 \leq n_3[/tex] vers une configuration [tex]0 \leq m_1 \leq m_2 \leq m_3[/tex] avec [tex]m_1 < n_1[/tex].

[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 :

Une solution

On part donc d'une configuration [tex]0 < n_1 \leq n_2 \leq n_3[/tex]. Bien sûr, en cas d'égalité de deux des 3 nombres, on vide l'un dans l'autre et l'algorithme s'arrête. Je vais appeler les récipients R1, R2 et R3.
On écrit la division euclidienne de [tex]n_2[/tex] par [tex]n_1[/tex] : [tex]n_2 = q \times n_1 + r,\ 0 \leq r < n_1[/tex] et on va montrer comment vider R2 jusqu’à [tex]r[/tex].
L'observation principale est que, à chaque fois qu'on verse de R2 vers R1, le contenu de R1 progresse selon le schéma [tex]2^n \times n_1[/tex] et le contenu de R2 selon le schéma [tex](q - \sum_0^n 2^i)n_1 + r[/tex]. Bien sûr, on n'arrivera pas à annuler [tex]q[/tex] en règle générale (ça marche uniquement dans les cas où existe un [tex]k[/tex] tel que [tex]q = \sum_0^k 2^i = 2^{k+1}-1[/tex]), et c'est là qu'intervient R3.
Donc, on écrit [tex]q[/tex] en base 2 : [tex]q = \sum_0^k \delta_{2^i}\;\delta_k=1,\, (\delta_i)_{0,k-1}\in \{0,1\}[/tex] ensuite, on regarde chaque [tex]\delta_i[/tex] en partant de [tex]i=0[/tex]. Si [tex]\delta_i=1[/tex], on verse de R2 dans R1, et si [tex]\delta_i=0[/tex], on verse de R3 dans R1 (R3 contient plus de litres que R2, donc, ça sera toujours possible). Ce procédé supprime donc de [tex]q[/tex] toutes les puissances de 2 telles que [tex]\delta_i=1[/tex] et donc annule [tex]q[/tex].
On se retrouve donc comme voulu avec R2 contenant [tex]r[/tex] litres. Soit [tex]r=0[/tex] et l'algorithme s'arrête, soit on recommence le procédé avec R2 devenant R1 et les deux autres triés correctement.

[EDIT] Pour plus de rigueur, je montre ici pourquoi il sera toujours possible d'utiliser R3 quand [tex]\delta_i=0[/tex].
J'écris [tex]n_3 = q_3 \times n_1 + r_3,\ 0 \leq r_3 < n_1[/tex]. Comme [tex]n_3 > n_2[/tex], alors [tex]q_3 \geq q[/tex] et en particulier [tex]q_3 \geq 2^k[/tex] (c'est le [tex]k[/tex] de l'écriture binaire de [tex]q[/tex]). On en déduit donc que [tex]q_3 > 2^k-1=\sum_0^{k-1}2^i[/tex]. Donc, à l'exception de l'indice [tex]k[/tex], on pourra toujours recourir à R3. Pour l'indice k, on n'a pas à recourir à R3 car [tex]\delta_k=1[/tex]

[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

arfr a écrit :

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,

arfr a écrit :

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 !

yoshi a écrit :

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 :

#Python 3.2.2
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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante et onze plus trente cinq
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums