Discussion :

[Ja Rasta]

Bonjour à tous.
J'ai exercice dans lequel on demande d'écrire un algo qui m'est impossible.

Voilà l'exercice :

On a une très grande échelle.On dispose de 2 vases identiques et on souhaite déterminer à partir de quel échelon un vase se casse si on le laisse tomber.On appelle n cet échelon.On ne peut bien entendu pas réutiliser un vase cassé.
La complexité d'une solution est évaluée en fonction du nombre de lancés des vases déjà effectués,avec comme paramètre n,l'échelon où le vase se casse.

1°) Proposer un algo pour trouver le bon échelon et donnez sa complexité.
2°)Si ce n'était pas déjà le cas,proposer une solution mieux que linéaire pour trouver le bon échelon.

Si quelqu'un voit comment résoudre ce problème,merci de m'aider.

[gpcbitnik38]

recherche par dichotomie :

tu te place au milieu de ton echelle.
si le vase casse tu considère que le barreau en dessous et tu recommence
si le vase ne casse pas tu considère que les barreau au dessus et tu recommence

tu itères jusqu’à ce qu'il ne reste plus qu'un barreau

[tbc92]

Ici, on a 2 vases à disposition.
Imaginons une échelle avec 100 barreaux. Dans une dichotomie, on teste le 50ème échelon, imaginons que le vase casse.
La bonne hauteur est donc un n° entre 1 et 49. Dans une dichotomie classique, on teste le 25ème échelon, et imaginons qu'à nouveau, le vase casse.
On n'a plus de vase à disposition, et on ne sait pas quel échelon est la bonne solution. On sait juste que la bonne réponse est entre 1 et 24.

Il faut donc adapter un peu la dichotomie.

[picodev]

C'est un problème classique … et la dichotomie n'est pas la meilleure stratégie. Supposons que l'échelle possède n barreaux. Avec une stratégie dichotomique on arrive dans le pire des cas à n/2 (aux arrondis près) essais, c'est le cas où le premier vase casse au premier essai (1 essai) il reste n/2-1 barreaux à essayer. Par exemple avec 100 barreaux, le premier vase casse au barreau 50, et dans le pire des cas le second ne se casse qu'au barreau 49 → 50 essais en tout.

Imaginons maintenant qu'on essaie tous les k barreaux. Dans le pire des cas le premier vase cassera après n/k barreaux avec k-1 essais supplémentaires. L'idée sera de minimiser n/k+k-1 … par exemple avec 100 barreaux on prend k=10, au pire des cas le premier vase ne se cassera qu'au barreau 100 (10 essais), nécessitant au pire encore 9 essais (de 91 à 99) pour un total de 19 essais ; on peut aussi prendre k de 8 à 13 pour obtenir 19 essais.

Dans un cadre plus général on peut partir d'une fonction f(x) strictement croissante et positive qui indique quel barreau est choisi pour le premier vase au x^ième essai. En gros le pire des cas est le maximum de S(k) = {i+f(i,k)-f(i-1,k)-1} i>0 avec f(i)<=n avec k un paramètre fixé définissant la stratégie. C'est une formule approximative évidemment. Ensuite il faut minimiser S(k) en fonction de k pour avoir la meilleure stratégie en fonction de k.

[tbc92]

Je pense (mais pas vérifié) que la bonne optimisation est de viser à racine(n) : Mais quid si on généralise à k vases restants ?
Je pense que cette question va m'empêcher de dormir !

[picodev]

oui, la dérivée de n/k+k-1 par rapport à k est (k²-n)/k² qui s'annule en √n. Maintenant ça ne veut pas dire que f(x)=x/n est la meilleure stratégie pour tout n …