Devinette avec Random

Rappel du premier message :

Ecrire un programme qui permet de faire deviner un nombre choisi
aléatoirement entre 0 et 100 (fonction
random de la librairie stdlib). le
programme signalera à chaque tentative si le nombre proposé est plus
petit ou plus grand que la solution.

C'est un exercice qui m'a été proposé.

Revenons à nos moutons.

La preuve est trés simple. Comme l'ordinateur utilise une méthode dichotomique il faudra chercher :
2^x=1000 --> Ln(1000)/Ln(2)=9,xxx=10 essais

Si on pose la question autrement: quel est le nombre secret qui demande le maximum de propositions avant qu'il soit dévoilé, sachant que la méthode adoptée est la dichotomie biensûr ?

on utilise le principe de la dichotomie comme ca si on veut deviner un nombre entre 0 et 1024 par exemple au pire cas on va faire 10 fois ))

moudhafer a écrit:on utilise le principe de la dichotomie comme ca si on veut deviner un nombre entre 0 et 1024 par exemple au pire cas on va faire 10 fois ))

Oui effectivement. ça ne dépasse pas 10 coups si le nombre est entre 0 et 1024;

Extensions :

Est-ce que tu peux déterminer le nombre maximal (au pire des cas) de coups si le nombre est entre 1000 et 2000 ?

Est-ce que tu peux caractériser le nombre le plus embêtant s'il existe (qui requiert le maximum de coup pour qu'on le devine) sachant qu'on travaille dans un intervalle borné I = [a, b].

je crois ce sont 4 nombres :
*a+1
*b-1
en premier lieu puis :
*(a+b)/2 -1
*(a+b)/2 +1
nn?

salem
j'attends votre reponse nabil,c bien ce que j'ai dit??

moudhafer a écrit:je crois ce sont 4 nombres :
*a+1
*b-1
en premier lieu puis :
*(a+b)/2 -1
*(a+b)/2 +1
nn?

Intuitivement et en ignorant certains cas particuliers, je dis la même réponse.

Il suffit d'imaginer "la trajectoire" que parcourt la suite pendant la recherche de la solution. Supposons que le domaine de recherche est I [a, b] = [1, -1+2^n], et que le nombre à deviner est 1, si on procède comme l'avait indiqué l'énoncé, on proposera les nombres suivants dans l'ordre :

U1 = 2^(n-1)
U2 = 2^(n-2)
U3 = 2^(n-3)
...
U(n-2) = 4
U(n-1) = 2
U(n) = 1

Soit n = E(Log2(b+1)) opérations.