Pull to refresh

Числа Фибоначчи на Brainfuck

Reading time 4 min
Views 5.1K
Прочитав в начале года статью «Brainfuck и счастливые билеты», я решил, что пора уже изучить Brainfuck и написать на нём что-нибудь интересное. Долго думать не пришлось. Я решил написать свою «ненормальную» реализацию чисел Фибоначчи, в которой пользователь вводит однозначное число, определяющее количество выводимых элементов ряда Фибоначчи.

В создании программы мне также помогли сайт о Brainfuck'е и таблица ASCII символов


Ну, понеслась!


Для начала, нужно составить алгоритм. А вот и он:

Из алгоритма видно, что в ячейке 1 (верхняя строка — номера ячеек) в конце каждого шага цикла содержится последнее вычисленное значение, а в ячейке 2 — предпоследнее.

Итак, пойдём по порядку. Определимся для начала с ячейками, что и где будет находиться. Буду писать подробно, чтобы в комментариях не возникали претензии, на то, что в тексте статьи много непонятных моментов. И тут же оговорюсь, что в ряде Фибоначчи будут опущены первые две позиции и начинаться он будет сразу с третьей (0, 1, 1, 2, 3, 5, ...).
Ячейка 1: значение 1
Ячейка 2: значение 0
Ячейка 3: значение 32 (пробел)
Ячейка 4: вводимое число
Ячейки с 5 по 8: вспомогательные
В ячейке 6 будет итоговое значение

Далее все ячейки будут именоваться Ях, где х — порядковый номер ячейки.

Сразу же приведу весь код, а после подробно его разберу. Для удобства понимания (и написания) кода каждый значимый кусок писал в отдельной строке.
+ (1)
>
>++++++++++ ++++++++++ ++++++++++ ++
>,
>++++++++[<------>-] (2)

<[ (3)

>[-]>[-]>[-]>[-] (4)
<<<<<<<[>>>>+>+>>+<<<<<<<-] (5)
>>>>>[<<<<<+>>>>>-] (6)
<<<<[>>>>+>+<<<<<-] (7)
>>>>>[<<<<<+>>>>>-] (8)
<[<+>-] (9)

<<<<[-] (10)
>>>>>>[<<<<<<+>>>>>>-] (11)
<<<<<<<[-] (12)
>>>>[<<<<+>>>>>+<-] (13)

++++++++[>++++++<-]>. (14)

<<<. (15)

>-] (16)

+++++++++++++.---. (17)


Приступим к разбору кода.


(1) — тут всё элементарно. В первых трёх строках заполняем ячейки данными, в четвёртой получаем число символов для вывода от пользователя.

(2) — получаем из него необходимое для расчётов число, вычитая 48.

(3) — начало цикла вывода чисел.

(4) — обнуляю Я5-Я8. В принципе, достаточно обнулять лишь Я6.

(5) — копирую данные из Я1 в Я5, Я6 и Я8. При этом Я1 становится пустой.
(6) — перемещаю данные из Я6 в Я1. Таким образом в Я1, Я5 и Я6 реализовано копирование данных из Я1 в Я5, т.е. берём две пустые ячейки (конечная и вспомогательная) и переносим в них данные из исходной в эти ячейки, а затем из вспомогательной в исходную.
В Я5 записываю для вычисления следующего значения ряда Фибоначчи.
В Я8 сохраняется предпоследнее на текущий момент значение ряда.

(7, 8) — аналогично (5, 6) копирую данные из Я2 в Я6, используя Я7 как вспомогательную.

(9) — перемещаю данные из Я6 в Я5, суммируя. Расчёт значения следующего числа Фибоначчи произведён.

(10, 11) — обнуляю Я2 и перемещаю данные из Я8 в Я2.
(12, 13) — обнуляю Я1 и перемещаю данные из Я5 в Я1 и Я6.
Таким образом в Я1 у нас записано последнее рассчитанное значение, а в Я2 — предпоследнее.

(14) — увеличиваю значение Я6 на 48 и вывожу значение на экран.
(15) — вывожу пробел.
(16) — уменьшаю счётчик, конец цикла.
(17) — переход на новую строку, сдвиг каретки (вывод 13, 10).

Скрытая, но разоблачённая способность программы.


Первый раз, когда я закончил написание программы, обнаружил, что она вывела мне совсем не ряд Фибоначчи, а несколько иной, не далёкий от мира программирования. Пришлось ещё раз взяться за карандаш и разобрать каждый шаг:

Эх, если бы я знал, что просчитай я на ещё один шаг вперёд, нашёл бы ошибку быстрее. Таким образом мне пришлось вычислять место ошибки, для чего пригодился следующий код между (15) и (16), который выводил на экран содержимое Я1 и Я2, используя Я7:
>>>>[-]
++++++++[<<<<<<++++++>>>>>>-]<<<<<<.>>>>>>++++++++[<<<<<<------>>>>>>-]
++++++++[<<<<<++++++>>>>>-]<<<<<.>>>>>++++++++[<<<<<------>>>>>-]
[-]+++++++++++++.---.[-]<<<<

Потом ещё немного пришлось пошаманить и, в итоге, выяснилось, что я просто не обнулял Я2 (10). Получилось так, что, удалив строку (10), вы получите ряд степеней двойки. :)

Завершаю статью.


Вот, в общем, и всё. Весь текст приложения в кратком виде:
+>>++++++++++++++++++++++++++++++++>,>++++++++[<------>-]<[>[-]>[-]>[-]>[-]<<<<<<<[>>>>+>+>>+<<<<<<<-]>>>>>[<<<<<+>>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<<<<[-]>>>>>>[<<<<<<+>>>>>>-]<<<<<<<[-]>>>>[<<<<+>>>>>+<-]++++++++[>++++++<-]>.<<<.>-][-]+++++++++++++.---.

Результат выполнения:
9
1 2 3 5 8 = E R g


Главное помните, что в Brainfuck всё относительно относительно текущей ячейки и значения в каждой. (:

Домашнее задание для начинающих: реализуйте вывод N количества элементов ряда Фибоначчи, где N — двузначное число.
Tags:
Hubs:
+13
Comments 30
Comments Comments 30

Articles