Функция или последовательность Фибоначчи

115

Последовательность Фибоначчи - это последовательность чисел, где каждое число в последовательности является суммой двух чисел, предшествующих ей. Первые два числа в последовательности - 1.

Вот первые несколько терминов

1 1 2 3 5 8 13 21 34 55 89 ...

Напишите кратчайший код, который либо:

  • Генерирует последовательность Фибоначчи без конца.

  • Дано nвычисление nчлена последовательности. (Либо 1, либо ноль индексируется)

Вы можете использовать стандартные формы ввода и вывода.

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


Для функции, которая принимает n, должно поддерживаться достаточно большое возвращаемое значение (наибольшее число Фибоначчи, которое соответствует как минимум нормальному размеру слова вашего компьютера).


Leaderboard

Крис Шут-Янг
источник

Ответы:

48

Perl 6, 10 символов:

Список анонимных бесконечных последовательностей Фибоначчи:

^2,*+*...*

Такой же как:

0, 1, -> $x, $y { $x + $y } ... Inf;

Итак, вы можете назначить его массиву:

my @short-fibs = ^2, * + * ... *;

или же

my @fibs = 0, 1, -> $x, $y { $x + $y } ... Inf;

И получить первые одиннадцать значений (от 0 до 10) с помощью:

say @short-fibs[^11];

или с:

say @fibs[^11];

Подождите, вы также можете получить первые 50 номеров из самого анонимного списка:

say (^2,*+*...*)[^50]

Это возвращает:

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169
63245986 102334155 165580141 267914296 433494437 701408733 1134903170 
1836311903 2971215073 4807526976 7778742049

И несколько простых тестов:

real    0m0.966s
user    0m0.842s
sys     0m0.080s

С участием:

$ time perl6 -e 'say (^2, *+* ... *)[^50]'

EOF

Марко Аурелио да Силва
источник
Я бы даже не подумала о ^2замене 0,1. +1
Конрад Боровски
2
Это больше не действует, вам нужно будет записать его как |^2,*+*...*, равное количеству байтов 0,1,*+*...*.
Брэд Гилберт b2gills
5
Perl такой странный
Cyoce
1
В какой версии Perl 6 был написан этот ответ?
CalculatorFeline
3
@CalculatorFeline Произошло большое изменение, известное как GLR (Great List Refactor), которое произошло незадолго до первого официального релиза, который был 2015-12-25. Этот код работал бы вплоть до того времени.
Брэд Гилберт b2gills
73

Brainfuck, 22 удара

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

Создает последовательность Фибоначчи, постепенно перемещаясь по ленте памяти.

Р. Мартиньо Фернандес
источник
5
Красивый! Буквально красиво! Или, может быть, нет ... в любом случае +1 за это :)
Пер Хорншой-Ширбек
2
Это 3.344 или 4 байта в сжатом мозговом потоке . (6 ln (22)) / ln (256)
Уилл Шервуд
24
16 байтов:+[[<+>->+>+<<]>]
прим.
3
14 байтов:+[.[>+>+<<-]>]
Чарлим
2
@ Stefnotch конечно, короче разрушительный. Вышеупомянутое решение заканчивается последовательностью Фибоначчи на ленте, что также делает 16-байтовое решение.
Примо
51

Haskell, 17 15 14 символов

f=1:scanl(+)1f

Попробуйте онлайн!

Anon.
источник
4
Почему бы не вырезать два пробела f=0:scanl(+)1 f?
Р. Мартиньо Фернандес
@Martinho: отредактировано, спасибо.
Анон.
Вау, это даже короче, чем обычно f@(_:x)=0:1:zipWith(+)f x! Надо запомнить это.
FUZxxl
4
Вы можете даже лишить другого места f=0:scanl(+)1f.
FUZxxl
37

C # 4, 58 байт

Stream (69; 65, если слабо набрано IEnumerable )

(Принимая usingдирективу для System.Collections.Generic.)

IEnumerable<int>F(){int c=0,n=1;for(;;){yield return c;n+=c;c=n-c;}}

Одно значение (58)

int F(uint n,int x=0,int y=1){return n<1?x:F(n-1,y,x+y);}
Джон Скит
источник
6
Учитывая, что nэто uint, n==0можно сократить до n<1. И поток может сохранить несколько символов, обрезая пространство после универсального типа и объявляя xв более широкой области, чем необходимо. На самом деле, ров xполностью:n+=c;c=n-c;
Питер Тейлор
1
@Peter: Спасибо, отредактирую, когда у меня будет время.
Джон Скит
Ваша версия с одним значением соответствует моему рекурсивному лямбда-выражению ... хорошо!
Эндрю Грей,
1
@ wizzwizz4 если я не ошибаюсь, если !nработает, то так же должно быть, только nесли вы перевернете условное.
Cyoce
3
@JonSkeet Aw. И тут я подумал, что я бы победил Джона Скита в C # ... :-)
wizzwizz4
32

GolfScript, 12

Теперь всего 12 персонажей!

1.{.@.p+.}do
jtjacques
источник
+1 хорошая работа. Если вы сделаете его короче, чем 13 символов, я немедленно приму ваш ответ (если, конечно, кто-то не сделает еще более короткий ответ). :-P
Крис Шестер-Янг
1
Я люблю вызов. Готово! ;-)
Jtjacques
Хорошо, ты выиграл. По крайней мере, пока кто-то не сделает что-то еще короче (если это вообще возможно). :-P
Крис Шестер-Янг
5
это определение почти такое же короткое, как само название «Фибоначчи»! +1
агент-ю
23

> <> - 15 символов

0:nao1v LF a+@:n:<o
Кевин Браун
источник
Хотя вы можете сократить его, 0:nao1v LF a+@:n:<oесли хотите. Дает 15 :) Фактически, это также делает вывод немного более читабельным ...
tomsmeding
5
13 символов:01r:nao$:@+$r
randomra
21

J, 10 символов

Использование встроенного расчета коэффициентов ряда Тейлора, так что, возможно, немного обмануть. Узнал это здесь .

   (%-.-*:)t.

   (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075
randomra
источник
2
@aditsu (q:^-^:p) 6- это место, 64 729где p четное. J, вероятно, хорош для того, что он делает загадки. :)
randomra
2
Еще лучше: (<:^-^:>) 4есть 81и <:^-^:> 4есть 53.5982.
Рандомра
2
Смайлики, продемонстрированные здесь, - это то, к чему должен стремиться весь код J. Кстати, еще одна альтернатива - +/@:!&i.-использование 9 байтов.
миль
1
@ миля Очень мило! Вы должны опубликовать это, поскольку оно полностью отличается от моего.
Рандомра
21

Гексагония ,18 14 12

Спасибо Мартину за 6 байтов!

1="/}.!+/M8;

Expanded:

  1 = "
 / } . !
+ / M 8 ;
 . . . .
  . . .

Попробуйте онлайн


Старый, ответь. Это остается, потому что изображения и пояснения могут быть полезны для новых пользователей Hexagony.

!).={!/"*10;$.[+{]

Expanded:

  ! ) .
 = { ! /
" * 1 0 ;
 $ . [ +
  { ] .

Это печатает последовательность Фибоначчи, разделенную символами новой строки.

Попробуйте онлайн! Но будьте осторожны, онлайн-переводчику не очень нравится бесконечный вывод.

объяснение

Эта программа содержит две «подпрограммы», каждая из которых запускается одним из двух используемых IP-адресов. Первая подпрограмма печатает новые строки, а вторая выполняет вычисление и вывод Фибоначчи.

Первая подпрограмма начинается с первой строки и перемещается слева направо все время. Сначала он печатает значение в указателе памяти (инициализируется в ноль), а затем увеличивает значение в указателе памяти на 1. После отсутствия операции IP переходит на третью строку, которая сначала переключается на другую ячейку памяти, а затем печатает новую строку. Поскольку символ новой строки имеет положительное значение (его значение равно 10), код всегда будет переходить к пятой строке, следующей. Пятая строка возвращает указатель памяти на наше число Фибоначчи, а затем переключается на другую подпрограмму. Когда мы вернемся из этой подпрограммы, IP вернется к третьей строке после выполнения no-op.

Вторая подпрограмма начинается в верхнем правом углу и начинает движение на юго-восток. После бездействия мы вынуждены отправиться на запад вдоль второй линии. Эта строка печатает текущее число Фибоначчи, прежде чем перемещать указатель памяти в следующее место. Затем IP переходит на четвертую строку, где вычисляет следующее число Фибоначчи, используя два предыдущих. Затем он возвращает управление первой подпрограмме, но когда он восстанавливает контроль над программой, он продолжается до тех пор, пока не встретит скачок, где он отскакивает от зеркала, которое первоначально использовалось, чтобы указать его на запад, когда он возвращается ко второй строке.


Предварительные красивые картинки!

Левая сторона изображения - это программа, правая часть - память. Синее поле - это первый IP-адрес, и оба IP-адреса указывают на следующую команду, которая должна быть выполнена.

введите описание изображения здесь

Примечание. Рисунки могут показаться красивыми только тем, у кого такие же ограниченные навыки в программах для редактирования изображений: PI добавит как минимум еще 2 итерации, чтобы использование *оператора стало более понятным.

Примечание 2: Я видел ответ алефальфы только после того, как написал большую часть этого, я полагал, что он все еще был ценным из-за разделения, но фактические части наших программ Фибоначчи очень похожи. Кроме того, это самая маленькая программа Hexagony, в которой я видел использование более одного IP, поэтому я подумал, что в любом случае было бы неплохо сохранить: P

FryAmTheEggman
источник
Вы должны сделать ссылку на все, что вы использовали для создания красивых картинок, а затем разместить ссылку на esolangs.org/wiki/Hexagony .
mbomb007
1
@ mbomb007 Я использовал gimp, чтобы вручную создать каждый кадр, а затем загрузил изображения на какой-то сайт, посвященный созданию картинок. Хотя несколько раз в течение этого процесса я думал о создании инструмента для этого, учитывая, насколько это было утомительно.
FryAmTheEggman
@FryAmTheEggman Впечатляет! Сделайте это вызовом. Я уверен, что кто-то опубликует ответ. : D Еще лучше, если бы вы могли создать сайт, похожий на онлайн-переводчика fish.
mbomb007
@ mbomb007 Это может быть немного амбициозным вызовом на этом сайте, не говоря уже о том, что он, вероятно, сильно пострадает от того, что он действительно широк. Я не думаю, что я опубликую это, но не стесняйтесь делать это самостоятельно, если вы думаете, что у вас есть хороший способ представить это. Кроме того, я считаю, что Тимви создал идеал C # для гексагонии, хотя я никогда не использовал его, потому что не беспокоился о моно.
FryAmTheEggman
1
@ mbomb007 Иде живет здесь , кстати, забыл связать его в прошлый раз.
FryAmTheEggman
18

Корова , 108

 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo
Timtech
источник
17

Python 2, 34 байта

Python, использующий рекурсию ... вот и StackOverflow!

def f(i,j):print i;f(j,i+j)
f(1,1)
jtjacques
источник
15

Желе , 3 байта

+¡1

Попробуйте онлайн!

Как это устроено

+¡1    Niladic link. No implicit input.
       Since the link doesn't start with a nilad, the argument 0 is used.

  1    Yield 1.
+      Add the left and right argument.
 ¡     For reasons‡, read a number n from STDIN.
       Repeatedly call the dyadic link +, updating the right argument with
       the value of the left one, and the left one with the return value.

¡ заглядывает на две ссылки слева. Поскольку существует только один, это должно быть тело цикла. Поэтому число читается из ввода. Поскольку аргументов командной строки нет, это число считывается из STDIN.

Деннис
источник
12

Golfscript - один номер - 12/11/10

12 символов для получения ввода от стандартного ввода:

~0 1@{.@+}*;

11 символов для ввода уже в стеке:

0 1@{.@+}*;

10 символов для дальнейшего определения 1 как 0-го числа Фибоначчи:

1.@{.@+}*;
AAAAAAAAAAAA
источник
1
Опция «Вычисляет, учитывая n, n-е число Фибоначчи». Так что бросьте ~и у вас есть 11 символов, которые берут nв стек и оставляют F_nв стеке.
Питер Тейлор
12

Рубин

29 27 25 24 символов

p a=b=1;loop{b=a+a=p(b)}

Изменить: сделал это бесконечный цикл. ;)

st0le
источник
13
кто-нибудь заметил b=a+a=bэто палиндром? :)
st0le
2
да st0le сделал :)
gnibbler
Я знаю, что опаздываю на вечеринку, но может кто-нибудь объяснить, как эта b=a+a=bчасть работает? Не могу обернуть голову вокруг этого.
Мистер Лама
3
@GigaWatt, Подумайте об этом так, инструкции выполняются слева направо ... такnewb=olda+(a=oldb)
st0le
Вы можете сохранить 2 символа, используя loop:p 1,a=b=1;loop{p b=a+a=b}
Patrick Oscity
11

Mathematica, 9 символов

Fibonacci

Если встроенные функции не разрешены, вот явное решение:

Mathematica, 33 32 31 символов

#&@@Nest[{+##,#}&@@#&,{0,1},#]&
celtschk
источник
#&@@Nest[{#+#2,#}&@@#&,{0,1},#]&32 символа
Chyanog
1
@chyanog 31:#&@@Nest[{+##,#}&@@#&,{0,1},#]&
Мистер Волшебник,
1
@ Mr.Wizard 24 символа (26 байт):Round[GoldenRatio^#/√5]&
JungHwan Мин
1
или 23 символа (27 байтов):Round[((1+√5)/2)^#/√5]&
JungHwan Мин
10

DC (20 байтов)

В качестве бонуса это даже запутано;)

zzr[dsb+lbrplax]dsax

РЕДАКТИРОВАТЬ: Я могу указать, что он печатает все числа в последовательности Фибоначчи, если вы будете ждать достаточно долго.

Hiato
источник
13
Я бы не назвал это запутанным - обфусцированный код должен быть сложным для понимания, и что касается dc, то код здесь совершенно прост.
Набб
10

Прелюдия , 12 байт

Одна из немногих проблем, где Prelude на самом деле довольно конкурентоспособна:

1(v!v)
  ^+^

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

объяснение

В Prelude все строки выполняются параллельно, при этом указатель команд пересекает столбцы программы. Каждая строка имеет свой собственный стек, который инициализируется нулем.

1(v!v)
  ^+^
| Push a 1 onto the first stack.
 | Start a loop from here to the closing ).
  | Copy the top value from the first stack to the second and vice-versa.
   | Print the value on the first stack, add the top two numbers on the second stack.
    | Copy the top value from the first stack to the second and vice-versa.

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

Обратите внимание, что это начинает последовательность Фибоначчи с 0.

Мартин Эндер
источник
10

Гексагония , 6 байт

Не конкурирует, потому что язык новее, чем вопрос.

1.}=+!

Ungolfed:

  1 .
 } = +
  ! .

Он печатает последовательность Фибоначчи без разделителя.

alephalpha
источник
2
Это небольшая проблема, заключающаяся в том, что он не печатает разделитель между числами. Это не совсем хорошо указано в вызове, хотя. (И я действительно счастлив, что кто-то использует Гексагонию. :))
Мартин Эндер
9

TI-BASIC, 11

Легендарный игрок в гольф TI-BASIC Кеннет Хаммонд ("Weregoose") с этого сайта . Выполняется за время O (1) и считает 0 0-м членом последовательности Фибоначчи.

int(round(√(.8)cosh(Anssinh‾¹(.5

Использовать:

2:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     1

12:int(round(√(.8)cosh(Anssinh‾¹(.5
                                     144

Как это работает? Если вы посчитаете, получается, что sinh‾¹(.5)это равно ln φ, так что это модифицированная версия формулы Бине, которая округляется вместо использования (1/φ)^nпоправочного члена. round((Круглый до 9 знаков после запятой) необходимо для предотвращения ошибок округления.

Томас Ква
источник
8

К - 12

Вычисляет nи n-1число Фибоначчи.

{x(|+\)/0 1}

Просто число nthФибоначчи.

{*x(|+\)/0 1}
isawdrones
источник
+1 Неплохо! Если бы вы могли уменьшить его только на один символ (и предоставьте мне способ проверить это), я приму ваш ответ. :-)
Крис Шестер-Янг
Единственный способ уменьшить это - заменить функцию вызовом известного числа: n (| + \) / 0 1 Протестируйте его с помощью этого интерпретатора .
isawdrones
7

Ява, 55

Я не могу конкурировать с краткостью большинства языков здесь, но я могу предложить существенно другой и, возможно, гораздо более быстрый (постоянное время) способ вычисления n-го числа:

Math.floor(Math.pow((Math.sqrt(5)+1)/2,n)/Math.sqrt(5))

nявляется вводом (int или long), начиная с n = 1. Он использует формулу Бине и раунды вместо вычитания.

Ханс-Петер Стёрр
источник
Я люблю это решение
Андреас
Кажется, это не работает для меня, но рано, и я могу что-то упустить! Предполагая, 0что первое число в последовательности, это дает 0, 0, 1, 1, 3, 4, 8, 12, 21, 33для первых 10 чисел
Shaggy
@ Шэгги Ой! Извините, я ввел ошибку - исправлена.
Ханс-Петер Стёрр
6

Рубин, 25 символов

ответ st0le сокращен.

p 1,a=b=1;loop{p b=a+a=b}
Матма Рекс
источник
6
На самом деле вы можете сократить его еще больше, используяa=b=1;loop{p a;b=a+a=b}
Ventero
6
Значит, вы ответили на его вопрос? : P
mbomb007
6

FAC: функциональный APL, 4 символа (!!)

Не мое, поэтому размещено как вики сообщества. FAC - это диалект APL, который, по-видимому, предложил Хай-Чен Ту в качестве своей кандидатской диссертации в 1985 году. Позднее он написал вместе с Аланом Дж. Перлисом статью « FAC: функциональный язык APL ». Этот диалект APL использует «ленивые массивы» и допускает массивы бесконечной длины. Определяет оператор "iter" ( ) для компактного определения некоторых рекурсивных последовательностей.

Монадический ("унарный") случай в основном Хаскелла iterate, и определяется как (F⌼) A ≡ A, (F A), (F (F A)), …. Диадический ( «двоичный») случае определяется несколько аналогично для двух переменных: A (F⌼) B ≡ A, B, (A F B), (B F (A F B)), …. Почему это полезно? Ну, как оказалось, это именно тот тип рецидива, который имеет последовательность Фибоначчи. Фактически, один из приведенных примеров

1+⌼1

производя знакомую последовательность 1 1 2 3 5 8 ….

Итак, вы, возможно, самая короткая из возможных реализаций Фибоначчи на языке программирования, не являющемся новинкой. : D

Светлячок
источник
О, я случайно удалил ваш пост из сообщества как часть моего (ручного) массового удаления. Ну что ж. ;-)
Крис Шутер-Янг
6

R, 40 байт

Не видел решения R, так что:

f=function(n)ifelse(n<3,1,f(n-1)+f(n-2))
plannapus
источник
1
Я знаю, что это старый ответ, но вы можете сократить до 38 байт
Роберт С.
6

Додос , 26 байт

	dot F
F
	F dip
	F dip dip

Попробуйте онлайн!

Как это устроено

Функция F выполняет всю тяжелую работу; он определяется рекурсивно следующим образом.

F(n) = ( F(|n - 1|), F(||n - 1| - 1|) )

Всякий раз, когда n> 1 , мы имеем | n - 1 | = n - 1 <n и || n - 1 | - 1 | = | n - 1 - 1 | = n - 2 <n , поэтому функция возвращает (F (n - 1), F (n - 2)) .

Если n = 0 , то | n - 1 | = 1> 0 ; если n = 1 , то || n - 1 | - 1 | = | 0 - 1 | = 1 = 1 . В обоих случаях попытки рекурсивных вызовов F (1) вызывают исключение Surrender , поэтому F (0) возвращает 0, а F (1) возвращает 1 .

Например, F (3) = (F (1), F (2)) = (1, F (0), F (1)) = (1, 0, 1) .

Наконец, основная функция определяется как

main(n) = sum(F(n))

поэтому он складывает все координаты вектора, возвращенного F .

Например, main (3) = sum (F (3)) = sum (1, 0, 1) = 2 .

Деннис
источник
5

Desmos , 61 байт

Golfed

Нажмите add sliderкнопку для n.

p=.5+.5\sqrt{5}
n=0
f=5^{-.5}\left(p^n-\left(-p\right)^{-n}\right)

Последняя строка - это вывод.

Ungolfed

Это функция.

\phi =\frac{1+\sqrt{5}}{2}
f_{ibonacci}\left(n\right)=\frac{\phi ^n-\left(-\phi \right)^{-n}}{\sqrt{5}}
Конор О'Брайен
источник
5

Cubix , 10 байт

Не конкурирующий ответ, потому что язык новее, чем вопрос.

Cubix - это новый двухмерный язык, созданный @ETHproductions, в котором код помещается в куб, размер которого соответствует размеру.

;.o.ON/+!)

Попробуйте онлайн

Это оборачивает на 2 x 2 куб следующим образом

    ; .
    o .
O N / + ! ) . .
. . . . . . . .
    . .
    . .
  • O вывести значение TOS
  • N вставить новую строку в стек
  • / отражать север
  • o вывести символ ТОС
  • ; поп TOS
  • / отражать восток после обхода куба
  • + добавить 2 верхних значения стека
  • ! пропустите следующую команду, если TOS равен 0
  • ) увеличить TOS на 1. Это существенно запускает последовательность.

Это бесконечный цикл, который печатает последовательность с разделителем новой строки. Он использует тот факт, что большинство команд не извлекают значения из стека.
Если разделитель игнорируется, то это может быть сделано с 5 байтами.O+!)

MickyT
источник
5

Brainfuck, 16,15, 14/13 символов

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

Генерирует последовательность Фибоначчи и ничего не распечатывает. Кроме того, короче, чем выше.

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

Этот имеет 14 символов, но выводит символы ASCII со значениями последовательности Фибоначчи.

Stefnotch
источник
1
Это хорошо, но могу ли я сказать, что 14-байтовая версия выводит только 2-ю 1-ю? Как в «1 2 3 5 8» вместо «1 1 2 3 5 8»?
Чарлим
1
@Charlim О, ты прав. Я понятия не имею, что думал я 2014 года. В любом случае, я просто исправил это, переместив инструкцию печати в начало цикла.
Stefnotch