Geben Sie bei Eingabe einer positiven Ganzzahl die Anzahl der Schritte aus, die erforderlich sind, um die Eingabe über eine Binärsuche ab 1 zu finden.
Wir simulieren eine binäre Suche nach der als Eingabe angegebenen Ganzzahl, bei der der simulierte Sucher wiederholt eine Ganzzahl erraten und feststellen kann, ob sie zu hoch, zu niedrig oder korrekt ist. Die Strategie zum Finden der Ganzzahl lautet wie folgt:
Sei n die als Eingabe angegebene Ganzzahl, die wir zu finden versuchen.
Beginnen Sie mit einer Schätzung von 1. (Erhöhen Sie für jede Schätzung die Anzahl der Schritte (unabhängig davon, ob sie richtig war oder nicht) und stoppen Sie sofort und geben Sie die Gesamtzahl der Schritte aus, wenn die Schätzung richtig war.)
Verdoppeln Sie die Schätzung so oft, bis sie größer als n (die Zielzahl) ist. (Oder wenn es korrekt ist, dies aber bereits durch unsere oben erwähnte Richtigkeitsregel abgedeckt ist.)
Setzen Sie nun eine obere Grenze der ersten Potenz von 2, die größer als n ist (dh die Zahl, die gerade erraten wurde), und setzen Sie eine untere Grenze der Potenz von 2 direkt darunter.
Errate wiederholt den Durchschnitt (abgerundet) der oberen und unteren Schranke. Wenn es zu hoch ist, legen Sie es als obere Grenze fest. Wenn es zu niedrig ist, legen Sie es als Untergrenze fest. Dieser Vorgang führt garantiert zu einer korrekten Vermutung.
Hier ist ein Beispiel für die Eingabe von n = 21:
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 24 -> 20 -> 22 -> 21
\__________________________/
repeated doubling \________________________/
repeated averaging
Da es sich um Code-Golf , wird der kürzeste Code in Bytes gewinnen.
Hier sind alle Ausgaben von n = 1 bis 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
Und hier sind einige größere Testfälle:
1234 -> 21
1337 -> 22
3808 -> 19
12345 -> 28
32768 -> 16
32769 -> 32
50000 -> 28
Jelly,
1815109 BytesProbieren Sie es online! oder überprüfen Sie die kleinen und großen Testfälle .
Hintergrund
Sei n eine positive ganze Zahl und m die kleinste Potenz von 2 , die größer oder gleich oder gleich n ist .
Die Verdopplungsphase dauert einen Schritt für jede Ziffer in der binären Darstellung von m .
Nehmen Sie die binäre Darstellung von n , entfernen Sie die erste, höchstwertige Ziffer (immer 1 ) und alle nachfolgenden Nullen. Die Mittelungsphase dauert einen Schritt für jede verbleibende Ziffer.
Um die Berechnung von m zu vermeiden , beobachten wir, dass wenn n <m , die Anzahl der Binärziffern von n genau eins kleiner ist als die Anzahl der Binärziffern von m .
Wenn wir die erste Binärziffer von n durch eine 0 ersetzen , das Ergebnis umkehren, die ursprünglichen Binärziffern anhängen und alle führenden Nullen entfernen, geschieht Folgendes:
Wenn n eine Potenz von 2 ist , werden alle Ziffern der ersten (modifizierten) Hälfte entfernt, wobei nur die Ziffern der ursprünglichen Binärdarstellung von n = m übrig bleiben .
Wenn n ist nicht eine Potenz von 2 , die Ziffer in der ersten Hälfte , dass entspricht die höchstwertigen Stelle ist nicht entfernt bekommen, für die Tatsache kompensieren , dass n eine Binärziffer weniger hat als m .
Wie es funktioniert
quelle
’B;Bt0L
(7 Bytes) funktioniert in der neuesten Version von Jelly nach dem gleichen Ansatz wie in meiner Julia-Antwort .ES6, 38 Bytes
Wie in anderen Antworten angedeutet, können Sie die Anzahl der Schritte aus den Positionen des ersten und des letzten Bits berechnen.
Die Anzahl der Schritte in der Verdopplungsphase beträgt
n=33-Math.clz32(x-1)
. Wir wollen 2ⁿ ≥ x,n=33-Math.clz32(x)
geben aber 2ⁿ> x, also subtrahieren wir 1 von x, um dies zu kompensieren.Die Anzahl der Schritte in der Mittelungsphase ist einfacher, es ist einfach
n=Math.clz32(x&-x)-Math.clz32(x)
.x&-x
ist ein praktischer Ausdruck, der mit dem niedrigsten Bit vonx
(als Zweierpotenz) bewertet wird .quelle
x&-x
Arbeit? Ich hätte gedacht, dass es zum absoluten Wert von x auswerten würde.Pyth,
1513 BytesIch habe festgestellt, dass die zu berechnende Zahl ist
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].
Probieren Sie es hier aus .
quelle
Julia,
3735 BytesVielen Dank an @AlexA. zum Speichern von 2 Bytes!
Dies folgt den Beobachtungen aus meiner Jelly-Antwort , geht aber anders mit den Randfällen um.
Wenn n> 1 ist , hat die Binärdarstellung von n - 1 eine Stelle weniger als die der nächsten Potenz von 2 , was dadurch ausgeglichen wird, dass die erste Stelle der Binärdarstellung von n nicht entfernt wird .
Durch Entfernen aller Nullen von beiden Seiten wird auch der Kantenfall 1 behandelt .
quelle
Haskell, 82 Bytes
Dies ist eine ziemlich einfache Implementierung in Haskell:
Weniger golfen:
quelle