Alice , 38 36 bajtów
Dzięki Leo za oszczędność 2 bajtów.
/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+
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 jprzesuwa bieżący adres IP do RAS przed skokiem. Polecenie return kwyświetla adres RAS i tam skacze. Jeśli RAS jest pusty, knic nie robi.
Istnieją również inne sposoby manipulacji RAS. Dwa z nich są istotne dla tego programu:
wwypycha 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.Jjest jak, jale 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 kzawsze 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 IP jlub wktóry go przepchnął.
W ten sposób zacznijmy od podprogramu w powyższym programie:
01dt,t&w.2,+k
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...kpę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:
Stack
01 Push 0 and 1, to initialise Fibonacci sequence. [n ... 0 1]
dt, Pull bottom element n to top. [... 0 1 n]
t&w Run this loop n times... [... F(i-2) F(i-1)]
. Duplicate F(i-1). [... F(i-2) F(i-1) F(i-1)]
2, Pull up F(i-2). [... F(i-1) F(i-1) F(i-2)]
+ Add them together to get F(i). [... F(i-1) F(i)]
k End of loop.
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.
/o....
\i@...
To tylko dwie szybkie wycieczki do trybu porządkowego, aby odczytać i wydrukować liczby całkowite dziesiętne.
Po tym ijest taki, wktóry pamięta aktualną pozycję przed przejściem do podprogramu, z powodu drugiego /. To pierwsze wywołanie podprogramu oblicza F(n)i F(n+1)na wejściu n. 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:
;B1dt&w;31J;d&+
^^^
Oto 31Jkolejne wywołanie podprogramu i dlatego oblicza liczbę Fibonacciego.
Stack
[F(n) F(n+1)]
; Discard F(n+1). [F(n)]
B Push all divisors of F(n). [d_1 d_2 ... d_p]
1 Push 1. This value is arbitrary. [d_1 d_2 ... d_p 1]
The reason we need it is due to
the fact that we don't want to run
any code after our nested loops, so
the upcoming outer loop over all
divisors will *start* with ';' to
discard F(d+1). But on the first
iteration we haven't called the
subroutine yet, so we need some
dummy value we can discard.
dt&w Run this loop once for each element [d_1 d_2 ... d_p 1]
in the stack. Note that this is once OR
more than we have divisors. But since [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)]
we're treating the stack as a queue,
the last iteration will process the
first divisor for a second time.
Luckily, the first divisor is always
1 and F(1) = 1, so it doesn't matter
how often we process this one.
; Discard the dummy value on the [d_1 d_2 ... d_p]
first iteration and F(d+1) of OR
the previous divisor on subsequent [d_i d_(i+1) ... F(d_(i-1))]
iterations.
31J Call the subroutine without pushing [d_(i+1) ... F(d_i) F(d_i+1)]
the current address on the RAS.
Thereby, this doubles as our outer
loop end. As long as there's an
address left from the 'w', the end
of the subroutine will jump there
and start another iteration for the
next divisor. Once that's done, the
'k' at the end of the subroutine will
simply do nothing and we'll continue
after it.
; Discard the final F(d_i+1).
d&+ Get the stack depth D and add the top [final result]
D+2 values. Of course that's two more
than we have divisors, but the stack is
implicitly padded with zeros, so that
doesn't matter.