Problème de "Léchelle"

par **Croow** » 27 Jan 2012, 23:33

Mr.Dupond fabrique des oeufs en céramique et veut tester leurs résistances. Pour cela il dispose d'une échelle de 100 barreaux. Il veut donc trouver le barreaux maximum ou en laissant tomber l'oeuf, il reste intact. Mais il y a une condition, cela doit se faire en effectuant le moins de test possible.

Voila l'intitulé, pas très clair mais c'est ca. Pour ma part j'ai exploré la piste des probabilités, et j'aimerais me concentrer sur un formule algébrique possible. Mais si vous avez d'autres solutions, elles sont le bienvenus ! :D Merci

par **vingtdieux** » 28 Jan 2012, 01:53

Tout est question de precision. On ne sait pas quel intervalle mesure un barreau...
Mai bon, il faut commencer au niveau 50 puis faire augmentation ou diminution de moitie d'intervalle. Si l'oeuf casse on essaye au barreau 25 sinon on fait un essai au barreau 75.
Prenons un exemple: l'oeuf casse a 50 mais pas a 25, donc la hauteur possible du laché est comprise entre 25 et 50.
Ainsi de suite...

par **Croow** » 28 Jan 2012, 09:28

vingtdieux a écrit:Tout est question de precision. On ne sait pas quel intervalle mesure un barreau...
Mai bon, il faut commencer au niveau 50 puis faire augmentation ou diminution de moitie d'intervalle. Si l'oeuf casse on essaye au barreau 25 sinon on fait un essai au barreau 75.
Prenons un exemple: l'oeuf casse a 50 mais pas a 25, donc la hauteur possible du laché est comprise entre 25 et 50.
Ainsi de suite...

Ouais j'ai déjà procédé a ça, j'ai aussi eu le temps de trouver une méthode par dichotomie entre temps, mais merci quand même !

par **nodjim** » 28 Jan 2012, 10:34

La méthode décrite par Vingrdieux est aussi une dichotomie, quelle autre dichotomie utilises tu ?

par **Croow** » 28 Jan 2012, 11:17

Il n'y a qu'une seule méthode par dichotomie, donc en fait j'utilise la même, mais sous la forme d'un algorithme :P

par **nodjim** » 28 Jan 2012, 13:12

C'est à dire que tu aurais pu commencer la dichotomie par une autre valeur que 50 par exemple.

par **ffpower** » 31 Jan 2012, 02:00

Es tu sur de l'énoncé?
Dans l'énoncé que je connais, on a que deux oeufs à notre disposition :we:

par **Croow** » 18 Fév 2012, 13:49

Désolé de la longueur d'attente, et c'est exact le problème a évoluer et nous n'avons plus que 2 oeufs !

Serai tu un élève du programme ?! :D

par **ffpower** » 18 Fév 2012, 13:59

Je ne sais pas de quel programme tu parles, c'est juste que j'avais déjà rencontré cet exercice^^

par **Ouvrit** » 19 Fév 2012, 01:12

Croow a écrit:Désolé de la longueur d'attente, et c'est exact le problème a évoluer et nous n'avons plus que 2 oeufs !

L'objectif principal est de déterminer le numéro du barreau le plus haut pour lequel l'oeuf ne se casse pas ; la réduction du nombre maximal d'essais est un objectif secondaire.

Le problème change radicalement avec 2 oeufs, car une fois le premier oeuf cassé, il ne peut être question de casser le deuxième oeuf sans réaliser l'objectif principal ; ce qui signifie que les essais suivants partent obligatoirement du barreau situé juste au-dessus du barreau le plus haut pour lequel un essai réussi (oeuf intact) a été réalisé (à défaut, du barreau n°1).

Dans ces conditions, le nombre maximal d'essais est de 14 ; la procédure est la suivante :
- tant que l'essai est réussi, le test de l'oeuf se fait à partir des barreaux de numéros 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 ;
- après un test sur le barreau n°100, si l'oeuf est intact, la réponse est le barreau n° 100, sinon le barreau n°99 ;
- si le premier oeuf s'est cassé lors d'un test sur un autre barreau que le n°100, un nouvel essai est effectué à partir du barreau situé juste au-dessus du dernier barreau pour lequel l'essai a été réussi (ou le barreau n°1 si aucun essai n'a été réussi) ; ceci, jusqu'au barreau situé en-dessous du dernier test raté ou jusqu'à ce que le deuxième oeuf soit cassé.

par **nodjim** » 19 Fév 2012, 08:22

Une répartition qui donne plus de chance de finir au bout de 13 tests:
13,25,36,46,55,64,72,79,85,90,94,96,99,100. Si le résultat est <=55, 13 essais seulement. Il y a bien entendu bien d'autres configurations possibles.

par **Ouvrit** » 19 Fév 2012, 14:43

nodjim a écrit:Une répartition qui donne plus de chance de finir au bout de 13 tests:
13,25,36,46,55,64,72,79,85,90,94,96,99,100. Si le résultat est <=55, 13 essais seulement. Il y a bien entendu bien d'autres configurations possibles.

J'ai préféré donner la liste la plus explicite possible. Difficile d'optimiser, vu que l'énoncé :

- n'indique pas clairement qu'un des barreaux de l'échelle répond obligatoirement à la question ; si c'était le cas, il serait inutile d'effectuer un essai sur le barreau n°1 ;
- ne précise pas la répartition des barreaux sur l'échelle, qui pourrait être quelconque ; aussi, je considère que la loi de probabilité de la variable aléatoire "numéro de barreau" est inconnue.

par **maths309514** » 16 Jan 2013, 21:41

si il y a 3 oeuf et que on a 8 essaies
quel methode adopté???

par **hammana** » 19 Jan 2013, 16:54

maths309514 a écrit:si il y a 3 oeuf et que on a 8 essaies
quel methode adopté???

Je propose de laisser un oeuf tomber du premier barreau, puis de remonter un barreau plus haut, et de continuer jusqu'à ce qu'i se casse, on obtient le résultat en ne sacrifiant qu'un seul oeuf.

Problème de "Léchelle"