Rozważ wyrażenie 2^2^...^2
z n
operatorami ^
. Operator ^
oznacza potęgowanie („do potęgi”). Załóżmy, że nie ma domyślnej asocjatywności, więc wyrażenie musi być całkowicie nawiasowane, aby stało się jednoznaczne. Liczbę sposobów nawiasowania wyrażenia podano w liczbach katalońskich C_n=(2n)!/(n+1)!/n!
.
Czasami różne nawiasy dają na przykład ten sam wynik liczbowy (2^2)^(2^2)=((2^2)^2)^2
, więc liczba różnych możliwych wyników liczbowych dla danej n
jest mniejsza niż C_n
dla wszystkich n>1
. Sekwencja zaczyna się 1, 1, 2, 4, 8, ...
w przeciwieństwie do liczb katalońskich1, 2, 5, 14, 42, ...
Problem polega na tym, aby napisać najszybszy program (lub funkcja), która przyjmuje n
jako dane wejściowe i zwraca liczbę różnych możliwych wyników liczbowych wyrażenia 2^2^...^2
z n
operatorami ^
. Wydajność nie powinna ulec znacznemu pogorszeniu w miarę n
wzrostu, więc bezpośrednie obliczenie wież dużej mocy jest prawdopodobnie złym pomysłem.
źródło
2^n
, a zatem śledzenie czegokolwiek byłoby zbędnen
. Tj. Samo stosowanie reguł potęgowania wydaje się rozsądne. Jednak z pewnością jest to mądrzejszy i całkowicie algebraiczny sposób.n
jest wciąż zbyt duży, by go obliczyć. Nadal dobrze zauważone. Być może rekurencyjna reprezentacja w postaci „1 lub 2 ^ (...) lub (...) + (...)”; ale nadal masz problem ze znormalizowaniem takiej reprezentacji liczby (lub porównać dwie reprezentacje dla równości wartości).n
dwie pary iC_n=(2n)!/(n+1)!/n!
powinna być liczba nawiasów, to dla n = 3 powinno to być 5, prawda? Rozumiem(2^2)^2
i2^(2^2)
, ale jakie są pozostałe trzy kombinacje? Myślę, że C_n podaje liczbę nawiasów dla n + 1 dwójki.Odpowiedzi:
Python 2.7
Podejście to wykorzystuje następujące uwagi:
Każda liczba całkowita może być reprezentowana jako suma potęg dwóch. Potęgi potęg dwójki można również przedstawić jako potęgi dwójki. Na przykład:
Te wyrażenia, z którymi się skończyliśmy, mogą być reprezentowane jako zestawy zestawów (w Pythonie użyłem wbudowanego
frozenset
):0
staje się pustym zestawem{}
.2^a
staje się zbiorem zawierającym zbiór reprezentującya
. Np .:1 = 2^0 -> {{}}
i2 = 2^(2^0) -> {{{}}}
.a+b
staje się konkatenacją zbiorów reprezentującycha
ib
. Na przykład,3 = 2^(2^0) + 2^0 -> {{{}},{}}
Okazuje się, że wyrażenia formularza
2^2^...^2
można łatwo przekształcić w ich unikatową reprezentację zestawu, nawet gdy wartość liczbowa jest zbyt duża, aby można ją było zapisać jako liczbę całkowitą.Ponieważ
n=20
działa to w 8.7s na CPython 2.7.5 na moim komputerze (nieco wolniej w Pythonie 3 i znacznie wolniej w PyPy):(Koncepcja dekoratora notatek została skopiowana z http://code.activestate.com/recipes/578231- prawdopodobnie-the-fastest-memoization-decorator-in-the-/ .)
Wynik:
Czasy dla różnych
n
:Każda
n
powyżej 21 powoduje błąd pamięci na moim komputerze.Byłbym zainteresowany, gdyby ktokolwiek mógł to przyspieszyć, tłumacząc go na inny język.
Edycja: Zoptymalizowana
get_results
funkcja. Ponadto użycie Python 2.7.5 zamiast 2.7.2 sprawiło, że działał on nieco szybciej.źródło
(a^b)^c = (a^c)^b
, i nadal jest ono znacznie wolniejsze niż ta implementacja Pythona.DO#
Jest to tłumaczenie kodu Python flornquake'a na język C # przy użyciu procedury dodawania niższego poziomu, która zapewnia umiarkowane przyspieszenie w stosunku do tłumaczenia bezpośredniego. To nie jest najbardziej zoptymalizowana wersja, jaką mam, ale to trochę dłużej, ponieważ musi przechowywać zarówno strukturę drzewa, jak i wartości.
źródło