Podsekwencja to dowolna sekwencja, którą można uzyskać z innej, usuwając dowolną liczbę znaków. Wyraźne niepustymi subsekwencje 100
są 0
, 1
, 00
, 10
, 100
. Wyraźne niepustymi subsekwencje 1010
są 0
, 1
, 00
, 01
, 10
, 11
, 010
, 100
, 101
, 110
, 1010
.
Napisz program lub funkcję, która podając dodatnią liczbę całkowitą n zwraca liczbę różnych niepustych podciągów binarnego rozszerzenia n .
Przykład: ponieważ 4
jest 100
binarny i widzieliśmy, że ma pięć różnych niepustych podsekwencji powyżej, więc f(4) = 5
. Począwszy od n = 1 , sekwencja zaczyna się:
1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12
Jednak Twój program musi działać dla dowolnego n <2 50 w ciągu sekundy na dowolnej nowoczesnej maszynie. Kilka dużych przykładów:
f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674
Odpowiedzi:
Python 3 ,
95 bajtów83 bajty[-12 bajtów dzięki Mr.XCoder :)]
Wypróbuj online!
Uwaga na temat algorytmu. Algorytm oblicza przyrost w unikalnych podsekwencjach podanych przez bit w danej pozycji t. Przyrost dla pierwszego bitu wynosi zawsze 1. Algorytm przebiega następnie przez sekwencję bitów s (t) i dodaje przyrost v [s (t)]. Na każdym kroku przyrost dla uzupełnienia s (t), v [1 - s (t)] jest aktualizowany do v [1] + v [0]. Ostateczna liczba jest sumą wszystkich przyrostów.
Powinien działać w O (log2 (n)), gdzie n jest liczbą wejściową.
źródło
JavaScript (ES6),
5351 bajtówPrzypadki testowe
Pokaż fragment kodu
Sformatowane i skomentowane
Wersja nierekurencyjna, 63 bajty
Zaoszczędź 3 bajty dzięki @ThePirateBay
Przypadki testowe
Pokaż fragment kodu
źródło
map
) zmiennej zmiennejl
zamiast pustej tablicy.Python 2 , 56 bajtów
Wypróbuj online!
Biorąc metodę z NofP .
59 bajtów iteracyjnie:
Wypróbuj online!
źródło
Galaretka , 10 bajtów
Wykorzystuje poprawa @ XNOR jest na @ algorytmu NofP użytkownika .
Wypróbuj online!
tło
Niech (a 1 , ..., a n ) będzie skończoną sekwencją binarną. Dla każdej nieujemnej liczby całkowitej k ≤ n zdefiniuj o k jako liczbę unikalnych podsekwencji (a 1 , ..., k ), które są albo puste, albo kończą się na 1 , z k jako liczba niepowtarzalnych podsekwencji, które są albo pusty, albo kończy się na 0 .
Oczywiście o 0 = z 0 = 1 , ponieważ jedynym podsekwencją pustej sekwencji jest pusta sekwencja.
Dla każdego indeksu k , całkowita liczba podciągów (a 1 , ..., a k ) jest o k + Z k - 1 (odejmowanie 1 rachunki za fakt, że zarówno o k a z k policzyć pusty sekwencja). Całkowita liczba niepustych podsekwencji wynosi zatem o k + z k - 2 . Wyzwanie polega na obliczeniu o n + z n - 2 .
Ilekroć k> 0 , możemy obliczyć o k a z k rekurencyjnie. Istnieją dwa przypadki:
a k = 1
z k = z k-1 , ponieważ (a 1 , ..., k-1 ) i (a 1 , ..., k-1 , 1) mają te same podsekwencje, które kończą się na 0 .
Dla każdego z niepustych podsekwencji o k - 1 (a 1 , ..., a k ), które kończą się na 1 , możemy usunąć końcowy 1, aby uzyskać jeden z o k-1 + z k-1 - 1 podsekwencje (a 1 , ..., k-1 ) . I odwrotnie, dodanie 1 do każdej z ostatnich sekwencji o k-1 + z k-1 - 1 daje jedną z poprzednich sekwencji o k - 1 . Zatem o k - 1 = ok-1 + zk-1 - 1 oraz o k = o k-1 + z k-1 .
k = 0
Podobnie jak w poprzednim przypadku, otrzymujemy wzory rekurencyjne o k = o k-1 i z k = z k-1 + o k-1 .
Jak to działa
źródło
05AB1E , 12 bajtów
Wypróbuj online! Objaśnienie: Jak wskazano w innych odpowiedziach, liczba podsekwencji dla ciągu binarnego
a..y0
kończących się na 1 jest taka sama jak liczba dla ciągu binarnegoa..y
, podczas gdy liczba kończąca się na0
jest całkowitą liczbą podsekwencji dla binarnego stringa..y
(z których każdy zyskuje0
przyrostek) plus jeden dla0
siebie. W przeciwieństwie do innych odpowiedzi nie dołączam pustego podsekwencji, ponieważ oszczędza to bajt konstruujący stan początkowy.źródło
Java 8, 97 bajtów
Port odpowiedzi @xnor na Python 2 , co z kolei jest ulepszeniem odpowiedzi @NofP na Python 3 .
Wypróbuj tutaj.
Może to dobrze, że znacznik czasu ograniczonego był obecny, ponieważ początkowo miałem następujące przypadki, aby brutalizować wszystkie podsekwencje:
Wypróbuj tutaj.
Co również działało, ale trwało zbyt długo w przypadku ostatnich trzech przypadków testowych. Nie wspominając już, że jest znacznie dłuższy (
208204 bajtów ).źródło
Kod maszynowy 6502 (C64), 321 bajtów
Demo online
Demo online ze sprawdzaniem błędów (346 bajtów)
Zastosowanie:
sys49152,[n]
npsys49152,911188917558917
.Ograniczenie czasu i przypadki testowe wymagają rozwiązań do obliczania liczb 64-bitowych, więc czas na udowodnienie, że C64 kwalifikuje się jako „ nowoczesna maszyna ”;)
Oczywiście wymaga to sporo kodu, system operacyjny nie zapewnia niczego dla liczb całkowitych szerszych niż 16 bitów . Lame część tutaj: to kolejna implementacja (nieco zmodyfikowana) algorytmu NofP lub. ulepszony wariant xnora . Dzięki za pomysł;)
Wyjaśnienie
Oto skomentowana lista demontażu odpowiedniej części wykonującej algorytm:
Reszta to wejście / wyjście i konwersja między ciągiem a 64-bitową liczbą całkowitą bez znaku (little-endian) przy użyciu algorytmu podwójnego dabla. Jeśli jesteś zainteresowany, oto całe źródło zestawu dla wersji z kontrolą błędów - wersja „golfowa” znajduje się w gałęzi „golf”.
źródło