Problème d'algorithme
larose29
Messages postés
4
Statut
Membre
-
mype Messages postés 2459 Date d'inscription Statut Membre Dernière intervention -
mype Messages postés 2459 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
j'ai un pb d'algorithme, si quelqu'un peut m'aider ce serait trop cool!!!
J'ai douze éléments, l'un des douze éléments a un poids différent de celui des onze autres et l'on ignore si cette différence est en plus ou en moins. En trois pesées et à l'aide d'une balance de type Roberval sans poids ne permettant que la comparaison qualitative, il s'agit d'identifier cet élément tout en déterminant s'il est plus lourd ou plus léger.
Voilà le problème, je sèche...
Merci d'avance
j'ai un pb d'algorithme, si quelqu'un peut m'aider ce serait trop cool!!!
J'ai douze éléments, l'un des douze éléments a un poids différent de celui des onze autres et l'on ignore si cette différence est en plus ou en moins. En trois pesées et à l'aide d'une balance de type Roberval sans poids ne permettant que la comparaison qualitative, il s'agit d'identifier cet élément tout en déterminant s'il est plus lourd ou plus léger.
Voilà le problème, je sèche...
Merci d'avance
Configuration: Linux Fedora Firefox 1.5.0.1
3 réponses
-
1ere pesée :Dans ta balance tu mets 6 poids d'un coté et 6 de l'autre.
2eme pesée :
Puis tu prend les 6 1ers poids et tu les pèses ainsi : 3 d'un coté 3 de l'autre
A] S'il y a une différence alors le poids est dans ce tas, (*) et s'il provient du paquet de 6 le plus lourd, il est plus lourd (sinon il est plus léger).
3eme pesée :
Peser deux des 3 poids, s'ils sont égaux c'est celui qui n'a pas étté pesé ; sinon c'est le plus léger ou plus lourd selon (*)
B] S'ils sont égaux alors le poids est dans l'autre tas
Et dans ce cas on a perdu une pesée... alors on pourra résoudre l'exo qu'en 4 pesées (en faisant comme en A).
Il y a donc 50% de chance de le résoudre en 3 pesées, à moins que quelqu'un ait une autre idée...-
Merci pour ta réponse mais en fait tu me dis qu'il n'est pas possible de résoudre ce problème à 100%.
J'ai quand même essayé de résoudre ce problème et je suis arrivée à ce stade:
disons qu'on a 12 éléments numéroté de 1 à 12
Première pesée: je pèse 4 éléments de chaque coté, {1,2,3,4} et{5,6,7,8}
***si {1,2,3,4} ={5,6,7,8} ca veut dire que l'élément différent est dans les 4 derniers , donc je pèse {7,8}et {9,10} si {7,8}={9,10} alors je pèse {10}et{11}
si 10=11 c'est que c'est 12 qui est différent sinon c'est 11
si {7,8}!={9,10} la différence vient facilement de 9 ou 10
mais la ou ca se complique c'est quand {1,2,3,4} est différent de {5,6,7,8} sachant qu'il ne nous reste plus que 2 pesées!!!
Quelqu'un verrait -il une solution?
Merci d'avance
-
-
-
la compilation verifie si ton programme est correcte et permet ensuite de l'executer
