Если задано положительное целое число N , ваша задача состоит в том, чтобы возвратить количество шагов, необходимых для достижения N следующим алгоритмом :

1. Найти наименьшее треугольное число Т _я такое , что Т _я  ≥ Н . Постройте соответствующий список L = [1, 2, ..., i] .

2. Хотя сумма членов L больше, чем N , удалите первый член из списка.

3. Если сумма членов L теперь меньше N , увеличьте i и добавьте его в список. Продолжайте с шага № 2.

Мы останавливаемся, как только N достигнут. Только первый шаг выполняется систематически. Шаги № 2 и № 3 могут не обрабатываться вообще.

Примеры

Ниже приведен пример для N = 11 :

Таким образом, ожидаемый результат для N = 11 равен 4 .

Другие примеры:

• N = 5 - мы начинаем с T ₃ = 1 + 2 + 3 = 6 , затем 2 + 3 = 5 . Ожидаемый результат: 2 .
• N = 10 - требуется только первый шаг, потому что 10 - это треугольное число: T ₄ = 1 + 2 + 3 + 4 = 10 . Ожидаемый результат: 1 .

Первые 100 значений

Ниже приведены результаты для 1 ≤ N ≤ 100 :

  1,  2,  1,  4,  2,  1,  2, 10,  2,  1,  4,  2,  6,  2,  1, 22,  8,  2, 10,  2,
  1,  2, 12,  6,  2,  4,  2,  1, 16,  2, 18, 50,  2,  6,  2,  1, 22,  6,  2,  4,
 26,  2, 28,  2,  1,  8, 30, 16,  2,  6,  4,  2, 36,  2,  1,  2,  4, 12, 40,  2,
 42, 14,  2,108,  2,  1, 46,  2,  6,  4, 50,  2, 52, 18,  2,  4,  2,  1, 56, 12,
  2, 20, 60,  4,  2, 22, 10,  2, 66,  2,  1,  4, 10, 24,  2, 40, 72,  8,  2,  6

правила

• Вы можете написать либо полную программу, либо функцию, которая либо печатает, либо возвращает результат.
• Вам необходимо обработать любое N ≤ 65536 менее чем за одну минуту на оборудовании среднего уровня.
• Если у вас достаточно времени, ваша программа / функция теоретически должна работать для любого значения N , которое изначально поддерживается вашим языком. Если это не так, пожалуйста, объясните почему в своем ответе.
• Это код гольф, поэтому самый короткий ответ в байтах выигрывает!

Желе , 29 31 байт

ÆDµ’H+Ṛ%1$ÐḟṂ
>TḢ_@Ç}‘Ḥ
R+\ðċȯç

Монадическая ссылка, которая возвращает результат (N = 65536 занимает менее двух секунд).

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

Как?

Подробное объяснение алгоритма можно найти в фантастическом посте Мартина Эндера .

ÆDµ’H+Ṛ%1$ÐḟṂ - Link 1, smallest natural number, M, that satisfies the below*, N
              - * N = T(M) - T(i) for some non-negative integer i <= M
ÆD            - divisors of N
  µ           - monadic chain separation, call that d
   ’          - increment d (vectorises)
    H         - halve (vectorises
      Ṛ       - reverse d
     +        - add (vectorises)
          Ðḟ  - filter discard if:
       %1$    -   modulo one is truthy (those which are the result of even divisors)
            Ṃ - minimum

>TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N
>         - T(i) > N
 T        - truthy indexes
  Ḣ       - head (yields the first i for which T(i) > N)
     Ç}   - call last link (1) as a monad converted to a dyad using the right argument
   _@     - subtract with reverse @rguments
       ‘  - increment
        Ḥ - double 

R+\ðċȯç - Main link: N
R       - range -> [1,2,...,N]
 +\     - reduce with addition -> [1,3,6,10,...T(N)]
   ð    - dyadic chain separation, call that t
    ċ   - count occurrences of N in t (1 if N is triangular else 0)
      ç - call last link (2) as a dyad(t, N)
     ȯ  - or

Полнофункциональная 29-байтовая реализация, которую я создал по описанному алгоритму, занимает 4 минуты 30 для N = 65536 на моем ноутбуке, поэтому я полагаю, что это не считается.

Ṁ‘ṭµS<³µ¿
ḊµS>³µ¿
0®Ḃ‘©¤ĿÐĿL’

Использование цикла while для каждого шага 3 и его повторное использование в качестве шага 1 равно длине, с которой я могу справиться при инициализации списка, поскольку проверка на шаге 3 не означает создание списка до тех пор, пока ничего не останется, а затем поиск первого индекса значения:

ḊµS>³µ¿
Ṁ‘ṭ
Ḥ½_.ĊR®Ḃ‘©¤ĿÐĿS€i

Mathematica, 79 байтов

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&

объяснение

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

Поэтому я утверждаю, что последовательность, которую мы должны вычислить:

f (n) = 2 * ( A212652 (n) - A002024 (n)) + 1 + A023532 (n-1)

В качестве альтернативы, это f (n) = 1, если n - треугольное число и f (n) = 2 * ( A212652 (n) - A002024 (n) + 1) в противном случае.

В первом выражении A023532 просто кодирует эти два разных случая. Две другие последовательности (плюс 1) представляют собой разницу между наибольшим целым числом k в самом длинном разложении n на последовательные целые числа (k-i + 1) + (k-i + 2) + ... + k = n и наибольшее целое число j, так что 1 + 2 + ... + j <n .

В нескольких простых словах, вот как мы находим ответ на нетреугольные числа: первое, найти наибольший треугольное число T _J , который меньше , чем п . Тогда j - предпоследнее целое число, которое добавляется на шаге 1 (потому что после добавления j + 1 мы превысим n ). Затем разложите n на как можно больше (или как можно меньше) последовательных целых чисел и назовите максимум среди этих чисел k . Результат просто 2 * (кДж) . Интуитивно понятная причина этого заключается в том, что максимум разложения растет на 1 через каждый шаг, и мы останавливаемся, когда достигаемк .

Нам нужно показать четыре вещи, чтобы доказать, что это работает:

1. f (n) = 1 для треугольных чисел. Это тривиально, потому что первый шаг просто перебирает все треугольные числа. Если мы нажмем n точно во время этого процесса, мы закончим и оставался только один шаг для вычисления.
2. Для всех остальных чисел мы всегда заканчиваем после шага удаления, а не после шага вставки. Это означает, что все остальные f (n) четны.
3. На каждом шаге вставки после первого мы добавляем только один номер. Это гарантирует, что мы достигнем разложения, включающего k после kj пар шагов.
4. Окончательная декомпозиция n, которую мы получаем, всегда является самой длинной из возможных декомпозиций n на последовательные целые числа, или, другими словами, это всегда декомпозиция n с наименьшим максимумом среди суммируемых чисел. Другими словами, последнее число, которое мы добавляем к сумме, всегда A212652 (n) .

Мы уже показали, почему (1) верно. Далее мы докажем, что мы не можем закончить на шаге вставки, кроме начального (что не происходит для нетреугольных чисел).

Предположим, что мы закончили на шаге вставки, достигнув n после добавления значения p к сумме. Это означает, что перед этим шагом вставки значение было np ( или меньше, если мы добавили несколько значений одновременно). Но этому этапу вставки предшествовал этап удаления (поскольку мы не могли нажать n на шаге 1). Последнее значение q, которое мы удалили на этом шаге удаления, было обязательно меньше p из-за того, как работает алгоритм. Но это означает, что до того, как мы удалили q, у нас было n-p + q ( или меньше ), которое меньше n, Но это противоречие, потому что нам пришлось бы прекратить удалять целые числа, когда мы нажимаем n-p + q вместо удаления другого q . Это доказывает пункт (2) выше. Итак, теперь мы знаем, что мы всегда заканчиваем этапом удаления и что поэтому все нетреугольные числа имеют четные выходные данные.

Далее мы докажем (3), что каждый шаг вставки может вставить только одно значение. Это по существу следствие (2). Мы показали, что после добавления одного значения мы не можем точно указать n , а поскольку при проверке использовалось неравенство, мы также не можем оказаться ниже n (поскольку тогда n-p + q все равно будет меньше n, и мы не должны были удалять что много ценностей в первую очередь). Поэтому всякий раз, когда мы добавляем одно значение, мы гарантированно превышаем n, потому что мы опустились ниже n , удалив меньшее значение. Следовательно, мы знаем, что верхний конец суммы увеличивается на 1 при каждом следующем шаге. Мы знаем начальное значение этого верхнего конца (это наименьшее м такое, чтоT _m > n ). Теперь нам просто нужно выяснить этот верхний предел, как только мы достигнем окончательной суммы. Тогда количество шагов просто вдвое больше разницы (плюс 1).

Для этого мы докажем (4), что окончательная сумма - это всегда разложение n на максимально возможное число целых чисел или разложение, где максимум в этом разложении минимален (т. Е. Это самое раннее возможное разложение). Мы снова сделаем это из-за противоречия (формулировка в этой части может быть немного более строгой, но я уже потратил слишком много времени на это ...).

Скажем, самое раннее / самое длинное из возможных разложений n - это некоторое a + (a + 1) + ... (b-1) + b , a ≤ b , и скажите, что алгоритм его пропускает. Это означает, что в момент добавления b a больше не должен быть частью суммы. Если бы a было частью суммы s , то у нас было бы n ≤ s в этот момент. Таким образом, либо сумма содержит только значения от a до b , что равно n, и мы останавливаемся (следовательно, мы не пропустили эту декомпозицию), либо в сумме есть хотя бы одно значение меньше, чем a, в этом случае выигрыш n <sи это значение будет удалено, пока мы не достигнем точной суммы (опять же, декомпозиция не была пропущена). Таким образом, мы должны избавиться от а, прежде чем добавить б . Но это означает, что нам придется столкнуться с ситуацией, в которой а является наименьшим компонентом суммы, а наибольшая - еще не б . Однако в этот момент мы не можем удалить a , потому что сумма явно меньше n (так как b отсутствует), поэтому мы должны сначала добавить значения, пока мы не добавим b и точно не достигнем n . Это доказывает (4).

Итак, взяв эти вещи вместе: мы знаем, что первая пара шагов дает нам максимальное значение A002024 (n) . Мы знаем, что максимальное значение окончательного разложения составляет A212652 (n) . И мы знаем, что этот максимум увеличивается один раз за каждую пару шагов. Следовательно, окончательное выражение равно 2 * ( A212652 (n) - A002024 (n) + 1) . Эта формула почти работает для треугольных чисел, за исключением того, что для них нам нужен только 1 шаг вместо 2, поэтому мы корректируем результат с помощью индикаторной функции треугольных чисел (или ее обратной, в зависимости от того, что удобнее).

Наконец, что касается реализации. Для первой последовательности я использую формулу MIN (нечетное d | n; n / d + (d-1) / 2) из OEIS. Получается сэкономить несколько байтов, если мы возьмем в это выражение множитель 2, чтобы получить MIN (нечетное d | n; 2n / d + d-1) , потому что это -1 затем отменяется с +1 в моей первой версии из f (n), который непосредственно кодирует два случая для треугольных и нетреугольных чисел. В коде это:

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]

Для последней последовательности ( 1, 2, 2, 3, 3, 3, ...) мы можем использовать простую замкнутую форму:

⌊(2#)^.5+.5⌋

И, наконец, обратная индикаторная функция треугольных чисел равна 0, если 8n + 1 - идеальный квадрат. Это может быть выражено в Mathematica как

⌈Sqrt[8#+1]~Mod~1⌉

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

Поскольку я пошел на все эти проблемы, вот график последовательности до n = 1000 (я мог бы также вычислить 100k за пару секунд, но на самом деле он не показывает никаких дополнительных сведений):

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

Mathematica, 72 байта

(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&

Чистая функция, принимающая целочисленный аргумент.

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

For[ ... ]

ForЦикл.

l=u=c=k=0

Инициализация; установите l(нижний), u(верхний), c(счетчик) и k(сумма) в 0.

k!=#

Состояние; повторить пока kне равно входу.

c++

Приращение; увеличить счетчик c.

If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]

тело

If[#>k, ... ]

Если вход больше чем k:

While[#>k,k+=++u]

В то время как входное значение больше k, увеличение uи увеличение kна u.

Если ввод не больше чем k:

While[#<k,k-=l++]

В то время как ввод меньше k, уменьшите kна lи увеличьте l.

( ... ;c)

Вернитесь cпосле цикла.

Python 2 , 104 байта

N=input();i=s=0;l=()
while N!=sum(l):exec'while sum(l)'+['<N:i+=1;l+=i,','>N:l=l[1:]'][s%2];s+=1
print s

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

Чередует добавление терминов в конец списка и удаление терминов в начале.

Haskell , 70 63 68 64 байта

РЕДАКТИРОВАТЬ:

• -7 байт: избавился от пробела, двух знаков и некоторых скобок, отрицая смысл a. Исправлены ошибки в объяснении.
• +5 байт: Argh, полностью пропустил требование 65536, и оказалось, что (1) степени 2 особенно дороги, потому что они получают удар только тогда, когда вы добираетесь до самого числа (2), поэтому суммируются большие расстояния (которые оборачиваются вокруг ноль) все время. Заменил сумму на математическую формулу.
• -4 байта: скорректировано aи bлинейно, чтобы получить условия в формуле суммирования для отмены.

1#1 является анонимной функцией, принимающей и возвращающей целое число

Использовать как (1#1) 100.

1#1
(a#b)n|s<-a*a-b*b=sum$[a#(b+2)$n|s>8*n]++[(b#a)(-n)+1|s<8*n]

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

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

• (a#b)nпредставляет текущий шаг расчета. a, bчисла в 1, 3, 5, .., в то время как nможет быть положительным или отрицательным в зависимости от шага.
  • На шаге 1 или 3 он представляет список [(a+1)/2,(a+3)/2..(b-1)/2]и номер цели -n.
  • На шаге 2 он представляет список [(b+1)/2,(b+3)/2..(a-1)/2]и номер цели n.
• Странное соответствие между a, bсписками и для того, чтобы можно было суммировать с коротким выражением s=a*a-b*b.
  • На шаге 1 и 3 это то же самое, что и s= -8*sum[(a+1)/2..(b-1)/2].
  • На шаге 2 это так же, как s=8*sum[(b+1)/2..(a-1)/2].
• Разветвление выполняется путем создания списочных представлений, которые создают элементы только в одном случае, и суммирования результатов.
  • Если s>8*n, то bувеличивается на 2 перед повторением.
    • На шаге 1 и 3 список увеличивается, а на шаге 2 - уменьшается.
  • Если s<8*n, то рекурсия изменяет шаг, меняя местами aи b, и отрицая n, и к результату добавляется 1.
  • Если s==8*n, то ни одно из двух представлений списка не дает никаких элементов, поэтому сумма равна 0.
• (1#1) nпредставляет собой фиктивную "стадию 2" перед запуском, которая немедленно изменяется на шаг 1, из которого строится список [1..0]=[].

PHP> = 7,0, 74 байта

while($i=$r<=>$argn)for($s++;($r<=>$argn)==$i;)$r+=$i+1?-++$y:++$x;echo$s;

использовать оператор космического корабля

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

расширенный

while($i=$r<=>$argn) # if input is not equal sum of array
  for($s++;  # raise count steps
  ($r<=>$argn)==$i;)
  # so long as value compare to input has not change to lower/higher to higher/lower or equal  
    $r+=$i+1
      ?-++$y # if $i was higher remove the first integer
      :++$x;} # if $i was lower add the next highest integer     
echo$s; # Output steps

C 94 91 байт

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

c;s;m;M;f(n){while(s-n){while(s<n)s+=++M;c++;if(s==n)break;while(s>n)s-=++m;c++;}return c;}

JavaScript (ES6), 82 байта

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

Тестовый фрагмент

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

<input type="number" oninput="o.textContent=D(this.value)"></input>
<pre id='o'></pre>

постоянный ток , 61 байт

dsN[ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx]dsFxz2-

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

объяснение

Основной рекурсивный макрос:

ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx
   9k4*d2*1+dv-0k2/-                              # Compute triangular root
                    d1+*2/                        # Compute triangular number
  d                       -d[q]s.0=.              # Check if sum is exact
 d                                  -lN-          # Compute S-N or S+N
                                        0lN-sN    # Update N := -N
d                                             lFx # Leave the trail and recurse

Этот макрос:

1. Находит минимальное треугольное число, которое превышает текущее число в стеке (используя модифицированную формулу треугольного корня ).
2. Проверяет, представляет ли треугольная сумма Sточное текущее число. Выходит, если это так.
3. Перейдите к шагу 1 с S+N(чрезмерное приближение) или S-N(недостаточное приближение), выбор чередуется между итерациями.

Когда он завершается, след, оставленный в стеке, сообщает основной программе, сколько итераций потребовалось.

Python 3, 150 138 байт

n=int(input())
S=sum
l=[1]
i=s=1
while S(l)<n:i+=1;l+=[i]
while S(l)!=n:
 while S(l)>n:l.pop(0)
 s+=1
 if S(l)<n:i+=1;l+=[i];s+=1
print(s)

Changelog:

• Изменено добавление к + =, удалено еще (спасибо musicman523, Loovjo; -12 байт)

Пакет, 126 байт

@echo off
set/an=s=l=u=0
:l
if %s% lss %1 set/as+=u+=1,n+=!!l&goto l
if %s% gtr %1 set/as-=l+=1&goto l
cmd/cset/an+n+2-!l

Пояснение: lноль, если шаг 2 никогда не выполнялся. Это позволяет nотслеживать количество итераций шага 3. Поскольку алгоритм никогда не останавливается на шаге 3, следовательно, он должен выполнить шаг 1 один раз и шаг 2 n+1раза для общего количества n+n+2шагов. Однако если параметр является треугольным числом, то шаг 2 никогда не выполняется, поэтому нам нужно вычесть один шаг.

Python 2, 86 81 байт

n=input()
l=u=i=s=0
while n:k=n>0;i+=k^s;s=k;l+=k;n-=l*k;u+=k^1;n+=u*-~-k
print i

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

Вычисляет 65536 тестов в 0.183sTIO.

Эта рекурсивная версия на 84 байта не может вычислить все значения до 65536:

def f(n,l=[0],m=1):k=n>sum(l);return n==sum(l)or f(n,[l[1:],l+[l[-1]+1]][k],k)+(m^k)

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

Mathematica, 92 байта

(For[q=a=b=0;t={},t~AppendTo~q;q!=#,If[q<#,q+=++b,q-=++a]];Length@Split@Sign@Differences@t)&

Чистая функция, принимающая целочисленный аргумент и возвращающая целое число.

Переменные aи bобозначают (постоянно изменяющиеся) начальные и конечные числа в рассматриваемой сумме, в то время как qобозначают промежуточную сумму (чисел от a+1до b); tотслеживает все найденные значения q. После инициализации этих переменных Forцикл продолжает выполняться If[q<#,q+=++b,q-=++a], который либо добавляет новое число в конец, либо вычитает число спереди, как предписывает спецификация, до тех пор, пока не будет qравен входному значению.

Теперь нам просто нужно извлечь количество шагов из tсписка qзначений, встречающихся на этом пути. Например, когда на входе 11, Forцикл выходит с tвыравниванием {0,1,3,6,10,15,14,12,9,15,11}. Лучший способ, который я нашел для вычисления количества шагов из этого, состоит в том, чтобы посчитать, сколько раз различия переходят от повышения к понижению; это то, что Length@Split@Sign@Differences@tделает команда verbose , но я подозреваю, что это можно улучшить.

C (tcc), 71 байт (61 + 10)

Аргументы командной строки (включая пробел):

-Dw=while

Источник:

c,m,M,s;f(n){w(++c,s-n){w(c&s<n)s+=++M;w(~c&s>n)s-=m++;}--c;}

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

cсчитает количество шагов mи Mхранить минимум и максимум диапазона, sсуммы. Изначально все они равны нулю.

Постоянно cувеличивается и sсравнивается с n. Пока они неравны:

• Если cнечетно, то до тех пор, пока s<n, добавьте целое число в конец диапазона: увеличить Mна единицу и sна M.

• Если cчетное, то, пока s>n, удалите целое число из начала диапазона: уменьшите sна mи увеличьте mна единицу.

Когда цикл завершается, cон был увеличен слишком много раз. Уменьшение его приводит к правильному результату, и он рассчитывается в правильном регистре, чтобы действовать как возвращаемое значение.

Забавно случается, что используются те же самые имена переменных, что и в ответе Халеда . Они не копируются.

Perl 6 , 114 байт

{((0,0,1),->(\a,\b,\c){b,(a..*).first(->\d{(d,b).minmax.sum*c>=$_*c}),-c}...->(\a,\b,\c){(a,b).minmax.sum==$_})-1}

(вдохновленный более ранней реализацией Haskell )

Попробуйте.
Он работает со входом 65536 менее чем за 45 секунд на моем компьютере, но я не смог заставить его работать менее чем за 60 секунд с TIO.run.
У меня есть Rakudo v2017.04 +, где он имеет v2017.01 .
Rakudo / NQP / MoarVM получает оптимизации почти ежедневно, поэтому в промежутке между ними может быть любое их количество, необходимое для своевременного выполнения.

расширенный

{
  (

    # generate a sequence

    (0,0,1),           # initial value 

    -> (\a,\b,\c) {
      b,               # swap the first two values

      (a..*)
      .first(          # find the first number that brings us to or past the input

        -> \d {
          (d,b).minmax # get a Range object regardless of which is larger
          .sum * c     # sum it, and negate it every other time

          >=           # is it equal to or greater than

          $_ * c       # negate the original input every other time
        }

      ),

      -c               # invert for next round
    }

    ...                # keep doing that until

    -> (\a,\b,\c) {
     (a,b).minmax.sum == $_ # it finally reaches the input
    }

  ) - 1 # count the number of elements in the sequence
        # and subtract one for the initializer
}

Обратите внимание, что в Rakudo есть оптимизация для Range.sumтого, чтобы ему не приходилось перебирать все значения.