Фибоначчи orial

36

Определение

Последовательность Фибоначчи F(n)на натуральных числах определяется так:

1. F(1) = 1
2. F(2) = 1
3. F(n) = F(n-1) + F(n-2), where n is an integer and n > 2

Fibonacci-orial положительного целого числа является продуктом [F(1), F(2), ..., F(n)].

задача

Учитывая положительное целое число n, найдите Фибоначчи-Ориал n.

Спекуляции

Фибоначчи 100должно вычисляться менее чем за 5 секунд на приемлемом компьютере.

Testcases

n   Fibonacci-orial of n
1   1
2   1
3   2
4   6
5   30
6   240
7   3120
8   65520
9   2227680
10  122522400
11  10904493600
12  1570247078400
13  365867569267200
14  137932073613734400
15  84138564904377984000
16  83044763560621070208000
17  132622487406311849122176000
18  342696507457909818131702784000
19  1432814097681520949608649339904000
20  9692987370815489224102512784450560000
100 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000

Ссылки

  • Обязательный OEIS A003266
  • OEIS A000045 - последовательность Фибоначчи
Дрянная Монахиня
источник
Относящиеся .
Утренняя монахиня
1
@LuisMendo Сумма Фибоначчи ... вы уже догадались, Фибоначчи. Ну, минус один.
Утренняя монахиня
2
@LeakyNun В настоящее время ответ JavaScript завершает только 15 контрольных примеров, поскольку JavaScript не может правильно сравнивать (или манипулировать) числами, превышающими 2 ^ 53 - 1. Это, скорее всего, похоже на большинство представленных здесь материалов, поскольку большинство языков не цифры поддержки, которые большие
MayorMonty
1
Что вы подразумеваете под "разумным компьютером"?
Эрик Outgolfer
2
-1 потому что это похоже на несколько проблем, взятых вместе (диапазон, фибоначчи каждого, факториал) без особых интересных комбинаций.
Esolanging Fruit

Ответы:

63

Mathematica, 10 байт

Fibonorial

Еще одна встроенная система Mathematica надежно побита языком игры в гольф без встроенной.

Мартин Эндер
источник
49
Я ... что ... почему, Математика ?!
Линн
3
Забыл, что функция даже существовала!
LegionMammal978
3
@ Линн Правило 35 : если оно существует, то есть функция Mathematica;)
Beta Decay
9
@BetaDecay Я думал, что мы установили, что это Правило 110 .
Мартин Эндер
1
Нет, правило 110 - это нечто совсем другое. Хотя я уверен, что у Mathematica есть для этого встроенные функции.
AdmBorkBork
27

Желе , 6 байт

+С1ḊP

Вход 100 заканчивается через 500 мс локально. Попробуйте онлайн!

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

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

   1    Yield 1.
+       Add the left and right argument.
 С     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.
        Collect all values of the left argument into an array.
    Ḋ   Dequeue; discard the first Fibonacci number (0).
     P  Product; multiply the remaining ones.
Деннис
источник
Так не является +¡1ли она встроенной в n-й +С1Фибоначчи и являются ли первые n-числами Фибоначчи?
Caird Coneheringaahing
@cairdcoinheringaahing Довольно много.
Деннис
Я думал, что была встроенная функция Фибоначчи?
MilkyWay90
21

На самом деле , 4 байта

Запускает ввод 100 в течение 0,2 секунды. Код:

R♂Fπ

Объяснение:

R     # Get the range [1, ..., input].
 ♂F   # Map over the array with the fibonacci command.
   π  # Take the product.

Использует кодировку CP-437 . Попробуйте онлайн! ,

Аднан
источник
1
Это правильный инструмент для работы :) Благодаря некоторым улучшениям функции Фибоначчи, которые недавно сделал Лики Нун, 100 тестовых примеров выполняются за 0,1 секунды на TIO .
Mego
16

Brainfuck, 1198 1067 817 770 741 657 611 603

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

Несжатый, с комментариями:

# parse input (max 255)
,[>++++++[-<-------->]<<[->++++++++++<]>>,]
>+>+>>+>+<<<<<<
[->>>
  # compute next fibonacci number
  [[-]<
    [->+<]>>
    [-<+<+>>]<
    # perform carries
    [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<
      [->[-]>>>>>>+>+<<<<<<<<[->+<]]
    ]]]]]]]]]+>>>>>>>>
  ]<<<<<<<<
  # multiplication
  [->
    # extract next digit of F_n (most significant first)
    [-<+<<+>>>]<
    [->+<]>>>
    # move back to the end
    [<<<<<
      [->>>>>>>>+<<<<<<<<]>>>>>>>>>>>>>
    ]<<<<<<<<
    # digit wise multiplication (shifting current digit)
    [->>>
      [-<<<<<<<<+>>>>
        [->+>>+<<<]>
        [-<+>]>>>
      ]<<
      # shift previous total over one gap (in effect multiplying by 10)
      [->>>>>>>+>+<<<<<<<<]<+<<<<<<<<
    ]>>>[-]>>>>>
    # add product to total
    [[-]>
      [->+<]>
      # perform carries
      [-<+>
        [-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>[-<+>
          [->>>>>>+>+<<<<<<<<[-]]
        ]]]]]]]]>
      ]<<[<]+>>>>>>>>
    ]<<<<<<<<
    [<<<<<<<<]>>>>>
    [>>>>>>>>]+<<<<<<<<
  ]>>>>>>>>>>>
  # overwrite previous product
  [<[-]>>
    [-<<+>>]>>>>>>>
  ]<<<<<<<<
  [<<<<<<<<]>>
]>>>>>>
# output product
[>>>>>>>>]<<<<<<<<
[+++++
  [-<++++++++>]<.<<<<<<<
]

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

Время выполнения для n = 100 составляет менее 1 секунды с онлайн-переводчиком (около 0,2 с локально, используя мой собственный переводчик). Максимальное входное значение составляет 255, но для поддержки интерпретатора потребуется ~ 54000 ячеек (он-лайн переводчик, похоже, поддерживает 64 КБ).


Журнал изменений

Сохранено около 130 байтов с лучшим извлечением текущей цифры для умножения на, и путем объединения добавить и перенести в один проход. Это также, кажется, немного быстрее.

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

Разбил еще 50, опять же с лучшим извлечением текущей цифры для умножения на, просто не двигая ее вперед на первой итерации и работая там, где она есть. Дальнейшая микрооптимизация занимает около 10 байт.

Еще 30 ушло. Маркировка цифр, которые уже были приняты с 0, а не 1, облегчает их поиск. Это также делает проверку завершения цикла умножения несколько проще.

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

Сохраненные еще 50, исключив еще одну ячейку, повторно используя маркер для цифр Фибоначчи, чтобы отметить последнюю взятую цифру. Я также смог объединить цикл, чтобы сдвинуть предыдущие итоги с циклом умножения цифр.

Сохранено 8 байтов при разборе ввода. К сожалению.

Примо
источник
14

Python, 45 байт

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

Ввод взят из стандартного ввода. Вывод для n = 100 заканчивается слишком быстро, чтобы точно рассчитать время. n = 1000 занимает примерно 1 с.

Образец использования

$ echo 10 | python fib-orial.py
122522400

$ echo 100 | python fib-orial.py
3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Примо
источник
13

Haskell 41 29 байт

1 + 11 байт, сохраненных замечаниями @ Laikoni.

f=1:scanl(+)1f
(scanl(*)1f!!)

1, fИ !!отдельные лексемы. Первые строки определяют последовательность Фибоначчи, вторая - это функция, которая вычисляет последовательность Фибоначчи и возвращает n-й для данного n. Он начинает печатать цифры практически сразу даже при n = 1000.

Кристиан Сиверс
источник
1
Вы можете избавиться от места (scanl(*)1f!!).
Лайкони
2
И есть более короткий генератор Фибоначчи здесь :f=1:scanl(+)1f
Laikoni
@Laikoni Это удивительно, спасибо!
Кристиан Сиверс
2
@WillNess Я думаю, что меня оправдывают не только действия других пользователей, но и meta.codegolf.stackexchange.com/questions/2419/… и meta.codegolf.stackexchange.com/questions/9031/… (но есть намного больше, и я не прочитал все)
Кристиан Сиверс
1
@ Flawr Вы бы приняли 42+как функцию, которая добавляет 42? Вы не должны, потому что это просто незаконченное выражение. Но в Haskell мы можем добавить круглые скобки и получить раздел (42+) , способ написать функцию \n->42+n. Здесь то же самое, только с !!(двоичный инфиксный оператор для индексации) вместо +и с более сложным первым операндом.
Кристиан Сиверс
11

Python 2, 39 байт

f=lambda n,a=1,b=1:n<1or a*f(n-1,b,a+b)

Проверьте это на Ideone .

Деннис
источник
Вы можете указать, что он возвращает Trueв некоторых случаях.
Утренняя монахиня
5
Это вернуло бы только Trueдля ввода 0 , который не является положительным.
Деннис
6

J, 17 16 байт

1 байт - это лучшее решение для миль.

[:*/+/@(!|.)\@i.

Идея та же, что и в оригинале, но вместо того, чтобы формировать матрицу для работы с второстепенными диагоналями, мы формируем диагонали на лету.


оригинал

Чтобы получить первые n фибономов:

*/\(#{.+//.)!/~i.

Чтение справа налево ...
Создать массив последовательных целых ( i.) с точностью до указанного, из этого массива создать таблицу ( /~) биномиальных коэффициентов ( !), вычисленных по каждой паре в массиве, эта таблица является вершиной треугольника Паскаля, расположенной в конец первой строки и все элементы под главной диагональю равны 0, к счастью для реализации !. Если вы суммируете ( +/) все второстепенные диагонали ( /.), вы получите числа Фибоначчи, но вам нужно взять ( {.) столько же первых элементов из полученного массива, сколько length ( #) самой таблицы. Затем произведение ( */), примененное к последовательным префиксам ( \) массива, приводит к желаемой последовательности фибонориалов.Если вы хотите, вы можете взять только последний, используя еще 2 байта ( {:), но я подумал, что отображать их все - не грех :).
NB. the previous code block is not a J function,

   {:*/\(#{.+//.)!/~i. 10
122522400

Для больших чисел в J вы используете xв конце:

   {:*/\(#{.+//.)!/~i. 100x
3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225...

Программа работает на avarage 0.11s .

   100 timex '{:*/\(#{.+//.)!/~i.100x'
0.112124
Дэн Дуб
источник
1
Альтернативой, которая является функцией, является [:*/+/@(!|.)\@i.использование 16 байтов. Он формирует те же биномиальные коэффициенты вдоль таблицы, которую вы генерируете, !/~за исключением того, что он формирует ее, используя префиксы i..
миль
4

Pyth, 13 байт

u*Gs=[sZhZ)Q1

демонстрация

Это использует умный, не типичный трюк. Пять персонажей (u*G ... Q1 ) говорят, что результат является продуктом ввода многих чисел. Остальная часть кода генерирует числа.

=[sZhZ)обновляет переменную Zв списке [s(Z), h(Z)]. Затем sсуммирует этот список для умножения.

Zизначально равен 0. s, для целых чисел, это функция тождества. h, на его, это + 1функция. Так что на первой итерации Zстановится [0, 1]. sв списках есть функция суммы, как упомянуто выше. hэто функция головы. Итак, вторая итерация [1, 0].

Вот список:

Iter  Z          Sum
0     0          Not used
1     [0, 1]     1
2     [1, 0]     1
3     [1, 1]     2
4     [2, 1]     3
5     [3, 2]     5

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

isaacg
источник
4

Mathematica 25 24 байта

С благодарностью Мартину Эндеру.

1##&@@Fibonacci@Range@#&

1##&@@Fibonacci@Range@#&@100

Время: 63 микросекунды.

{0.000063, 
3371601853146468125386964065447576689828006172937411310662486977801540
6711385898686165008341900290675836651822917015531720110825745874313823
1009903039430687777564739516714333248356092511296002464445971530050748
1235056111434293619038347456390454209587101225261757371666449068625033
9995735521655245297254676280601708866020010771376138030271586483293355
0772869860576999281875676563330531852996518618404399969665040724619325
7877568825245646129366994079739720698147440310773871269639752334356493
6789134243905645353892122400388956268116279491329780860702550826683922
9003714114129148483959669418215206272639036409444764264391237153249138
8089634845995941928089653751672688740718152064107169357399466473375804
9722605947689699525073466941890502338235963164675705844341280523988912
2373033501909297493561702963891935828612435071136036127915741683742890
4150054292406756317837582840596331363581207781793070936765786629772999
8328572573496960944166162599743042087569978353607028409125185326833249
36435856348020736000000000000000000000000}
DavidC
источник
Поочередно, с таким же количеством байтов:1##&@@Fibonacci~Array~#&
Грег Мартин
4

Желе, 8 байт

RḶUc$S€P

Моя первая подача в желе. Он не такой короткий, как ответ @Dennis , но его длина всего на 2 байта при использовании другого метода.

Локально, это требует около 400 мс по сравнению с 380 мс с версией @Dennis для n = 100.

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

объяснение

RḶUc$S€P  Input: n
R         Generate the range [1, 2, ..., n]
          For each value x in that range
 Ḷ          Create another range [0, 1, ..., x-1]
  U         Reverse that list
   c        Compute the binomial coefficients between each pair of values
    $       Bind the last two links (Uc) as a monad
     S€   Sum each list of binomial coefficients
          This will give the first n Fibonacci numbers
       P  Take the product of those to compute the nth Fibonacci-orial
миль
источник
3

PARI / GP, 29 байт

f=n->prod(i=1,n,fibonacci(i))

Или в качестве альтернативы:

f=n->prod(i=a=!b=0,n,b=a+a=b)
Примо
источник
3

R, 99 96 78 76 66 байт

Этот ответ использует формулу Бине , а также prod(x)функцию. Поскольку R не имеет встроенного Phiзначения, я определил его сам:

p=(1+sqrt(5))/2;x=1;for(n in 1:scan())x=x*(p^n-(-1/p)^n)/sqrt(5);x

Это работает менее чем за 5 секунд, но R имеет тенденцию давать Infв качестве ответа для этих больших чисел ...

Ungolfed:

r=sqrt(5)
p=(1+r)/2 
x=1
for(n in 1:scan())        
    x=x*(p^n-(-1/p)^n)/r    
x

-2 байта благодаря @Cyoce!
О, я люблю этот сайт! -10 байт благодаря @ user5957401

Фредерик
источник
Можно было бы немного сэкономить, сохранив sqrt(5)переменную
Cyoce
Поскольку вы используете только Nодин раз, вы можете просто вызвать сканирование внутри 1:Nбита. то есть for(n in 1:scan()). Вы также можете сохранить несколько символов, просто используя *вместо prod()функции в вашем цикле for. Ваш цикл for состоит только из одной строки, поэтому вам также не нужны фигурные скобки.
user5957401
Хорошая идея использовать формулу Бине. В твоем духе но только 53 байтаfunction(n,N=1:n,p=5^.5)prod(((1+p)^N-(1-p)^N)/2^N/p)
Майкл М
3

R, 82 , 53 , 49 байтов (48 байтов с различным стилем ввода)

b=d=1;a=0;for(i in 1:scan()){d=d*b;b=a+b;a=b-a};d

Если мы можем просто предшествовать коду с введенным номером, мы получим 48 байт

->n;b=d=1;a=0;for(i in 1:n){d=d*b;b=a+b;a=b-a};d

РЕДАКТИРОВАТЬ: новый код. Оригинал ниже:

a=function(n)ifelse(n<3,1,{v=c(1,1,3:n);for(i in 3:n)v[i]=v[i-1]+v[i-2];prod(v)})

a(100)Хотя не верну ничего, кроме Inf . И это не будет работать ни для чего, кроме неотрицательных целых чисел.

Ungolfed:

a=function(n){
   if(n<3) return(1)
   v=c(1,1,3:n)
   for(i in 3:n)
       v[i]=v[i-1]+v[i-2]
   prod(v)
}
user5957401
источник
3

Java, 165 байт

Golfed:

BigInteger f(int n){BigInteger[]a={BigInteger.ZERO,BigInteger.ONE,BigInteger.ONE};for(int i=0;i<n;){a[++i%2]=a[0].add(a[1]);a[2]=a[2].multiply(a[i%2]);}return a[2];}

Это еще один случай, когда BigIntegerтребуется из-за большого количества. Однако мне удалось свести текст BigIntegerк минимуму, уменьшив его размер. Я также сравнил со статическим импортом, и это увеличило общую длину.

Эта программа работает, отслеживая три числа в массиве. Первые два - два предыдущих числа Фибоначчи. Третье - это накопленная стоимость. Цикл начинается с вычисления следующего значения и сохранения его в чередующихся (0, 1, 0, 1, ...) индексах массива. Это позволяет избежать необходимости сдвигать значения с помощью дорогостоящих (с точки зрения размера источника) операций присваивания. Затем возьмите это новое значение и умножьте его на аккумулятор.

Избегая временных объектов и ограничивая цикл двумя операторами присваивания, я смог выжать довольно много байтов.

Ungolfed:

import java.math.BigInteger;

public class Fibonacci_orial {

  public static void main(String[] args) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "1", "1" },
      { "2", "1" },
      { "3", "2" },
      { "4", "6" },
      { "5", "30" },
      { "6", "240" },
      { "7", "3120" },
      { "8", "65520" },
      { "9", "2227680" },
      { "10", "122522400" },
      { "11", "10904493600" },
      { "12", "1570247078400" },
      { "13", "365867569267200" },
      { "14", "137932073613734400" },
      { "15", "84138564904377984000" },
      { "16", "83044763560621070208000" },
      { "17", "132622487406311849122176000" },
      { "18", "342696507457909818131702784000" },
      { "19", "1432814097681520949608649339904000" },
      { "20", "9692987370815489224102512784450560000" },
      { "100", "3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new Fibonacci_orial().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  BigInteger f(int n) {
    BigInteger[] a = { BigInteger.ZERO, BigInteger.ONE, BigInteger.ONE };
    for (int i = 0; i < n;) {
      a[++i % 2] = a[0].add(a[1]);
      a[2] = a[2].multiply(a[i % 2]);
    }
    return a[2];
  }
  // End golf

}

Выход программы:

Input: 1
Expected: 1
Actual:   1

Input: 2
Expected: 1
Actual:   1

Input: 3
Expected: 2
Actual:   2

Input: 4
Expected: 6
Actual:   6

Input: 5
Expected: 30
Actual:   30

Input: 6
Expected: 240
Actual:   240

Input: 7
Expected: 3120
Actual:   3120

Input: 8
Expected: 65520
Actual:   65520

Input: 9
Expected: 2227680
Actual:   2227680

Input: 10
Expected: 122522400
Actual:   122522400

Input: 11
Expected: 10904493600
Actual:   10904493600

Input: 12
Expected: 1570247078400
Actual:   1570247078400

Input: 13
Expected: 365867569267200
Actual:   365867569267200

Input: 14
Expected: 137932073613734400
Actual:   137932073613734400

Input: 15
Expected: 84138564904377984000
Actual:   84138564904377984000

Input: 16
Expected: 83044763560621070208000
Actual:   83044763560621070208000

Input: 17
Expected: 132622487406311849122176000
Actual:   132622487406311849122176000

Input: 18
Expected: 342696507457909818131702784000
Actual:   342696507457909818131702784000

Input: 19
Expected: 1432814097681520949608649339904000
Actual:   1432814097681520949608649339904000

Input: 20
Expected: 9692987370815489224102512784450560000
Actual:   9692987370815489224102512784450560000

Input: 100
Expected: 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000
Actual:   3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000

источник
2

Рубин, 39 байт

->n{f=i=b=1;n.times{f,i,b=i,f+i,b*f};b}
Линн
источник
36: -> n {f = i = b = 1; n.times {b * = f; i = f + f = i}; b}
GB
2

Javascript (ES6), 51 39 байт

Рекурсивная реализация (39 байт)

f=(n,a=p=i=b=1)=>++i<n?f(n,b,p*=b+=a):p

Оригинальная реализация (51 байт)

n=>{for(i=a=b=p=1;++i<n;){c=a;a=b;p*=b+=c}return p}

Примечание. Начинается ошибка округления для числа Фибоначчи, равного 16, 100 - это просто бесконечность, запускается, как представляется, <1 секунда.

Pandacoder
источник
Я сделал альтернативную 53-байтовую версию n=>[...Array(n)].reduce(p=>(c=a,a=b,p*=b+=c),a=1,b=0)только для того, чтобы узнать, что вы посчитали, f=что не требуется, сэкономив вам 2 байта.
Нил
Честная оценка. Мое обоснование было таким, что его можно было вызывать и использовать повторно, а не просто вызывать.
Пандакодер
Конечно, но если кто-то хочет использовать его повторно, у него все еще есть возможность присвоить ему имя.
Нил
@Neil Хорошо, теперь я пошел и повторно внедрил это, и теперь f = является обязательным, иначе это не может фактически выполнить. : D
Пандакодер
Ну, по крайней мере, вы исправили количество байтов для оригинальной реализации.
Нил
2

DC (GNU или OpenBSD) , 36 байт

Файл A003266-v2.dc:

0sA1sB1?[1-d0<LrlBdlA+sBdsA*r]dsLxrp

(без завершающей строки)

... теперь результат хранится в стеке вместо использования именованного регистра ( Yв версии 1). Команда rне доступна в оригинале dc(см. Страницу Dc RosettaCode ).

Бег:

$ time dc -f A003266-v2.dc <<< 100
337160185314646812538696406544757668982800617293741131066248697780154\
067113858986861650083419002906758366518229170155317201108257458743138\
231009903039430687777564739516714333248356092511296002464445971530050\
748123505611143429361903834745639045420958710122526175737166644906862\
503399957355216552452972546762806017088660200107713761380302715864832\
933550772869860576999281875676563330531852996518618404399969665040724\
619325787756882524564612936699407973972069814744031077387126963975233\
435649367891342439056453538921224003889562681162794913297808607025508\
266839229003714114129148483959669418215206272639036409444764264391237\
153249138808963484599594192808965375167268874071815206410716935739946\
647337580497226059476896995250734669418905023382359631646757058443412\
805239889122373033501909297493561702963891935828612435071136036127915\
741683742890415005429240675631783758284059633136358120778179307093676\
578662977299983285725734969609441661625997430420875699783536070284091\
2518532683324936435856348020736000000000000000000000000

real    0m0.005s
user    0m0.004s
sys     0m0.000s

Пытаюсь объяснить:

tosявляется содержимым вершины стека, не удаляя его.
nosэто элемент ниже tos.

0 sA # push(0) ; A=pop()
1 sB # push(1) ; B=pop()
1    # push(1)
     # this stack position will incrementally hold the product
?    # push( get user input and evaluate it )
[    # start string
 1-  # push(pop()-1)
 d   # push(tos)
 0   # push(0)
 <L  # if pop() < pop() then evaluate contents of register L
 r   # exchange tos and nos
     # now nos is the loop counter
     # and tos is the bucket for the product of the fibonacci numbers
 lB  # push(B)
 d   # push(tos)
 lA  # push(A)
 +   # push(pop()+pop())
     # now tos is A+B, nos still is B 
 sB  # B=pop()
     # completes B=A+B
 d   # push(tos)
 sA  # A=pop()
     # completes B=A
     # tos (duplicated new A from above) is the next fibonacci number
 *   # push(nos*tos)
     # tos now is the product of all fibonacci numbers calculated so far
 r   # exchange tos and nos
     # now tos is the loop counter, nos is the product bucket
]    # end string and push it
d    # push(tos)
sL   # L=pop()
x    # evaluate(pop())
r    # exchange tos and nos
     # nos now is the former loop counter
     # tos now is the complete product. \o/
p    # print(tos)
     # this does not pop() but who cares? :-P

DC , 41 байт

... прямо, никаких хитростей

Файл A003266-v1.dc:

0sA1sB1sY?[1-d0<LlBdlA+sBdsAlY*sY]dsLxlYp

(без завершающей строки)

Бег:

$ for i in $(seq 4) ; do dc -f A003266-v1.dc <<< $i ; done
1
1
2
6
$ time dc -f A003266-v1.dc <<< 100
337160185314646812538696406544757668982800617293741131066248697780154\
067113858986861650083419002906758366518229170155317201108257458743138\
231009903039430687777564739516714333248356092511296002464445971530050\
748123505611143429361903834745639045420958710122526175737166644906862\
503399957355216552452972546762806017088660200107713761380302715864832\
933550772869860576999281875676563330531852996518618404399969665040724\
619325787756882524564612936699407973972069814744031077387126963975233\
435649367891342439056453538921224003889562681162794913297808607025508\
266839229003714114129148483959669418215206272639036409444764264391237\
153249138808963484599594192808965375167268874071815206410716935739946\
647337580497226059476896995250734669418905023382359631646757058443412\
805239889122373033501909297493561702963891935828612435071136036127915\
741683742890415005429240675631783758284059633136358120778179307093676\
578662977299983285725734969609441661625997430420875699783536070284091\
2518532683324936435856348020736000000000000000000000000

real    0m0.006s
user    0m0.004s
sys     0m0.004s

источник
1
* вздох! * ... писать dcкод определенно проще, чем объяснять его ...
1
Да, нам действительно нужна IDE с каким-то сумасшедшим гаджетом для визуализации нескольких стеков ... это было бы здорово.
Джо
1
У меня есть несколько идей, что добавить в качестве новых команд, но идея с наибольшим эффектом выглядит следующим образом: Добавить команду «изменить стек по умолчанию». ;-)
2
... или поменять стек по умолчанию с именованным регистром. Это сделало бы больше узлов в мозгах пользователей, но не требовалось бы, чтобы имя стека по умолчанию имело имя ...] :-)
1
Да, это определенно было бы удобно! Я также хотел бы очистить один элемент, повернуть элементы, которые не находятся на вершине стека, и, возможно, перенести верхние nэлементы в другой стек сразу. Пока, однако, я все еще не знаю, как скомпилировать dcиз исходного кода. : /
Джо
2

C # 110 109 107 103 101 94 байта

using i=System.Numerics.BigInteger;i f(i n){i a=0,b=1,x=1;for(;n-->0;)x*=a=(b+=a)-a;return x;}

объяснение

//Aliasing BigInteger saves a few bytes
using i=System.Numerics.BigInteger;

//Since BigInteger has an implicit from int we can also change the input
//and save two more bytes.
i f(i n)
{
    //using an alternative iterative algorithm (link to source below) to cut out the temp variable
    //b is next iteration, a is current iteration, and x is the running product
    i a = 0, b = 1, x = 1; 

    //post decrement n down to zero instead of creating a loop variable
    for (; n-- > 0;)

        //The bracket portion sets the next iteration             
        //get the current iteration and update our running product
        x *= a = (b += a) - a;

    return x;
}

Итерационный алгоритм Фибоначчи

ДжастинМ - Восстановить Монику
источник
Учитывая, что это работает намного лучше, чем я ожидал, я хотел найти максимальное значение N, которое вернется менее чем через 5 секунд, я получил 1540, который дает число длиной 247441 цифр.
JustinM - Восстановить Монику
Впечатляет. Сколько времени занимает 1541, чтобы посчитать из любопытства?
Пандакодер
@Pandacoder Итак, с недавним изменением алгоритма он стал значительно быстрее. 1541 за 755 мс, так что я сейчас найду новый саб 5 макс.
JustinM - Восстановить Монику
@Pandacoder, так что время работы меняется примерно на 100 мс, но 2565, кажется, в среднем около 5 секунд
JustinM - Восстановить Монику
Как долго это число?
Пандакодер
2

Мозг-Flak , 54 байта

([{}]<(())>){(({})()<{({}()<([({})]({}{}))>)}{}{}>)}{}

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

Умножение в Brain-Flak занимает много времени для больших входов. Просто умножаем F 100 на F 99 с помощью общего алгоритма умножения заняло бы миллиарды лет.

К счастью, есть более быстрый способ. Обобщенная последовательность Фибоначчи, начинающаяся с(k, 0) будет генерировать те же члены, что и обычная последовательность, умноженная наk . Используя это наблюдение, Brain-Flak может умножаться на число Фибоначчи так же легко, как он может генерировать числа Фибоначчи.

Если стек состоит из -nдвух чисел с последующим {({}()<([({})]({}{}))>)}{}{}вычислениемn итерации обобщенной последовательности Фибоначчи и отбрасываться все до последнего. Остальная часть программы просто устанавливает начальную 1 и повторяет ее для всех чисел в диапазоне n...1.

Вот тот же алгоритм на других языках, предоставляемых этим интерпретатором:

Brain-Flak Classic, 52 байта

({}<(())>){(({})[]<{({}[]<(({}<>)<>{}<>)>)}{}{}>)}{}

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

Brain-Flueue, 58 байт

<>(<(())>)<>{(({}<>)<{({}({}))({}[()])}{}>[()]<>)}<>({}){}

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

Мини-Флак, 62 байта

([{}()](())){(({})()({({}()([({})]({}{}))[({})])}{}{})[{}])}{}

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

Nitrodon
источник
1

Mathematica - 32 26 байтов

Fibonacci@i~Product~{i,#}&

@MartinEnder нарезал 6 байтов!

Yytsi
источник
1

GAP 28 байт

До сегодняшнего дня не знал, что GAP имеет Fibonacciвстроенную функцию .

n->Product([1..n],Fibonacci)
Кристиан Сиверс
источник
Можете ли вы ссылку на GAP? Понятия не имею, что это.
Утренняя монахиня
О, конечно (но я не первый, кто использует это здесь ...)
Кристиан Сиверс
1

Рубин, 85 байт

g =->x{(1..x).to_a.collect{|y|(0..y).inject([1,0]){|(a,b),_|[b, a+b]}[0]}.inject(:*)}

Получилось хорошо, но, возможно, есть более короткое решение.

Быстрый расчет Фибоначчи взят здесь: ссылка

Проверьте это здесь

Seims
источник
1

Юлия, 36 байт

!x=[([1 1;1 0]^n)[2]for n=1:x]|>prod
Линн
источник
1

Брейк-Флак , 110 104 100 байт

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

({}<((())<>)>){({}[()]<<>(({})<>({}<>)<>)>)}<>{}([[]]()){({}()<({}<>)<>({<({}[()])><>({})<>}{})>)}{}

объяснение

Сначала мы запускаем улучшенную версию любезности генератора последовательностей Фибоначчи доктора Грина Эггса и Железного Человека

({}<((())<>)>){({}[()]<<>(({})<>({}<>)<>)>)}<>{}

Тогда, пока в стеке есть более одного элемента

([[]]()){({}()<...>)}

умножить два верхних элемента

({}<>)<>({<({}[()])><>({})<>}{})

и вытолкнуть лишний ноль

{}
Мастер пшеницы
источник
1
К сожалению, я думаю, что это неверно, поскольку для ввода 25 требуется более 10 секунд. Алгоритм очень неэффективен (как и язык), поэтому вычисление его для 100, вероятно, займет часы.
DJMcMayhem
1

Clojure, 70 байт

Clojure не очень хороший язык для игры в гольф. Ну что ж.

Попробуйте это на http://tryclj.com .

(last(nth(iterate(fn[[a b r]][b(+ a b)(* r(+ a b))])[0N 1 1])(dec n)))
user16973
источник
1

Свифт, 68 байт

func f(n:Int,_ a:Int=1,_ b:Int=1)->Int{return n<1 ?1:a*f(n-1,b,a+b)}
Александр - Восстановить Монику
источник
1

JavaScript (ES6), 46 байт

f=(n,a=1,b=1,c=i=1)=>n==i?c:f(n,b,a+b,c*b,++i)

Использует рекурсивные и аккумуляторные переменные. Ошибки округления начинаются с f(16).

CPU1
источник