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

#26 02-05-2013 16:48:48

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Jeu d'eau

Bonjour,

yoshi a écrit :

Donc j'attends toujours une explication dénuée d'une procédure elliptique

je peux essayer, en espérant que Yassine me pardonnera d'avoir volé ses explications :

on a donc 3 contenus différents que l'on ordonne n1<n2<n3.
l'idée est d'obtenir r<n1 dans un récipient, alors on aura s et u dans les 2 autres récipients et on ordonnera r,s et u pour refaire comme avec n1,n2 et n3

comme n1, n2 et n3 sont des entiers, on fait la division euclidienne n2=q.n1 + r
C'est donc dans le récipient contenant n2 que l'on va obtenir r strictement inférieur à n1

et l'on va remplir le récipient qui contient n1 et qui contiendra successivement 2.n1, 4.n1, 8.n1,...

on écrit q en base 2 et je prends un exemple : n1=5, n2=49 alors q=9 (1001 en base 2) et r=4
le poids 1 de q en base 2 est 1 : je transfère n1=5 de n2 dans n1 qui devient 10
le poids 2 de q en base 2 est 0 : je transfère n1=10 de n3 dans n1 qui devient 20
le poids 4 de q en base 2 est 0 : je transfère n1=20 de n3 dans n1 qui devient 40
le poids 8 de q en base 2 est 1 : je transfère n1=40 de n2 dans n1 qui devient 80

j'ai donc transféré 5+40 = 45 de n2 dans n1 : reste 4 dans n2, c'est ce que l'on veut !!!
j'ai donc transféré 10+20 = 30 de n3 dans n1 : peu importe le reste dans n3, il est toujours possible de prendre dans n3 car n3>n2.

La démonstration de Yassine est impeccable.

Hors ligne

#27 02-05-2013 18:51:26

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

Re : Jeu d'eau

@totomm : je n'aurais mieux expliqué ma méthode.

L'algorithme de yoshi m'intrigue beaucoup. Je l'ai essayé sur plusieurs exemples, il semble toujours trouver les bonnes manipulations, et semble plus optimal que ma méthode. Néanmoins, je n'arrive pas à comprendre son principe.
Un exemple qui m'interpelle : La boucle principale du programme ne semble pas nécessiter que le tableau soit trié (il est trié avant d'entrer dans la boucle, ensuite, assez rapidement le tableau n'est plus trié et l'algo semble quand même trouver son chemin). On pourrait donc supprimer ce premier tri. Si on le fait, l'algo plante avec l'exemple (2,4,1). J'ai essayé de trouver un triplet trié, qui au bout de quelques applications de la fonction principale de l'algo donnerait (2,4,1) et je n'y suis pas (encore) arrivé. Est-ce à dire que la configuration (2,4,1) est inatteignable ? Pourquoi ?
Pourquoi quand N[1] > N[0], on teste que N[1] est un multiple de N[0] (r == 0 en ligne 6) et pas quand N[0] > N[1] (lignes 23,24) ? Dans la mesure où l'algo ne s'attend pas à ce que le tableau soit trié, ça devrait être symétrique.
Si je supprime le tri initial, l'algo ne traite pas pareil le triplet (2,5,20) et (5,2,20) !!

A suivre...


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

#28 02-05-2013 19:18:37

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

Re : Jeu d'eau

RE,

La boucle principale du programme ne semble pas nécessiter que le tableau soit trié (il est trié avant d'entrer dans la boucle, ensuite, assez rapidement le tableau n'est plus trié

Je m'intrigue moi-même, c'est dire...
J'ai peut-être une explication.
D'après l'exemple de totomm, j'ai vu que ton algo nécessitait que N[0] < N ([1]...
N'ayant pas compris ce que tu faisais exactement, après observation, j'ai pris le parti de faire en sorte que dans le couple (R1,R2) les rôles soient interchangeables : le plus chargé remplissait l'autre . T on algo semble fonctionner de façon univoque R2 --> R1 : je fonctionne dans les deux sens...
D'autre part, je veille autant que possible à ce que R3 soit plus chargé que les autres, pour cela si R1 est plus chargé que R3 alors je remplis R3 avec R1.
Quant à la fin de la programmation, elle repose sur (jusqu'à preuve du contraire) sur un hasard heureux : totomm ayant détecté une faute de frappe :
- en essayant de la corriger logiquement, le prog tournait effectivement en rond
- en la corrigeant de façon illogique, j'avais toujours un reste de 0 et donc le else qui suivait le if r==0 ne servait à rien : j'ai donc tiré la conclusion qui s'imposait, supprimer le morceau...
Et, invraisemblablement, le prog tourne !

J'ai l'impression qu'il aboutit très très souvent (sinon plus) :
- d'une part à une contenance puissance de 2 dans l'un des récipients
- en descend un autre jusqu'à 1
- puis le remonte 1,2,4,8,16... jusqu'à l'égalité...


N=sorted([101,102,999])
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]:
        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 doublage de l'autre
N[nb%10],N[nb//10]=0,N[nb//10]*2
print
print "** Fin **"
print N

@+

[EDIT] Je me penche sur l'explication de totomm demain matin : le soir, je ne suis pas bon à grand chose !

Dernière modification par yoshi (02-05-2013 19:42:39)


Arx Tarpeia Capitoli proxima...

Hors ligne

#29 03-05-2013 11:38:58

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Jeu d'eau

Bonjour,

une boucle infinie dans le programme post #23 :

[12, 19, 26]    ligne 4et 5 q=1 r=7 Faire N0reçoitN1 en ligne 14
[24, 7, 26]    ligne 23 q=3, Faire N0->N1 car q impair =  3
[17, 14, 26]    ligne 23 q=3, Faire N0->N1 car q impair =  1
[3, 28, 26]     Faire N0reçoitN1 car N0<N1, r>0
[6, 25, 26]     Faire N0reçoitN1 car N0<N1, r>0
[12, 19, 26]     Faire N0reçoitN1 car N0<N1, r>0

Hors ligne

#30 03-05-2013 14:27:13

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

Re : Jeu d'eau

bonjour,

Exact...
Alors 12 19 26 : écart 7 de chaque côté de 19.
Mais 11 - 18 - 25 donne une réponse.
Ecart inférieur de part et d'autre de 19 : 13-19-25 donne une réponse, le problème n'est pas là...
Je vais voir pourquoi  plus avant.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#31 03-05-2013 15:06:26

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Jeu d'eau

ReBonjour,

Ce n'est pas un problème d'écart entre n1,n2,n3... :
C'est que l'algorithme implémenté n'est pas démontré...

voir le bouclage de 14,17,36 qui boucle sur 25,6,36
voir le bouclage de 15,22,48 qui boucle sur 3,28,54...

Hors ligne

#32 03-05-2013 15:45:11

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

Re : Jeu d'eau

totomm a écrit :

ReBonjour,

Ce n'est pas un problème d'écart entre n1,n2,n3... :
C'est que l'algorithme implémenté n'est pas démontré...

voir le bouclage de 14,17,36 qui boucle sur 25,6,36
voir le bouclage de 15,22,48 qui boucle sur 3,28,54...

Bonjour,
Dommage, ça aurait été amusant de comprendre pourquoi il marchait !
@totomm, comment as-tu remonté le fil de l'algo pour trouver les exemples ?


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

#33 03-05-2013 16:51:13

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Jeu d'eau

reBonjour,

Yossine a écrit :

@totomm, comment as-tu remonté le fil de l'algo pour trouver les exemples ?

J'ai d'abord mis une signalétique dans le programme de yoshi (depuis mes doutes exprimés post #24)
et j'ai vu sur différents essais que la façon d'obtenir un résultat était un peu erratique (au sens : dépendant des chiffres utilisés)

J'ai donc transformé le programme yoshi en une procédure Vider(N) en lui adjoignant un comptage pour limiter chaque durée
et j'ai utilisé la force brute N=[a,b,c] avec a depuis 1, b depuis a+1 et c depuis b+1, avec a+b+c<max
J'ai pris max petit pour avoir un temps d’exécution  global petit puis je l'ai augmenté raisonnablement...
Aucun mérite dans ce procédé qui a été mené rapidement

Hors ligne

#34 03-05-2013 17:36:22

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

Re : Jeu d'eau

Le mérite, c'est d'y penser !
Donc, la bonne implémentation à ce stade est celle que totomm a donnée au post#20.

Je tente une explication des mes notations LaTex à yoshi.
L'écriture d'un nombre en base 2 est une série de 1 et 0, démarrant forcément à gauche par 1. Prenant par exemple le chiffre 6, il s'écrit [tex]\overline{110}^2=1\times 2^2 + 1 \times 2^1 + 0 \times 2^0[/tex]. Si je numérote les digits en commençant par la droite, je note alors [tex]\delta_0=0, \delta_1=1, \delta_2=2[/tex] les digits du chiffre 6. Ce qui me donne [tex]\overline{110}^2=\delta_2\times 2^2 + \delta_1 \times 2^1 + \delta_0 \times 2^0[/tex]. Cette notation se généralise pour n'importe quel nombre [tex]n[/tex]. Je commence d'abord par trouver la plus grande puissance de 2 qui figurera dans l'écriture binaire de [tex]n[/tex] (c'est le nombre de digit - 1). C'est le nombre k tel que [tex]2^k \leq n < 2^{k+1}[/tex], mon nombre [tex]n[/tex] s'écrit alors de manière unique sous la forme [tex]n = \overline{\delta_k \delta_{k-1} \ldots \delta_1\delta_0}^2=\delta_k \times 2^k + \delta_{k-1} \times 2^{k-1} + \cdots + \delta_1 \times 2^1 + \delta_0 \times 2^0[/tex]. Chaque [tex]\delta_i[/tex] valant 0 ou 1 et [tex]\delta_k[/tex] valant forcément 1 (on peut vérifier que ça découle de la définition de k).
Je ne sais pas si c'est plus clair comme ç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

#35 03-05-2013 20:09:16

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

Re : Jeu d'eau

Re,

J'ai essayé diverses modifs, mais rien de probant, donc à revoir...
@yassine.
Je vais te faire de la peine...

L'écriture d'un nombre en base 2 est une série de 1 et 0, démarrant forcément à gauche par 1. Prenant par exemple le chiffre 6, il s'écrit [tex]\overline{110}^2=1×2^2+1×2^1+0×2^0[/tex] (...).

Certes, je n'ai pas ton niveau, mais là, tu me prends pour une bille, coco... Ce n'est pas bien !
Je ne crois pas avoir besoin de leçon sur ce sujet.
Mon intérêt n'était pas tant la décomposition d'un nombre de la base dix en base deux (ou n'importe quelle autre base d'ailleurs) c'est ce que tu faisais de tout ce baratin en LateX (encore la volonté de faire compact ?)...
Chapeau à totomm d'avoir compris, je suis admiratif...

Tu viens d'écrire ci-dessus :

Si je numérote les digits en commençant par la droite, je note alors [tex]\delta_0=0, \delta_1=1, \delta_2=2[/tex] les digits du chiffre 6. Ce qui me donne [tex]\overline{110}^2=\delta_2\times 2^2 + \delta_1 \times 2^1 + \delta_0 \times 2^0[/tex].

digits = bits ? si oui, alors appelons un chat, un chat...
Alors
1. [tex]\overline{110}^2= \overline{6}^{10}[/tex]
2. En reprenant [tex]\delta_2=2,\,\delta_1=1\; \text{et} \; \delta_0=0[/tex]  j'ai  [tex]\delta_2\times 2^2 + \delta_1 \times 2^1 + \delta_0= 2\times 2^2+2\times 2^1+0 =12[/tex] et non 6. Tu as surement voulu écrire [tex]\delta_2=1[/tex]

Tu avais écrit page 1 :

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]

Pour moi :
[tex]q = \sum_0^k \delta_{2^i} = \delta_0+\delta_2+\delta_4+...\delta_{2^k}[/tex]... Pourquoi les bits de rang puissance de 2 seulement ?
D'autre part, prenons 7 qui s'écrit [tex]\overline{111}^2[/tex] (tu vois, je sais...), et en admettant que tu aies voulu dire [tex]\delta_0=1,\,\delta_1=1,\,\delta_2=1[/tex], que vaut la somme 1+1+1 (ta somme des [tex]\delta_i[/tex] ?
- en base 10 : 3.
- en base 2 : (1+1)+1= 10+1 =11 (tu vois, je sais aussi...)
Moi j'ai plutôt l'impression que le quotient q = 7 s'écrit [tex]q =2^2\times \delta_2+2^1 \times \delta_1+2^0\times \delta_0[/tex] avec [tex]i \in\{0,1,2\},\;\delta_i \in \{1,1,1\}[/tex]

Donc, j'en reste à l'explication de totomm, que je vais tâcher d'implémenter à ma façon et voir ce que ça donne : dans ce système, je vois la nécessité du tri.
Mais, j'essaierai de reprendre mon idée en appliquant cet algo, mais sans tri.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#36 04-05-2013 08:59:44

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

Re : Jeu d'eau

yoshi a écrit :

Certes, je n'ai pas ton niveau, mais là, tu me prends pour une bille, coco... Ce n'est pas bien !

Loin de moi cette intention. Je souhaitais mettre au propre une explication aussi exhaustive que possible. Désolé si je t'ai froissé. Toutes mes plates excuses.

yoshi a écrit :

digits = bits ? si oui, alors appelons un chat, un chat...

En l'occurrence, ta formulation est plus précise. 'digit' indiquant les chiffres '0' à '9' là où 'bit' est plus précis et indique '0' ou '1'. Je trouvais 'bit' trop connoté 'informatique'.

yoshi a écrit :

Tu as surement voulu écrire [tex]\delta_2=1[/tex]

Tout à fait. Désolé pour la coquille.

yoshi a écrit :
Yassine a écrit :

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]

Grosse bourde de ma part. Je comprends maintenant ton désarroi ! Le texte était correct, mais la formule incorrecte. Il faut bien sûr lire :

Donc, on écrit q en base 2 : [tex]q = \sum_0^k \delta_k 2^i\;\delta_k=1,\, (\delta_i)_{0,k-1}\in \{0,1\}[/tex]

Désolé à nouveau.

Dernière modification par Yassine (04-05-2013 17:00:35)


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

#37 04-05-2013 10:43:13

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

Re : Jeu d'eau

Bonjour,

Et oui, on n'est jamais à l'abri...

J'ai réfléchi...
Voilà un p'tit truc tout bête.
J'ai fait quelques essais, ça a l'air de marcher... Maintenant, il faut que j'aille plus loin et que je teste autrement.
totomm va passer par là, et avec son adaptation, le verdict tombera.
Je vais relire les posts précédents pour voir s'il y autre chose à savoir que ce que je résume ici :
- remplir R1 avec R2 et/ou R3
- tri
- recommencer jusqu'à vidage de R2


def vidage(L):
    print L
    while not L[1]==0:
        M=L
        L=sorted(L)
        if M!=L:
            print L
        q=L[1]//L[0]
        lg=len(bin(q))-2
        for i in range(lg):
            L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]  
            print L

Difficile de faire plus court...

Sortie :

>>> vidage([18,17,23])
[18, 17, 23]
[17, 18, 23]
[34, 1, 23]
[1, 23, 34]
[2, 22, 34]
[4, 20, 34]
[8, 16, 34]
[16, 16, 26]
[32, 0, 26]

vidage([12,17,23]  --> [12, 0, 40]
vidage([13,17,23]) --> [24, 0, 29]
vidage([6,25,1000]) --> [64 0, 997]
vidage([52,53,105]) --> [128, 0, 82]

Explications (pour qui ne saurait pas)
>>> bin(5)
'0b101'
>>> type(bin(5))
<type 'str'>
Confirmation : python convertit un nombre en binaire et restitue une chaîne...
>>> bin(9)
'0b1001'
>>> bin(9)[2:]
'1001'
q=L[1]//L[0]
Alors, j'obtiens le nombre de bits significatifs de q avec longueur de chaîne -2 : lg=len(bin(q))-2
Puis je boucle sur cette longueur...
(q>>i) & 1 :
j'obtiens le ieme bit par décalage vers la droite de i (>>) avec un & 1 logique...
* Si le résultat de ce calcul vaut 1, alors L[2-((q>>i) & 1)] donne L[1] et c'est R2 que je vide
* Si le résultat de ce calcul vaut 0, alors L[2-((q>>i) & 1)] donne L[2] et c'est R3 que je vide


@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#38 04-05-2013 16:59:24

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Jeu d'eau

Bonjour,

@ yoshi :
j'ai admiré la ligne : L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]

et bien sûr fait quelques essais : tout à fait conformes.

Hors ligne

#39 04-05-2013 19:21:13

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

Re : Jeu d'eau

totomm a écrit :

Bonjour,

@ yoshi :
j'ai admiré la ligne : L[0],L[2-((q>>i)&1)]=L[0]*2,L[2-((q>>i)&1)]-L[0]

et bien sûr fait quelques essais : tout à fait conformes.

Je n'avais pas fait gaffe, c'est vrai que c'est très astucieux ! Chapeau bas !


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

#40 05-05-2013 18:56:19

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

Re : Jeu d'eau

Salut,


Alors, j'ai implémenté le cas signalé par afr.
J'ai également trouvé deux variantes du même cas (pb de triple) qu'aurait pu trouver arfr...
Par exemple
cas n° 1
[16,21,48] qui si on laisse faire l'algo conduit à :
[32, 5, 48]
[5,32,48]
[10,32,43]....

Alors qu'il faut faire :
[16,21,48]
[32,21,32]
[0,21,64]  ou  [64,21,0]

cas n° 2
Variante 1
[16, 17, 51]
où il faut faire
[16,34,34]  et non [32, 1, 51]

Variante 2
[16, 17, 48]
où il faut faire
[32,34,32]  et non [32, 1,48]

Bien sûr, je ne peux pas modifier l'algo (pour l'instant ?), donc, je suis obligé de traiter ces deux cas particuliers à part...
Script en forum programmation.

@+


Arx Tarpeia Capitoli proxima...

Hors 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)?
quarantesix moins trente neuf
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