Вызов
В этой задаче вам дадут целое число N (меньше 10 6 ), найдите минимальный способ суммирования в N, используя только числа Фибоначчи - это разбиение называется представлением Цекендорфа .
Вы можете использовать любое число Фибоначчи более одного раза, и если есть более одного представления, выведите любое.
Например, если входное значение равно 67, то одним из возможных выходных данных может быть использование чисел Фибоначчи 1,3,8,55, которое также является минимальным числом чисел Фибоначчи, которое можно использовать для получения суммы 67 .
Вход N указан в одной строке, входы заканчиваются EOF.
Примеры
Дано в формате input: output
0: 0
47: 34+13
3788: 2584+987+144+55+13+5
1646: 1597+34+13+2
25347: 17711+6765+610+233+21+5+2
677: 610+55+8+3+1
343: 233+89+21
3434: 2584+610+233+5+2
Ограничения
- Количество входов не должно превышать 10 6 значений.
- Ваша программа не должна запускаться более 5 секунд для всех входов.
- Вы можете использовать любой язык по вашему выбору.
- Самое короткое решение побеждает!
code-golf
fibonacci
integer-partitions
донкихотский
источник
источник
Ответы:
Сборка Motorola 68000 - 34 байта
(Синтаксис ассемблера GNU)
36 → 34: заставил генератор Фибоначчи останавливаться при переполнении, а не путем подсчета, и зафиксировал
0
случай, чтобы он выводил,[0]
а не[]
. Однако прохождение негативаN
сейчас вылетает.Комментарий вверху - это прототип C этой функции, использующий расширение языка для определения, куда и куда идут параметры (по умолчанию они идут в стек).
Мой TI-89 с процессором 10 МГц занимает 5 минут, чтобы запустить эту функцию на 1 - 1 000 000.
Хотя машинный код (в настоящее время) меньше байтов, чем решение GolfScript, вероятно, было бы несправедливо принять это как самое короткое решение, потому что:
Если у вас TI-89/92 / V200, вы можете скачать полный проект здесь (устаревший):
https://rapidshare.com/files/154945328/minfib.zip
Удачи в RapidShare, чтобы получить актуальный файл. Кто-нибудь знает хороший хост для таких больших файлов? 8940 - это очень много байтов.
источник
Javascript (142)
Только обрабатывает один вход за один раз. Потому что многострочный ввод бесполезен для JavaScript.
http://jsfiddle.net/EqMXQ/
источник
C, 244 символа
С пробелами:
Эта программа будет читать числа из стандартного ввода и записывать в стандартный вывод.
источник
Golfscript, 43 символа
Я думаю, что это может быть уменьшено на 3–5 символов с большим усилием. Например, разворачивание, чтобы затем выбросить массив, кажется расточительным.
источник
F # -
282 252241 символовисточник
Питон - 183 символа
Большая часть кода обрабатывает несколько входов :(
источник
n=input()
в конце предыдущей строки?print
Mathematica 88
Пример вывода
источник
EXCEL: 89 символов в уникальном коде:
источник
Scala - 353 символа (100 символов для обработки нескольких входов)
источник
Iterator.continually(Console.readLine).takeWhile(_ != "").foreach(line => h(Integer.parseInt(line)))
можно сократить доio.Source.stdin.getLines.foreach(l=>h(Integer.parseInt(l)))
40 символов.Python 3 (170 символов)
Многострочный ввод, остановка на пустой строке
источник
C, 151 символов
читаемая версия:
источник
R 170
Обрабатывает несколько входов и выводит результат в STDOUT
источник
R (460 символов)
Другая версия, использующая R.
Чтение из файла «input», вывод в файл «output»
пример ввода
пример вывода
Более читаемая версия:
источник
D (196 символов)
Беги с
rdmd --eval=…
. Это удобно скрывает шаблонimport x, y, z;
иvoid main() {…}
:источник
Используя Java
источник