Programowanie w Brainf**ku

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

Dłuższy przykład: algorytm Euklidesa

Algorytm Euklidesa oblicza największy wspólny dzielnik dwóch liczb k i l - czyli największą taką liczbę, która dzieli zarówno k, jak i l. W swojej najprostszej wersji, zapisany pseudokodem, algorytm ten wygląda następująco:

dopóki k > 0:
    jeśli k > l: 
        zamień k i l
    w przeciwnym wypadku:
        l := l - k
wynik := l

Spróbujmy zapisać go w Brainf**ku. Tak jak poprzednio, ustalmy układ pamięci. Niech pierwsza komórka pamięci zawiera wartość k, a druga - l. Uzyskany wynik zachowajmy w l. Kolejne komórki będą pełnić rolę tymczasowych w różnych operacjach.

Na początku musimy sprawdzić, czy k jest niezerowe. Przygotujmy więc najpierw kopię k w trzeciej komórce pamięci:

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

Możemy zacząć pętlę. Kopia k w komórce trzeciej przyda się do wykonania porównania, możemy ją zachować. Musimy jeszcze skopiować l do komórki czwartej:

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

Wykonajmy porównanie, używając wcześniej przygotowanego kodu:

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

Wykorzystamy teraz wzorzec if-then-else:

+<[[-]>-

Zamianę k i l najlepiej wykonać, używając trzeciej komórki jako tymczasowej:

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

Zamknijmy gałąź then i zacznijmy gałąź else:

]>[-

Skopiujmy k do trzeciej komórki pamięci, jednocześnie wykonując odejmowanie od l, po czym przywróćmy k z kopii:

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

Można teraz zamknąć gałąź else:

>]

Aby zakończyć pętlę, przygotujmy kopię k w komórce trzeciej, tak samo, jak na początku programu:

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

Można zakończyć pętlę; wynik znajduje się w drugiej komórce pamięci.

]<

Oto i kompletny kod programu:

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

Zachęcam do jego wypróbowania w interpreterze poniżej.

Co dalej?

Przedstawiony w artykule zbiór technik powinien ułatwić programowanie w języku Brainf**k, jednak bez wątpienia nie jest to zbiór kompletny. Przedstawione operacje arytmetyczne są dość ograniczone - operują tylko na pojedynczych bajtach, i znają tylko wartości dodatnie. Opracowanie kodu, który działałby na dłuższych liczbach, być może też ujemnych, może być ciekawym wyzwaniem, podobnie jak napisanie kodu dla dzielenia i modulo.

Dobrym ćwiczeniem dla ambitnych jest napisanie programu, który tłumaczyłby programy napisane w uproszczonym C lub Pascalu na programy napisane w Brainf**ku.

5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com