Eine Untersequenz ist eine beliebige Sequenz, die Sie durch Löschen einer beliebigen Anzahl von Zeichen von einer anderen abrufen können. Die unterschiedlichen nicht-leeren Teilsequenzen 100
sind 0
, 1
, 00
, 10
, 100
. Die unterschiedlichen nicht-leeren Teilsequenzen 1010
sind 0
, 1
, 00
, 01
, 10
, 11
, 010
, 100
, 101
, 110
, 1010
.
Schreiben Sie ein Programm oder eine Funktion, die bei einer positiven Ganzzahl n die Anzahl der eindeutigen nicht leeren Teilsequenzen der binären Erweiterung von n zurückgibt .
Beispiel: da 4
ist 100
in binär, und wir haben gesehen, dass es oben fünf verschiedene nicht leere Untersequenzen hatte, also f(4) = 5
. Ab n = 1 beginnt die Sequenz:
1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12
Ihr Programm muss jedoch auf jedem modernen Computer in weniger als einer Sekunde für n <2 50 funktionieren . Einige große Beispiele:
f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674
Antworten:
Python 3 ,
95 Bytes83 Bytes[-12 Bytes dank Mr.XCoder :)]
Probieren Sie es online!
Eine Anmerkung zum Algorithmus. Der Algorithmus berechnet das Inkrement in eindeutigen Teilsequenzen, die durch das Bit an einer gegebenen Position t gegeben sind. Das Inkrement für das erste Bit ist immer 1. Der Algorithmus durchläuft dann die Folge der Bits s (t) und addiert das Inkrement v [s (t)]. Bei jedem Schritt wird das Inkrement für das Komplement von s (t), v [1 - s (t)] auf v [1] + v [0] aktualisiert. Die letzte Zahl ist die Summe aller Inkremente.
Es sollte in O (log2 (n)) ausgeführt werden, wobei n die Eingabenummer ist.
quelle
JavaScript (ES6),
5351 BytesTestfälle
Code-Snippet anzeigen
Formatiert und kommentiert
Nicht rekursive Version, 63 Bytes
3 Bytes gespart dank @ThePirateBay
Testfälle
Code-Snippet anzeigen
quelle
map
der Flag-Variablenl
anstelle eines leeren Arrays die innere Funktion (das erste Argument von ) zuweisen .Python 2 , 56 Bytes
Probieren Sie es online!
Nimmt die Methode von NofP .
59 Bytes iterativ:
Probieren Sie es online!
quelle
Gelee , 10 Bytes
Dies nutzt die Verbesserung von @ xnor gegenüber dem @ NofP-Algorithmus .
Probieren Sie es online!
Hintergrund
Sei (a 1 , ..., a n ) eine endliche binäre Folge. Definieren Sie für jede nicht negative ganze Zahl k ≤ n o k als die Anzahl der eindeutigen Teilfolgen von (a 1 , ..., a k ) , die entweder leer sind oder mit 1 enden , z k als die Anzahl der eindeutigen Teilfolgen, die leer sind entweder leer oder mit 0 enden .
Es ist klar, o 0 = z 0 = 1 , da die einzige Untersequenz der leeren Sequenz die leere Sequenz ist.
Für jeden Index k die Gesamtzahl von Untersequenzen von (a 1 , ..., a k ) ist o k + z k - 1 (Subtrahieren 1 trägt der Tatsache Rechnung , dass beide o k und Z k Zählung der leere Sequenz). Die Gesamtzahl der nicht-leerer Subsequenzen ist daher o k + z k - 2 . Die Herausforderung besteht darin, o n + z n - 2 zu berechnen .
Jedes Mal , wenn k> 0 , können wir berechnen o k und z k rekursiv. Es gibt zwei Fälle:
a k = 1
z k = z k-1 , da (a 1 , ..., a k-1 ) und (a 1 , ..., a k-1 , 1) die gleichen Teilfolgen haben, die mit 0 enden .
Für jede der o k - 1 nicht-leeren Subsequenzen von (a 1 , ..., a k ) dieses Ende in 1 , können wir den nachlauf entfernen 1 zu erhalten , eine des o k-1 + z k-1 - 1 Teilfolgen (a 1 , ..., a k-1 ) . Umgekehrt führt das Anhängen einer 1 an jede der letzteren o k-1 + z k-1 - 1 Sequenzen zu einer der o k- 1 früheren Sequenzen. Somit ist o k - 1 = ok-1 + zk-1 - 1 und o k = o k-1 + z k-1 .
a k = 0
Ähnlich wie im vorherigen Fall erhalten wir die rekursiven Formeln o k = o k-1 und z k = z k-1 + o k-1 .
Wie es funktioniert
quelle
05AB1E , 12 Bytes
Probieren Sie es online! Erläuterung: Wie in den anderen Antworten angegeben, ist die Anzahl der Teilfolgen für eine Binärzeichenfolge
a..y0
, die mit einer 1 endet, dieselbe wie für die Binärzeichenfolgea..y
, während die Anzahl, die mit einer 1 endet,0
die Gesamtanzahl der Teilfolgen für die Binärzeichenfolge ist Zeichenfolgea..y
(die jeweils ein0
Suffix erhalten) plus eins für0
sich. Im Gegensatz zu den anderen Antworten schließe ich die leere Untersequenz nicht ein, da dies ein Byte erspart, das den Anfangszustand aufbaut.quelle
Java 8, 97 Bytes
Port von @xnors Python 2-Antwort , was wiederum eine Verbesserung von @NofPs Python 3-Antwort darstellt .
Probieren Sie es hier aus.
Vielleicht ist es eine gute Sache, dass der zeitlich begrenzte Tag vorhanden war, weil ich anfangs Folgendes hatte, um alle Teilsequenzen zu brutalisieren:
Probieren Sie es hier aus.
Das hat auch funktioniert, hat aber für die letzten drei Testfälle viel zu lange gedauert. Ganz zu schweigen davon, dass es viel länger ist (
208 bis204 Bytes ).quelle
6502 Maschinencode (C64), 321 Bytes
Online-Demo
Online-Demo mit Fehlerprüfung (346 Bytes)
Verwendung:
sys49152,[n]
zBsys49152,911188917558917
.Die zeitliche Beschränkung und die Testfälle erfordern Lösungen für die Berechnung von 64-Bit-Zahlen. Daher ist es an der Zeit, zu beweisen, dass der C64 als " moderne Maschine" eingestuft ist " qualifiziert ist;)
Dies erfordert natürlich einiges an Code, das Betriebssystem bietet nichts für ganze Zahlen, die breiter als 16 Bit sind . Der lahme Teil hier: Es ist eine weitere Implementierung (leicht modifiziert) des NofP-Algorithmus resp. xnors verbesserte Variante . Danke für die Idee;)
Erläuterung
Hier ist eine kommentierte Demontage-Liste des relevanten Teils, der den Algorithmus ausführt:
Der Rest ist Eingabe / Ausgabe und Konvertieren zwischen Zeichenfolge und 64-Bit-Ganzzahl ohne Vorzeichen (Little-Endian) unter Verwendung eines Double-Dabble-Algorithmus. Falls Sie interessiert sind, finden Sie hier die gesamte Assembly-Quelle für die Version mit Fehlerprüfung - die "Golfed" -Version befindet sich im Zweig "Golf".
quelle