Wszyscy znamy sekwencję Fibonacciego :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
Zamiast tego f(n) = f(n-1) + f(n-2)
weźmiemy cyfrową sumę poprzednich 2 wpisów.
Sekwencja powinna zacząć się od tego 0, 1
, po czym różnice są szybko widoczne. Ta lista jest indeksowana na 0, możesz również użyć indeksowania 1, którego użyłeś.
f(0) = 0
f(1) = 1
f(2) = 1 # 0 + 1
f(3) = 2 # 1 + 1
f(4) = 3 # 1 + 2
f(5) = 5 # 2 + 3
f(6) = 8 # 3 + 5
f(7) = 13 # 8 + 5
f(8) = 12 # 8 + 1 + 3
f(9) = 7 # 1 + 3 + 1 + 2
f(10) = 10 # 1 + 2 + 7
f(11) = 8 # 7 + 1 + 0
f(12) = 9 # 1 + 0 + 8
f(13) = 17 # 8 + 9
f(14) = 17 # 9 + 1 + 7
f(15) = 16 # 1 + 7 + 1 + 7
f(16) = 15 # 1 + 7 + 1 + 6
f(17) = 13 # 1 + 6 + 1 + 5
f(18) = 10 # 1 + 5 + 1 + 3
f(19) = 5 # 1 + 3 + 1 + 0
f(20) = 6 # 1 + 0 + 5
f(21) = 11 # 5 + 6
f(22) = 8 # 6 + 1 + 1
f(23) = 10 # 1 + 1 + 8
f(24) = 9 # 8 + 1 + 0
f(25) = 10 # 1 + 0 + 9
f(26) = 10 # 9 + 1 + 0
f(27) = 2 # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)
Uwaga: nie zauważyłem powtórzenia, dopóki nie opublikowałem samego wyzwania, a tutaj myślałem, że nie będzie możliwe napisanie kolejnej powieści Fibonacciego.
Twoim zadaniem jest, biorąc pod uwagę liczbę n
, wyprowadzenie n-tej cyfry tej sekwencji.
3 pierwsze cyfry: [0,1,1]
,
24-cyfrowy powtarzalny wzór: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]
Wskazówka: Być może będziesz w stanie wykorzystać to powtórzenie na swoją korzyść.
To jest golf golfowy , zwycięzcą jest najniższa liczba bajtów.
BONUS: Jeśli użyjesz powtórzenia w swojej odpowiedzi, przyznam odpowiedź o najniższej liczbie bajtów, która korzysta z powtórzenia w sekwencji, nagrodę 100 punktów. Należy ją przesłać jako część oryginalnej odpowiedzi, po oryginalnej odpowiedzi. Zobacz ten post jako przykład tego, o czym mówię: https://codegolf.stackexchange.com/a/108972/59376
Aby zakwalifikować się do tej premii, Twój kod musi działać w stałym czasie ( O(1)
) z wyjaśnieniem.
Zwycięzca bonusowy: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis wygrał.
Najbardziej wyjątkowa implementacja: https://codegolf.stackexchange.com/a/108970/59376
( Otrzyma również 100 punktów, sfinalizowane po wybraniu poprawnej odpowiedzi)
źródło
%24
„normalne” rozwiązanie?O(1)
. Twój kod powinien działać w stałym czasie, jeśli naprawdę wykorzystuje powtórzenie.Odpowiedzi:
Oaza , 5 bajtów
Kod:
Wypróbuj online!
Wersja rozszerzona:
Wyjaśnienie:
źródło
JavaScript (ES6), 45 bajtów
x
iy
nie mogą być oba9
, ponieważ wymagałoby to poprzedniego numeru0
, więc ich suma cyfrowa nie może przekroczyć17
. Oznacza to, że cyfrowy pierwiastek dla liczb większych niż9
jest taki sam, jak reszta modulo9
.źródło
Python 2, 53 bajty
Funkcja rekurencyjna. Przypadki bazowe
n=0
in=1
wydajnościn
, większej liczby oblicza wartość wywołującf(n-1)
if(n-2)
konwersji do każdego ciągu, łącząc dwa łańcuchy, przekształcając każdy znak na całkowitą użyciemmap
zint
funkcji, a następnie sumuje otrzymaną listą.Korzystając z informacji modulo-24, mogę obecnie uzyskać 56-bajtową nierekurencyjną funkcję bez nazwy:
źródło
JavaScript (ES6), 34 bajty
Może zamrozić przeglądarkę dla danych wejściowych powyżej 27 lub więcej, ale działa dla wszystkich wartości wejściowych. Można to zweryfikować za pomocą prostej pamięci podręcznej:
Jak wskazano w genialnej odpowiedzi Neila , wyjście nigdy nie może przekroczyć 17, więc suma cyfrowa dowolnego wyjścia powyżej 9 jest równa
n%9
. Działa to również z wyjściami poniżej 9; możemy sprawić, że będzie działał również dla 9, odejmując 1 z~-
przed modułem, a następnie dodając z powrotem 1 po.Najlepsze, co mogę zrobić z kodowaniem na twardo, to 50 bajtów:
źródło
Galaretka , 8 bajtów
Wypróbuj online!
Jak to działa
Alternatywne rozwiązanie, 19 bajtów, stały czas
Wypróbuj online!
Jak to działa
źródło
JavaScript (ES6),
52 4645 bajtówStosowanie
Wydajność
Wyjaśnienie
Ta funkcja sprawdza, czy dane wejściowe są mniejsze niż 2, a jeśli tak, zwraca dane wejściowe. W przeciwnym razie tworzy tablicę dwóch wartości, które są dołączane do siebie jako ciągi znaków. Te dwie wartości są wynikiem wywołania funkcji za pomocą
input - 1
iinput - 2
....
Operatora dzieli to ciąg znaków w postaci tablicy, która jest następnie jest przekształcona do łańcucha ponownie, ale teraz z+
es pomiędzy wartościami. Ten ciąg jest następnie interpretowany jako kod, więc suma jest obliczana, a następnie zwracana.Jest to algorytm podwójnie rekurencyjny, co czyni go dość nieefektywnym. Do wprowadzenia potrzeba 2
n-2
wywołań funkcjin
. Jako takie, oto dłuższe, ale szybsze rozwiązanie. Dzięki ETHproductions za wymyślenie tego.źródło
[..._(--$)+[_(--$)]]
:-)05AB1E , 8 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
CJam,
2220 bajtówZaoszczędzono 2 bajty dzięki Martinowi Enderowi
Prosty algorytm rekurencyjny, nic szczególnego. 0-indeksowane.
Wypróbuj online! lub test na 0-50 (faktycznie działa dość szybko).
Wyjaśnienie
CJam, 42 bajty
Rozwiązanie wykorzystujące powtórzenie. Algorytm podobny do rozwiązania Jonathana Allana.
Wypróbuj online!
źródło
Perl 6 ,
4137 bajtówSpróbuj
Spróbuj
źródło
*.comb.sum+*.comb.sum
.MATL , 15 bajtów
Wypróbuj online!
źródło
Python 2 ,
5446 bajtówMocno zainspirowany odpowiedzią ESET @ETHproductions .
Wypróbuj online!
źródło
C, 96 bajtów
lub 61 bajtów liczących kody ucieczki jako 1 bajt każdy
0 zindeksowanych. Podobnie do niektórych innych odpowiedzi indeksuję tabelę wartości, ale skompresowałem ją do 4-bajtowych porcji. Nie zawracałem sobie głowy badaniem wersji mod 24, ponieważ nie sądziłem, że jest tak interesująca, ponieważ inni już to zrobili, ale spójrzmy prawdzie w oczy, C i tak nie wygra.
wyjaśnienie:
Wypróbuj online!
źródło
Japt ,
2725 bajtówWypróbuj online!
Zaoszczędzono 2 bajty dzięki produktom ETH.
źródło
´
zamiast--
zapisać dwa bajty.Haskell , 54 bajty
Wypróbuj online! Stosowanie:
(g!!) 12
źródło
Mathematica, 49 bajtów
Prosta definicja rekurencyjna. Po chwili robi się dość wolny.
Mathematica,
7971 bajtówTwarde kodowanie wzoru okresowego. Błyskawicznie i satysfakcjonująco obraźliwe dla Mathematiki :) Dzięki JungHwan Min za oszczędność 8 bajtów!
źródło
LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ"
jest o 8 bajtów krótszy niż43626804920391712116157158790~IntegerDigits~18
.LetterNumber
...Python 2 , 56 bajtów
Proste iteracyjne rozwiązanie.
Wypróbuj online!
Używanie
(a%9or a)+(b%9or b)
okazało się być krótsze niżsum(map(int(`a`+`b`)))
!źródło
sum(map(int,a+b))
(nie mogę dowiedzieć się, jak używać `w komentarzach)PowerShell , 79 bajtów
Wypróbuj online!
Długie nudne iteracyjne rozwiązanie, które wykonuje bezpośrednie obliczenia sumy cyfr w każdej
for
pętli. Na końcu pętli potrzebna jest liczba$b
, więc pozostaje ona w potoku, a dane wyjściowe są niejawne. Zauważ, że jeśli wejście jest0
, wtedy pętla nie wejdzie, ponieważ warunek jest fałszywy, więc$b
pozostaje0
.źródło
Partia, 85 bajtów
Zastanawiałem się, jak przenieść moją odpowiedź JavaScript na partię, ale wskazówka była w rozwiązaniu Python @ Dennisa.
źródło
Pyth, 20 bajtów
Program, który pobiera liczbę całkowitą zerową i wypisuje wynik.
Zestaw testowy (pierwsza część do formatowania)
Jak to działa
[Wyjaśnienie nastąpi później]
źródło
Rubinowy, 58 bajtów
Proste zakodowane rozwiązanie.
źródło
ułożone w stos , 40 bajtów
Ta lambda jest równoważna następującej lambda:
Wypróbuj online!
źródło
Oktawa, 148 bajtów
źródło
Haskell, 151 bajtów
Wywołaj funkcję
f 123456789012345678901234567890123456789012345678
na przykład za pomocą.Kod działa również z bardzo dużymi indeksami. Dzięki zaimplementowanej funkcjonalności modulo 24 jest bardzo szybki.
Nieskompresowany kod:
źródło
R, 90 bajtów
Strasznie długie rozwiązanie, ale lepsze niż 108, które pierwotnie miałem. Podejrzewam, że istnieje o wiele lepszy sposób, ale nie widzę tego w tej chwili.
Jest to nienazwana funkcja, która używa
gsub
iscan(t=
dzieli liczby w wektorze na cyfry. Ich suma jest dodawana do wektora podczas upuszczania pierwszego elementu.repeat
służy do przechodzenia międzyn
czasami sekwencji, a wynik jest pierwszą pozycją wektora.źródło
PHP, 80 bajtów
Wersja online
źródło
Mathematica, 67 bajtów
źródło