Programowanie w Brainf**ku

28.12.2009 - Marek Materzok
TrudnośćTrudnośćTrudność

Przykład: liczby Fibonacciego

Nauczyliśmy się już dodawać i mnożyć liczby, a przede wszystkim oswoiliśmy się z najbardziej przydatną konstrukcją w Brainf**ku - k-krotnym powtórzeniem (czyli iteracją). To już w zupełności wystarcza, żeby pisać całkiem pożyteczne programy! Poniżej zaprezentuję jak, używając dopiero co nabytych umiejętności, napisać program obliczający k-tą liczbę Fibonacciego.

Dla tych, którzy liczb Fibonacciego nie znają - jest to ciąg liczbowy zdefiniowany w następujący sposób:

  • F(0)=0
  • F(1)=1
  • F(k)=F(k-1)+F(k+2)

Wyrażając się słowami, pierwsze dwa wyrazy ciągu to 0 i 1, a każdy kolejny jest sumą dwóch poprzednich. Pierwsze wyrazy ciągu to 0, 1, 1, 2, 3, 5, 8, 13; klasyczny algorytm obliczający k-tą liczbę Fibonacciego zapisany w pseudokodzie wygląda następująco:

a := 0
b := 1
k := k - 1
dopóki k > 0:
    t := a + b
    a := b
    b := t
    k := k - 1
wynik := b

Algorytm ten zawiera jedno uproszczenie, mianowicie nie daje prawidłowej odpowiedzi dla k=0, jednak uproszczenie to ułatwi nam zapisanie algorytmu w Brainf**ku.

Na początku musimy się zdecydować na układ pamięci. Przyjmijmy, że wejściowa wartość k będzie w pierwszej komórce, następnie zapiszemy a, b i t, natomiast kolejnych komórek będziemy używać do zapisywania tymczasowych wyników.

Na początku programu zainicjujmy wartość b (a już jest zainicjalizowane, ponieważ na początku pracy programu Brainf**kowego wszystkie komórki są wyzerowane) i zdekrementujmy k:

->>+<<

Ponieważ będziemy kkrotnie powtarzać pewne operacje, użyjemy tej samej struktury, co przy dodawaniu i mnożeniu:

[-

Wartość t ma być sumą a i b. Ponieważ b będzie nam jeszcze potrzebne, wykonajmy jego kopię; wartość a natomiast nie będzie już używana i nie musimy jej kopiować. Jedną z kopii b można zapisać od razu do t:

>>[->+>+<<]>>[-<<+>>]

Teraz wystarczy dodać a do t:

<<<[->>+<<]

Obliczyliśmy właśnie t. Możemy teraz przenieść wartość b do a:

>[-<+>]

Podobnie, przenosimy wartość t do b. Nie będziemy już korzystać z komórki t, nie przeszkadza nam (a wręcz pomaga!), że będzie wyzerowana:

>[-<+>]

Pozostało już tylko przenieść głowicę na pozycję wyjściową i zakończyć pętlę:

<<<]

Oto i gotowy program obliczający k-tą liczbę Fibonacciego wraz z prezentacją jego działania:

->>+<<[->>[->+>+<<]>>[-<<+>>]<<<[->>+<<]>[-<+>]>[-<+>]<<<]
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com