Biorąc pod uwagę dodatnią liczbę całkowitą, wypisz liczbę kroków potrzebnych do znalezienia danych wejściowych poprzez wyszukiwanie binarne od 1.

Symulujemy binarne wyszukiwanie liczby całkowitej podanej jako dane wejściowe, w której symulowany wyszukiwarka może wielokrotnie zgadywać liczbę całkowitą i otrzymywać informację, czy jest ona za wysoka, za niska lub poprawna. Strategia znajdowania liczby całkowitej jest następująca:

• Niech n będzie liczbą całkowitą podaną jako dane wejściowe, które próbujemy znaleźć.

• Zacznij od zgadywania 1. (Dla każdego zgadnięcia zwiększ liczbę kroków (niezależnie od tego, czy było poprawne, czy nie)) i natychmiast zatrzymaj i wyślij całkowitą liczbę kroków, jeśli zgadnięcie było poprawne.)

• Dwukrotnie zgadnij, aż zgadnięcie będzie większe niż n (liczba docelowa). (Lub jeśli jest to poprawne, ale jest to już objęte naszą regułą zgadywania, o której mowa powyżej.)

• Teraz ustaw górną granicę pierwszej potęgi 2, która jest większa niż n (tj. Właśnie odgadnięta liczba), i ustaw dolną granicę potęgi 2 bezpośrednio pod nią.

• Wielokrotnie zgadnij średnią (zaokrągloną w dół) górnej granicy i dolnej granicy. Jeśli jest za wysoko, ustaw go jako górną granicę. Jeśli jest za niski, ustaw go jako dolną granicę. Ta procedura gwarantuje, że ostatecznie spowoduje prawidłowe zgadnięcie.

Oto przykład wprowadzenia n = 21:

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

Ponieważ jest to code-golf , wygra najkrótszy kod w bajtach.

Oto wszystkie dane wyjściowe od n = 1 do 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

A oto kilka większych przypadków testowych:

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

Japt, 13 12 bajtów

O rany, przez pewien czas pokonałem zarówno Jelly, jak i Pytha: D

¢a1 ªJ +1+¢l

Przetestuj online!

Oto strategia, której używam: niech x będzie wejściową liczbą całkowitą, a niech b będzie reprezentacją binarną x . Prawidłowe wyjściowy 1 + długość b + ostatni indeks 1 w b minus 1, jeżeli wskaźnik ten ma wartość 0.

Galaretka, 18 15 10 9 bajtów

B>WU;BḄBL

Wypróbuj online! lub sprawdź małe przypadki testowe i duże przypadki testowe .

tło

Niech N jest liczbą całkowitą dodatnią, a m najmniejszą moc 2 , która jest równa lub większa niż lub równa n .

• Faza podwojenia ma jeden krok dla każdej cyfry w binarnej reprezentacji m .

• Weź binarną reprezentację n , usuń pierwszą, najbardziej znaczącą cyfrę (zawsze 1 ) i wszystkie zera końcowe. Faza uśredniania trwa jeden krok dla każdej pozostałej cyfry.

Aby uniknąć obliczenia m , obserwujemy, że jeśli n <m , liczba cyfr binarnych n jest dokładnie o jeden mniejsza niż liczba cyfr binarnych m .

Jeśli zamienimy pierwszą cyfrę binarną n na 0 , odwróć wynik, dołącz oryginalne cyfry binarne i usuń wszystkie początkowe zera, a następnie:

• Jeśli n jest potęgą 2 , wszystkie cyfry pierwszej (zmodyfikowanej) połowy są usuwane, pozostawiając tylko cyfry oryginalnej reprezentacji binarnej n = m .

• Jeśli n jest nie potęgą liczby 2 , cyfra w pierwszej połowie, która odpowiada najbardziej znaczącej cyfry ma nie zostaną usunięte, kompensując tym, że n ma binarną cyfrę mniej niż m .

Jak to działa

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 bajtów

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

Jak wspomniano w innych odpowiedziach, można obliczyć liczbę kroków na podstawie pozycji pierwszego i ostatniego bitu.

Liczba kroków w fazie podwojenia wynosi n=33-Math.clz32(x-1). Chcemy 2ⁿ ≥ x, ale n=33-Math.clz32(x)daje nam 2ⁿ> x, więc odejmujemy 1 od x, aby to zrekompensować.

Liczba kroków w fazie uśredniania jest łatwiejsza, po prostu n=Math.clz32(x&-x)-Math.clz32(x). x&-xjest przydatnym wyrażeniem, które ocenia do najniższego bitu x(jako potęga 2).

Pyth, 15 13 bajtów

h-y.ElQ/PPyQ2

Odkryłem, że liczba do obliczenia to 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].

Wypróbuj tutaj .

Julia, 37 35 bajtów

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

Dzięki @AlexA. za zapisanie 2 bajtów!

Jest to zgodne z obserwacjami z mojej odpowiedzi Jelly , ale inaczej traktuje przypadki brzegowe.

Jeśli n> 1 , binarna reprezentacja n - 1 ma jedną cyfrę mniejszą niż jedna z następnej potęgi 2 , co jest kompensowane przez nie usuwanie pierwszej cyfry binarnej reprezentacji n .

Usuwając wszystkie zera z obu stron , zajmujemy się również przypadkiem krawędzi 1 .

Haskell, 82 bajty

Jest to dość prosta implementacja w 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

Mniej golfa:

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