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

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

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

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

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

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

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

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

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

Leaderboard

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}

body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

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

Brainfuck, 22 удара

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

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

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

f=1:scanl(+)1f

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

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);}

GolfScript, 12

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

1.{.@.p+.}do

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

0:nao1v LF a+@:n:<o

J, 10 символов

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

   (%-.-*:)t.

   (%-.-*:)t. 0 1 2 3 4 5 10 100
0 1 1 2 3 5 55 354224848179261915075

Гексагония ,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

Корова , 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

Python 2, 34 байта

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

def f(i,j):print i;f(j,i+j)
f(1,1)

Желе , 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.

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

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

~0 1@{.@+}*;

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

0 1@{.@+}*;

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

1.@{.@+}*;

Рубин

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

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

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

Mathematica, 9 символов

Fibonacci

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

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

#&@@Nest[{+##,#}&@@#&,{0,1},#]&

DC (20 байтов)

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

zzr[dsb+lbrplax]dsax

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

Прелюдия , 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.

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

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

1.}=+!

Ungolfed:

  1 .
 } = +
  ! .

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

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 знаков после запятой) необходимо для предотвращения ошибок округления.

К - 12

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

{x(|+\)/0 1}

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

{*x(|+\)/0 1}

Юлия, 18 байт

n->([1 1;1 0]^n)[]

Ява, 55

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

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

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

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

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

p 1,a=b=1;loop{p b=a+a=b}

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

R, 40 байт

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

f=function(n)ifelse(n<3,1,f(n-1)+f(n-2))

05AB1E, 7 байтов

Код:

1$<FDr+

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

Додос , 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 .

GolfScript, 13 символов

2,~{..p@+.}do

(Мой ответ на предыдущий вопрос переполнения стека .)

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}}

Cubix , 10 байт

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

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

;.o.ON/+!)

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

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

    ; .
    o .
O N / + ! ) . .
. . . . . . . .
    . .
    . .

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

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

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

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

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

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

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