Прочитав в начале года статью «Brainfuck и счастливые билеты», я решил, что пора уже изучить Brainfuck и написать на нём что-нибудь интересное. Долго думать не пришлось. Я решил написать свою «ненормальную» реализацию чисел Фибоначчи, в которой пользователь вводит однозначное число, определяющее количество выводимых элементов ряда Фибоначчи.
В создании программы мне также помогли сайт о Brainfuck'е и таблица ASCII символов
Для начала, нужно составить алгоритм. А вот и он:
Из алгоритма видно, что в ячейке 1 (верхняя строка — номера ячеек) в конце каждого шага цикла содержится последнее вычисленное значение, а в ячейке 2 — предпоследнее.
Итак, пойдём по порядку. Определимся для начала с ячейками, что и где будет находиться. Буду писать подробно, чтобы в комментариях не возникали претензии, на то, что в тексте статьи много непонятных моментов. И тут же оговорюсь, что в ряде Фибоначчи будут опущены первые две позиции и начинаться он будет сразу с третьей (0, 1, 1, 2, 3, 5, ...).
Ячейка 1: значение 1
Ячейка 2: значение 0
Ячейка 3: значение 32 (пробел)
Ячейка 4: вводимое число
Ячейки с 5 по 8: вспомогательные
В ячейке 6 будет итоговое значение
Далее все ячейки будут именоваться Ях, где х — порядковый номер ячейки.
Сразу же приведу весь код, а после подробно его разберу. Для удобства понимания (и написания) кода каждый значимый кусок писал в отдельной строке.
(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), вы получите ряд степеней двойки. :)
Вот, в общем, и всё. Весь текст приложения в кратком виде:
Результат выполнения:
Главное помните, что в Brainfuck всё относительно относительно текущей ячейки и значения в каждой. (:
Домашнее задание для начинающих: реализуйте вывод N количества элементов ряда Фибоначчи, где N — двузначное число.
В создании программы мне также помогли сайт о 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 — двузначное число.