Вы можете разложить число больше 0 как уникальную сумму положительных чисел Фибоначчи. В этом вопросе мы делаем это путем многократного вычитания максимально возможного положительного числа Фибоначчи. Например:
1 = 1
2 = 2
3 = 3
4 = 3 + 1
12 = 8 + 3 + 1
13 = 13
100 = 89 + 8 + 3
Теперь я называю произведение Фибоначчи теми же списками, что и выше, но с добавлением, замененным умножением. Например, f(100) = 89 * 8 * 3 = 2136
.
Напишите программу или функцию, которая с положительным целым числом n возвращает произведение Фибоначчи от этого числа.
Testcases:
1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236
code-golf
math
sequence
fibonacci
code-golf
word
code-golf
cipher
code-golf
string
math
subsequence
code-golf
regular-expression
code-golf
brainfuck
assembly
machine-code
x86-family
code-golf
math
factorial
code-golf
math
geometry
code-golf
math
arithmetic
array-manipulation
math
number
optimization
stack
metagolf
code-golf
tips
assembly
code-golf
tips
lisp
code-golf
number-theory
path-finding
code-golf
number
sequence
generation
code-golf
math
geometry
code-golf
grid
permutations
code-golf
code-golf
graphical-output
geometry
fractal
knot-theory
code-golf
math
arithmetic
code-golf
interpreter
balanced-string
stack
brain-flak
code-golf
math
set-theory
code-golf
math
array-manipulation
code-golf
code-golf
string
natural-language
code-golf
code-golf
math
linear-algebra
matrix
code-golf
string
encode
orlp
источник
источник
2
можно разложить как-1 + 3
. Правильное утверждение теоремы Цекендорфа состоит в том, что положительное число Фибоначчи может быть однозначно разложено как сумма непоследовательных чисел Фибоначчи с положительным индексом.Ответы:
Желе ,
1615 байтНе особенно быстро и не дружественно для памяти, но достаточно эффективно для всех тестовых случаев. Попробуйте онлайн!
Как это устроено
источник
Python, 54 байта
Просто старая добрая рекурсия.
источник
Perl,
6963 + 4 (-pl61
флаг) = 67 байтС помощью:
Ungolfed:
Ideone .
источник
061
- это кодировка ASCII для символа'1'
. Хороший хак, чтобы$\
распечатать его практически бесплатно.JavaScript (ES6),
7842 байтаПорт ответа @ Sp3000. Оригинальная 78-байтовая версия:
источник
> <> , 57 байт
Ожидается, что входной номер будет присутствовать в стеке при запуске программы.
Создает последовательность Фибоначчи (
f0, f1, f2, ..., fn
) в стеке, пока не будет достигнуто число, превышающее значение input (i
). Затем с продуктом (p
), инициализированным1
...Попробуйте онлайн!
источник
Pyth, 28 байт
Я думаю, что это может быть гораздо дальше ...
Попробуйте онлайн!
источник
Pyth, 24 байта
Попробуйте онлайн: демонстрация или тестовый набор
Объяснение:
Q
назначается с номером входа.Часть
h.WgQeH,eZsZ1
вычисляет наибольшее число Фибоначчи, которое меньше или равноQ
Так что, если
Q = 10
он генерирует числа / пары:Остальная часть кода вычисляет раздел и умножает числа вместе:
Очевидно, есть много более коротких решений (хотя с очень плохим временем выполнения), например
*FhfqQsTyeM.u,eNsNQ1
.источник
Haskell, 44 байта
Yay для взаимной рекурсии:
a
предыдущее число Фибоначчиb
текущее число Фибоначчиc
это входf
желаемая функцияМеньше гольфа:
источник
На самом деле, 22 байта
Попробуйте онлайн!
Объяснение:
источник
Javascript (ES6)
13410692 байтаСпасибо за @cat для определения места.
Просто неоптимизированная версия, сделанная на моем телефоне, я играю в гольф, как только прихожу домой. Идеи приветствуются.
источник
ВОЗВРАТ , 44 байта
Try it here.
Удивительно неэффективная анонимная лямбда, которая оставляет результат на Stack2. Использование:
ПРИМЕЧАНИЕ. ␌ и ␁ - это заполнители для соответствующих непечатаемых символов: подача формы и начало курса .
объяснение
источник
PHP, 119 байт
Код (для удобства чтения обернут в две строки):
Первая строка вычисляет
$f
числа Фибоначчи меньше, чем$n
(аргумент, указанный в командной строке). Вторая строка вычисляет факторы Фибоначчи (путем вычитания) и умножает их, чтобы вычислить произведение в$o
.Добавьте код
<?php
(технически не является частью программы), поместите его в файл (fibonacci-factors.php
) и запустите его следующим образом:Или запустить его с помощью
php -d error_reporting=0 -r '... code here ...' 100
.Разгнанный код и набор тестов можно найти на Github .
источник
Q, 47 байт
Тестовое задание
читать его как пары (i, map (m, i)), где m - вычисляющая функция, а i - различные аргументы
пишет
объяснение
n funtion\arg
применяет функцию (function (function (... function (args)))) n раз (внутренне использует рекурсию тала) и возвращает последовательность результатов. Мы вычисляем 60 первых элементов ряда Фибоначчи как*+60(|+\)\1 0
. В этом случае функция равна ( | +): + \, примененный к последовательности, вычисляет частичные суммы (ex + \ 1 2 3 равно 1 3 6), и | переворачивает последовательность. Таким образом, на каждой «итерации» мы вычисляем частичные суммы двух предыдущих чисел Фибоначчи и возвращаем частичные суммы, обратные.60(|+\)\1 0
генерирует последовательности 1 0, 1 1, 2 1, 3 2, 5 3, 8 5, 13 8, 21 13, ...*+
примененные к этому результату, переворачивают (traspose) и принимают первое. Результатом является последовательность 1 1 2 3 5 8 13 21 34 55 ..(cond)function\args
применяет функцию (function (.. function (args))), в то время как cond true, и возвращает последовательность частичных результатовfunction[arg]
применяется к функции более чем одного аргумента создает проекцию (частичное применение)Мы можем дать имя аргументам, но неявными именами являются x, y, z
{y-x x bin y}[*+60(|+\)\1 0]
объявляет лямбду с аргументами x, y с частичной проекцией (arg x - ряд Фибоначчи, рассчитывается как * + 60 (| +) \ 1 0). x представляет значения Фибоначчи, а y число для обработки. Бинарный поиск (bin) используется для определения индекса большего числа Фибоначчи <= y (x bin y
) и вычитания соответствующего значения x.Чтобы рассчитать произведение по частичным результатам, мы обращаем их и вычисляем разницу для каждой пары (
-':|
), отбрасываем первое (1_
потому что равно 0) и умножаем на (*/
).Если нас интересует накопленная сумма, код такой же, но
+/
вместо*/
. Мы также можем использовать любой другой диадический оператор вместо + или *Об эффективности исполнения
Я знаю, что в этом конкурсе эффективность не проблема. Но в этой задаче мы можем варьировать от линейных затрат до экспоненциальных, так что мне это интересно.
Я разработал вторую версию (длина 48 байт без комментариев) и повторил тестовые кейсы по 1000 раз на обеих версиях.
время выполнения: оригинальная версия 0'212 сег, новая версия 0'037 сег
Оригинальная версия рассчитывает фиббонитную серию один раз для каждой функции приложения; Новая версия Фибоначчи рассчитывает только один.
В обоих случаях для вычисления ряда Фибоначчи используется хвостовая рекурсия
источник