Введение
Ваша цель - найти наименьшее количество единиц, которое нужно добавить или умножить вместе, чтобы получить входное значение, это A005245 .
вход
Один положительное целое число N .
Выход
Наименьшее число тех , которые должны быть добавлены / умножаются , чтобы получить N .
Пример ввода
7
Пример вывода
6
объяснение
(
1
+1
+1
) * (1
+1
) +1
= 7Поскольку для этого требуются
6
, выход6
Контрольные примеры
1 1
2 2
3 3
5 5
10 7
20 9
50 12
Так как это проблема кода-гольфа , выигрывает наименьшее количество байтов.
code-golf
sequence
arithmetic
integer
expression-building
Спирали Чюу
источник
источник
f(x) != x.primeFactorisation().sum()
кроме 1?Ответы:
Python 2 ,
7470 байтПопробуйте онлайн!
Альтернативная версия, 59 байт (не проверено)
Это работает по крайней мере до n = 1 000 000 , но мне еще предстоит доказать, что это работает для всех положительных n .
Попробуйте онлайн!
источник
n=a*j+b
сb<j
, но , возможно , нам нужноb>=j
?b>=j
и другоеb>=a
. Но вы правы, не очевидно, что этого не произойдет.a*b+c*d
соa,b,c,d
всеми выражениями суммирования и очень эффективна.Желе ,
1614 байтовСпасибо Денису за сохранение 2 байта!
Попробуйте онлайн!
Логическое объяснение
Дано число n :
1
, ответ1
. Иначе:Представление либо,
a + b
либоa × b
, гдеa
иb
являются выражениями.Рассмотрим все возможные значения
a
иb
:a + b
, тоa
иb
находятся в пределах досягаемости[1 .. n-1]
.a × b
,a
иb
являются собственные делителиn
больше1
.В обоих случаях список
[[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]
вычисляется (ÆḌḊ,Ṗ
), отображает текущую ссылку на каждое число߀€
, добавляет правильные пары вместе (+U$
) и получает минимальное значение (FṂo
).Объяснение кода
источник
JavaScript (ES6),
10896 байтОчень неэффективно;
Array(n>>1)
немного ускоряет его за счет байта. Объяснение:n%++i
ненулевая , еслиi
не является фактором, такn%++i/0
этоInfinity
(и , следовательно , truthy, а также , безусловно , не является минимальным) , еслиi
не является фактором, ноNaN
(и , следовательно , falsy) , еслиi
это фактор. Изменить: 12 байтов сохранены с вдохновением от @ edc65.источник
f(50)
но, к сожалению, Windows Update перезагрузил мой компьютер, прежде чем он мог завершить работу.a
массив. Разве вы не можете объединить оценки в 2 лямбды и взять мин?(i+=2)
другим,++i
поэтому я экономлю всего 12 байт, спасибо!Пари / ГП , 66 байт
Порт Дениса Python ответ :
Попробуйте онлайн!
Пари / ГП , 72 байта
Дольше, но эффективнее:
Попробуйте онлайн!
источник
f(n)=vecmin(concat(n,[f(j)+f(n\j)+f(n%j)|j<-[2..n-1]]))
.Пари / ГП , 213 байтов
Изменить: меня жестоко избили .
Попробуйте онлайн!
источник
Python 2 , 181 байт
Попробуйте онлайн!
источник
f
не должна быть анонимной, так как она вызывает себя рекурсивно.Wolfram Language (Mathematica) , 59 байт
Сохранено 3 байта благодаря Мартину Эндеру. Использование кодировки CP-1252, где
±
один байт.Попробуйте онлайн!
источник
±
вместоf
сохранения 3 байта в предположении, что источник закодирован в CP 1252: tio.run/##y00syUjNTSzJTE78///QRkNbQ@tDG/PirWx9M/…Perl 5 , -p 78 байт
79 байтов в старом стиле (
+1
за-p
)Тот факт, что Perl должен использовать дополнительные
$
для любого скалярного доступа, действительно вредит длине гольфов, которые делают много арифметических ...Этот метод в основном похож на другие, уже опубликованные (попробуйте умножение и сложение, чтобы построить целевое число, выберите самый дешевый). Однако, он не повторяется многократно, поэтому его можно использовать для относительно больших входов.
Он также не пытается минимизировать затраты на построение числа путем сложения или умножения, потому что в perl 5 нет встроенной функции,
min
а числовая сортировка слишком длинная (как видно из сортировки, все еще находящейся в коде). Вместо этого я просто предполагаю, что если число является целевым фактором, я буду использовать умножение. Это безопасно, так как если, например,3
является фактором12
(таким образом, он суммирует стоимость3
и12/3
) позже в цикле, он рассмотрит,9=12-3
что не будет фактором, поэтому9+3
с той же стоимостью, что3+9
и в любом случае будет испытано. Однако это может не сработать для целей<= 4
(это только для1
и2
). Добавление$_
в список, чтобы минимизировать это исправления. К сожалению, мне это не нужно для базовых случаев, потому что я уже инициализирую@;
с правильными начальными значениями, поэтому он стоит 3 байта.Попробуйте онлайн!
источник