Słynna sekwencja Fibonacciego F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1)
(dla tego wyzwania zaczynamy od 0).
Twoje wyzwanie: Biorąc pod uwagę, n , wyjście suma wszystkich d XX liczb Fibonacciego dla wszystkich dzielników d z n -tego numeru Fibonacciego. Jeśli wolisz bardziej formalną notację,
Dane wejściowe : dodatnia liczba całkowita n
Wynik : suma
Rozważmy na przykład n=4
. F(4) = 3
Dzielnikami 3 są 1 i 3, więc wynik powinien być F(1) + F(3) = 1 + 2 = 3
.
W przypadku n=6
, F(6) = 8
oraz dzielniki do 8: 1, 2, 4, 8, więc wyjście F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26
.
Przypadki testowe:
1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26
To jest golfowy kod , wygrywa najkrótsza odpowiedź w bajtach. Obowiązują standardowe luki .
code-golf
number-theory
fibonacci
division
Neil A.
źródło
źródło
Galaretka , 7 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło
Mathematica, 29 bajtów
źródło
Mathematica uproszczona , 14 bajtów
No cóż, ostatecznie okazało się to identyczne z rozwiązaniem @ MartinEnder ...
źródło
N
)Japt , 11 bajtów
Wypróbuj online!
źródło
05AB1E , 11 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Haskell, 54 bajty
Przykład użycia:
g 6
->26
. Wypróbuj online!źródło
Alice ,
3836 bajtówDzięki Leo za oszczędność 2 bajtów.
Wypróbuj online!
Niemal na pewno nie optymalne. Przepływ sterowania jest dość skomplikowany i chociaż jestem całkiem zadowolony z liczby bajtów, które zapisały się w porównaniu z poprzednimi wersjami, mam wrażenie, że nadmiernie komplikuję rzeczy, które mogą być prostszym i krótszym rozwiązaniem.
Wyjaśnienie
Najpierw muszę trochę rozwinąć stos adresów zwrotnych Alice (RAS). Podobnie jak wiele innych fungeoidów, Alice ma polecenie skakania w kodzie. Ma jednak także polecenia powrotu do miejsca, z którego przybyłeś, co pozwala dość wygodnie implementować podprogramy. Oczywiście, ponieważ jest to język 2D, podprogramy naprawdę istnieją tylko zgodnie z konwencją. Nic nie stoi na przeszkodzie, abyś wszedł do podprogramu lub go opuścił w inny sposób niż polecenie powrotu (lub w dowolnym punkcie podprogramu), a w zależności od sposobu korzystania z RAS może nie istnieć czysta hierarchia skoku / powrotu.
Zasadniczo jest to realizowane za pomocą polecenia skoku, który
j
przesuwa bieżący adres IP do RAS przed skokiem. Polecenie returnk
wyświetla adres RAS i tam skacze. Jeśli RAS jest pusty,k
nic nie robi.Istnieją również inne sposoby manipulacji RAS. Dwa z nich są istotne dla tego programu:
w
wypycha bieżący adres IP do RAS, nie skacząc gdziekolwiek Jeśli powtórzysz to polecenie, możesz dość łatwo napisać proste pętle&w...k
, co zrobiłem już w poprzednich odpowiedziach.J
jest jak,j
ale nie pamięta bieżącego adresu IP w RAS.Należy również zauważyć, że RAS nie przechowuje żadnych informacji o kierunku IP. Zatem powrót do adresu z
k
zawsze zachowuje bieżący kierunek IP (a zatem także to, czy jesteśmy w trybie kardynalnym, czy zwykłym), niezależnie od tego, w jaki sposób przeszliśmy przez ten adres IPj
lubw
który go przepchnął.W ten sposób zacznijmy od podprogramu w powyższym programie:
Ta procedura podciąga dolny element stosu, n , do góry, a następnie oblicza liczby Fibonacciego F (n) i F (n + 1) (pozostawiając je na górze stosu). Nigdy nie potrzebujemy F (n + 1) , ale zostanie on odrzucony poza podprogramem, ze względu na to, w jaki sposób
&w...k
pętle oddziałują z RAS (który rodzaj wymaga, aby te pętle znajdowały się na końcu podprogramu). Powodem, dla którego bierzemy elementy od dołu zamiast od góry, jest to, że możemy traktować stos bardziej jak kolejkę, co oznacza, że możemy obliczyć wszystkie liczby Fibonacciego za jednym razem, bez konieczności przechowywania ich gdzie indziej.Oto jak działa ten podprogram:
Koniec pętli jest nieco trudny. Dopóki na stosie znajduje się kopia adresu „w”, rozpoczyna się kolejna iteracja. Po ich wyczerpaniu wynik zależy od sposobu wywołania podprogramu. Jeśli podprogram został wywołany z „j”, to ostatnie „k” powraca tam, więc koniec pętli podwaja się jako powrót podprogramu. Jeśli podprogram został wywołany z „J”, a na stosie nadal znajduje się adres z wcześniejszego stosu, przeskakujemy tam. Oznacza to, że jeśli podprogram został wywołany w samej zewnętrznej pętli, to „k” powraca na początek tej zewnętrznej pętli. Jeśli podprogram został wywołany z „J”, ale RAS jest teraz pusty, wówczas to „k” nic nie robi, a IP po prostu porusza się po pętli. Wszystkie trzy przypadki wykorzystamy w programie.
Wreszcie do samego programu.
To tylko dwie szybkie wycieczki do trybu porządkowego, aby odczytać i wydrukować liczby całkowite dziesiętne.
Po tym
i
jest taki,w
który pamięta aktualną pozycję przed przejściem do podprogramu, z powodu drugiego/
. To pierwsze wywołanie podprogramu obliczaF(n)
iF(n+1)
na wejściun
. Potem wskakujemy tutaj, ale teraz przemieszczamy się na wschód, więc pozostali operatorzy programu pracują w trybie kardynalnym. Główny program wygląda następująco:Oto
31J
kolejne wywołanie podprogramu i dlatego oblicza liczbę Fibonacciego.źródło
Aksjomat, 68 bajtów
jakiś test
źródło
Pari / GP , 34 bajty
Wypróbuj online!
źródło
Python 2 ,
8984 bajtów-5 bajtów dzięki ovs
Wypróbuj online!
źródło
R, 77 bajtów
Korzysta z biblioteki „gmp”. Ma to wbudowaną funkcję Fibonacciego i zapewnia możliwość wykonywania dużych liczb. Spowodowało to kilka problemów z sekwencjami i aplikacjami, choć wciąż jest mniejszy niż tworzenie własnej funkcji Fibonacciego.
Wyjaśnienie
Test
Bez użycia gmp
81 bajtów , funkcja rekurencyjna, która jest beznadziejnie wolna po wybraniu dużych (9+) liczb
88 bajtów , formuła Bineta, która będzie działać dobrze z większymi liczbami, ale nadal dość szybko osiąga limit liczb całkowitych
źródło
Perl 6 , 49 bajtów
źródło
CJam , 26 bajtów
Wypróbuj online!
Jestem pewien, że można to zrobić lepiej. Wyjaśnienie:
Chodzi o to, aby mieć tablicę liczb Fibonacciego i dodać iloczyn iloczynu za pomocą tablicy z 1s i 0s, jeśli ta liczba jest lub nie jest dzielnikiem wejścia.
źródło
JavaScript (ES6),
7665 bajtówPrzypadki testowe
Pokaż fragment kodu
źródło
JavaScript (ES6),
10510410310197 bajtówSpróbuj
źródło
(z=g(i)/y)>~~z
na(z=g(i)/y)%1
, jeśli tylko sprawdzasz, żez
jest to liczba całkowita.g(z)
na,g(z|0)
ale przywracając nas do tej samej liczby bajtów.Q, 75 bajtów
źródło
C (gcc) ,
939080 bajtówWypróbuj online!
źródło
Dodaj ++ , 89 bajtów
Wypróbuj online!
źródło