Inscription / Connexion Nouveau Sujet
les pesées
Bonsoir
Cinq objets de poids tous différents, une balance type Roberval et c'est tout.
Combien de pesées suffisent pour classer ces cinq objets dans l'ordre décroissant de poids?
salut
avec m1<m2<m3<m4<m5.
en cherchant le poids le plus petit on effectuera au mieux 4 premieres pesées.
en cherchant ensuite le poids le plus grand m5 ,on effectuera en décomptant m1 ,
3 pesées. on a donc m1 - - - m5
en décomptant m1 et m5 , il restera m2,m3et m4 et en cherchant le poids le plus petit des 3 (m2) on aura au mieux 2 pesées , on aura donc m1 m2 - - m5 et pour les deux derniers poids restant une pesée suffira soit en tout 4 + 3 + 2 + 1 = 10 pesées
en m'inspirant de LittleFox il y a autant de pesées que de permutations d'ordre 2 (transpositions) pour ranger les cinq nombres dans l'ordre croissant
Cliquez pour afficher
dpi : je ne comprends pas ce que signifie ton code : que veulent dire les deux premières lignes ""1 et 2 ..."" ? que signifie gagnant ? perdant ?
Cliquez pour affichermais j'ai l'impression que vous ordonnez quatre objets en quatre pesées ... et je ne vois pas comment ...
Bonsoir
Je disais " gagnant" pour le plus lourd d'une pesée...
Soit ABCDE 5 produits à peser et supposons que le palmarès
des poids soit BCADE bien sûr inconnu du poseur
P1 A/B donnera B>A
P2 C/D donnera C>D
P3 B/C donnera B>C et donc B>C>D
P4 A/D donnera A>D
P5 E/B donnera B>E
P6 E/D donnera D>E et donc B>C>D>E
c'est donc la place de A qu'il reste à trouver par rapport à C
P7 A/C donnera C>A donc B>C>A>D>E
Quel que soit la répartition, cette méthode marche si la 7 ème pesée
est réfléchie.
C'est un problème très étudié 
L'article donne une minoration du nombre de comparaisons nécessaires.
Pour 5 objets elle est égale à 7.
J'ai l'impression que la méthode de dpi fonctionne, mais j'aimerai bien voir comment la formaliser.
Si quelqu'un a le courage de s'y coller . . .
Finalement la méthode de dpi, que je salue, ne marche pas.
Une tentative de formalisation.
Quitte à échanger les valeurs on peut supposer A>B et C>D ce qui consomme deux pesées.
On compare A et C à la troisième pesée :
-- si A>C on a A>C>D et A>B,
-- si C>A on a C>A>B et C>D.
En échangeant les valeurs on peut se ramener au premier cas.
Après 3 pesées on a donc A>C>D et A>B.
On prend ce résultat comme position de départ, et il reste 4 pesées.
À la 4° pesée on compare B et D.
Si D>B on a A>C>D>B et il suffit évidement ( dichotomie ) de 3 pesées pour placer E.
Sinon on a A>C>D et A>B et B>D. C'est le cas critique et il reste 3 pesées.
Dans le cas critique il reste 10 ordres possibles :
EABCD AEBCD ABECD ABCED ABCDE EACBD AECBD ACEBD ACEBD ACBED ACBDE.
Or, avec trois tests binaire, on ne peut discriminer que 2³=8 positions.
Un PS.
Ce qui ne veut pas dire qu'un algorithme triant les cinq valeurs en sept comparaisons n'existe pas.
Bonsoir,
je suis trop endormi pour lire ta démonstration.
Juste un point, 6 pesées déterminent 2⁶= 64 ordres possibles, or il y en a 120 pour 5 objets.
Il faut donc au moins 7 pesées.
7 se confirme selon les méthodes.
J'ai volontairement repris "ma" méthode
Soit toujours ABCDE l'ordre des objets et aléatoirement
CBEAD l'ordre des poids descendant (inconnu dans l'absolu).
Les 4 premières pesées sont ordonnées:
1 A/B --->B>A
2 C/D --->C>D
3 B/C--->C>B
4 A/D---> A>D -->C>B>A>D chance cas général 3
reste la place de E
5 E/B---> B>E
6 E/A---> E>A -->chance C>B>E>A>D
Dans le cas général une 7 ème pesée sera nécessaire
je ne comprends rien à votre exemple avec votre exemple particulier ...
on peut toujours raisonner à permutation près et considérer que l'ordre est l'ordre alphabétique : a < b < c < d < e
1/ je compare a et b : a < b
2/ je compare c et d : c < d
3/ je compare b et d : a < b < d et c < d ou c < d < b et a < b (on choisit le premier à permutation près)
et là je ne comprends pas comment dans le cas général on peut en une pesée ordonner a, b, c et d ... comme dpi
avec la méthode de ming et ont image ça va mieux ... je comprends : en fait on commence à trier le cinquième avant d'avoir trier complètement les quatre premiers ...
merci ... 
Il me semble qu'il est toujours possible d'ordonner n objets avec comparaisons.
En fait c'est presque évident.
La difficulté étant de trouver l'algorithme convenable.
re bonjour verdurin
Pendant que ta douce et tendre fait la vaisselle ou la lessive ou rien ... que sais-je,
peux-tu me dire pourquoi dans mon arbre ci-dessus je ne trouve , pour 6 pesées, que 30 cas ascendants et donc 30 cas descendants soit 60 cas au lieu des 26 que tu m'as promis?
Merci
Un PS.
Ce qui ne veut pas dire qu'un algorithme triant les cinq valeurs en sept comparaisons n'existe pas.
Algorithme dont j'ai proposé un exemple il y a un bout de temps maintenant
.
J'ai vérifié avec toutes les permutations possibles et il fonctionne .
Ce n'est pas un algorithme très général cependant. Mais la méthode de construction est générale bien que rapidement très lourde.
Salut LittleFox.
Je n'avais pas ouvert ton message caché.
Ce qui est l'inconvénient de ce type de choses.
re bonjour verdurin
Pendant que ta douce et tendre fait la vaisselle ou la lessive ou rien ... que sais-je,
peux-tu me dire pourquoi dans mon arbre ci-dessus je ne trouve , pour 6 pesées, que 30 cas ascendants et donc 30 cas descendants soit 60 cas au lieu des 26 que tu m'as promis?
Merci
Je t'ai promis quelque chose ?
Sept pesées peuvent distinguer au mieux 128 cas.
Ici il faut en distinguer 120=2x60.
Sinon, je me permets une remarque un peu aigre :
tu es à l'origine du sujet. Et si tu avais signalé que LittleFox avait donné une solution au quatrième message, ça m'aurait évité de me couvrir de ridicule en répétant ce qu'il avait dit.
Quand tu ouvres un fil ( surtout dans la section détente où il y a des messages cachés ) il me semble qu'il est poli de le gérer un minimum.
Bonsoir verdurin
Tout d'abord, je ne pense pas que tu t'es couvert de ridicule.
Ensuite, si je n'ai rien dit de l'intervention de Littlefox, c'est tout simplement parce que ... je ne comprends rien à la programmation et à peine quelques mots en Anglais . La notion de code m'est inconnue et donc je suis incapable de commenter sa réponse.
Enfin, je ne pouvais ni savoir ni comprendre que tu n'avais pas lu son texte, sinon, j'en aurais certainement écrit un mot.
Voilà, excuse-moi de ce quiproquo.
PS quand je dis :"que tu m'as promis" c'est une figure de style
Je peux essayer d'expliquer le code en français mais avec 15 cas différents, ça prend beaucoup de texte et on est pas à l'abri d'une erreur de frappe ou d'interprétation. D'où le code que j'ai pu vérifier et corriger en le faisant tourner sur toutes les permutations possibles.
Soit les pierre a',b',c',d',e, on fait 3 comparaisons :
Si a'>b' alors on inverse a' et b', même chose pour c' et d'.
Ensuite, si a'> c' alors on inverse a'b' et c'd'.
Toutes ces comparaisons sont indépendantes et coupent donc les permutations possibles exactement en deux, ce qui est optimal.
Les comparaisons suivantes ne sont plus indépendantes et doivent donc être choisies en fonction des résultats précédents. On a un arbre de comparaisons. En choisissant correctement ces comparaisons on obtient un arbre de profondeur maximale 4 (une feuille de profondeur 3 et les autres 4). Et donc 3+4 = 7, on peut trier nos pierres en 7 pesées.
Soit a,b,c,d,e les pierres après ces permutations, on va chaque fois en comparer 2 et aller à gauche si la première est plus petite, sinon on va à droite. Les feuilles donnent l'ordre des pierres pour qu'elles soient en ordre croissant.
c<e
/ \
d<e a<e
/ \ / \
b<d b<e b<c b<c
/ \ / \ / \ / \
b<c b<e b<c b<d b<e b<d | b<d
/ \ / \ / \ / \ / \ / \ | / \
abcde acbde acdbe acdeb abced acbed acebd acedb abecd aebcd aecbd aecdb eabcd eacbd eacdbLe code est vraiment juste cet arbre avec :
if <comparaison> :
<gauche>
else :
<droite>et
return <feuille>ps : je me suis bien amusé à dessiner cet arbre, les espaces dans l'éditeur n'ont pas la même taille quand visualisés
Il me semble qu'il est toujours possible d'ordonner n objets avec
En fait c'est presque évident.
La difficulté étant de trouver l'algorithme convenable.
En fait c'est faux,
Pour ceux intéressés par ce genre d'algorithme de tri allez voir l'algorithme de Ford-Johnson
Pardon pour les références en anglais
Oui tout à fait, on retrouve bien les 15 possibilités, ce qui est normal. Mais pourquoi fois 2? Plutôt fois 8, 8x15=120 = le nombre de permutations de 5 éléments.
bonjour littleFox
Dans mon arbre, je n'ai pas explicité les 15 permutations obtenue par l'échange:
A<---->D, B<---->C ce qui fait 30 permutations parmi lesquelles, on a, à coup sûr, les deux permutations croissantes et décroissantes en 6 ou 7 tris.
Bonjour LittleFox
Disons que je n'aime guère les références en anglais.
Mais que je peux les lire.
Ceci étant j'aurais préféré un lien vers une démonstration plutôt que des liens vers des affirmations.
Merci quand même.
Bonjour LittelFox
J'ai indiqué à verdurin ma méconnaissance de la programmation.
Je ne comprends donc pas dans ton arbre le rapport avec les 6 ou 7 pesées.
Tandis que si tu lis le mien, tu vois apparaitre nettement chacune des pesées et chaque résultat.
Chaque niveau horizontal de l'arbre est une pesée. Et c'est vrai que je ne mets que les résultats finaux. Mais il me semble que c'est très clair quand même.
Je ne comprends pas ton problème, on a le même (genre d') arbre simplement le tien est mis en horizontal, le mien en vertical. Nos solutions sont équivalentes.
Je ne vois pas ce que je peux faire de plus...
Annuler
connectez vous