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

Я хотел бы знать, может ли кто-то генерировать только первые N элементов последовательности Фибоначчи за очень короткое время. Я пытаюсь сделать это на python, но меня интересует любой короткий ответ, на любом языке. Функция F (N) генерирует первые N элементов последовательности, либо возвращает их как возврат функции, либо печатает их.

Интересно, что ответы на вопросы кода-гольфа начинаются с 1 1 2, а не с 0 1 1 2. Это соглашение в код-гольфе или программировании в целом? (Википедия говорит, что последовательность Фибоначчи начинается с нуля.)

Образец Python (первые 5 элементов):

def f(i,j,n):
    if n>0:
        print i;
        f(j,i+j,n-1)
f(1,1,5)

С

Не стал считать, но вот забавный пример:

f(n){return n<4?1:f(--n)+f(--n);}
main(a,b){for(scanf("%d",&b);a++<=b;printf("%d ",f(a)));}

Доказательство это работает.

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

                         #                                // 1
                         f                                // 1
                         //                               // 2
                        (n)                               // 3
                       {/**/                              // 5
                      return n                            // 8
                    <2 ? 1:f(--n)                         // 13
                +f(--n); } main(a, b)                     // 21
          {a = 0, b = 0;scanf("%d",&b); for(              // 34
;a < b; a+=1) { int res = f(a); printf("%d ", res); } }   // 55

Доказательство это работает.

Хаскелл (26)

Удивительно, но это всего на один символ длиннее, чем J-решение.

F = ( `take`s)
S = 0: scanl (+) 1s

Я сбрил несколько персонажей:

1. Использование takeв качестве бинарного оператора;
2. Использование scanlвместо многословного zipWith.

Вот однострочный Python. Он использует плавающую точку, поэтому могут быть некоторые, nдля которых он более не точен.

F=lambda n:' '.join('%d'%(((1+5**.5)/2)**i/5**.5+.5)for i in range(n))

F(n)возвращает строку, содержащую первые nчисла Фибоначчи, разделенные пробелами.

GolfScript, 16 символов

~0 1@{.2$+}*;;]`

Пример вывода:

$ ruby golfscript.rb ~/Code/golf/fib.gs <<< "12"
[0 1 1 2 3 5 8 13 21 34 55 89]

Perl, 50 символов

sub f{($a,$b,$c)=@_;$c--&&say($a)&&f($b,$a+$b,$c)}

Скала 71:

def f(c:Int,a:Int=0,b:Int=1):Unit={println(a);if(c>0)f(c-1,b,a+b)};f(9)

печать

0
1
1
2
3
5
8
13
21
34

Perl, 29 28 байт

perl -E'say$b+=$;=$b-$;for-pop..--$;' 8
1
1
2
3
5
8
13
21

объяснение

Это основано на классическом $b += $a = $b-$aповторении, которое работает следующим образом:

• В начале каждого цикла $aсодержит F(n-2)и $bсодержитF(n)
• После $a = $b-$a $aсодержитF(n-1)
• После $b += $a $bсодержитF(n+1)

Проблема здесь заключается в инициализации. Классический путь, $b += $a = $b-$a || 1но затем последовательность идет1 2 3 5 ...

Расширяя последовательность Фибоначчи влево:

... 5 -3 2 -1 1 0 1 1 2 3 5 ...

Вы видите, что правильной отправной точкой является $a = -1и $b = 0. Инициализация $ a может быть объединена с настройкой цикла

Наконец, замените $a, $;чтобы избавиться от места доfor

Я могу дать вам двухстрочное решение Python. Это вернет их в виде списка.

f = lambda n: 1 if n < 2 else f(n-1) + f(n-2)
g = lambda m: map(f, range(0,m))

print g(5)

Вы можете распечатать их, добавив еще одну карту, чтобы сделать их строками, а затем добавив соединение, но мне это просто не нужно.

К сожалению, я не знаю, как вставить рекурсивную лямбду map, поэтому я застрял в двух строках.

Python (78 символов)

Я использовал формулу Бине для вычисления чисел Фибоначчи -

[(1 + SQRT (5)) ^ п- (1-SQRT (5) ^ п] / [(2 ^ п) SQRT (5)]

Это не так мало, некоторые другие ответы здесь, но мальчик это быстро

n=input()
i=1
x=5**0.5
while i<=n:
    print ((1+x)**i-(1-x)**i)/((2**i)*x)
    i+=1

Схема

Это оптимизировано с использованием хвостовой рекурсии:

(define (fib n)
  (let fib ([n n] [a 0] [b 1])
    (if (zero? n) (list a)
        (cons a (fib (- n 1) b (+ a b))))))

Haskell

fib n = take n f
f = 0:1:zipWith (+) f (tail f)

Доказательство того, что это работает .

J, 25 символов

Я понимаю, что решения J, вероятно, не то, что вы ищете, но вот одно из них. :-)

0 1(],+/&(_2&{.))@[&0~2-~

Применение:

    0 1(],+/&(_2&{.))@[&0~2-~ 6
0 1 1 2 3 5
    0 1(],+/&(_2&{.))@[&0~2-~ 10
0 1 1 2 3 5 8 13 21 34

Как это работает:

Начиная справа (потому что J программы читаются справа налево),

2-~ 6~Оператор меняет аргумент глагола , так это то же самое,6-2

Пока игнорируем раздел в скобках, 0 1(...)@[&0~ xберём глагол в скобках и выполняем его xраз, используя список в 0 1качестве входных данных - ~снова меняются аргументы здесь, давая x (...)@[&0 ] 0 1, что означает, что я могу сохранить ввод в конце функции.

В скобках вилка , ],+/&(_2&{.)которая состоит из трех глаголов - ], ,и +/&(_2&{.).

Вилка берет три глагола a b cи использует их следующим образом: (x a y) b (x c y)где xи yявляются аргументами вилки. Это ,центральный глагол в этой вилке и объединяет результаты x ] yи x +/&(_2&{.) yвместе.

]возвращает левый аргумент без изменений, поэтому x ] yоценивается как x.

+/&(_2&{.)берет два последних элемента из данного списка (_2&{.)- в данном случае 0 1- и затем складывает их вместе +/( &s просто действуют как клей).

После того, как глагол сработал, результат возвращается для следующего запуска, генерируя последовательность.

TI-Basic, 43 символа

:1→Y:0→X
:For(N,1,N
:Disp X
:Y→Z
:X+Y→Y
:Z→X
:End

Этот код может быть непосредственно вставлен в основную программу или преобразован в отдельную программу, на которую ссылается первая.

APL (33)

{⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}

Применение:

   {⍎'⎕','←0,1',⍨'←A,+/¯2↑A'⍴⍨9×⍵-2}7
0 1 1 2 3 5 8

Python (55)

a,b=0,1

for i in range(int(input())):a,b=b,a+b;print(b)

Powershell - 35 символов

Powershell принимает трубопроводный вход , так что я в убеждении , что n |в n | <mycode>не должно быть против моего счета, но вместо этого лишь часть инициирования «функции» на языке.

Первое решение предполагает, что мы начинаем с 0:

%{for($2=1;$_--){($2=($1+=$2)-$2)}}

Второе решение предполагает, что мы можем начать с 1:

%{for($2=1;$_--){($1=($2+=$1)-$1)}}

Пример вызова: 5 | %{for($2=1;$_--){($1=($2+=$1)-$1)}}

Урожайность:

1
1
2
3
5

Интересно отметить , что попытки избежать накладных расходов на for()петле в результате одной и той же количество символов: %{$2=1;iex('($1=($2+=$1)-$1);'*$_)}.

Питон, 43 символа

Вот три принципиально разных однострочника, которые не используют формулу Бине.

f=lambda n:reduce(lambda(r,a,b),c:(r+[b],a+b,a),'.'*n,([],1,0))[0]
f=lambda n:map(lambda x:x.append(x[-1]+x[-2])or x,[[0,1]]*n)[0]
def f(n):a=0;b=1;exec'print a;a,b=b,a+b;'*n

Я никогда не злоупотреблял reduceтак сильно.

постоянный ток, 32 символа:

На самом деле это всегда будет отображать две первые 1, поэтому функция работает только так, как ожидается для N> = 2 .

?2-sn1df[dsa+plarln1-dsn0<q]dsqx

C, 75 символов:

Не так круто, как принятый ответ, но короче и намного быстрее:

main(n,t,j,i){j=0,i=scanf("%d",&n);while(n--)t=i,i=j,printf("%d\n",j+=t);}

CL, 64 символа:

Одна из моих наиболее часто используемых закладок в этом семестре имеет интересный пример, который короче, чем многие другие здесь, и это всего лишь прямой вызов loopмакроса - в основном только одно утверждение! Удалили все, что могли:

(loop repeat n for x = 0 then y and y = 1 then(+ x y)collect y)

Довольно коротко, красиво и читабельно! Для чтения ввода n (включая окружающие пробелы) можно заменить (read), добавив 3 символа.

ЛОЖЬ, 28 байтов

0 1- 1 10[$][@@$@+$." "@1-]#

Python 2, 38 байт

Улучшение ранее опубликованного решения:

a=b=1
exec'print a;a,b=b,a+b;'*input()

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

Python 3, 46 байт

Не так эффективно в Python 3:

a=b=1
exec('print(a);a,b=b,a+b;'*int(input()))

C99, 58 знаков

Следующая функция заполняет массив целых чисел первыми nзначениями из последовательности Фибоначчи, начиная с 0.

void f(int*a,int n){for(int p=0,q=1;n--;q+=*a++)*a=p,p=q;}

Тестировать жгут, принимая nв качестве аргумента командной строки:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
     int n = (argc > 1) ? atoi(argv[1]) : 1;
     int a[n];
     f(a, n);
     for (int i = 0; i < n; ++i)
          printf("%d\n", a[i]);
}

CoffeeScript, 48

f=(n,i=1,j=1)->(console.log i;f n-1,j,i+j)if n>0

65 в js:

function f(n,i,j){if(n>0)console.log(i),f(n-1,(j=j||1),(i||1)+j)}

PHP, 87

function f($n,$a=array(0,1)){echo' '.$a[0];$n>0?f(--$n,array($a[1],array_sum($a))):'';}

Использует array_sumи рекурсивную функцию для генерации рядов.

Например:

 $ php5 fibo.php 9
 0 1 1 2 3 5 8 13 21 34 

F #, 123

let f n = Seq.unfold(fun (i,j)->Some(i,(j,i+j)))(0,1)|>Seq.take n
f 5|>Seq.iter(fun x->printfn "%i" x)

Скала, 65 символов

(Seq(1,0)/:(3 to 9)){(s,_)=>s.take(2).sum+:s}.sorted map println

Это печатает, например, первые 9 чисел Фибоначчи. Для более удобной версии, берущей длину последовательности из ввода с консоли, требуется 70 символов:

(Seq(1,0)/:(3 to readInt)){(s,_)=>s.take(2).sum+:s}.sorted map println

Остерегайтесь использования диапазона, ограничивающего это значениями Int.

Q 24

f:{{x,sum -2#x}/[x;0 1]}

Первые n чисел Фибоначчи

Луа, 85 байт

Я учу Lua, поэтому я хотел бы добавить этот язык в пул.

function f(x)
    return (x<3) and 1 or f(x-1)+f(x-2)
end
for i=1,io.read() do
    print(f(i))
end

и все это заняло 85 символов с параметром в качестве аргумента командной строки. Еще один хороший момент - это то, что его легко читать.

ЛОЖЬ, 20 символов

^1@[1-$][@2ø+$.\9,]#

Ввод должен быть в стеке перед запуском этого.

Пыть , 3 байта

ř⁻Ḟ

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

ř создает массив [1, 2, 3, ..., x]
⁻ Уменьшает каждый элемент один раз (так как Ḟ имеет индекс 0)
Ḟ для каждого элемента в x преобразует его в эквивалент Фибоначчи

машинный код x86 - 379 байт

Версия с заголовками ELF, набравшими 484 байта:

00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 0300 0100 0000 c080 0408 3400 0000  ............4...
00000020: 0000 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
00000030: 0000 0000 0100 0000 0000 0000 0080 0408  ................
00000040: 0000 0000 e401 0000 0010 0000 0500 0000  ................
00000050: 0010 0000 0100 0000 0000 0000 0090 0408  ................
00000060: 0000 0000 0000 0000 0000 1000 0600 0000  ................
00000070: 0010 0000 0000 0000 0000 0000 0000 0000  ................
00000080: 51b9 0090 0408 8801 31c0 ba01 0000 00eb  Q.......1.......
00000090: 0351 89c1 31c0 89c3 43b0 04cd 8031 c099  .Q..1...C....1..
000000a0: 4259 c300 0000 0000 0000 0000 0000 0000  BY..............
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000c0: 31c0 9942 b903 9004 08c6 4101 0ac6 4102  1..B......A...A.
000000d0: 01c6 4103 013a 7103 0f84 ff00 0000 3a71  ..A..:q.......:q
000000e0: 0374 2680 4103 050f b641 036b c008 0041  .t&.A....A.k...A
000000f0: 048a 4104 e887 ffff ff80 6904 30c6 4103  ..A.......i.0.A.
00000100: 0183 e903 3a71 0375 da8a 4104 e86f ffff  ....:q.u..A..o..
00000110: ff3a 7106 0f84 ba00 0000 0fb6 4105 8841  .:q.........A..A
00000120: 060f b641 0788 4105 0fb6 4107 0041 06c6  ...A..A...A..A..
00000130: 4107 003a 7106 0f84 8800 0000 c641 0701  A..:q........A..
00000140: fe49 063a 7106 0f84 7800 0000 c641 0702  .I.:q...x....A..
00000150: fe49 063a 7106 0f84 6800 0000 c641 0703  .I.:q...h....A..
00000160: fe49 063a 7106 0f84 5800 0000 c641 0704  .I.:q...X....A..
00000170: fe49 063a 7106 744c c641 0705 fe49 063a  .I.:q.tL.A...I.:
00000180: 7106 7440 c641 0706 fe49 063a 7106 7434  q.t@.A...I.:q.t4
00000190: c641 0707 fe49 063a 7106 7428 c641 0708  .A...I.:q.t(.A..
000001a0: fe49 063a 7106 741c c641 0709 fe49 063a  .I.:q.t..A...I.:
000001b0: 7106 7410 fe41 08fe 4109 fe49 060f b641  q.t..A..A..I...A
000001c0: 0688 4107 c641 0601 83c1 033a 7106 0f85  ..A..A.....:q...
000001d0: 46ff ffff 3a71 030f 8501 ffff ffb3 0031  F...:q.........1
000001e0: c040 cd80                                .@..

Версия без заголовка (это та, которая будет оценена):

00000000: 67c6 4101 0a67 c641 0201 67c6 4103 0167  g.A..g.A..g.A..g
00000010: 3a71 030f 842a 0167 3a71 0374 2e67 8041  :q...*.g:q.t.g.A
00000020: 0305 6667 0fb6 4103 666b c008 6700 4104  ..fg..A.fk..g.A.
00000030: 678a 4104 e80d 0167 8069 0430 67c6 4103  g.A....g.i.0g.A.
00000040: 0166 83e9 0367 3a71 0375 d267 8a41 04e8  .f...g:q.u.g.A..
00000050: f200 673a 7106 0f84 df00 6667 0fb6 4105  ..g:q.....fg..A.
00000060: 6788 4106 6667 0fb6 4107 6788 4105 6667  g.A.fg..A.g.A.fg
00000070: 0fb6 4107 6700 4106 67c6 4107 0067 3a71  ..A.g.A.g.A..g:q
00000080: 060f 84a3 0067 c641 0701 67fe 4906 673a  .....g.A..g.I.g:
00000090: 7106 0f84 9200 67c6 4107 0267 fe49 0667  q.....g.A..g.I.g
000000a0: 3a71 060f 8481 0067 c641 0703 67fe 4906  :q.....g.A..g.I.
000000b0: 673a 7106 0f84 7000 67c6 4107 0467 fe49  g:q...p.g.A..g.I
000000c0: 0667 3a71 0674 6167 c641 0705 67fe 4906  .g:q.tag.A..g.I.
000000d0: 673a 7106 7452 67c6 4107 0667 fe49 0667  g:q.tRg.A..g.I.g
000000e0: 3a71 0674 4367 c641 0707 67fe 4906 673a  :q.tCg.A..g.I.g:
000000f0: 7106 7434 67c6 4107 0867 fe49 0667 3a71  q.t4g.A..g.I.g:q
00000100: 0674 2567 c641 0709 67fe 4906 673a 7106  .t%g.A..g.I.g:q.
00000110: 7416 67fe 4108 67fe 4109 67fe 4906 6667  t.g.A.g.A.g.I.fg
00000120: 0fb6 4106 6788 4107 67c6 4106 0166 83c1  ..A.g.A.g.A..f..
00000130: 0367 3a71 060f 8521 ff67 3a71 030f 85d6  .g:q...!.g:q....
00000140: fe00 0000 6651 66b9 7801 0000 6788 0166  ....fQf.x...g..f
00000150: 31c0 66ba 0100 0000 eb05 6651 6689 c166  1.f.......fQf..f
00000160: 31c0 6689 c366 43b0 04cd 8066 31c0 6699  1.f..fC....f1.f.
00000170: 6642 6659 c300 0000 0000 00              fBfY.......

$\infty$ числа Фибоначчи.