Supposons que vous répertoriez les nombres entiers positifs dans un triangle, puis retournez-le de gauche à droite. Étant donné un nombre, affichez le numéro auquel il est envoyé. Il s'agit d'un mappage auto-inverse.

         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

C'est le nième élément de A038722 , un indexé:

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

Cette séquence inverse des morceaux contigus des entiers positifs avec des longueurs croissantes:

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

Cas de test:

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

Classement:

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 octets

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

Une implémentation de la formule suivante d'OEIS :

Démo

let f =

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

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

Gelée , 8 7 octets

RṁR€UFi

Merci à @ErikTheOutgolfer pour avoir économisé 1 octet!

Essayez-le en ligne!

Comment ça marche

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 octets

Merci à Sp3000 pour l' .Cidée.

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

Essayez-le en ligne!

Explication

Je pense qu'il peut y avoir un moyen plus court de calculer cela en utilisant des nombres triangulaires, mais je pensais que c'était un abus intéressant d'un intégré, alors voici une solution différente.

L'idée de base est d'utiliser les modules intégrés "pack" et "unpack" d'Alice. "Pack", ou Z, prend deux entiers les mappe bijectivement à un seul entier. "Déballer", ou Y, inverse cette bijection et transforme un entier en deux. Normalement, cela peut être utilisé pour stocker une liste ou un arbre d'entiers dans un seul (grand) entier et récupérer les valeurs individuelles plus tard. Cependant, dans ce cas, nous pouvons utiliser les fonctions dans l'ordre inverse, pour laisser la nature de la bijection fonctionner pour nous.

Décompresser un entier en deux entiers consiste essentiellement en trois étapes:

1. Carte ℤ → ℕ (y compris zéro) avec un simple "pliage". C'est-à-dire, mappez des entiers négatifs sur des naturels impairs et des entiers non négatifs sur des naturels pairs.

2. Carte ℕ → ℕ ² , à l'aide de la fonction d'appariement Cantor . Autrement dit, les naturels sont écrits le long des diagonales d'une grille infinie et nous renvoyons les indices:

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

   Par exemple, 8serait mappé à la paire (1, 2).

3. Mappez ℕ ² → ℤ ² , en utilisant l'inverse de l'étape 1 sur chaque entier individuellement. Autrement dit, les naturels impairs sont mappés sur des nombres entiers négatifs, et même les naturels sont mappés sur des nombres entiers non négatifs.

Pour regrouper deux entiers en un, nous inversons simplement chacune de ces étapes.

Maintenant, nous pouvons voir que la structure de la fonction d'appariement de Cantor code commodément le triangle dont nous avons besoin (bien que les valeurs soient décalées d'une unité). Pour inverser ces diagonales, tout ce que nous devons faire est d'échanger les coordonnées x et y dans la grille.

Malheureusement, étant donné que les trois étapes ci-dessus sont combinées en un seul intégré Y(ou Z), nous devons annuler les mappages ℤ → ℕ ou ℕ → ℤ nous-mêmes. Cependant, ce faisant, nous pouvons enregistrer quelques octets en utilisant directement les mappages ℕ ⁺ → ℤ ou ℤ → ℕ ⁺ , pour prendre soin de l'erreur de coup par coup dans le tableau. Voici donc l'algorithme entier:

1. Carte ℕ ⁺ → ℤ en utilisant (n / 2) * (-1) ^n-1 . Ce mappage est choisi de telle sorte qu'il annule le mappage implicite ℤ → ℕ lors du déballage, sauf qu'il décale la valeur de 1.
2. Décompressez le résultat en deux nombres entiers.
3. Échangez-les.
4. Emballez à nouveau les valeurs échangées dans un seul entier.
5. Carte ℤ → ℕ ⁺ avec | 2n | + (n ≥0) . Encore une fois, ce mappage est choisi de telle sorte qu'il annule le mappage implicite ℕ → ℤ lors de l'empaquetage, sauf qu'il décale la valeur de 1.

Avec cela à l'écart, nous pouvons regarder le programme:

/o
\i@/...

Il s'agit simplement d'un cadre pour les programmes arithmétiques linéaires avec entrée et sortie entières.

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

Gelée , 8 octets

Ḥ½+.Ḟ²‘_

Essayez-le en ligne!

Port de ma réponse MATL.

MATL , 15 11 octets

EX^.5+kUG-Q

Essayez-le en ligne!

Cela utilise la formule

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

Octave , 71 68 octets

3 octets économisés grâce à Conor O'Brien .

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

Cela ne fonctionne pas pour les grandes entrées en raison de limitations de mémoire.

Essayez-le en ligne!

Explication

Tenez compte des commentaires n = 4. Le code construit d'abord la matrice

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

Ensuite , il remplace les entrées non nulles dans l' ordre des colonnes-major (vers le bas, puis à travers) par 1, 2, 3...:

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

Il retourne ensuite la matrice verticalement:

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

Enfin, il prend la n-ème valeur non nulle dans l'ordre des colonnes, ce qui est dans ce cas 6.

Haskell , 31 octets

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

Essayez-le en ligne!

Cette réponse utilise simplement la formule. C'est la réponse la moins intéressante ici, mais c'est aussi la plus golfique.

Haskell , 38 36 34 octets

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

Essayez-le en ligne!

(!0) est la fonction sans point qui nous intéresse.

Explication

Permettez-moi de commencer en disant que je suis très satisfait de cette réponse.

L'idée de base ici est que si nous supprimons le plus grand nombre triangulaire plus petit que notre entrée, nous pouvons l'inverser et rajouter le nombre triangulaire. Nous définissons donc un opérateur !, !prend notre entrée régulière x, mais il prend également un nombre supplémentaire y. ygarde une trace de la taille du nombre triangulaire croissant. Si x>ynous voulons récursif, nous diminuons xpar yet d' augmenter ypar un. Nous calculons donc (x-y)!(y+1)et ajoutons y+1à cela. Si x<=ynous avons atteint notre cas de base, pour inverser xle placement dans la ligne du triangle, nous revenons 1-x.

Haskell , 54 octets

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

Essayez-le en ligne!

(!!)$0:(>>=)[1..]f est une fonction sans point

Explication

La première chose qui nous intéresse est f, fest une fonction qui prend xet retourne la xth ligne du th triangle en sens inverse. Pour ce faire, il calcule d'abord le x-1nd nombre triangulaire et l'affecte à u. u<-div(x^2-x)2. Nous retournons ensuite la liste [u+x,u+x-1..u+1]. u+xest le xnuméro triangulaire et le premier numéro de la ligne, u+x-1est inférieur de un et le deuxième numéro de la ligne u+1est un de plus que le dernier numéro triangulaire et donc le dernier numéro de la ligne.

Une fois que nous avons, fnous formons une liste (>>=)[1..]f, qui est un aplatissement du triangle. Nous ajoutons zéro au début avec 0:pour que nos réponses ne soient pas compensées par un, et le fournissons à notre fonction d'indexation (!!).

Haskell , 56 octets

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

Essayez-le en ligne!

Celui-ci fait 2 octets de plus mais un peu plus élégant à mon avis.

C (gcc) , 48 octets

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

Essayez-le en ligne!

Probablement sous-optimal, mais je suis assez content de celui-ci. Utilise le fait que

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

(Si j'ai bien écrit la formule, c'est.)

05AB1E , 30 octets

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

Essayez-le en ligne!

Husk , 6 octets

!ṁ↔´CN

Essayez-le en ligne!

Explication

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

(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

Définit une fonction fqui effectue le mappage.Essayez-le en ligne!

Non golfé

Nous trouvons le plus petit nombre triangulaire supérieur ou égal au nombre d'entrée, ainsi que la ligne du triangle dans laquelle se trouve notre nombre. À partir de ceux-ci, nous pouvons calculer la version inversée du nombre.

• Si le nombre triangulaire actuel est inférieur à N, passez à la ligne suivante du triangle. (Nous traitons la ligne du haut comme la ligne 2 pour simplifier les calculs.)
• Sinon, la version inversée de N est (TN) + (TR) +2.

La fonction principale flipappelle simplement la fonction d'aide à _flippartir de la ligne supérieure.

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

·LD£í˜¹<è

Essayez-le en ligne!

Explication

·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

L'aplatissement des tableaux ne gère malheureusement pas très bien les grandes listes.
Au prix d'un octet, nous pourrions faire · t2z + ïn¹-> en utilisant la formule mathématique floor(sqrt(2*n)+1/2)^2 - n + 1trouvée sur OEIS .

Lot, 70 octets

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

Utilise une boucle pour trouver l'index du nombre triangulaire au moins aussi grand que n.

PHP, 35 octets

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

Même formule que celle utilisée dans l' approche Arnaulds

C #, 46 44 octets

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

Je porte la solution de @ Arnauld . Merci!

• Pow de 0,5 est Sqrt. 2 octets enregistrés!

APL (Dyalog), 27 octets

J'ai deux solutions en même temps.

Un train:

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

Essayez-le en ligne!

Et un dfn:

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

Essayez-le en ligne!

Ces deux solutions créent d'abord le triangle inversé, puis extraient l'élément à l'index indiqué par l'argument ( 1basé sur).

J, 25 octets

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

Comme explication, réfléchissez f(n) = n(n+1)/2. f(r), étant donné la ligne r, renvoie le nombre le plus à gauche de la r^e ligne du triangle en miroir. Maintenant, réfléchissez g(n) = ceiling[f⁻¹(n)]. g(i), étant donné l'index i, renvoie la ligne sur laquelle se trouve l'index i. Ensuite, f(g(n))retourne le plus à gauche numéro de la ligne sur laquelle l' indice n est trouvé. C'est donc h(n) = f(g(n)) - (n - f(g(n)-1)) + 1la réponse au problème ci-dessus.

Simplifiant, nous obtenons h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1.

D'après l'apparence de la formule de @ Arnauld, il semble que:

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

Pyt , 13 12 octets

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

Approche du port d' Arnauld