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 …

[tatayo]

Bonjour,
Une solution serait de procéder ainsi:

1. On teste le premier barreau. Si ça casse, on a la réponse.
2. Sinon on teste les barreau de 3 en 3, jusqu'à la casse du vase au barreau n.
3. Ensuite on teste le barreau n-2.
4. Si le vase casse, la réponse est n-2.
5. Sinon on test n-1. Si la vase casse, la réponse est n-1, sinon c'est n

J'ai pris un "pas" de 3, mais on peut imaginer un pas plus élevé si l'échelle comporte un nombre important de barreaux.
Par contre j'avoue que je ne sais pas comment calculer le "pas" idéal.

Tatayo.

[François DORIN]

Bonjour,
Une solution serait de procéder ainsi:

1. On teste le premier barreau. Si ça casse, on a la réponse.
2. Sinon on teste les barreau de 3 en 3, jusqu'à la casse du vase au barreau n.
3. Ensuite on teste le barreau n-2.
4. Si le vase casse, la réponse est n-2.
5. Sinon on test n-1. Si la vase casse, la réponse est n-1, sinon c'est n

Avec deux vases, c'est exactement la solution la plus adaptée et qui minimise le nombre d'essais (On ignore, bien entendu, la fragilisation du vase suite à des petites chutes successives )

J'ai pris un "pas" de 3, mais on peut imaginer un pas plus élevé si l'échelle comporte un nombre important de barreaux.
Par contre j'avoue que je ne sais pas comment calculer le "pas" idéal.

Le pas ne vas pas déprendre de la taille de l'échelle, mais du nombre de vases à disposition. Avec les vases restants, il faut être en mesure de faire une recherche dichotomique pour diminuer le nombre d'essais. Donc, pour le pas, à vue de nez, je dirais .

[nono_31]

Bonjour,

Il me semble que vous avez écarté un peu vite la dichotomie.
Au pire cas, elle requiert log2(n) étapes (et non n/2) ce qui est mieux que sqrt(n) !

Cordialement.

[tbc92]

@nono_31 : la dichotomie 'pure' ne fonctionne pas ici, car quand un vase est cassé, il ne peut plus servir.
Relis mon premier message.

Si on dit qu'il faut viser à racine(n) quand on a 2 vases, ok... mais notons n le nombre d'échelons, et k le nombre de vases disponibles.
f(n,k) = 1 quand k vaut 1
f(n,k) = racine(n) quand k vaut 2
f(n,k) = n/2 quand k est très grand
Mais je vois mal la forme de cette fonction pour k supérieur à 2, mais pas très grand.

[picodev]

Avec deux vases, c'est exactement la solution la plus adaptée et qui minimise le nombre d'essais (On ignore, bien entendu, la fragilisation du vase suite à des petites chutes successives )


Le pas ne vas pas déprendre de la taille de l'échelle, mais du nombre de vases à disposition. Avec les vases restants, il faut être en mesure de faire une recherche dichotomique pour diminuer le nombre d'essais. Donc, pour le pas, à vue de nez, je dirais .

Pour v=2, le pas ne dépend que de la taille de l'échelle → pas(n) = ⌊√n⌋ pour un nombre d'essais E(n)=2⌊√n⌋-1.
Pour v>2 je vois plus une application récursive → on commence avec un pas de ⌊√n⌋, puis on passe à un problème de taille inférieure avec un pas de ⌊∜n⌋, sauf si on tombe dans le cas où on peut appliquer une recherche dichotomique.

Bonjour,

Il me semble que vous avez écarté un peu vite la dichotomie.
Au pire cas, elle requiert log2(n) étapes (et non n/2) ce qui est mieux que sqrt(n) !

Cordialement.

La dichotomie n'est intéressante et optimale uniquement si on dispose de suffisamment de vases … Si n≤2^v-1, alors la meilleure stratégie est la recherche dichotomique. Si v=1, alors la meilleure et la seule stratégie consiste à tester tous les barreaux en commençant à 1 et en prenant le suivant tant qu'on a pas cassé le vase.
Avec v=2, une bonne stratégie semble être celle que j'ai décrite, mais je n'ai pas prouvé qu'il n'en existait pas de meilleure.

[François DORIN]

Pour v=2, le pas ne dépend que de la taille de l'échelle → pas(n) = ⌊√n⌋ pour un nombre d'essais E(n)=2⌊√n⌋-1.

En fait, j'avais mal compris la méthode proposée par tatayo. Je pensais qu'il s'agissait de réduire le problème à un problème dichotomique à l'aide du premier vase. Et dans ce cas, la taille de l'échelle n'intervient pas dans le pas, mais uniquement le nombre de vases initial. Quand on lit trop vite...

[nono_31]

Quand on lit trop vite...

Pareil pour moi !