Давайте посчитаем...

Считайте до 2 и обратно до 1
Считайте до 4 и обратно до 1
Считайте до 6 и обратно до 1
... хорошо, вы поняли ...

собрать все это вместе, и вы получите следующую последовательность

 {1,2,1,2,3,4,3,2,1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,2,3...}

Задача
Учитывая целое число n>0для 1-индексированного (или n>=0для 0-индексированного), выведите n-й член этой последовательности

Контрольные примеры

Input->Output  

1->1  
68->6  
668->20  
6667->63  
10000->84

правила

Ваша программа должна быть в состоянии вычислить решения до n = 10000 в течение минуты

Это код-гольф , поэтому выигрывает самый короткий код в байтах!

JavaScript (ES7),  59 ... 44  43 байта

Сохранено 1 байт благодаря Титу

Ожидаемый ввод: 1-индексированный.

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

Изначально вдохновлен формулой A004738 , которая представляет собой похожую последовательность. Но в итоге я переписал его полностью.

Контрольные примеры

let f=

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

console.log(f(1))     // -> 1
console.log(f(68))    // -> 6
console.log(f(668))   // -> 20
console.log(f(6667))  // -> 63
console.log(f(10000)) // -> 84

Как?

Последовательность может быть организована в виде треугольника с левой частью в порядке возрастания и правой частью в порядке убывания.

Ниже приведены первые 4 строки, содержащие первые 32 условия:

            1 | 2
        1 2 3 | 4 3 2
    1 2 3 4 5 | 6 5 4 3 2
1 2 3 4 5 6 7 | 8 7 6 5 4 3 2

Теперь давайте введем некоторые переменные:

 row  | range   | ascending part              | descending part
 r    | x to y  | 1, 2, ..., i                | 4(r+1)-(i+1), 4(r+1)-(i+2), ...
------+---------+-----------------------------+-----------------------------------------
  0   |  1 -  2 |                           1 | 4-2
  1   |  3 -  8 |                   1   2   3 | 8-4  8-5  8-6
  2   |  9 - 18 |           1   2   3   4   5 | 12-6 12-7 12-8  12-9  12-10
  3   | 19 - 32 |   1   2   3   4   5   6   7 | 16-8 16-9 16-10 16-11 16-12 16-13 16-14

Мы начинаем с 2 элементов в верхней части и добавляем 4 элемента в каждой новой строке. Следовательно, количество элементов в 0-индексированной строке r может быть выражено как:

a(r) = 4r + 2

1-индексированная начальная позиция x строки r задается суммой всех предыдущих членов в этом арифметическом ряду плюс один, что приводит к:

x(r) = r * (2 + a(r - 1)) / 2 + 1
     = r * (2 + 4(r - 1) + 2) / 2 + 1
     = 2r² + 1

Взаимно, учитывая 1-индексированную позицию n в последовательности, соответствующая строка может быть найдена с помощью:

r(n) = floor(sqrt((n - 1) / 2))

или как код JS:

r = (~-n / 2) ** 0.5 | 0

Как только мы знаем r (n) , мы вычитаем начальную позицию x (r) минус один из n :

n -= r * r * 2

Мы сравниваем n с a (r) / 2 + 1 = 2r + 2, чтобы выяснить, находимся ли мы в восходящей части или в нисходящей части:

n < ++r * 2 ?

Если это выражение истинно, мы возвращаем n . В противном случае мы возвращаем 4 (r + 1) - n . Но так как r был уже увеличен в последнем утверждении, это упрощается как:

n : r * 4 - n

Haskell , 37 байт

(!!)$do k<-[1,3..];[1..k]++[k+1,k..2]

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

Zero-индексироваться. Создает список и индексирует его. Спасибо Эрджану Йохансену за сохранение 2 байта!

Haskell , 38 байт

(!!)[min(k-r)r|k<-[0,4..],r<-[1..k-2]]

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

Zero-индексироваться. Создает список и индексирует его.

Haskell , 39 байт

n%k|n<k=1+min(k-n)n|j<-k+4=(n-k)%j
(%2)

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

Zero-индексироваться. Рекурсивный метод.

Python , 46 байт

f=lambda n,k=2:-~min(n,k-n)*(n<k)or f(n-k,k+4)

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

Ноль индексируется.

Шелуха , 8 байт

!…ṁoe1DN

1-индексироваться. Попробуйте онлайн!

объяснение

!…ṁoe1DN  Implicit input (an integer).
       N  Positive integers: [1,2,3,4,...
  ṁo      Map and concatenate
      D   double: [2,4,6,8,...
    e1    then pair with 1: [1,2,1,4,1,6,1,8,...
 …        Fill gaps with ranges: [1,2,1,2,3,4,3,2,1,2,3,4,5,6,...
!         Index with input.

Perl 6 , 29 байт

{({|(1...$+=2...2)}...*)[$_]}

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

0 на основе

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

  (
    # generate an outer sequence

    {           # bare block lambda

      |(        # flatten into outer sequence

        # generate an inner sequence

        1       # start at 1

        ...     # go (upward) towards:

        $       # an anonymous state variable (new one for each outer sequence)
          += 2  # increment by 2

        ...     # go (downward) towards:

        2       # stop at 2 (1 will come from the next inner sequence)

      )
    }

    ...         # keep generating the outer sequence until:
    *           # never stop

  )[ $_ ]       # index into outer sequence
}

Внутренняя последовательность 1...$+=2...2производит

(1, 2).Seq
(1, 2, 3, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2).Seq
...

Чтобы получить его на основе 1, добавьте 0,перед вторым {или добавьте -1после$_

R, 64 байта

function(n)unlist(sapply(seq(2,n,2),function(x)c(2:x-1,x:2)))[n]

Функция, которая принимает аргумент n. Он создает вектор 2:nс шагом 2. Для каждого из них создается вектор 1:(x-1)и x:2. Это в общей сложности будет дольше, чем n. Мы unlistэто, чтобы получить вектор и взять nвторую запись.

Python 2 , 56 байт

def f(x):n=int((x/2)**.5);print 2*n-abs(2*n*n+2*n+1-x)+2

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

Это 0-индексированный.

-1 байт благодаря @JustinMariner

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

Отметим, что 1-индексированная n-th-группа ( 1, 2, ... 2n ..., 2, 1) происходит из элементов, пронумерованных от 0 2(n-1)^2до 2n^2.

Чтобы найти элемент по индексу x, мы можем найти номер группы, в nкоторой он xнаходится. Из этого мы вычисляем расстояние от центра группы, которая xнаходится. (Это расстояние есть abs(2*n**2+2*n+2-x)).

Однако, поскольку элементы уменьшаются дальше от центра группы, мы вычитаем расстояние от максимального значения группы.

05AB1E , 8 байтов

Код:

ÅÈ€1Ÿ¦¹è

Использует кодировку 05AB1E . Попробуйте онлайн!

Объяснение:

ÅÈ           # Get all even numbers until input (0, 2, ..., input)
  €1         # Insert 1 after each element
    Ÿ        # Inclusive range (e.g. [1, 4, 1] -> [1, 2, 3, 4, 3, 2, 1])
     ¦       # Remove the first element
      ¹è     # Retrieve the element at the input index

JavaScript, 39 байт

f=(n,t=2)=>n>t?f(n-t,t+4):n>t/2?t-n+2:n

Желе , 10 , 9 байт

ḤŒḄṖµ€Fị@

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

Также 1 индексируется и заканчивается довольно быстро.

Один байт сохранен благодаря @ErikTheOutgolfer!

Объяснение:

Гипотетически, скажем, input ( a) равен 3.

    µ€      # (Implicit) On each number in range(a):
            #
Ḥ           # Double
            #   [2, 4, 6]
            #
 ŒḄ         # Convert to a range, and Bounce
            #   [[1, 2, 1], [1, 2, 3, 4, 3, 2, 1], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]
            #
   Ṗ        # Pop
            #   [[1, 2], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2]]
            #
     F      # Flatten
            #   [1, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2]
            #
      ị@    # Grab the item[a]
            #   1
            #

MATL , 15 байт

li:"@EZv4L)]vG)

1 на основе.

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

Это время для самых больших тестовых случаев в TIO, но заканчивается на моем настольном компьютере (компилятор работает на MATLAB R2017a). Чтобы отобразить прошедшее время, добавьте Z`в конце кода.

>> matl 'li:"@EZv4L)]vG)Z`'
> 10000
84
15.8235379852476

объяснение

Код генерирует гораздо больше терминов, чем необходимо. В частности, он вычисляет n«кусочки» последовательности, где каждый кусочек является счетчиком до 1.

l       % Push 1
i       % Push input, n
:       % Range [1 2 ...n]
"       % For each k in that range
  @E    %   Push 2*k
  Zv    %   Symmetric range: [1 2 ... 2*k-1 2*k 2*k-1 ... 2 1]
  4L)   %   Remove last entry: [1 2 ... 2*k-1 2*k 2*k-1 ... 2]
]       % End
v       % Concatenate all stack contents into a column vector
G)      % Get n-th entry. Implicitly display

Шелуха , 12 10 байт

!ṁ§¤+hḣṫİ0

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

1-индексированный, работает довольно быстро

объяснение

!ṁ§¤+hḣṫİ0
 ṁ      İ0    Map the following function over the even numbers and concatenate the results together
  §   ḣṫ      Get the ranges 1-n and n-1, then... 
   ¤+h         remove the last element from both of them and concatenate them together
!             Return the element of the resulting list at the given index

Mathematica, 90 байт

Flatten[{1}~Join~Table[Join[Rest[p=Range@i],Reverse@Most@p],{i,2,Round[2Sqrt@#],2}]][[#]]&

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

Сетчатка , 62 байта

.+
$*
^((^.|\2..)*)\1.
6$*1$2$2;1
(?=.+;(.+))\1(.+).*;\2.*
$.2

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Ввод 1-индексирован. Первый этап - просто десятичное в унарное преобразование. Второй этап находит наибольшее квадратное число sстрого меньше, чем половина n; $1есть s², пока $2есть 2s-1. Он вычисляет два значения, во-первых, число чисел в текущем прогоне вверх / вниз 4(s+1) = 4s+4 = 2$2+6, и, во-вторых, положение в этом прогоне, то есть n-2s² = n-(2$1+1)+1 = n-$&+1, которое просто требует 1компенсировать значение, 1используемое для обеспечения строгого неравенства. Затем на последнем этапе отсчитывается от этой позиции до начала и конца цикла, берется младший результат и преобразуется в десятичное число.

Mathematica, 67 байт

(t=z=1;While[(x=3-4t+2t^2)<#,t++;z=x];If[#-z>2t-2,4t-5+z-#,#-z+1])&

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

Perl 5 , 43 + 1 (-p) = 44 байта

$_=($n=2*int sqrt$_/2)+2-abs$n/2*$n+$n+1-$_

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

Я работал над формулой для прямого вычисления n-го элемента. Затем я увидел, что @ fireflame241 выполнил эту работу, и отправил ее в Perl.

# Perl 5 , 50 + 1 (-n) = 51 байт

push@r,1..++$",reverse 2..++$"while@r<$_;say$r[$_]

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

Результаты 0 проиндексированы.

Haskell , 115 81 байт

y%x=snd(span(<x)$scanl(+)y[y+1,y+3..])!!0
g 1=1
g x|1%x>2%x=1+g(x-1)|1>0=g(x-1)-1

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

Здесь происходит какое-то волшебство. Возможно, может быть короче, если бы я использовал нормальный подход, хотя.

объяснение

Сначала мы определимся %. %это функция, которая принимает две переменные x, иy . Он создает список scanl(+)y[y+1,y+3..]и находит первый элемент этого списка больше, чем x. scanl(+)просто выполняет итерационные суммы, чтобы получить треугольные числа, которые мы сделали бы scanl(+)0[1..], чтобы получить квадратные числа, которые мы сделали бы scanl(+)0[1,3..]. Два списка , в частности , мы будем строить являются scanl(+)2[3,5..]и scanl(+)1[2,4..]эти точки перегиба узора.

Теперь мы определяем основную функцию, gкоторая принимает x. Если xэто один, мы возвращаемся, 1потому что это первое значение. В противном случае мы проверяем следующие две точки перегиба, если перегиб вниз больше, 1%x>2xмы возвращаем преемника, g$x-1иначе мы возвращаем предшественника g$x-1.

Хорошо, но почему это работает?

Прежде всего «Что с тем, как мы находим вершины?». Важно отметить расстояние между последовательными вершинами одного типа. Вы заметите, что различия увеличиваются на 2 каждый раз. Это имеет смысл, потому что основания треугольников расширяются на 2 каждый раз. Мы можем сделать константу разницы списков с помощью литерала списка, например, так, [2,4..]и мы используем, scanl(+)чтобы превратить эти списки в наши списки вершин, основываясь на расположении первой вершины и первой разности.

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

Хаскелл , 56 51 46 байт

Вот мое лучшее решение с меньшим количеством математики и меньшим количеством байтов.

d x|e<-[1..x-1]=e++map(x+1-)e
(([1..]>>=d)!!0)

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

Пайк , 14 байт

SF}SDtO_+)sQt@

Попробуй это здесь!

S              -    range(1, input)
 F}SDtO_+)     -   for i in ^:
  }            -      ^ * 2
   S           -     range(1, ^)
        +      -    ^ + v
     tO_       -     ^[1:-1:-1]
          s    -  sum(^)
           Qt@ - ^[input-1]

C # (.NET Core) , 120 байт

Объяснение: довольно просто, первый вложенный цикл поднимается до нашего максимума, второй возвращается обратно до 2. Повтор для каждого кратного 2.

x=>{var a=0;for(int i=2,j=0;j<x;i+=2){for(var b=1;b<=i&j<x;b++,j++){a=b;}for(var c=i-1;c>1&j<x;c--,j++){a=c;}}return a;}

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

Рубин , 78 75 байт

Сохранено 1 байт благодаря Step Hen

Сохранено 1 байт благодаря Mr. Xcoder

->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a<2;a+=c<1?-1:1};a}

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

Надеюсь, я смогу получить несколько советов о том, как потратить побитный счет. Я пытался принять простой подход.

Java (OpenJDK 8) , 53 байта

n->{int i=2;for(;n>i;i+=4)n-=i;return n>i/2?i-n+2:n;}

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

-2 байта благодаря Nevay.

1-индексироваться.

TL; DR Мы разбиваем последовательность на удобные порции, находим порцию n, затем находим nthпозицию в порции.

Здесь мы можем разделить последовательность как [[1,2],[1,2,3,4,3,2],[1,2,3,4,5,6,5,4,3,2],...], что дает нам размеры фрагмента 4i-2. Начиная с i=2, мы вычитаем iиз n, по существу , движется вверх кусок в то время. Как только мы удовлетворяем n<=i, мы знаем, nчто теперь позиция правильного значения в текущем чанке.

Затем мы получаем значение, сравнивая nс iразмером фрагмента. Средняя точка каждого куска равна i/2+1; если nменьше, мы просто возвращаемся n. Если nбольше, мы вернемся i-n+2.

пример

n = 16, i = 2

Is n > i? Yes, n = n - 2 = 14, i = i + 4 = 6
Is n > i? Yes, n = n - 6 = 8, i = i + 4 = 10
Is n > i? No, stop looping.
10 / 2 + 1 = 6
Is n > 6? Yes, return i - n + 2 = 8 - 6 + 2 = 4

Python 2 , 5! байт (120 байт: P)

r=range
a=[]
for i in r(2,998,2): 
	for j in r(1,i+1): a.append(j)
	for j in r(i-1,1,-1): a.append(j)
print a[input()-1]

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

Прямо, делает список, а затем принимает элемент input'th

Python 3 , 184 156 байт

l,n,r=list,next,range
h=lambda x:l(r(1,x))+l(r(x-2,1,-1))
def g():
	x=3
	while True:yield from h(x);x+=2
def f(i):
	x=g()
	for _ in r(i-1):n(x)
	return n(x)

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

игра в гольф с генератором Python для «ленивой» оценки

QBIC , 47 байт

g=q{p=p+1~p=:|_Xg\g=g+q~g=1or g>=r|r=r+1┘q=q*-1

объяснение

g=q         var g is the current value of the sequence; set to 1 at the start
{           DO infinitely
p=p+1       raise the step counter (var p)
~p=:|_Xg    IF p equals the input term a (read from cmd line) THEN QUIT, printing g
\           ELSE
g=g+q       raise (or decrement) g by q (q is 1 at the start of QBIC)
~g=1        IF g is at the lower bound of a subsequence
    or g>=r OR g is at the upper bound (r start as 2 in QBIC)
|r=r+1      THEN increment r (this happens once on lower bound, and once on upper, 
            total of 2 raise per subsequence)
┘q=q*-1     and switch q from 1 to -1

Röda , 54 байта

f n{seq 1,n|{|i|seq 1,2*i;seq 2*i-1,2}_|head n+2|tail}

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

Звоните с: try f(n)

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

Поскольку функция действительно возвращает фактический ответ вскоре после его вызова (явно меньше минуты), я думаю, что этот ответ действителен.

(В Röda функции могут возвращать значения до их выхода из-за параллелизма.)

C # (.NET Core) , 99 95 86 байт

n=>{int i=1,t=2,d=0;for(;n>1;){i+=1-2*d;if(i==t){d++;t+=2;}if(i==1)d--;n--;}return i;}

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

Лямбда-функция, которая принимает и возвращает целое число. Единый цикл, который обрабатывает счет вверх и вниз.

PHP, 65 + 1 байт

for($x=$d=$z=1;--$argn;)$d=($x+=$d)>1?$x>$z?-1:$d:!!$z+=2;echo$x;

Запустите как трубу с -Rили попробуйте онлайн (или раскомментируйте одну из других версий).

Порт рекурсивного JavaScript tsh занимает 66 байтов:

function f($n,$t=2){return$t<2*$n?$t<$n?f($n-$t,$t+4):$t-$n+2:$n;}

Порт решения Арнаулда занимает 62 + 1:

$n=$argn;echo($n-=($r=(~-$n/2)**.5|0)*$r*2)<++$r*2?$n:$r*4-$n;

Гольф-порт Java на Ксандерхолле имеет самый короткий код (55 + 1 байт):

for($n=$argn;$n+2>$i+=4;)$n-=$i-2;echo$n*2>$i?$i-$n:$n;

Pyth ,  19  18 байт

-yhKs@/Q2 2a*yKhKt

Попробуй это здесь!