Funkcja półwykładnicza to taka, która po złożeniu daje funkcję wykładniczą. Na przykład jeśli f(f(x)) = 2^x
, to f
byłaby funkcja półwykładnicza. W tym wyzwaniu obliczysz określoną funkcję półwykładniczą.
W szczególności obliczymy funkcję od liczb całkowitych nieujemnych do liczb całkowitych nieujemnych o następujących właściwościach:
Monotonicznie rośnie: jeśli
x < y
, tof(x) < f(y)
Co najmniej połowę wykładniczą: Dla wszystkich
x
,f(f(x)) >= 2^x
Leksykograficznie najmniejszy: Spośród wszystkich funkcji o powyższych właściwościach wypisz tę, która minimalizuje
f(0)
, co przy takim wyborze minimalizujef(1)
, a następnief(2)
itd.
Początkowe wartości tej funkcji dla danych wejściowych 0, 1, 2, ...
to:
[1, 2, 3, 4, 8, 9, 10, 11, 16, 32, 64, 128, 129, 130, 131, 132, 256, 257, ...]
Możesz wyprowadzić tę funkcję za pomocą dowolnej z następujących metod, albo jako funkcja, albo jako pełny program:
Weź
x
jako wejście, wyjścief(x)
.Weź
x
jako dane wejściowe, wypisz pierwszex
wartościf
.Nieskończone wyświetlanie wszystkich
f
.
Jeśli chcesz pobierać x
i generować f(x)
, x
musi być zerowany.
To jest golfowy kod - wygrywa najkrótszy kod w bajtach. Standardowe luki są jak zawsze zakazane.
Odpowiedzi:
JavaScript (ES7),
5148 bajtówZaoszczędź 3 bajty dzięki @Arnauld
Pobiera n i wysyła n -ty element w sekwencji.
JavaScript (ES7),
706864 bajtówFunkcja rekurencyjna, która przyjmuje
x
i zwraca pierwszex
elementy sekwencji jako tablicę.Jak to działa
Tablica a jest generowana proceduralnie, po jednym elemencie na raz, aż osiągnie pożądaną długość. (Port nieskończonej techniki zastosowanej w doskonałej odpowiedzi Xnora w Pythonie prawdopodobnie byłby krótszy.)
Możemy dokonać następującej obserwacji dla każdego indeksu i (indeksowanego 0):
Jest to prawdą, ponieważ f (f (j)) musi wynosić co najmniej 2 j , a f (f (j)) jest równoważne z [a [j]] , co z kolei jest równoważne z [i] .
Zwykle poprawna opcja to dokładnie 2 j . Jednak w przypadku liczby pojedynczej i = 2 , 2 istnieje w tablicy o indeksie j = 1 , co oznacza, że 2 j będzie równe 2 - ale to oznacza, że mielibyśmy 2 zarówno na [1], jak i [2] . Aby obejść ten problem, bierzemy maksymalnie 2 j oraz [i-1] + 1 (jeden więcej niż poprzedni element), co daje 3 dla i = 2 .
Ta technika zdarza się również, aby zadecydować, czy j istnieje - jeśli nie,
.indexOf()
metoda JS zwraca -1 , co prowadzi do przyjęcia maksimum [i-1] + 1 i 2 -1 = 0,5 . Ponieważ wszystkie elementy w sekwencji mają co najmniej 1 , zawsze zwróci poprzedni element plus jeden.(Piszę to wyjaśnienie późno w nocy, więc proszę dać mi znać, jeśli coś jest mylące lub coś przeoczyłem)
źródło
272
i wyższe dają nieprawidłowe odpowiedzi z powodu problemów z przepełnieniem liczb całkowitych. To dobrze, ponieważ działa do limitu typu danych.2**
zamiast,1<<
mam nadzieję, naprawić problem..99
zabija rozwiązanie. Ale po co używać,+.99
a nie tylko+.9
? Co za różnica?Math.log2(...)
i musiałem obliczyć pułap. Teraz nie jest wcale potrzebny. Dzięki! Przyjrzę się temu2**
-2**...+.99|0
początkowo używałem, ale1<<
był krótszy, ponieważ nie potrzebowałem|0
. Teraz myślę, że nie ma różnicy ...Python 2 , 60 bajtów
Wypróbuj online!
Drukuje na zawsze.
Python , 61 bajtów
Wypróbuj online!
Funkcja. Dane wyjściowe
True
zamiast1
.źródło
Perl 5, 53 + 1 (
-p
) = 54 bajtówWypróbuj online
źródło
Bash, 66 bajtów
Wypróbuj online
źródło
Galaretka , 14 bajtów
Wypróbuj online!
Jak to działa
źródło
Python 2 , 111 bajtów
Wypróbuj online!
Jest to znacząca modyfikacja odpowiedzi user202729 . Opublikowałbym to ulepszenie jako komentarz, ale odpowiedź została usunięta, więc komentarze zostały wyłączone.
źródło
x**2
jest zbyt mały.x=1000
. Możesz spróbować2**x
- strasznie duży, ale codegolf to codegolf.2**x
tworzy zbyt duży zakres, aby Python mógł kontynuować.Szybki , 137 bajtów
Pobiera dane wejściowe jako
Int
(liczba całkowita) i drukuje jako[Int]
(tablica liczb całkowitych).Wersja bez golfa
źródło
?
?