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

    Прочитав в начале года статью «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 — двузначное число.
    Метки:
    Поделиться публикацией
    Похожие публикации
    Комментарии 30
    • +1
      Уже была на Хабре статья habrahabr.ru/blogs/crazydev/94421/, вывод программы — первые 16 чисел Фибоначчи, причем не как один символ, а как нормальные числа.
      • 0
        А программа из этого топика рабочая?
        У меня не успевает выполниться ни в моем brainfuck.progopedia.ru/, ни в ideone.com/
        То ли зацикливается, то ли уж очень медленно работает.
        • +1
          Да, я делал на «a Brainfuck interpreter» в Ubuntu.
          На обоих сайтах работает. В Прогопедии нужно просто поле для ввода перед стартом заполнить. В ideone нужно нажать на «click here to paste input (stdin) or additional note» и вписать входные данные в первое поле.
          • –2
            Так же не работает. Где-то зацикливается вероятно.
            • 0
              Только что на обоих сайтах проверил. Могу привести скриншоты.
              • 0
                Да, с вводом проблема была.
            • 0
              Ага, упустил, что ввод нужен.
          • +1
            Я нашёл эту реализацию уже при подготовке статьи. Отличие от моей в том, что у меня работает относительно входных данных. Да и моя статья чуть более полезна для тех, кто хочет попробовать Brainfuck. К тому же у меня код покомпактнее будет…
          • +1
            Не могу не упомянуть статью моего друга bfdeveloper про морской бой, в котором я выступал в качестве консультанта при написании генератора псевдослучайных чисел. А фибоначчи могли бы и сколькоугоднозначные, это уже интересно.
            • –1
              Спасибо. Отличная статья!
            • +1
              Пора уже открывать блог по программированию на Brainfuck'е. Где-то давным давно я даже видел рисование псевдографикой множества Мандельброта.
              • 0
                Это невозможно! Ну, по крайней мере, не нормально…
              • 0
                Как Вы думаете, это шутка или суровая реальность?
                • 0
                  вероятно, ищут программера, готового трахаться с чем-то неизвестным
                  • 0
                    Вот, вот! Типа после Brainfuck'а уже ничего не страшно…
              • 0
                ++++++++[>++++++>>>>>++++<<<<<<-],>[-<->]+>+<<[>>>>[-]<<[-<+>>+>+<<]<[->+<]>>[-<<+>>]>>++++++++[<++++++>-]<.>>.<<<<<<-]+++++++++++++.---.
                ну может хоть тут кто-нибудь со мной посоревнуется на краткость кода? :-)
                • +1
                  Только я, видимо :)
                  [code]
                  ,>++++++++[>++++<<------>-]>>>+<<<<
                  [>>>[>>+<<-]>[>+>+<<-]>>[<<<+>>>-]<
                  [<+>>+<-]++++++++[>++++++<-]>.[-]<<
                  <<.<<-]+++++++++++++.---.
                  [code]
                  130 символов супротив ваших 137, при том же функционале :)
                  • +1
                    апдейт:
                    [code],>++++++++[>++++>++++++<<<------>-]>
                    >>>+<<+<<<[>>>>[<+>>>+<<-]>[>+>+<<-]
                    >>[<<<+>>>-]<[<+>-]<<<.<.<<-]+++++++
                    ++++++.---.[/code]
                    даже 119 символов
                    • +1
                      ,>>>++++++++[<<<------>++++>++++++>-
                      ]>+<<+<<[>>>[<+>>>+<<-]>[<+>>+<-]>[<
                      +>-]<<<.<.<-]+++++++++++++.---.
                      • 0
                        Замечательный результат! Уважаю!
                        • +1
                          Апдейт:
                          ,>>>++++[>++++[<<<<--->++>+++>>-]<-]>+<<+<
                          <[>>>[<+>>>+<<-]>[<+>>+<-]>[<+>-]<<<.<.<-]
                          +++++++++++++.---.

                          Чувствую, сражение идет за каждый символ :)
                          102 против 103.
                          • +2
                            ,>>>++++[>++++[<<<<--->++>+++>>-]<-]>+<<+<
                            <[>>>[<+>>>+<<-]>[<+>>+<-]>[<+>-]<<<.<.<-]
                            >[--<+>]<---.---.

                            101 ;-)
                            • +1
                              ,>>>++++[>++++[<<<<---<+>>++>+++>>-]<-]>+<<+
                              <<[>>>[<+>>>+<<-]>[<+>>+<-]>[<+>-]<<<.<.<-]<
                              ---.---.

                              96 :)
                              • +1
                                ,<<<++++[>++++[>+++>--->++>+<<<<-]<-]+>>+>[<
                                <[->+<<<+>>]<[->+<<+>]<[->+<]>>>.>>.<-]>>---
                                .---.

                                93
                                • 0
                                  ну типа я победил, да? ;-)

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.