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

         1                      1         
       2   3                  3   2       
     4   5   6    <--->     6   5   4     
   7   8   9  10         10   9   8   7   
11  12  13  14  15     15  14  13  12  11

Это n-й элемент A038722 с одним индексом:

1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...

Эта последовательность инвертирует непрерывные куски натуральных чисел с увеличением длины:

 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...
<-><----><-------><-----------><------------------>

Тестовые случаи:

1 -> 1
2 -> 3
3 -> 2
4 -> 6
14 -> 12
990 -> 947
991 -> 1035
1000 -> 1026
1035 -> 991
1036 -> 1081
12345 -> 12305

Leaderboard:

var QUESTION_ID=117879,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/117879/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

JavaScript (ES7), 26 байт

n=>((2*n)**.5+.5|0)**2-n+1

Реализация следующей формулы от OEIS :

демонстрация

let f =

n=>((2*n)**.5+.5|0)**2-n+1

for(n = 1; n <= 50; n++) {
  console.log(n, '->', f(n))
}

Желе , 8 7 байт

RṁR€UFi

Спасибо @ErikTheOutgolfer за сохранение 1 байта!

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

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

RṁR€UFi  Main link. Argument: n

R        Range; yield [1, ..., n].
  R€     Range each; yield [[1], [1, 2], [1, 2, 3], ..., [1, ..., n]].
 ṁ       Mold the left argument like the right one, yielding
         [[1], [2, 3], [4, 5, 6], ...]. The elements of the left argument are 
         repeated cyclically to fill all n(n+1)/2 positions in the right argument.
    U    Upend; reverse each flat array, yielding [[1], [3, 2], [6, 5, 4], ...].
     F   Flatten, yielding [1, 3, 2, 6, 5, 4, ...].
      i  Index; find the first index of n in the result.

Алиса , 27 байт

Спасибо Sp3000 за .Cидею.

/o
\i@/.2:e2,tE*Y~Z.H2*~.C+

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

объяснение

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

Основная идея состоит в том, чтобы использовать встроенные модули «pack» и «unpack» Алисы. «Пакет», или Z, принимает два целых числа, отображает их биективно в одно целое число. «Распаковать», илиY , инвертирует эту биекцию и превращает одно целое в два. Обычно это можно использовать для хранения списка или дерева целых чисел в одном (большом) целом числе и восстановления отдельных значений позже. Однако в этом случае мы можем использовать функции в обратном порядке, чтобы позволить природе биекции работать на нас.

Распаковка одного целого числа в два целых состоит в основном из трех шагов:

1. Карта ℤ → ℕ (включая ноль) с простым «складыванием». То есть отображать отрицательные целые числа в нечетные натуральные числа, а неотрицательные целые числа - в четные натуральные.

2. Карта ℕ → ℕ ² , используя функцию сопряжения Кантора . То есть натуральные числа записываются по диагонали бесконечной сетки, и мы возвращаем индексы:

      ...
   3  9 ...
   2  5 8 ...
   1  2 4 7 ...
   0  0 1 3 6 ...
   
      0 1 2 3
   

   Например 8, будет сопоставлен с парой (1, 2).

3. Карта ℕ ² → ℤ ² , используя обратный шаг 1 на каждое целое по отдельности. То есть нечетные натуральные числа отображаются в отрицательные целые числа, а четные натуральные числа отображаются в неотрицательные целые числа.

Чтобы упаковать два целых числа в одно, мы просто инвертируем каждый из этих шагов.

Теперь мы можем видеть, что структура функции сопряжения Кантора удобно кодирует нужный нам треугольник (хотя значения не совпадают). Чтобы перевернуть эти диагонали, все, что нам нужно сделать, это поменять местами x и y координаты на сетке.

К сожалению, поскольку все три из вышеперечисленных шагов объединены в одну встроенную Y(или Z), нам нужно отменить отображения ℤ → ℕ или ℕ → ourselves самостоятельно. Тем не менее, при этом мы можем сохранить пару байтов, непосредственно используя сопоставления ℕ ⁺ → ℤ или ℤ → ℕ ⁺ , чтобы позаботиться об ошибке «один за другим» в таблице. Итак, вот весь алгоритм:

1. Карта ℕ ⁺ → ℤ с использованием (n / 2) * (-1) ^n-1 . Это отображение выбрано таким, что оно отменяет неявное отображение ℤ → during во время распаковки, за исключением того, что оно сдвигает значение вниз на 1.
2. Распакуйте результат в два целых числа.
3. Поменяйте их местами.
4. Снова упакуйте измененные значения в одно целое число.
5. Карта ℤ → ℕ ⁺ с использованием | 2n | + (n≥0) . Опять же, это отображение выбрано таким, что оно отменяет неявное отображение ℕ → during во время упаковки, за исключением того, что оно сдвигает значение на 1.

С этим из пути мы можем смотреть на программу:

/o
\i@/...

Это просто структура для линейных арифметических программ с целочисленным вводом и выводом.

.    Duplicate the input.
2:   Halve it.
e    Push -1.
2,   Pull up the other copy of the input.
t    Decrement.
E    Raise -1 to this power.
*    Multiply. We've now computed (n/2) * (-1)^(n-1).
Y    Unpack.
~    Swap.
Z    Pack.
.H   Duplicate the result and take its absolute value.
2*   Double.
~    Swap with other copy.
.C   Compute k-choose-k. That's 1 for k ≥ 0 and 0 for k < 0.
+    Add. We've now computed |2n| + (n≥0).

Желе , 8 байт

Ḥ½+.Ḟ²‘_

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

Порт моего MATL ответа.

MATL , 15 11 байт

EX^.5+kUG-Q

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

Это использует формулу

a(n) = floor(sqrt(2*n)+1/2)^2 - n + 1.

Октава , 71 68 байт

3 байта сохранены благодаря Конору О'Брайену .

x=triu(ones(n=input('')));x(~~x)=1:nnz(x);disp(nonzeros(flip(x))(n))

Это не работает для больших входов из-за ограничений памяти.

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

объяснение

Рассмотрим ввод n = 4. Код сначала строит матрицу

 1     1     1     1
 0     1     1     1
 0     0     1     1
 0     0     0     1

Затем он заменяет ненулевые элементы в столбцах порядка (вниз, а затем по горизонтали) от 1, 2, 3...:

 1     2     4     7
 0     3     5     8
 0     0     6     9
 0     0     0    10

Затем он переворачивает матрицу по вертикали:

 0     0     0    10
 0     0     6     9
 0     3     5     8
 1     2     4     7

Наконец, он принимает n-ное ненулевое значение в мажорном столбце, который в данном случае равен 6.

Haskell , 31 байт

r=round
f n=r(sqrt$2*n)^2-r n+1

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

Этот ответ просто использует формулу. Это наименее интересный ответ здесь, но он также оказывается самым гольфом.

Haskell , 38 36 34 байта

x!y|x<=y=1-x|v<-y+1=v+(x-y)!v
(!0)

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

(!0) это функция без точек, с которой мы имеем дело.

объяснение

Позвольте мне начать с того, что я очень доволен этим ответом.

Основная идея здесь заключается в том, что, если мы удалим наибольшее треугольное число, меньшее нашего ввода, мы можем обратить его вспять и добавить обратно треугольное число. Таким образом, мы определяем оператор !, который !принимает наш обычный ввод x, но он также требует дополнительного числа y. yотслеживает размер растущего треугольного числа. Если x>yмы хотим рекурсию, мы уменьшаем xпутем yи увеличения yна единицу. Итак, мы рассчитаем (x-y)!(y+1)и добавим y+1к нему. Если x<=yмы достигли нашего базового случая, для обратного xразмещения в строке треугольника мы возвращаемся1-x .

Haskell , 54 байта

f x|u<-div(x^2-x)2=[u+x,u+x-1..u+1]
(!!)$0:(>>=)[1..]f

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

(!!)$0:(>>=)[1..]f это бессмысленная функция

объяснение

Первое, что нас интересует f, f- это функция, которая принимает xи возвращает xстроку в обратном порядке. Это делается путем вычисления первого x-1треугольного числа и присвоения его u. u<-div(x^2-x)2, Затем мы возвращаем список [u+x,u+x-1..u+1]. u+xэто xтреугольное число и первое число в строке, u+x-1на единицу меньше, чем второе число в строкеu+1 на единицу больше, чем последнее треугольное число и, следовательно, последнее число в строке.

После того, как fу нас есть, мы формируем список (>>=)[1..]f, который является уплощением треугольника. Мы добавляем ноль в начало, 0:чтобы наши ответы не были смещены на единицу, и добавляем его в нашу функцию индексации(!!) .

Haskell , 56 байт

f 0=[0]
f x|u<-f(x-1)!!0=[u+x,u+x-1..u+1]
(!!)$[0..]>>=f

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

Это на 2 байта длиннее, но, на мой взгляд, немного более элегантно.

C (gcc) , 48 байтов

k,j,l;f(n){for(k=j=0;k<n;)l=k,k+=++j;n=1+k-n+l;}

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

Возможно, неоптимальный, но я очень доволен этим. Использует тот факт, что

NTF _N = T _N + A057944 ( N ) - N + 1

(Если я правильно написал формулу, то есть.)

05AB1E , 30 байтов

U1V[YLO>X›iYLOX-UY<LO>X+,q}Y>V

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

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

!ṁ↔´CN

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

объяснение

!ṁ↔´CN  -- implicit input N, for example: 4
   ´ N  -- duplicate the natural numbers:
           [1,2,3,…] [1,2,3,…]
    C   -- cut the second argument into sizes of the first:
           [[1],[2,3],[4,5,6],[7,8,9,10],…]
 ṁ↔     -- map reverse and flatten:
           [1,3,2,6,5,4,10,9,8,7,15,…
!       -- index into that list:
           6

тинилисп , 78 байт

(d _(q((R N T)(i(l T N)(_(a R 1)N(a T R))(a 2(a T(s T(a N R
(d f(q((N)(_ 2 N 1

Определяет функцию, fкоторая выполняет сопоставление.Попробуйте онлайн!

Ungolfed

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

• Если текущее треугольное число меньше N, перейдите к следующей строке треугольника. (Мы рассматриваем верхний ряд как ряд 2, чтобы сделать математику проще.)
• В противном случае перевернутая версия N имеет вид (TN) + (TR) +2.

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

(load library)

(def _flip
 (lambda (Num Row Triangular)
  (if (less? Triangular Num)
   (_flip Num (inc Row) (+ Triangular Row))
   (+ 2
    (- Triangular Num)
    (- Triangular Row))))))

(def flip
 (lambda (Num) (_flip Num 2 1)))

05AB1E , 9 байтов

·LD£í˜¹<è

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

объяснение

·L          # push range [1 ... 2n]
  D         # duplicate
   £        # split the first list into pieces with size dependent on the second list
    í       # reverse each sublist
     ˜      # flatten
      ¹<è   # get the element at index <input>-1

К сожалению, выравнивание массивов не очень хорошо справляется с большими списками.
Ценой в 1 байт мы могли бы сделать · t2z + ïn¹->, используя математическую формулу, floor(sqrt(2*n)+1/2)^2 - n + 1найденную в OEIS .

Пакетная, 70 байт

@set/ai=%2+1,j=%3+i
@if %j% lss %1 %0 %1 %i% %j%
@cmd/cset/ai*i+1-%1

Использует цикл, чтобы найти индекс треугольного числа, по крайней мере, такого же размера, как n.

PHP, 35 байт

<?=((2*$argn)**.5+.5^0)**2-$argn+1;

Та же формула, которая используется в подходе Арно

C #, 46 44 байта

n=>Math.Pow((int)(Math.Sqrt(2*n)+.5),2)-n+1;

Я портирую решение @ Арно . Спасибо!

• Пау 0,5 является Sqrt. 2 байта сохранены!

APL (Дьялог), 27 байт

У меня есть два решения на одном и том же bytecount.

Поезд:

⊢⊃⊃∘(,/{⌽(+/⍳⍵-1)+⍳⍵}¨∘⍳)

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

И DFN:

{⍵⊃⊃((⍳⍵),.{1+⍵-⍳⍺}+\⍳⍵)}

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

Оба эти решения сначала создают перевернутый треугольник, а затем извлекают элемент по индексу, указанному аргументом ( 1-based).

J, 25 байт

3 :'>:y-~*:>.-:<:%:>:8*y'

В качестве объяснения рассмотрим f(n) = n(n+1)/2. f(r), Учитывая строку r, возвращает крайний левый номер - r^й строке зеркальном треугольника. Теперь рассмотрим g(n) = ceiling[f⁻¹(n)]. g(i)с учетом индекса iвозвращает строку, по которой найден индекс i. Затем f(g(n))возвращает крайний левый номер строки, в которой найден индекс n. Итак, h(n) = f(g(n)) - (n - f(g(n)-1)) + 1является ответом на вышеуказанную проблему.

Упрощая, мы получаем h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1.

Из формул @ Арнаулда видно, что:

ceiling[(-1 + sqrt(1 + 8n))/2] = floor[1/2 + sqrt(2n)],

Пыть , 13 12 байт

←Đ2*√½+⌊²-~⁺

Порт Арнаулда подход