Я нашел эту последовательность во время работы над Evolution of OEIS , но не удосужился опубликовать ее как ответ. После написания эталонной реализации в Mathematica я подумал, что это забавное упражнение, которое нужно выполнить как отдельную задачу, так что здесь мы идем.
Давайте построим числовой реактор деления! Рассмотрим положительное целое число N
. В качестве примера рассмотрим 24
. Чтобы разделить это число, мы должны найти наибольшее число последовательных натуральных чисел, которые суммируются N
. В этом случае это так 7 + 8 + 9 = 24
. Итак, мы разделились 24
на три новых числа. Но это не было бы большой частью реактора деления без цепных реакций. Итак, давайте рекурсивно повторим процесс для этих компонентов:
24
/|\
/ | \
/ | \
7 8 9
/ \ /|\
3 4 / | \
/ \ / | \
1 2 2 3 4
/ \
1 2
Обратите внимание, что мы останавливаем процесс всякий раз, когда число не может быть разложено на меньшие последовательные целые числа. Также обратите внимание, что мы могли бы написать 9
как 4 + 5
, но 2 + 3 + 4
имеет больше компонентов. Деление число от N
теперь определяется как количество целых чисел , полученных в этом процессе, в том числе N
себя. Вышеуказанное дерево имеет 13 узлов, поэтому F(24) = 13
.
Эта последовательность является записью OEIS A256504 .
Первые 40 терминов, начиная с N = 1
, являются
1, 1, 3, 1, 5, 6, 5, 1, 6, 7, 12, 10, 12, 11, 12, 1, 8, 16, 14, 17, 18, 18,
23, 13, 21, 18, 22, 23, 24, 19, 14, 1, 22, 20, 23, 24, 31, 27, 25, 26
Первые 1000 терминов можно найти в этой пастбине .
Соревнование
Учитывая положительное целое число N
, определите его число деления F(N)
. (Таким образом, вам не нужно покрывать ведущих, 0
перечисленных в OEIS.)
Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).
Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.
Бонусный вопрос: можете ли вы найти какие-нибудь интересные свойства этой последовательности?
источник
Ответы:
Pyth,
232221 байтЭто определяет рекурсивную функцию
y
. Попробуйте онлайн: демонстрацияОбъяснение:
источник
Деление ,
1328989887797 байтЭтот ответ немного неоправданно длинен (хотелось бы, чтобы у нас были разборные регионы ) ... пожалуйста, не забудьте прокрутить мимо этого и показать другим ответам некоторую любовь!
Работа над этим кодом была тем, что вдохновило этот вызов. Я хотел добавить ответ в Fission в EOEIS, что привело меня к этой последовательности. Тем не менее, на самом деле изучение Fission и его внедрение заняло несколько недель, включая и выключая его. В то же время, последовательность действительно выросла на мне, поэтому я решил опубликовать для нее отдельную задачу (плюс, в любом случае, EOEIS не был бы слишком далеко внизу дерева).
Итак, я представляю вам, чудовище:
Ожидается, что на входе нет завершающего символа новой строки, так что вы можете назвать его как
echo -n 120 | ./Fission oeis256504.fis
.Компоновка, возможно, все еще может быть более эффективной, поэтому я думаю, что здесь еще много возможностей для совершенствования (например, она содержит
911581461374 пробелов).Прежде чем мы перейдем к объяснению, обратите внимание на проверку: официальный переводчик работает не совсем так, как есть. а)
Mirror.cpp
не компилируется во многих системах. Если вы столкнулись с этой проблемой, просто закомментируйте ошибочную строку - уязвимый компонент (случайное зеркало) не используется в этом коде. б) Есть пара ошибок, которые могут привести к неопределенному поведению (и, скорее всего, для такой сложной программы). Вы можете применить этот патч, чтобы исправить их. Как только вы это сделаете, вы сможете скомпилировать интерпретатор сИнтересный факт: эта программа использует почти все компоненты, которые может предложить Fission, за исключением
#
(случайное зеркало),:
(полупрозрачное зеркало)-
или|
(обычное зеркало) и"
(режим печати).Что на земле?
Предупреждение: это будет довольно долго ... Я предполагаю, что вы действительно заинтересованы в том, как работает Fission и как можно программировать в ней. Потому что если нет, я не уверен, как я мог бы обобщить это. (Следующий абзац дает общее описание языка.)
Fission - это двумерный язык программирования, где потоки данных и управления представлены атомами, движущимися через сетку. Если вы видели или использовали Marbelous раньше, концепция должна быть смутно знакомой. Каждый атом имеет два целочисленных свойства: неотрицательную массу и произвольную энергию. Если масса становится отрицательной, атом удаляется из сетки. В большинстве случаев вы можете рассматривать массу как «значение» атома, а энергию как некое мета-свойство, которое используется несколькими компонентами для определения потока атомов (то есть большинство видов переключателей зависят от знака энергия). Я буду обозначать атомы
(m,E)
, когда это необходимо. В начале программы сетка начинается со связки(1,0)
атомы, где бы вы ни находились, из четырех компонентовUDLR
(где буква указывает направление, в котором атом движется изначально). Затем доска заполняется целой кучей компонентов, которые изменяют массу и энергию атомов, меняют их направления или делают другие более сложные вещи. Полный список см. На странице esolangs , но я представлю большинство из них в этом объяснении. Другим важным моментом (который программа использует несколько раз) является то, что сетка является тороидальной: атом, который сталкивается с любой из сторон, вновь появляется на противоположной стороне, двигаясь в том же направлении.Я написал программу в нескольких небольших частях и собрал их в конце, так что вот как я объясню.
atoi
Этот компонент может показаться довольно неинтересным, но он приятен и прост и позволяет мне представить множество важных понятий арифметики и потока управления деления. Поэтому я подробно расскажу об этой части, поэтому я могу свести остальные части к введению новой механики деления и выделению компонентов более высокого уровня, с подробным потоком управления которыми вы сможете следить самостоятельно.
Fission может считывать только байтовые значения отдельных символов, а не целых чисел. Несмотря на то, что это приемлемая практика , я решил, что могу сделать это правильно и проанализировать действительные целые числа в STDIN. Вот
atoi
код:Двумя наиболее важными компонентами деления являются реакторы деления и синтеза. Реакторы деления являются любыми из
V^<>
(код выше использует<
и>
). Реактор деления может хранить атом (отправляя его в клин персонажа), по умолчанию(2,0)
. Если атом достигнет вершины персонажа, два новых атома будут отосланы в стороны. Их масса определяется путем деления поступающей массы на сохраненную массу (т.е. делится пополам по умолчанию) - левый атом получает это значение, а правый атом получает остаток массы (т. Е. Масса сохраняется при делении) , Оба исходящих атома будут иметь входящую энергию минуснакопленная энергия. Это означает, что мы можем использовать реакторы деления для арифметики - как для вычитания, так и для деления. Если реактор деления попадает с площадки, атом просто отражается по диагонали и затем будет двигаться в направлении вершины персонажа.Реакторы Fusion являются любыми из
YA{}
(код выше используетY
и{
). Их функция аналогична: они могут хранить атом (по умолчанию(1,0)
), и при попадании из вершины два новых атома будут отправлены в стороны. Однако в этом случае два атома будут идентичны, всегда сохраняя поступающую энергию и умножая поступающую массу на сохраненную массу. То есть по умолчанию термоядерный реактор просто дублирует любой атом, попадающий в его вершину. При ударе сбоку реакторы термоядерного синтеза немного сложнее: атом тожесохраняется (независимо от другой памяти), пока атом не попадет на противоположную сторону. Когда это происходит, новый атом высвобождается в направлении вершины, масса и энергия которой являются суммой двух старых атомов. Если новый атом попадает на ту же сторону до того, как соответствующий атом достигает противоположной стороны, старый атом просто перезаписывается. Реакторы синтеза могут быть использованы для осуществления сложения и умножения.Другой простой компонент , я хочу , чтобы выйти из пути есть
[
и]
которые просто установить направление атома направо и налево, соответственно (независимо от входящего направления). Вертикальными эквивалентами являютсяM
(вниз) иW
(вверх), но они не используются дляatoi
кода.UDLR
также действовать какWM][
после освобождения их начальных атомов.В любом случае, давайте посмотрим на код там. Программа начинается с 5 атомов:
R
ИL
на дне просто получить их прирост массы (с+
) , чтобы стать ,(10,0)
а затем хранили в делении и термоядерного реактора, соответственно. Мы будем использовать эти реакторы для анализа ввода base-10.L
верхнем правом углу масса уменьшается (с_
), чтобы стать(0,0)
и хранится в стороне от термоядерного реактораY
. Это нужно для того, чтобы отслеживать число, которое мы читаем - мы будем постепенно увеличивать и умножать это по мере того, как будем читать цифры.R
верхнем левом углу его масса устанавливается в код символа0
(48) с'0
, затем масса и энергия меняются местами@
и, наконец, масса увеличивается один раз,+
чтобы дать(1,48)
. Затем он перенаправляется с диагональными зеркалами\
и/
хранится в реакторе деления. Мы будем использовать48
вычитание для преобразования входных данных ASCII в фактические значения цифр. Нам также пришлось увеличить массу,1
чтобы избежать деления на0
.U
нижний левый угол - это то, что фактически приводит все в движение и изначально используется только для управления потоком.После перенаправления вправо управляющий атом попадает
?
. Это входной компонент. Он читает символ и устанавливает массу атома в значение ASCII для чтения, а энергию - в0
. Если вместо этого мы нажмем EOF, энергия будет установлена на1
.Атом продолжается, а затем ударяет
%
. Это переключатель зеркала. Для неположительной энергии это действует как/
зеркало. Но для положительной энергии она действует как a\
(а также уменьшает энергию на 1). Поэтому, пока мы читаем символы, атом будет отражаться вверх, и мы можем обработать символ. Но когда мы закончим с вводом, атом будет отражен вниз, и мы можем применить другую логику для получения результата. К вашему сведению, противоположный компонент есть&
.Итак, у нас сейчас атом движется вверх. Что мы хотим сделать для каждого символа, это прочитать его цифровое значение, добавить его к нашему промежуточному итогу и затем умножить это промежуточное значение на 10, чтобы подготовиться к следующей цифре.
Сначала атом персонажа попадает в (по умолчанию) термоядерный реактор
Y
. Это разделяет атом, и мы используем левую копию в качестве управляющего атома, чтобы вернуться к компоненту ввода и прочитать следующий символ. Правильная копия будет обработана. Рассмотрим случай, когда мы прочитали персонажа3
. Наш атом будет(51,0)
. Мы поменялись массой и энергией с тем@
, чтобы мы могли воспользоваться вычитанием следующего реактора деления. Реактор вычитает48
энергию (без изменения массы), поэтому он отсылает две копии(0,3)
- энергия теперь соответствует цифре, которую мы прочитали. Исходящая копия просто отбрасывается;
(компонент, который просто уничтожает все входящие атомы). Мы продолжим работать с исходящей копией. Вам нужно будет следовать по его пути через/
и\
немного отражает.@
Непосредственно перед термоядерным реактором SWAPS массы и энергии снова, таким образом, что мы добавим(3,0)
к нашему нарастающему итогу вY
. Обратите внимание, что сам промежуточный итог всегда будет иметь0
энергию.Сейчас
J
прыжок. То, что он делает, это скачок любого входящего атома вперед его энергией. Если это так0
, атом просто продолжает двигаться прямо. Если это1
будет пропустить одну ячейку, если2
это будет пропустить две ячейки и так далее. Энергия расходуется на прыжок, поэтому атом всегда заканчивается энергией0
. Поскольку текущий итог имеет нулевую энергию, скачок пока игнорируется, и атом перенаправляется в термоядерный реактор,{
который умножает его массу на10
. Нисходящая копия сбрасывается, в;
то время как исходная копия возвращается вY
реактор в качестве новой рабочей суммы.Вышеприведенное повторяется (забавным конвейерным способом, где новые цифры обрабатываются до того, как будут выполнены предыдущие), пока мы не нажмем EOF. Теперь
%
атом отправит вниз. Идея заключается в том , чтобы превратить этот атом в(0,1)
теперь перед ударять работает общий реактор так , что а) общее не влияет (нулевую массу) и б) мы получаем энергию1
перепрыгнуть[
. Мы можем легко заботиться об энергии$
, которая увеличивает энергию.Проблема в том, что при
?
сбросе EOF масса не сбрасывается, поэтому масса все равно будет равна массе последнего прочитанного символа, а энергия будет0
(потому что%
уменьшена1
обратно0
). Итак, мы хотим избавиться от этой массы. Для этого мы переставляем массу и энергию@
снова.Мне нужно ввести еще один компонент , прежде чем закончить этот раздел:
Z
. По сути это то же самое, что%
и&
. Разница заключается в том, что он позволяет атомам положительной энергии проходить прямо (при уменьшении энергии) и отклоняет атомы неположительной энергии на 90 градусов влево. Мы можем использовать это для устранения энергии атома, повторяя ееZ
снова и снова - как только энергия исчезнет, атом отклонится и покинет цикл. Вот этот шаблон:где атом будет двигаться вверх, когда энергия равна нулю. Я буду использовать этот шаблон в той или иной форме несколько раз в других частях программы.
Таким образом , когда атом покидает эту маленькую петлю, он будет
(1,0)
и мест , чтобы(0,1)
самые@
до попадания в реакторе слитого выпустить конечный результат ввода. Тем не менее, промежуточный итог будет отключен в 10 раз, потому что мы предварительно умножили его еще на одну цифру.Так что теперь с энергией
1
этот атом будет пропускать[
и прыгать в/
. Это отклоняет его в реактор деления, который мы подготовили разделить на 10 и исправить наше постороннее умножение. Опять же, мы отбрасываем одну половину с помощью;
и оставляем другую в качестве выходных данных (здесь представлено с помощью,O
которая просто напечатает соответствующий символ и уничтожит атом - в полной программе мы продолжаем использовать атом вместо этого).itoa
Конечно, нам также нужно преобразовать результат обратно в строку и распечатать его. Вот для чего эта часть. Это предполагает, что ввод поступает не раньше тика 10 или около того, но в полной программе это легко дается. Этот бит можно найти в нижней части полной программы.
Этот код представляет новый очень мощный компонент Fission: стек
K
. Стек изначально пуст. Когда атом с неотрицательной энергией попадает в стек, атом просто помещается в стек. Когда атом с отрицательной энергией попадает в стек, его масса и энергия будут заменены атомом на вершине стека (который таким образом выталкивается). Однако если стек пуст, направление атома меняется на противоположное, и его энергия становится положительной (т.е. умножается на-1
).Хорошо, вернемся к фактическому коду. Идея
itoa
фрагмента состоит в том, чтобы многократно использовать вход по модулю 10, чтобы найти следующую цифру, а целочисленное деление ввода на 10 для следующей итерации. Это даст все цифры в обратном порядке (от наименее значимого до наиболее значимого). Чтобы исправить порядок, мы помещаем все цифры в стопку и в конце выталкиваем их одну за другой, чтобы распечатать.Верхняя половина кода выполняет вычисление цифр:
L
плюсы дают 10, которые мы клонируем и подаем в реактор деления и термоядерного синтеза, так что мы можем делить и умножать на 10. Цикл, по сути, начинается после[
в верхнем левом углу. , Текущее значение делится: одна копия делится на 10, затем умножается на 10 и сохраняется в реакторе деления, в который затем попадает другая копия на вершине. Это вычисляетсяi % 10
какi - ((i/10) * 10)
. Также обратите внимание, чтоA
после деления и перед умножением разбивает промежуточный результат, так что мы можем ввести егоi / 10
в следующую итерацию.%
Прервет цикл когда переменные итерации хитов 0. Так как это более или менее делать-то время цикла, этот код будет работать даже для печати0
(без создания ведущих нулей в противном случае). Как только мы покидаем цикл, мы хотим очистить стек и вывести цифры.S
это противоположностьZ
, так что это переключатель, который будет отклонять входящий атом с неположительной энергией на 90 градусов вправо. Таким образом, атом фактически перемещается через край отS
прямой к точке,K
чтобы выскочить из цифры (обратите внимание на~
то, что у входящего атома есть энергия-1
). Эта цифра увеличивается на единицу,48
чтобы получить код ASCII соответствующего символа цифры.A
Расщепляет цифру напечатать одну копию с!
и подайте другую копию обратно вY
реактор для следующей цифры. Напечатанная копия используется в качестве следующего триггера для стопки (обратите внимание, что зеркала также посылают ее по краю, чтобы ударитьM
слева).Когда стек пуст, он
K
будет отражать атом и превращать его энергию так+1
, чтобы он проходил прямо черезS
.N
печатает новую строку (просто потому, что она аккуратная :)). И тогда атом идетR'0
снова, чтобы оказаться в сторонеY
. Так как вокруг нет никаких атомов, это никогда не будет выпущено, и программа завершится.Вычисление числа деления: рамки
Давайте перейдем к фактическому содержанию программы. Код в основном является портом моей эталонной реализации Mathematica:
где
div
число целых чисел в максимальном разделе.Основные отличия в том, что мы не можем иметь дело с полуцелыми значениями в Fission, поэтому я делаю много вещей, умноженных на два, и что в Fission нет рекурсии. Чтобы обойти это, я помещаю все целые числа в раздел в очередь для последующей обработки. Для каждого числа, которое мы обрабатываем, мы увеличиваем счетчик на единицу, а когда очередь пуста, мы освобождаем счетчик и отправляем его на печать. (Очередь
Q
работает точно так жеK
, как в порядке FIFO.)Вот основа для этой концепции:
Наиболее важными новыми компонентами являются цифры. Это телепорты. Все телепорты с одной цифрой принадлежат друг другу. Когда атом попадает в любой телепорт, он будет немедленно перемещать следующего телепорта в той же группе, где следующий определяется в обычном порядке слева направо, сверху вниз. Это не обязательно, но помогает с макетом (и, следовательно, немного в гольф). Существует также тот,
X
который просто дублирует атом, отправляя одну копию прямо вперед, а другую назад.К настоящему времени вы могли бы самостоятельно разобраться с большинством фреймворков. В верхнем левом углу находится очередь значений, которые еще предстоит обработать, и выпускаются по одному
n
за раз. Одна копияn
телепортируется в нижнюю часть, потому что она нужна нам при вычислении диапазона, другая копия переходит в блок в верхней части, который вычисляетdiv
(это, безусловно, самый большой раздел кода). Послеdiv
вычисления он дублируется - одна копия увеличивает счетчик в верхнем правом углу, который хранится вK
. Другая копия телепортируется вниз. Еслиdiv
это так1
, мы немедленно отклоняем его вверх и используем в качестве триггера для следующей итерации, не ставя в очередь новые значения. В противном случае мы используемdiv
иn
в разделе внизу, чтобы создать новый диапазон (то есть поток атомов с соответствующими массами, которые впоследствии помещаются в очередь), а затем отпустите новый триггер после того, как диапазон будет завершен.Как только очередь опустеет, триггер будет отражен, пройдя прямо через
S
и снова появившись в верхнем правом углу, где он освобождает счетчик (конечный результат), изA
которого затем телепортируетсяitoa
через8
.Вычисление числа деления: тело цикла
Таким образом, все, что осталось, - это две секции для вычисления
div
и генерации диапазона. Вычислительнаяdiv
это часть:Вы, наверное, уже видели достаточно, чтобы разобраться в этом с некоторым терпением. Разбивка высокого уровня такова: первые 12 столбцов или около того генерируют поток делителей
2n
. Следующие 10 столбцов отфильтровывают те, которые не удовлетворяютOddQ@# == IntegerQ[n/#]
. Следующие 8 столбцов отфильтровывают те, которые не удовлетворяютn/# > (# - 1)/2)
. Наконец, мы помещаем все действительные делители в стек, и как только мы закончим, мы опустошаем весь стек в реактор слияния (перезаписывая все, кроме последнего / самого большого делителя), а затем высвобождаем результат, после чего удаляем его энергию (которая была не Ноль от проверки неравенства).Там много безумных путей, которые на самом деле ничего не делают. Преимущественно,
\/\/\/\/
безумие наверху (5
s также являются его частью) и один путь вокруг дна (который проходит через7
s). Я должен был добавить их, чтобы справиться с некоторыми неприятными условиями гонки. Деление может использовать компонент задержки ...Код, который генерирует новый диапазон из
n
иdiv
это:Сначала мы вычисляем
n/div - (div + 1)/2
(оба условия скомпонованы, что дает одинаковый результат) и сохраняем их для дальнейшего использования. Затем мы генерируем диапазонdiv
сверху вниз1
и добавляем сохраненное значение к каждому из них.В обоих из них есть два новых общих паттерна, которые я должен упомянуть: один -
SX
илиZX
удар снизу (или повернутые версии). Это хороший способ дублировать атом, если вы хотите, чтобы одна копия шла прямо (поскольку перенаправление выходов термоядерного реактора иногда может быть громоздким). ВS
илиZ
вращается атом на ,X
а затем поворачивает зеркальную копию обратно в исходное направление распространения.Другая модель
Если мы храним какое-либо значение,
K
мы можем повторно получить его, ударяяK
отрицательной энергией сверху.A
Дублирует значение мы заинтересованы в том, и посылает то , что копировать правый на стек на следующий раз , когда нам это нужно.Что ж, это был настоящий том ... но если вы на самом деле справились с этим, надеюсь, у вас возникла идея, что Fission i͝s̢̘̗̗ ͢i̟nç̮̩r̸̭̬̱͔e̟̹̟̜͟d̙i̠͙͎̖͓̯b̘̠͎̭̰̼l̶̪̙̮̥̮y̠̠͎̺͜ ͚̬̮f̟͞u̱̦̰͍n͍ ̜̠̙t̸̳̩̝o ̫͉̙͠p̯̱̭͙̜͙͞ŕ̮͓̜o̢̙̣̭g̩̼̣̝r̤͍͔̘̟ͅa̪̜͇m̳̭͔̤̞ͅ ͕̺͉̫̀ͅi͜n̳̯̗̳͇̹.̫̞̲̞̜̳
источник
Now with 100% fewer scrollbars.
так вы говорите .. и это все еще будет продолжение ...CJam,
4241 байтПростой обход в ширину и условие остановки пустого следующего уровня.
Как это работает :
Попробуйте онлайн здесь
источник
Python 3, 112 байт
4 байта сохранены благодаря @FryAmTheEggman.
Объяснение будет позже ...
Бонус факт: каждая степень 2 имеет число деления 1. Это потому, что сумма последовательности четной длины всегда является суммой двух средних чисел, которая является нечетной, умноженной на половину длины последовательности, которая является целым числом , Сумма последовательности нечетной длины - это среднее число, умноженное на длину последовательности, которая является нечетной. Таким образом, поскольку степень 2 не имеет нечетного делителя, она может быть выражена только как сумма самого себя.
источник
Python 2,
11110297 байтНесколько читабельно:
Не слишком читаем:
Оба 97 байта.
b
Является лиn
минус(a-1)th
треугольное число. Еслиb % a == 0
, тоn
это суммаa
последовательных чисел, начиная сb
.источник
1else
. Работает только 2-е решение. Только в Python 3else
можно сразу следовать за номером.Python 2, 86
Менее гольф:
Идея состоит в том, чтобы протестировать потенциальные последовательности последовательных целых чисел, которые в сумме
n
. Прогон сохраняется непосредственно как набор,R
а не через его конечные точки.Мы проверяем, как сумма текущего прогона сравнивается с желаемой суммой
n
через их разность.f
на прогон, суммируем и добавляем 1 для текущего узла. Если запуск выполнен{n}
, мы перепробовали все нетривиальные возможные суммы, остановите рекурсию, удаливn
сначала.Спасибо Sp3000 за сохранение 3 символов.
источник
Python 2, 85
Я очень горжусь этим ответом, потому что он уже занимает десятки секунд для n = 9 и 5-10 минут для n = 10. В коде гольф это считается желательным атрибутом программы.
Существует также версия с коротким замыканием, которая не занимает много времени и использует такое же количество байтов:
Это может быть быстрее, но, по крайней мере, оно превышает предельное значение рекурсии по умолчанию, когда n становится немного выше 40.
Идея состоит в том, чтобы выполнить перебор чисел
a
и такd
, чтобыa + a+1 + ... + a+d == n
при значениях от 1 доn
.f(n,a+d/n,d%n+1)
Ветвь рекурсии перебирает(a, d)
пар. В случае, когда равенство выполнено, мне удается избежать дорогостоящегоmap(range(...))
вызова, разбив его на две ветви, независимо от длины последовательности. Числаa+1
черезd
которые сосредоточенные в один вызовf
, установивa
параметр так , что другой способ , чтобы разделить последовательность не может быть использован.источник
Haskell,
7669 байтИспользование:
Как это устроено:
источник
Сетчатка , 66 байт
Принимает ввод и печатает вывод в одинарном формате.
Вы можете поместить каждую строку в один файл или запустить код как есть с
-s
флагом. Например:Объяснение:
1
и преобразуем остальные в1
.Состояния строки на протяжении всего процесса с вводом
11111111111111 (unary 14)
:Большое спасибо за @MartinButtner за помощь в чате!
источник
CJam (43 байта)
Онлайн демо
Я уверен, что мне не хватает некоторых трюков с продвинутыми циклами, но это аккуратно использует свойство CJam (которое ранее раздражало меня), что внутри
%
карты результаты остаются в стеке, и поэтому могут быть доступны$
с помощью отрицательное смещение.источник
,
в начале./
и%
и несколько других неявно превращают числа в диапазоны.,_m*
можно заменить на2m*
. Формула арифметической прогрессии может быть заменена на~,>:Y_,+:+
и~\,>0\
становится!Y
. Наконец, если вы используете{}#
вместо{}=
, вам не нужно)
послеX
. Собираем все вместе:ri{):X2m*{~,>:Y_,+:+X=}#!Y{~$+}/)}%W=
Go, 133 байта
Это мой первый код гольф, извините, если я допустил какие-либо ошибки.
При этом используется идея о том, что делящаяся «композиция» также может рассматриваться как разница между двумя последовательностями упорядоченных целых чисел. Для примера возьмем расщепляющуюся «композицию» для числа 13. Это 6,7. Но это можно рассматривать как сумму целых чисел 1 ... 7 минус сумма целых чисел 1 ... 5
Напомним формулу из школьных дней Гаусса, сумма 1 ... n = (n ^ 2 + n) / 2. Таким образом, чтобы найти композицию последовательных целых чисел для данного n, мы могли бы также сказать, что мы ищем «конечные точки» p и q в диапазоне 1 ... n так, чтобы (p ^ 2 + p) / 2 - ( q ^ 2 + q) / 2 = n. В приведенном выше примере мы искали бы «конечные точки» 5 и 7, потому что 7 ^ 2 + 7 = 56/2, 5 ^ 2 + 5 = 30/2, 56 / 2-30 / 2 = 28-15 = 13
Теперь есть несколько возможных способов составления числа, как отметил Мартин, 9 = 2 + 3 + 4, но также и 4 + 5. Но кажется очевидным, что «самая низкая» начальная последовательность также будет самой длинной, потому что она требует больше маленькие числа для суммирования до большего числа, чем для средних чисел. (У меня нет доказательств к сожалению)
Таким образом, чтобы найти композицию из 9, протестируйте каждую «пару конечных точек», p и q, итерируя оба p и q отдельно от 0 до 9, и проверьте, если p ^ p + p / 2 - q ^ 2 + q / 2 = 9. Или, проще, умножьте уравнение на 2, чтобы избежать проблем округления при округлении и сохранить всю математику в целых числах. Тогда мы ищем p и q такие, что (p ^ p + p) - (q ^ q + q) = 9 * 2. Первое совпадение, которое мы найдем, будет конечными точками расщепляющейся композиции, потому что, как отмечалось, самая низкая группа чисел также будет самой длинной, и мы ищем от низкого до высокого (от 0 до 9). Мы вырываемся из цикла, как только мы находим соответствие.
Теперь рекурсивная функция находит эти «делящиеся конечные точки» p и q для заданного n, а затем вызывает себя для каждого из «потомков» в дереве от p до q. Для 9 он найдет 1 и 4, (20-2 = 18), затем перезвонит себе на 2, 3 и 4, суммируя результаты. Для чисел, подобных 4, он просто не находит совпадения и возвращает «1». Это может быть сокращено, но это как моя третья программа go, и я не эксперт по рекурсии.
Спасибо за чтение.
источник
CJam,
403533 байтаСпасибо @Optimizer за предложение
few
, которое сэкономило 2 байта.Попробуйте онлайн в интерпретаторе CJam .
Как это устроено
источник
ri{_,:)_few:+W%{1b1$=}=|{F}*}:F~],