15 января 2011 в 23:03

Числа Фибоначчи на 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 — двузначное число.
Павел @Mansiper
карма
17,0
рейтинг 0,0
Пользователь
Похожие публикации
Самое читаемое Разработка

Комментарии (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
        Я раньше увлекался Brainfuck'ом и у меня был целый сборник вот таких вот извращенских программ. Если интересно, то могу покопаться и найти.
      • +3
        • 0
          Спасибо. Вот это красота!
  • +5
    • 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
                  ну типа я победил, да? ;-)
                  • 0
                    Да, я думаю.
                    слоупок.жпг

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