Załóżmy, że podajesz liczby całkowite w trójkącie, a następnie odwracasz je od lewej do prawej. Podając liczbę, wypisz numer, na który została wysłana. To jest odwrotne odwzorowanie.

         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

To jest n-ty element A038722 z jednym indeksem:

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

Ta sekwencja odwraca ciągłe fragmenty liczb całkowitych dodatnich wraz ze wzrostem długości:

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

Przypadki testowe:

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

Tabela liderów:

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 bajtów

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

Wdrożenie następującej formuły z OEIS :

Próbny

let f =

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

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

Galaretka , 8 7 bajtów

RṁR€UFi

Dzięki @ErikTheOutgolfer za uratowanie 1 bajtu!

Wypróbuj online!

Jak to działa

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.

Alice , 27 bajtów

Dzięki Sp3000 za .Cpomysł.

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

Wypróbuj online!

Wyjaśnienie

Myślę, że może być krótszy sposób na obliczenie tego za pomocą liczb trójkątnych, ale pomyślałem, że jest to ciekawe nadużycie wbudowanej, więc oto inne rozwiązanie.

Podstawową ideą jest wykorzystanie wbudowanych „paczek” i „rozpakowywania” Alicji. „Paczka”, lub Z, bierze dwie liczby całkowite odwzorowuje je biotycznie na jedną liczbę całkowitą. „Rozpakuj” lub Yodwraca ten bijection i zamienia jedną liczbę całkowitą na dwie. Zwykle można tego użyć do przechowywania listy lub drzewa liczb całkowitych w jednej (dużej) liczbie całkowitej i odzyskania poszczególnych wartości później. Jednak w tym przypadku możemy użyć funkcji w odwrotnej kolejności, aby natura bijection działała dla nas.

Rozpakowanie jednej liczby całkowitej na dwie liczby całkowite składa się zasadniczo z trzech kroków:

1. Mapa ℤ → ℕ (w tym zero) z prostym „składaniem”. Oznacza to, że odwzoruj ujemne liczby całkowite na nieparzyste natury i nieujemne liczby całkowite na parzyste natury.

2. Mapa ℕ → ℕ ² , za pomocą funkcji parowania Cantor . Oznacza to, że naturale są zapisywane wzdłuż przekątnych nieskończonej siatki, a my zwracamy indeksy:

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

   Np. Zostanie 8zmapowany na parę (1, 2).

3. Mapa ℕ ² → ℤ ² , używając odwrotności kroku 1 na każdej liczbie całkowitej osobno. Oznacza to, że nieparzyste naturale są mapowane na ujemne liczby całkowite, a nawet naturale są mapowane na nieujemne liczby całkowite.

Aby spakować dwie liczby całkowite w jedną, po prostu odwracamy każdy z tych kroków.

Teraz widzimy, że struktura funkcji parowania Cantora wygodnie koduje potrzebny nam trójkąt (chociaż wartości są oddzielone od siebie). Aby odwrócić te przekątne, wszystko co trzeba zrobić to zamienić x i y współrzędne do sieci.

Niestety, ponieważ wszystkie trzy powyższe kroki są połączone w jeden wbudowany Y(lub Z), musimy sami cofnąć mapowania ℤ → ℕ lub ℕ → ℤ . Robiąc to, możemy jednak zaoszczędzić kilka bajtów, używając bezpośrednio mapowań ℕ ⁺ → ℤ lub ℤ → ℕ ⁺ , aby zająć się błędem off-by-one w tabeli. Oto cały algorytm:

1. Mapa ℕ ⁺ → ℤ pomocą (n / 2) * (-1) ^n-1 . To mapowanie jest wybrane tak, że anuluje niejawne mapowanie ℤ → ℕ podczas rozpakowywania, z tym wyjątkiem, że przesuwa wartość w dół o 1.
2. Rozpakuj wynik na dwie liczby całkowite.
3. Zamień je.
4. Ponownie spakuj zamienione wartości w jedną liczbę całkowitą.
5. Mapa ℤ → ℕ ⁺ za pomocą | 2n | + (n≥0) . Ponownie, to mapowanie jest wybrane tak, że anuluje niejawne mapowanie ℕ → ℤ podczas pakowania, z tym wyjątkiem, że przesuwa wartość w górę o 1.

W ten sposób możemy spojrzeć na program:

/o
\i@/...

Jest to po prostu struktura liniowych programów arytmetycznych z wejściowymi i wyjściowymi liczbami całkowitymi.

.    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).

Galaretka , 8 bajtów

Ḥ½+.Ḟ²‘_

Wypróbuj online!

Port mojej odpowiedzi MATL.

MATL , 15 11 bajtów

EX^.5+kUG-Q

Wypróbuj online!

To używa formuły

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

Oktawa , 71 68 bajtów

3 bajty zapisane dzięki Conorowi O'Brienowi .

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

Nie działa to w przypadku dużych danych wejściowych z powodu ograniczeń pamięci.

Wypróbuj online!

Wyjaśnienie

Rozważ wejście n = 4. Kod najpierw tworzy macierz

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

Następnie zastępuje niezerowe wpisy w kolejności kolumny-dur (w dół, a następnie w poprzek) przez 1, 2, 3...:

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

Następnie odwraca matrycę w pionie:

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

Wreszcie, przyjmuje n-tą niezerową wartość w porządku głównym kolumny, która w tym przypadku jest 6.

Haskell , 31 bajtów

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

Wypróbuj online!

Ta odpowiedź używa tylko formuły. Jest to najmniej interesująca odpowiedź tutaj, ale zdarza się również, że jest najbardziej golfowa.

Haskell , 38 36 34 bajtów

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

Wypróbuj online!

(!0) to funkcja bez punktów, o którą nam chodzi.

Wyjaśnienie

Zacznę od stwierdzenia, że ​​jestem bardzo zadowolony z tej odpowiedzi.

Podstawową ideą jest to, że jeśli usuniemy największą trójkątną liczbę mniejszą niż nasze dane wejściowe, możemy ją odwrócić i dodać z powrotem trójkątną liczbę. Zdefiniujemy więc operatora !, !przyjmujemy nasze zwykłe dane wejściowe x, ale także dodatkową liczbę y. yśledzi rozmiar rosnącej liczby trójkątnej. Jeśli x>ychcemy powtórzyć, zmniejszamy xsię yi zwiększamy yo jeden. Obliczamy (x-y)!(y+1)i dodajemy y+1do tego. Jeśli x<=yosiągnęliśmy nasz przypadek podstawowy, aby odwrócić xumieszczenie w rzędzie trójkąta, zwracamy 1-x.

Haskell , 54 bajty

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

Wypróbuj online!

(!!)$0:(>>=)[1..]f jest funkcją bez punktów

Wyjaśnienie

Pierwszą rzeczą, na której nam zależy f, fjest funkcja, która przyjmuje xi zwraca xw odwrotnym rzędzie th trójkąta. Robi to, najpierw obliczając x-1numer trójkątny i przypisując go u. u<-div(x^2-x)2. Następnie zwracamy listę [u+x,u+x-1..u+1]. u+xjest xth trójkątną liczbą i pierwszą liczbą w rzędzie, u+x-1jest o jeden mniejszą liczbą, a druga liczba w rzędzie u+1jest o jeden większa niż ostatnia liczba trójkątna, a zatem ostatnia liczba w rzędzie.

Kiedy już mamy, ftworzymy listę (>>=)[1..]f, która jest spłaszczeniem trójkąta. Z przodu dodajemy zero, 0:dzięki czemu nasze odpowiedzi nie zostaną przesunięte o jeden, i dostarczymy je do naszej funkcji indeksowania (!!).

Haskell , 56 bajtów

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

Wypróbuj online!

Ten jest o 2 bajty dłuższy, ale moim zdaniem nieco bardziej elegancki.

C (gcc) , 48 bajtów

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

Wypróbuj online!

Prawdopodobnie nieoptymalny, ale jestem z tego zadowolony. Wykorzystuje fakt, że

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

(To znaczy, jeśli poprawnie zapisałem formułę.)

05AB1E , 30 bajtów

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

Wypróbuj online!

Łuska , 6 bajtów

!ṁ↔´CN

Wypróbuj online!

Wyjaśnienie

!ṁ↔´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

tinylisp , 78 bajtów

(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

Definiuje funkcję, fktóra wykonuje mapowanie. Wypróbuj online!

Bez golfa

Znajdujemy najmniejszą liczbę trójkątną, która jest większa lub równa liczbie wejściowej, a także wiersz, w którym znajduje się nasza liczba. Na ich podstawie możemy obliczyć odwróconą wersję liczby.

• Jeśli bieżąca liczba trójkątna jest mniejsza niż N, przejdź do następnego rzędu trójkąta. (Traktujemy górny wiersz jak wiersz 2, aby matematyka była prostsza).
• W przeciwnym razie odwróconą wersją N jest (TN) + (TR) +2.

Główna funkcja flippo prostu wywołuje funkcję pomocnika, _flipzaczynając od górnego rzędu.

(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 bajtów

·LD£í˜¹<è

Wypróbuj online!

Wyjaśnienie

·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

Spłaszczanie tablic niestety nie radzi sobie dobrze z większymi listami.
Kosztem 1 bajtu moglibyśmy zrobić · t2z + ïn¹-> przy użyciu wzoru matematycznego floor(sqrt(2*n)+1/2)^2 - n + 1znalezionego w OEIS .

Partia, 70 bajtów

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

Korzysta z pętli, aby znaleźć indeks liczby trójkątnej co najmniej tak dużej jak n.

PHP, 35 bajtów

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

Ta sama formuła, która jest używana w podejściu Arnaulds

C #, 46 44 bajtów

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

I portu @ rozwiązania Arnauld za . Dziękuję Ci!

• Pow 0,5 to Sqrt. 2 bajty zapisane!

APL (Dyalog), 27 bajtów

Mam dwa rozwiązania w tej samej liczbie bajtów.

Pociąg:

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

Wypróbuj online!

I dfn:

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

Wypróbuj online!

Oba te rozwiązania najpierw tworzą odwrócony trójkąt, a następnie wyodrębniają element o indeksie podanym przez argument (na podstawie 1).

J, 25 bajtów

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

Jako wyjaśnienie zastanów się f(n) = n(n+1)/2. f(r), biorąc pod uwagę wiersz r, zwraca lewą liczbę r^trzeciego rzędu lustrzanego trójkąta. Teraz zastanów się g(n) = ceiling[f⁻¹(n)]. g(i), biorąc pod uwagę indeks i, zwraca wiersz, w którym znaleziono indeks i. Następnie f(g(n))zwraca lewą liczbę wiersza, w którym znaleziono indeks n. Tak więc h(n) = f(g(n)) - (n - f(g(n)-1)) + 1jest odpowiedź na powyższy problem.

Upraszczamy, rozumiemy h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1.

Z wyglądu formuły @ Arnauld wynika, że:

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

Pyt , 13 12 bajtów

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

Podejście do Port of Arnauld