Katakanlah Anda mencantumkan bilangan bulat positif dalam segitiga, lalu balikkan dari kiri ke kanan. Diberi nomor, tampilkan nomor yang dikirim. Ini adalah pemetaan terbalik sendiri.

         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

Ini adalah elemen ke- 9 dari A038722 , yang diindeks satu:

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

Urutan ini membalik potongan yang berdekatan dari bilangan bulat positif dengan panjang yang bertambah:

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

Kasus uji:

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

Papan peringkat:

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 byte

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

Implementasi formula berikut dari OEIS :

Demo

let f =

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

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

Jelly , 8 7 byte

RṁR€UFi

Terima kasih kepada @ErikTheOutgolfer untuk menghemat 1 byte!

Cobalah online!

Bagaimana itu bekerja

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 byte

Terima kasih kepada Sp3000 untuk .Cidenya.

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

Cobalah online!

Penjelasan

Saya pikir mungkin ada cara yang lebih pendek untuk menghitung ini menggunakan angka segitiga, tapi saya pikir ini adalah penyalahgunaan yang menarik dari built-in, jadi inilah solusi yang berbeda.

Ide dasarnya adalah memanfaatkan "bawaan" Alice dan "membongkar" bawaan. "Paket", atau Z, mengambil dua bilangan bulat memetakannya secara bijektif ke satu bilangan bulat. "Buka kemasan", atau Y, membalikkan bualan ini dan mengubah satu bilangan bulat menjadi dua. Biasanya, ini dapat digunakan untuk menyimpan daftar atau pohon bilangan bulat dalam satu bilangan bulat (besar) dan memulihkan nilai individu nanti. Namun, dalam hal ini kita dapat menggunakan fungsi dalam urutan yang berlawanan, untuk membiarkan sifat dari penambangan bekerja untuk kita.

Membongkar satu bilangan bulat menjadi dua bilangan bulat pada dasarnya terdiri dari tiga langkah:

1. Peta ℤ → ℕ (termasuk nol) dengan "lipat" sederhana. Yaitu, memetakan bilangan bulat negatif ke naturals yang aneh, dan bilangan bulat non-negatif ke naturals genap.

2. Peta ℕ → ℕ ² , menggunakan fungsi pemasangan Cantor . Yaitu, naturals ditulis di sepanjang diagonal grid yang tak terbatas dan kami mengembalikan indeks:

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

   Misalnya 8akan dipetakan ke pasangan (1, 2).

3. Peta ℕ ² → ℤ ² , menggunakan kebalikan dari langkah 1 pada setiap bilangan bulat secara individual. Artinya, naturals yang aneh dipetakan ke bilangan bulat negatif, dan bahkan naturals dipetakan ke bilangan bulat yang tidak negatif.

Untuk mengemas dua bilangan bulat menjadi satu, kita cukup membalikkan masing-masing langkah tersebut.

Sekarang, kita dapat melihat bahwa struktur fungsi pasangan Cantor dengan mudah mengkodekan segitiga yang kita butuhkan (walaupun nilainya tidak dalam satu per satu). Untuk membalikkan diagonal itu, yang perlu kita lakukan adalah menukar koordinat x dan y ke dalam kisi.

Sayangnya, karena ketiga langkah di atas digabungkan menjadi satu built-in Y(atau Z), kita perlu membatalkan pemetaan ℤ → ℕ atau ℕ → ℤ sendiri. Namun, saat melakukan itu kita dapat menyimpan beberapa byte dengan langsung menggunakan pemetaan ℕ ⁺ → ℤ atau ℤ → ℕ ⁺ , untuk mengatasi kesalahan off-by-one dalam tabel. Jadi di sini adalah keseluruhan algoritma:

1. Peta ℕ ⁺ → ℤ menggunakan (n / 2) * (-1) ^n-1 . Pemetaan ini dipilih sedemikian rupa sehingga membatalkan pemetaan implisit ℤ → ℕ selama pembongkaran, kecuali bahwa ia menggeser nilainya menjadi 1.
2. Bongkar hasilnya menjadi dua bilangan bulat.
3. Tukar mereka.
4. Kemas nilai yang ditukar menjadi satu integer lagi.
5. Peta ℤ → ℕ ⁺ menggunakan | 2n | + (n≥0) . Sekali lagi, pemetaan ini dipilih sedemikian rupa sehingga membatalkan pemetaan ℕ → ℤ implisit selama pengepakan, kecuali bahwa nilai tersebut naik nilainya sebesar 1.

Dengan itu, kita dapat melihat program:

/o
\i@/...

Ini hanyalah kerangka kerja untuk program aritmatika linier dengan input dan output integer.

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

Jelly , 8 byte

Ḥ½+.Ḟ²‘_

Cobalah online!

Port jawaban MATL saya.

MATL , 15 11 byte

EX^.5+kUG-Q

Cobalah online!

Ini menggunakan rumus

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

Oktaf , 71 68 byte

3 byte disimpan berkat Conor O'Brien .

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

Ini tidak berfungsi untuk input besar karena keterbatasan memori.

Cobalah online!

Penjelasan

Pertimbangkan input n = 4. Kode pertama membangun matriks

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

Kemudian menggantikan entri tidak nol dalam kolom-besar order (bawah, kemudian di) oleh 1, 2, 3...:

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

Kemudian ia membalik matriks secara vertikal:

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

Akhirnya, dibutuhkan nilai nbukan-nol dalam urutan kolom-utama, yang dalam hal ini adalah 6.

Haskell , 31 byte

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

Cobalah online!

Jawaban ini hanya menggunakan rumus. Ini adalah jawaban yang paling tidak menarik di sini, tetapi juga merupakan golfiest.

Haskell , 38 36 34 byte

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

Cobalah online!

(!0) adalah fungsi titik bebas yang menjadi perhatian kita.

Penjelasan

Biarkan saya memulai dengan mengatakan saya sangat senang dengan jawaban ini.

Ide dasar di sini adalah bahwa jika kita menghapus angka segitiga terbesar lebih kecil dari input kita, kita dapat membalikkannya dan menambahkan angka segitiga kembali. Jadi kami mendefinisikan operator !, !mengambil input reguler kami x, tetapi juga mengambil angka tambahan y. ymelacak ukuran angka segitiga yang tumbuh. Jika x>ykita ingin recurse, kami menurunkan xoleh ydan meningkatkan yper satu. Jadi kami menghitung (x-y)!(y+1)dan menambahkannya y+1. Jika x<=ykita telah mencapai base case kita, untuk membalikkan xpenempatan di deretan segitiga kita kembali 1-x.

Haskell , 54 byte

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

Cobalah online!

(!!)$0:(>>=)[1..]f adalah fungsi point-free

Penjelasan

Hal pertama yang kami perhatikan adalah f, fadalah fungsi yang mengambil xdan mengembalikan xderetan ke tiga dari segitiga secara terbalik. Ini dilakukan dengan terlebih dahulu menghitung angka x-1segitiga nd dan menetapkannya u. u<-div(x^2-x)2. Kami kemudian mengembalikan daftar [u+x,u+x-1..u+1]. u+xadalah angka xsegitiga ke - t dan angka pertama pada baris, u+x-1adalah satu kurang dari itu dan angka kedua pada baris u+1adalah satu lebih dari angka segitiga terakhir dan dengan demikian angka terakhir pada baris.

Setelah kita memiliki fkita membentuk daftar (>>=)[1..]f, yang merupakan perataan segitiga. Kami menambahkan nol ke depan dengan 0:sehingga jawaban kami tidak akan diimbangi oleh satu, dan menyediakannya ke fungsi pengindeksan kami (!!).

Haskell , 56 byte

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

Cobalah online!

Yang ini 2 byte lebih lama tapi menurut saya agak lebih elegan.

C (gcc) , 48 byte

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

Cobalah online!

Mungkin suboptimal, tapi saya cukup senang dengan yang ini. Menggunakan fakta itu

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

(Jika saya menuliskan formula dengan benar, itu adalah.)

05AB1E , 30 byte

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

Cobalah online!

Sekam , 6 byte

!ṁ↔´CN

Cobalah online!

Penjelasan

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

(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

Menentukan fungsi fyang melakukan pemetaan. Cobalah online!

Tidak disatukan

Kami menemukan bilangan segitiga terkecil yang lebih besar dari atau sama dengan bilangan masukan, serta deretan mana dari segitiga bilangan kita. Dari ini, kita dapat menghitung versi bilangan terbalik dari bilangan tersebut.

• Jika angka segitiga saat ini kurang dari N, kembalilah ke baris berikutnya dari segitiga. (Kami memperlakukan baris teratas sebagai baris 2 untuk membuat matematika lebih sederhana.)
• Jika tidak, versi N yang terbalik adalah (TN) + (TR) +2.

Fungsi utama flipcukup memanggil fungsi helper _flipmulai dari baris atas.

(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 byte

·LD£í˜¹<è

Cobalah online!

Penjelasan

·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

Perataan array sayangnya tidak menangani daftar yang lebih besar dengan sangat baik.
Dengan biaya 1 byte kita bisa melakukan · t2z + ïn¹-> menggunakan rumus matematika yang floor(sqrt(2*n)+1/2)^2 - n + 1ditemukan di OEIS .

Batch, 70 byte

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

Menggunakan loop untuk menemukan indeks angka segitiga setidaknya sebesar n.

PHP, 35 Bytes

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

Formula yang sama yang digunakan dalam Pendekatan Arnaulds

C #, 46 44 byte

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

Saya port solusi @ Arnauld . Terima kasih!

• Pow 0,5 adalah Sqrt. 2 byte disimpan!

APL (Dyalog), 27 byte

Saya punya dua solusi di bytecount yang sama.

Kereta:

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

Cobalah online!

Dan sebuah dfn:

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

Cobalah online!

Kedua solusi ini pertama-tama membuat segitiga terbalik dan kemudian mengekstrak elemen pada indeks yang dinyatakan oleh argumen ( 1berbasis).

J, 25 byte

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

Sebagai penjelasan, pertimbangkan f(n) = n(n+1)/2. f(r), mengingat baris r, mengembalikan angka paling kiri dari baris r^ke-3 dari segitiga cermin. Sekarang, pertimbangkan g(n) = ceiling[f⁻¹(n)]. g(i), mengingat indeks i, mengembalikan baris di mana indeks saya ditemukan. Kemudian, f(g(n))kembalikan angka paling kiri dari baris di mana indeks n ditemukan. Begitu,h(n) = f(g(n)) - (n - f(g(n)-1)) + 1 inilah jawaban untuk masalah di atas.

Menyederhanakan, kita dapatkan h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1 .

Dari tampilan rumus @ Arnauld, tampak bahwa:

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

Pyt , 13 12 byte

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

Pendekatan Port of Arnauld