Pull to refresh

10 противоестественных способов вычисления чисел Фибоначчи

Reading time 7 min
Views 10K
Задача вычисления первых двух десятков чисел Фибоначчи давно потеряла практическую ценность для программистов и используется преимущественно для иллюстрации базовых принципов программирования — рекурсии и итерации. Я же использую ее для демонстрации нескольких языков программирования, в которых она приобретает необычный и местами даже нездоровый вид.

Итак, мой рейтинг десяти наиболее противоестественных способов вычисления чисел Фибоначчи из написанных мной за последние полгода в рамках проекта Progopedia. Для уточнения задачи потребуем, чтобы выводом программы были первые 16 чисел в виде
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,…

10. Sanscript


Визуальный язык программирования, в котором все элементы языка представлены в виде элементарных блоков, из которых составляется собственно «код», именуемый диаграммой потоков (flowgram). Место в рейтинге этот язык заслужил размером диаграмм (два, ну три десятка элементов — максимум, который можно использовать на одной диаграмме без скроллинга и окончательного запутывания в связях между блоками) и неудобством использования ключевых структур языка (каждый цикл или условный переход требует для своего описания одной или нескольких отдельных диаграмм, которые мгновенно загромождают логику программы многоуровневой вложенностью и передачей глобальных переменных в виде параметров цикла). Ну, и собственно визуальностью — программа не пишется, а рисуется, и клавиатура как таковая используется только для ввода значений констант и (опционально) переименования элементарных блоков и написания комментариев.

Главная диаграмма потоков
Главная диаграмма потоков

Тело цикла
Тело цикла

9. gnuplot


Особенность этого языка (до версии 4.4.0) — отсутствие циклов как таковых. Впрочем, это можно простить — все-таки gnuplot не язык общего назначения, а программа для построения графиков. А цикл можно сымитировать, создав отдельный интерпретируемый файл с телом цикла, который «читается» для начала цикла и «перечитывается» для каждой итерации.

Файл run.gp (главный)

#!/usr/bin/env gnuplot
i = 1
a = 1
b = 1
res = ''
load "fibonacci.gp"
print res, '...'


Файл fibonacci.gp (имитация цикла)

res = res . a . ', '
c = a
a = b
b = b+c
i = i+1
if (i <= 16) reread


8. Haskell


Ленивые вычисления в комплекте с бесконечными списками — одна из самых известных фишек Haskell — позволяют определить (но не вычислить) числа Фибоначчи в одну строчку кода, остальной код запрашивает нужные числа и выводит их в нужном формате. А все-таки для программиста, получившего классическое воспитание в рамках процедурной парадигмы, этот способ далеко не очевиден и уж точно не естественен.

module Main where
import Text.Printf

fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

line n = printf "%d, " $ fibs !! n

main = do
sequence_ $ map line [1..16]
putStrLn "..."


7. SQL


Конечно, SQL сам по себе языком программирования не является, и в большинстве реализаций к нему прилагается процедурное расширение, с использованием которого поставленная задача решается вполне классическим образом. Интерес представляет решение без расширений, на «чистом» SQL. Впрочем, на «чистом» SQL решить не получится — по стандарту язык запросов не содержит ничего, что можно было бы использовать в качестве цикла. Решения получаются зависимыми от конкретной реализации и прилагающихся к ней плюшек.

7.1. Oracle SQL (с версии 9i)


Во внутреннем запросе генерируются индексы чисел (с 1 до 16) при помощи псевдостолбца level и конструкции connect by. В следующем запросе вычисляются сами числа Фибоначчи по их индексам при помощи формулы Бине. Оставшиеся два запроса упорядочивают числа по их индексам и соединяют их в одну строку нужного формата.

 SELECT REPLACE(MAX(SYS_CONNECT_BY_PATH(fib||', ', '/')),'/','')||'...' 
   FROM ( SELECT n, fib, ROW_NUMBER() 
            OVER (ORDER BY n) r 
            FROM (select n, round((power((1+sqrt(5))*0.5, n)
                                  -power((1-sqrt(5))*0.5, n))/sqrt(5)) fib 
                    from (select level n
                            from dual
                         connect by level <= 16) t1) t2
 ) 
  START WITH r=1 
CONNECT BY PRIOR r = r-1;


7.2. Oracle SQL (с версии 10g)


Удобный, но редко применяемый и поэтому малоизвестный оператор model позволяет реализовать цикл внутри SQL-запроса.

select max(s) || ', ...'
  from
(select s
   from dual
   model 
     return all rows
     dimension by ( 0 d ) 
     measures ( cast(' ' as varchar2(200)) s, 0 f)
     rules iterate (16)
     (  f[iteration_number] = decode(iteration_number, 
          0, 1, 1, 1, f[iteration_number-1] + f[iteration_number-2]), 
        s[iteration_number] = decode(iteration_number, 
          0, to_char(f[iteration_number]), 
          s[iteration_number-1] || ', ' || to_char(f[iteration_number]))
     )
);


7.3. MySQL


Возможность вычисления результатов запроса в цикле реализована более лаконично, чем в Oracle.

select concat(group_concat(f separator ', '), ', ...')
from (select @f := @i + @j as f, @i := @j, @j := @f
        from information_schema.tables, (select @i := 1, @j := 0) sel1
       limit 16) t


7.4. Microsoft SQL Server (с версии 2005)


Еще одна достаточно лаконичная реализация циклов, на этот раз с помощью рекурсивного запроса.

with fibonacci(a, b) as
(
 select 1, 1
  union all
 select b, a+b from fibonacci where b < 1000
)
SELECT cast(a as varchar)+', ' AS [text()]
  FROM fibonacci
   FOR XML PATH ('')


6. FP


FP — прототип всех существующих языков программирования, использующих парадигму программирование на уровне функций (function-level, не путать с functional, то есть просто функциональной). Изобретенный в 1977 году, он является скорее математической моделью, чем настоящим языком программирования: у него не было даже официального стандарта (кроме единственной статьи, в которой он описан), не говоря уже о реализации! Тем не менее, в наше время существуют интерпретаторы этого языка, обычно написанные в рамках студенческой работы. Одним из них является Furry Paws, и его уютное название совершенно не соответствует «комфортности» его использования.

Программирование на уровне функций предполагает построение программы из элементарных функций, комбинируемых при помощи функционалов (функциональных форм). Так, ~1 — элементарная функция, всегда возвращающая значение 1; id — функция, возвращающая переданное ей значение, [] — функциональная форма, объединяющая свои аргументы в последовательность и т.д.

one = eq.[id, ~1]
dec = sub.[id, ~1]
seq = one -> [~1] ; cat.[seq.dec, [id]]
fibonacci = lt.[id, ~3] -> ~1 ; add.[fibonacci.sub.[id, ~1], fibonacci.sub.[id, ~2]]

main = show.(return @fibonacci.(seq.~16))


5. J


Еще один язык, использующий «программирование на уровне функций», достойный преемник FP. Интересен тем, что практически любое выражение на нем можно записать несколькими способами, от почти традиционного до совершенно противоестественного (что и требовалось в данной статье). Так, например, вычисление чисел Фибоначчи при помощи формулы Бине можно записать вполне цивильно:

load 'printf'
g =: 0.5 * (1 + 5 ^ 0.5)
fib =: (0.2 ^ 0.5) * (g &^ - (1-g) &^)
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fib 1+i.16


А можно заменить практически все математические операции на их эквиваленты, специфичные для J:

load 'printf'
g =: -: >: %:5
fib =: (%:5) %~ g&^ - (1-g)&^
fstr =: '...' ,~ ,~^:4 '%d, '
fstr printf fib"0 >:i.16


И едва ли кому-то будет очевидно, что %: — это извлечение квадратного корня, >: — инкремент, -: — деление на два, а %~ — деление, причем при записи делимое и делитель меняются местами.

Вычисление с использованием рекурсии:

load 'printf'
fibr=: 1:`(-&2 + &fibr -&1) @.(2&<)"0
fstr=: '...' ,~ ,~^:4 '%d, '
fstr printf fibr 1+i.16


4. Hanoi Love


Малоизвестный эзотерический язык, интересный своим минимализмом и использованием стековой модели памяти. В отличие от следующего языка, основная сложность заключается не в выполнении арифметических действий, а в получении содержимого именно тех элементов стеков, которые нужны на каждом шаге. Вывод на печать, впрочем, так же неприятен, поэтому вычисляется и выводится только первая шестерка чисел.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;.'...;;;;;;;;;;;;.'...,..''''''..`.'.
..;.'.,.'...:...,.'..;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
"'.,.'...,"'.'...,"''.,...'.,..'..,...'...;.'.,.,!...,,,...;;"'"'"'


Описание языка и комментарии к приведенному коду можно найти на странице Hanoi Love.

3. Brainfuck


Классика жанра эзотерического программирования — Brainfuck. Язык, в котором даже копирование или сложение не является элементарной операцией, вывод на печать
трехзначного числа достоин отдельной оды, а уж использование его для решения какой-то конкретной задачи — ну просто мечта мазохиста :-)

В авторском интерпретаторе (Muller's Brainfuck) содержимое ячеек памяти хранится в переменных типа byte, и числа Фибоначчи с 14-го по 16-ое вызвали бы переполнение памяти. Реализация длинной арифметики на Brainfuck — это уже не симптом, а практически диагноз, поэтому при написании решения предполагалось, что ячейка памяти может хранить числа до 1000 (во многих реализациях языка для хранения используются достаточно вместительные типы данных).

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


Описание языка и комментарии к приведенному коду можно найти на странице Brainfuck.

2. Brainloller


Cамый простой из графических диалектов Brainfuck, придуманный Lode Vandevenne.
Программы читаются с картинок PNG, команды записываются пикселями разных цветов, и к имеющимся в Brainfuck восьми командам добавляются еще две — управление указателем на текущий пиксель. Ко всем прелестям Brainfuck добавляется еще полная нечитабельность «кода» и полная невозможность
«кодировать» без вспомогательных средств (например, конвертера программ и картинок).

Авторский интерпретатор языка канул в лету, поэтому для генерации «программы» пришлось писать свой. «Программа» приведена в десятикратном увеличении.



1. Unary


Куда уж хуже? — подумает читатель, листая экран дрогнувшей рукой. Да, бывает еще хуже. В предыдущих языках программу можно было хотя бы объять взглядом, а это уже немало.

Встречайте победителя рейтинга — Unary. Диалект Brainfuck, придуманный тем же Lode Vandevenne (о, мсье знает толк в извращениях!), предполагает, что команды Brainfuck преобразуются в двоичные коды и конкатенируются в одно двоичное число, унарная запись которого и является программой на Unary. Программа генерации чисел Фибоначчи представляет собой строку из
167967665105731198557055496639385943332278803897935697536099438828197
665241403160165880863622431582784595268769268183940269756210147305655
704025762911607244068691728105306566342622386432823429136972542304655
647901781271798433263001837026612851345264031562174039657802748245705
398528237993320520942720239597540583536934220029626573406470088757427
393143000966310611249037587993216365993804186165097620168960460854977
571944373603975793034586829061577464233522714007498991416860375267535
193648636795096472789203729505034887001634966681420589637468649908257
407260923590831776308356684326657774592110098643361324426156431864437
942781495979555960608253552679248495326880775320385281559763269974848
026839024530519989287202261977272377723622502479809174132505837648641
033569945906182518892142219706483917757108086522763280388915772444727
238483811923456440363260610571471034139736312976255142288379411989404
9017738035 (то есть примерно 1.68*10^906) нулей.

Я уверена, что перечисленные здесь языки — далеко не самое страшное, с чем может столкнуться программист (во всяком случае, не все из них :-) ), но я не волшебник, я только учусь.
Tags:
Hubs:
+122
Comments 89
Comments Comments 89

Articles