Wprowadzenie (może zostać zignorowane)
Umieszczenie wszystkich liczb dodatnich w regularnej kolejności (1, 2, 3, ...) jest trochę nudne, prawda? Oto szereg wyzwań związanych z permutacjami (przetasowaniami) wszystkich liczb dodatnich. Jest to piąte wyzwanie w tej serii (linki do pierwszego , drugiego , trzeciego i czwartego wyzwania).
W tym wyzwaniu spotkamy tablicę Wythoffa, która jest splecioną lawiną sekwencji Fibonacciego i sekwencji Beatty!
Te liczby Fibonacciego są prawdopodobnie dla większości z Was znany sekwencja. Biorąc pod uwagę dwie liczby początkowe i , następujące są podane przez: dla .
Sekwencja Beatty , ponieważ parametr oznacza: dla . Jedną z właściwości sekwencji Beatty jest to, że dla każdego parametru r jest dokładnie jeden parametr s = r / (r-1) , tak że sekwencje Beatty dla tych parametrów są rozłączne i połączone ze sobą, obejmują wszystkie liczby naturalne z wyłączeniem 0 (np .: B ^ r \ cup B ^ {r / (r-1)} = \ Bbb {N} \ setminus \ {0 \} ).
Teraz nadchodzi zadziwiająca część: możesz stworzyć tablicę, w której każdy wiersz jest sekwencją Fibonacciego, a każda kolumna jest sekwencją Beatty. Ta tablica jest tablicą Wythoffa . Najlepsze jest to, że każda liczba dodatnia pojawia się dokładnie raz w tej tablicy! Tablica wygląda następująco:
1 2 3 5 8 13 21 34 55 89 144 ...
4 7 11 18 29 47 76 123 199 322 521 ...
6 10 16 26 42 68 110 178 288 466 754 ...
9 15 24 39 63 102 165 267 432 699 1131 ...
12 20 32 52 84 136 220 356 576 932 1508 ...
14 23 37 60 97 157 254 411 665 1076 1741 ...
17 28 45 73 118 191 309 500 809 1309 2118 ...
19 31 50 81 131 212 343 555 898 1453 2351 ...
22 36 58 94 152 246 398 644 1042 1686 2728 ...
25 41 66 107 173 280 453 733 1186 1919 3105 ...
27 44 71 115 186 301 487 788 1275 2063 3338 ...
...
Element w wierszu kolumnie jest zdefiniowany jako:
gdzie to złoty współczynnik: .
Jeśli podążymy za anty-przekątnymi tej tablicy, otrzymamy A035513 , który jest sekwencją docelową dla tego wyzwania (zauważ, że ta sekwencja jest dodawana do OEIS przez samego Neila Sloane !). Ponieważ jest to wyzwanie „czystej sekwencji”, zadaniem jest wyprowadzenie dla danego jako danych wejściowych, gdzie to A035513 .
Istnieją różne strategie, które możesz zastosować, aby dostać się do , co sprawia, że wyzwanie (moim zdaniem) jest naprawdę interesujące.
Zadanie
Biorąc pod uwagę liczbę całkowitą , wypisz w formacie liczb całkowitych, gdzie to A035513 .
Uwaga: tutaj zakłada się indeksowanie 1; możesz użyć indeksowania opartego na 0, więc itd. Podaj to w swojej odpowiedzi, jeśli zdecydujesz się na to.
Przypadki testowe
Input | Output
---------------
1 | 1
5 | 7
20 | 20
50 | 136
78 | 30
123 | 3194
1234 | 8212236486
3000 | 814
9999 | 108240
29890 | 637
Może być fajnie wiedzieć, że największym dla jest
Zasady
- Wejścia i wyjścia są liczbami całkowitymi
- Twój program powinien co najmniej obsługiwać dane wejściowe w zakresie od 1 do 32767). Zauważ, że idzie w górę do 30 cyfr w tym zakresie ...
- Niepoprawne dane wejściowe (0, liczby zmiennoprzecinkowe, ciągi, wartości ujemne itp.) Mogą prowadzić do nieprzewidzianych wyników, błędów lub (nie) zdefiniowanego zachowania.
- Obowiązują domyślne reguły we / wy .
- Domyślne luki są zabronione.
- To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach
999
nie9999
Odpowiedzi:
Galaretka ,
2724 bajtówWypróbuj online!
Łącze monadyczne z wykorzystaniem indeksowania 1. Dzięki @JonathanAllan za lepszy sposób uzyskiwania wiersza i kolumn z
n
i oszczędzania 3 bajtów. W najkrótszej formie jest zbyt wolny, aby mógł być większy w TIO, więc następujące Wypróbuj online! zmniejsza rozmiar początkowej listy wierszy i kolumn kosztem trzech bajtów.Wyjaśnienie
Uwaga: jest to oparte na opisie kodu Python na stronie OEIS.
źródło
...×⁹r‘ÆḞ¤Sð/
zapisuje jeden w wersji amalgamacji ( TIO )R ,
143130124123 bajtówWypróbuj online!
splits
k
istnieje tylko po to, aby zapobiec wymuszeniudrop=F
argumentacji wm[-1:-2,]
sprawien=1
.Podziękowania dla Neila za wskazanie 1-bajtowego golfa.
R ,
150138132 bajtówWypróbuj online!
splits
nth
Dzięki Robinowi Ryderowi za
T[2]=1
podstęp w generowaniu sekwencji Fibonacciego.Oba rozwiązania są wysoce nieefektywne, tworząc
nxn
macierz (najprawdopodobniej)double
s, ponieważ R promujeinteger
(32-bit podpisany)double
automatycznie po przepełnieniu, ale drugie powinno być znacznie szybsze. Przyjmowanien
jako bignum powinno działać automatycznie, przy użyciu połączeniagmp::as.bigz(n)
, gdyby utrata precyzjidouble
była niepokojąca, a wtedy byłby językR + gmp
.źródło
(1+5^.5)/2
zamiast(.5+5^.5/2)
?Wolfram Language (Mathematica) , 90 bajtów
Wypróbuj online!
źródło
Galaretka , 30 bajtów
Wypróbuj online!
Jest to trochę powolne, ale ogromną poprawę wprowadzono z prefiksem
Ḥ½Ċ
(podwójne, pierwiastek kwadratowy, sufit), jak w tym zestawie testów .źródło
740496902
jest wynikiem dla999
Węgiel drzewny , 54 bajty
Wypróbuj online! Link jest do pełnej wersji kodu. 0-indeksowane. Używa tylko arytmetyki liczb całkowitych, więc działa dla dowolnych dużych wartości. Wyjaśnienie:
Wejście
q
.Oblicz antydiagonalny, odejmując coraz większe liczby
q
, co kończy się docelową liczbą wierszym
.Oblicz pierwsze
m+1
warunki A019446 , chociaż interesuje nas tylkom
th.Oblicz pierwsze
n+4
warunki uogólnionej serii Fibonacciego, która zaczyna się od[a(m), m]
. Terminy tej sekwencji sąm
terminami A019446 , A001477 , A000201 , A003622 , A035336 ; te dwie ostatnie są pierwszymi dwiema kolumnami tablicy Wythoffa, a zatem sekwencja ta jest kontynuowana wraz z resztą trzeciegom
rzędu tablicy.Podaj żądany termin.
źródło