Étant donné une entrée d'un entier positif, affichez le nombre d'étapes nécessaires pour trouver l'entrée via une recherche binaire commençant à 1.

Nous simulons une recherche binaire de l'entier qui a été donné en entrée, dans laquelle le chercheur simulé peut deviner à plusieurs reprises un entier et être informé s'il est trop élevé, trop bas ou correct. La stratégie pour trouver l'entier est la suivante:

• Soit n l'entier donné en entrée que nous essayons de trouver.

• Commencez avec une supposition de 1. (Pour chaque supposition, augmentez le nombre d'étapes (indépendamment du fait que ce soit correct ou non), et arrêtez immédiatement et affichez le nombre total d'étapes si la supposition était correcte.)

• Doublez la supposition à plusieurs reprises jusqu'à ce que la supposition soit supérieure à n (le nombre cible). (Ou si c'est correct, mais c'est déjà couvert par notre règle de supposition correcte mentionnée ci-dessus.)

• Maintenant, définissez une limite supérieure de la première puissance de 2 supérieure à n (c'est-à-dire le nombre qui vient d'être deviné) et définissez une limite inférieure de la puissance de 2 directement en dessous.

• Devinez à plusieurs reprises la moyenne (arrondie vers le bas) de la limite supérieure et de la limite inférieure. S'il est trop élevé, définissez-le comme limite supérieure. S'il est trop bas, définissez-le comme limite inférieure. Cette procédure est garantie pour éventuellement aboutir à une estimation correcte.

Voici un exemple, pour l'entrée de n = 21:

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 24 -> 20 -> 22 -> 21
\__________________________/
   repeated doubling      \________________________/
                             repeated averaging

Puisqu'il s'agit de code-golf , le code le plus court en octets gagnera.

Voici toutes les sorties de n = 1 à n = 100:

1
2
4
3
6
5
6
4
8
7
8
6
8
7
8
5
10
9
10
8
10
9
10
7
10
9
10
8
10
9
10
6
12
11
12
10
12
11
12
9
12
11
12
10
12
11
12
8
12
11
12
10
12
11
12
9
12
11
12
10
12
11
12
7
14
13
14
12
14
13
14
11
14
13
14
12
14
13
14
10
14
13
14
12
14
13
14
11
14
13
14
12
14
13
14
9
14
13
14
12

Et voici quelques cas de test plus importants:

1234 -> 21
1337 -> 22
3808 -> 19
12345 -> 28
32768 -> 16
32769 -> 32
50000 -> 28

Japt, 13 12 octets

Oh mon Dieu, je battais Jelly et Pyth pendant un certain temps: D

¢a1 ªJ +1+¢l

Testez-le en ligne!

Voici la stratégie utilisation I: laisser x le nombre entier d'entrée, et que b soit x est la représentation binaire. La sortie correcte est 1 + la longueur de b + le dernier index de 1 en b , moins 1 si cet index est 0.

Gelée, 18 15 10 9 octets

B>WU;BḄBL

Essayez-le en ligne! ou vérifiez les petits cas de test et les grands cas de test .

Contexte

Soit n un entier positif et m la plus petite puissance de 2 supérieure ou égale ou égale à n .

• La phase de doublage fait un pas pour chaque chiffre dans la représentation binaire de m .

• Prenez la représentation binaire de n , supprimez le premier chiffre le plus significatif (toujours 1 ) et tous les zéros de fin. La phase de calcul de moyenne fait une étape pour chaque chiffre restant.

Pour éviter de calculer m , nous observons que, si n <m , le nombre de chiffres binaires de n est exactement un de moins que le nombre de chiffres binaires de m .

Si nous remplaçons le premier chiffre binaire de n par un 0 , inversons le résultat, ajoutons les chiffres binaires d'origine et supprimons tous les zéros en tête, alors ce qui suit se produit:

• Si n est une puissance de 2 , tous les chiffres de la première moitié (modifiée) sont supprimés, ne laissant que les chiffres de la représentation binaire d'origine de n = m .

• Si n n'est pas une puissance de 2 , le chiffre de la première moitié qui correspond au chiffre le plus significatif n'est pas supprimé, compensant le fait que n a un chiffre binaire inférieur à m .

Comment ça fonctionne

B>WU;BḄBL  Main link. Input: n

B          Compute the binary representation of n.
 >W        Compare it with [n].
           n is positive, so it is not less than the first binary digit and the
           comparison yields zero. When comparing lists of different length, the
           elements in the longer list that do not have a pair remain untouched.
           Therefore, this will just zero out the first binary digit.
   U       Reverse the modified binary representation.
    ;B     Concatenate it with the unmodified binary representation of n.
      ḄB   Convert from binary to integer, and back to binary.
           This removes leading zeroes.
        L  Get the length of the resulting array.

ES6, 38 octets

x=>33-(g=Math.clz32)(x-1)+g(x&-x)-g(x)

Comme mentionné dans d'autres réponses, vous pouvez calculer le nombre de pas à partir des positions des premier et dernier bits.

Le nombre d'étapes dans la phase de doublement est n=33-Math.clz32(x-1). Nous voulons 2ⁿ ≥ x mais n=33-Math.clz32(x)nous donne 2ⁿ> x donc nous soustrayons 1 de x pour compenser.

Le nombre d'étapes dans la phase de moyenne est plus facile, c'est tout simplement n=Math.clz32(x&-x)-Math.clz32(x). x&-xest une expression pratique qui évalue au bit le plus bas de x(comme une puissance de 2).

Pyth, 15 13 octets

h-y.ElQ/PPyQ2

J'ai trouvé que le nombre à calculer est 1 + 2*ceil(log_2(x)) - [number of 2s in x's prime factorization, minus 1 if x is a power of 2 greater than 1].

Essayez-le ici .

Julia, 37 35 octets

n->endof(strip(bin(n-1)bin(n),'0'))

Merci à @AlexA. pour économiser 2 octets!

Cela fait suite aux observations de ma réponse Jelly , mais traite différemment des cas marginaux.

Si n> 1 , la représentation binaire de n - 1 a un chiffre de moins que celui de la puissance suivante de 2 , ce qui est compensé en ne supprimant pas le premier chiffre de la représentation binaire de n .

En supprimant tous les zéros des deux côtés , nous traitons également le cas de bord 1 .

Haskell, 82 octets

Il s'agit d'une implémentation assez simple dans Haskell:

f x=[j|j<-[1..],let g i|i<2=1|x>g(i-1)=2*g(i-1)|1<2=div(g(i-1)+g(i-2))2,g j==x]!!0

Moins golfé:

f x = head [ stepNum | stepNum <- [1..], step stepNum == x]
  where
    prevStep i = step (i-1)
    step i | i == 1         = 1
           | x > prevStep i = 2 * prevStep i
           | otherwise      = div (prevStep i + step (i-2)) 2