La plupart des gens ici connaissent le triangle de Pascal. Il est formé de rangées successives, où chaque élément est la somme de ses deux voisins supérieur gauche et supérieur droit. Voici les premières 5lignes (empruntées au triangle Générer Pascal ):

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
  . . .

Réduire ces rangées à gauche

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . .

Triez-les par ordre croissant

1
1 1
1 1 2
1 1 3 3
1 1 4 4 6
. . .

Lisez ce triangle par rangées

[1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 4, 6 ...]

Étant donné une entrée n, sortez le nnuméro e de cette série. Il s'agit d' OEIS 107430 .

Règles

• Vous pouvez choisir une indexation basée sur 0 ou 1. Veuillez indiquer lequel dans votre soumission.
• L'entrée et la sortie peuvent être supposées correspondre au type d'entier natif de votre langue.
• L'entrée et la sortie peuvent être fournies par n'importe quelle méthode pratique .
• Un programme complet ou une fonction sont acceptables. S'il s'agit d'une fonction, vous pouvez renvoyer la sortie plutôt que de l'imprimer.
• Les failles standard sont interdites.
• Il s'agit de code-golf, donc toutes les règles de golf habituelles s'appliquent et le code le plus court (en octets) l'emporte.

JavaScript (ES6), 79 octets

0 indexé.

f=(n,a=[L=1])=>a[n]||f(n-L,[...a.map((v,i)=>k=(x=v)+~~a[i-1-i%2]),L++&1?k:2*x])

Démo

f=(n,a=[L=1])=>a[n]||f(n-L,[...a.map((v,i)=>k=(x=v)+~~a[i-1-i%2]),L++&1?k:2*x])

console.log([...Array(79).keys()].map(n => f(n)).join(', '))

Comment?

f = (                       // f = recursive function taking:
  n,                        //   n = target index
  a = [L = 1]               //   a[] = current row, L = length of current row
) =>                        //
  a[n] ||                   // if a[n] exists, stop recursion and return it
  f(                        // otherwise, do a recursive call to f() with:
    n - L,                  //   n minus the length of the current row
    [                       //   an array consisting of:
      ...a.map((v, i) =>    //     replace each entry v at position i in a[] with:
        k =                 //       a new entry k defined as:
        (x = v) +           //       v +
        ~~a[i - 1 - i % 2]  //       either the last or penultimate entry
      ),                    //     end of map()
      L++ & 1 ?             //     increment L; if L was odd:
        k                   //       append the last updated entry
      :                     //     else:
        2 * x               //       append twice the last original entry
    ]                       //   end of array update
  )                         // end of recursive call

Cet algorithme génère directement les lignes triées du triangle de Pascal. Il met à jour n en fonction de la longueur de la ligne précédente jusqu'à ce qu'il existe un [n] . Par exemple, 6 itérations sont nécessaires pour n = 19 :

 L | n  | a[]
---+----+------------------------
 1 | 19 | [ 1 ]
 2 | 18 | [ 1, 1 ]
 3 | 16 | [ 1, 1, 2 ]
 4 | 13 | [ 1, 1, 3, 3 ]
 5 |  9 | [ 1, 1, 4, 4, 6 ]
 6 |  4 | [ 1, 1, 5, 5, 10, 10 ]
                        ^^

Octave , 46 octets

@(n)(M=sort(spdiags(flip(pascal(n)))))(~~M)(n)

1 basé.

Essayez-le en ligne!

Explication

Considérez n=4comme exemple.

pascal(n) donne une matrice Pascal:

 1     1     1     1
 1     2     3     4
 1     3     6    10
 1     4    10    20

Les rangées du triangle Pascal sont les antidiagonales de cette matrice. Il est donc retourné verticalement en utilisantflip(···)

 1     4    10    20
 1     3     6    10
 1     2     3     4
 1     1     1     1

qui transforme les antidiagonales en diagonales.

spdiags(···) extrait les diagonales (non nulles), en partant du coin inférieur gauche, et les organise sous forme de colonnes à remplissage nul:

 1     1     1     1     0     0     0
 0     1     2     3     4     0     0
 0     0     1     3     6    10     0
 0     0     0     1     4    10    20

M=sort(···)trie chaque colonne de cette matrice et affecte le résultat à la variable M:

 0     0     0     1     0     0     0
 0     0     1     1     4     0     0
 0     1     1     3     4    10     0
 1     1     2     3     6    10    20

L'indexation logique (···)(~~M)est maintenant utilisée pour extraire les non-zéros de cette matrice dans l'ordre des colonnes (vers le bas, puis à travers). Le résultat est un vecteur colonne:

 1
 1
 1
 1
···
10
10
20

Enfin, la n-ième entrée de ce vecteur est extraite à l'aide (···)(n)de ce qui donne dans ce cas 1.

Python 2 , 86 78 72 octets

-8 octets grâce à Rod

g=lambda n,r=[1]:r[n:]and r[n/2]or g(n-len(r),map(sum,zip([0]+r,r+[0])))

Essayez-le en ligne!

Non golfé

def g(n, row=[1]):
  if n < len(row):
    return row[n/2]
  else:
    next_row = map(sum, zip([0] + row, row + [0]))
    return g(n - len(row), next_row)

Essayez-le en ligne!

La fonction calcule récursivement la ligne du triangle de Pascal. Compte tenu de la ligne actuelle comme row, map(sum, zip([0] + row, row + [0])).
À chaque appel, nla longueur de la ligne en cours est réduite. Si la fonction arrive sur la ligne de droite, le nthnuméro le plus bas de la ligne doit être renvoyé.
Comme la première moitié d'une ligne est en ordre croissant et que chaque ligne est symétrique, le nombre est à l'index n/2(indexé sur 0, division entière).

Wolfram Language (Mathematica) , 55 octets

L'indexation est basée sur 1.

(##&@@@Sort/@Table[n~Binomial~k,{n,0,#},{k,0,n}])[[#]]&

Essayez-le en ligne!

Explication

C'est probablement jouable au golf, je ne suis pas un utilisateur très expérimenté de Mathematica.

Table[n~Binomial~k,{n,0,#},{k,0,n}]

Pour chaque n ∈ [0, entrée] ∩ ℤ , générez le tableau des binômes avec chaque k ∈ [0, n] ∩ ℤ .

Sort/@

Triez chacun. Utilise un raccourci pour Map[function,object]- function/@object.

(##&@@@...)[[#]]

Aplatissez la liste résultante et récupérez l'élément dont l'index dans la liste est l'entrée.

APL (Dyalog) , 26 25 octets

1 octet enregistré grâce à @ngn

{⍵⊃0~⍨∊(⍋⊃¨⊂)¨↓⍉∘.!⍨⍳1+⍵}

Essayez-le en ligne!

R , 58 octets

function(n)(m=apply(outer(0:n,0:n,choose),1,sort))[m>0][n]

Essayez-le en ligne!

Calcule n choose kpour chaque n,ken [0,1,...,n]tant que matrice, trie les lignes ascendant (*), et supprime les zéros, puis l' nélément e.

(*) Cela les transforme également en colonnes, mais c'est mieux car R stocke une matrice comme un vecteur colonne, ce qui nous permet de l'indexer directement tout en préservant l'ordre.

Haskell , 143 132 125 123 octets

((p>>=s.h)!!)
p=[1]:map(\r->zipWith(+)(0:r)(r++[0]))p
h r=splitAt(div(length r)2)r
s(a,b)=reverse b!a
(h:t)!b=h:(b!t)
x!_=x

La première ligne est une fonction sans point qui prend un index (basé sur 0) et renvoie le nombre approprié dans la séquence. Essayez-le en ligne!

Ceci est mon tout premier programme Haskell! Je suis sûr que cela peut devenir beaucoup plus court. Les pourboires sont appréciés.

Enregistré 2 octets grâce à nimi

Non golfé

pascalRows = [1] : map (\row -> zipWith (+) (0:row) (row++[0])) pascalRows
halves row = splitAt (div (length row) 2) row
joinSorted (first, second) = interleave (reverse second) first
interleave [] _ = []
interleave longer shorter = (head longer) : (interleave shorter (tail longer))
f n = (concatMap (joinSorted.halves) pascalRows) !! n

JavaScript, 57 octets

f=(i,r=1)=>i<r?i>1?f(i-2,--r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

0 indexé.

Comment cela se fait-il:

Étape 0:

c=(i,r)=>i?r&&c(i-1,r-1)+c(i,r-1):1
f=(i,r=1)=>i<r?c(i>>1,r-1):f(i-r,r+1)

Ce code est facile à comprendre:

• la fonction ccalcule la formule d'utilisation de combinaison: C (n, k) = C (n-1, k) + C (n-1, k-1); ou 1 si k == 0 ou k == n
• fonction fessayer de trouver le numéro de ligne et l' indice de la ligne, puis appeler la fonction c pour obtenir le résultat.

Étape 1:

c=(i,r)=>i>1?--r&&c(i-2,r)+c(i,r):1
f=(i,r=1)=>i<r?c(i,r):f(i-r,r+1)

Dans cette étape, nous essayons de modifier l'appel de la fonction cà ce c(i,r)qui en fait la même que paramètre f.

Étape 2:

c=(i,r)=>i>1?--r&&c(i-2,r)+c(i<r?i:r-1,r):1
f=(i,r=1)=>i<r?c(i,r):f(i-r,r+1)

Nous testons i<rsi l'utilisation de la fonction fou de la fonction c. C'est pourquoi nous musk maintenons les i<rprises pendant la récursivité de la fonction c.

Étape 3:

f=(i,r=1)=>i<r?i>1?--r&&f(i-2,r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

À cette étape, nous fusionnons ces deux fonctions en une seule.

Après un peu plus de golf, nous avons finalement obtenu la réponse décrite ci-dessus.

f=(i,r=1)=>i<r?i>1?f(i-2,--r)+f(i<r?i:r-1,r):1:f(i-r,r+1)

for(i=0,x=1;x<10;x++) {
document.write('<p>')
for(j=0;j<x;j++,i++) document.write(`<b>${f(i)}</b>`)
}

p { text-align: center; }
b { display: inline-block; width: 4ch; font-weight: normal; }

Gelée , 13 octets

0rcþ`ZṢ€Ẏḟ0⁸ị

Essayez-le en ligne!

Utilisation de l'algorithme Dyalog d'Uriel.

1 indexé.

Explication:

0rcþ`ZṢ€Ẏḟ0⁸ị
0r            Return inclusive range from 0 to n
    `         Call this dyad with this argument on both sides
   þ           Outer product with this dyad
  c             Binomial coefficient
     Z        Zip
       €      Call this link on each element
      Ṣ        Sort
        Ẏ     Concatenate elements
         ḟ0   Remove 0s
           ⁸ị Take the nth element

JavaScript (Node.js) , 65 octets

Même un tableau n'est pas utilisé. 0 indexé.

f=(n,i=0,g=x=>x?x*g(x-1):1)=>n>i?f(n-++i,i):g(i)/g(c=n>>1)/g(i-c)

Essayez-le en ligne!

Explication:

f=(n,i=0,                 )=>                                     // Main Function
         g=x=>x?x*g(x-1):1                                        // Helper (Factorial)
                             n>i?                                 // Is n > i?
                                 f(n-++i,i):                      // If so, call function
                                                                  // f(n-i-1, i+1) to skip
                                                                  // . i+1 terms
                                            g(i)/g(c=n>>1)/g(i-c) // If not, since sorting 
                                                                  // . the binomial coeffs
                                                                  // . equals to writing
                                                                  // . the first floor(i/2)
                                                                  // . coefficients twice
                                                                  // . each, so a shortcut

Pascal , 373 octets

function t(n,k,r:integer):integer;begin if(n<k)then t:=r-1 else t:=t(n,k+r,r+1)end;
function s(n,k:integer):integer;begin if(k=0)then s:=n else s:=s(n+k,k-1)end;
function f(n,k:integer):integer;begin if((k<1)or(k>n))then f:=0 else if n=1 then f:=1 else f:=f(n-1,k-1)+f(n-1,k)end;
function g(n:integer):integer;var k:integer;begin k:=t(n,0,1);g:=f(k,(n-s(0,k-1)+2)div 2)end;

g est la fonction.

Essayez-le en ligne!

Java 8, 187 octets

n->{int r=~-(int)Math.sqrt(8*n+1)/2+1,a[]=new int[r],k=r,x=0;for(;k-->0;a[k]=p(r,k))x+=k;java.util.Arrays.sort(a);return a[n-x];}int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}

Explication:

Essayez-le en ligne.

n->{                   // Method with integer as both parameter and return-type
  int r=~-(int)Math.sqrt(8*n+1)/2+1,
                       //  Calculate the 1-indexed row based on the input
      a[]=new int[r],  //  Create an array with items equal to the current row
      k=r,             //  Index integer
      x=0;             //  Correction integer
  for(;k-->0;          //  Loop down to 0
    a[k]=p(r,k))       //   Fill the array with the Pascal's Triangle numbers of the row
    x+=k;              //   Create the correction integer
  java.util.Arrays.sort(a);
                       //  Sort the array
  return a[n-x];}      //  Return the `n-x`'th (0-indexed) item in this sorted array

// Separated recursive method to get the k'th value of the r'th row in the Pascal Triangle
int p(int r,int k){return--r<1|k<2|k>r?1:p(r,k-1)+p(r,k);}

MATL , 11 octets

:qt!XnSXzG)

1 basé.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Considérez l'entrée 4comme exemple. ;est le séparateur de lignes pour les matrices ou les vecteurs de colonnes.

:     % Implicit input: n. Push the row vector [1 2 ... n]          
      S STACK: [1 2 3 4]
q     % Subtract 1, emlement-wise: gives [0 1 ... n-1]
      % STACK: [0 1 2 3]
t!    % Duplicate and transpose into a column vector
      % STACK: [0 1 2 3], [0; 1; 2; 3]
Xn    % Binomial coefficient, element-wise with broadcast. Gives an
      % n×n matrix where entry (i,j) is binomial(i,j), or 0 for i<j
      % STACK: [1 1 1 1;
                0 1 2 3;
                0 0 1 3;
                0 0 0 1]
S     % Sort each column
      % STACK: [0 0 0 1;
      %         0 0 1 1;
      %         0 1 1 3;
      %         1 1 2 3]
Xz    % Keep only nonzeros. Gives a column vector
      % STACK: [1; 1; 1; 1; 1; 2; 1; 1; 3; 3]
G)    % Get the n-th element. Implicitly display
      % STACK: 1

Lot, 128 octets

@set/as=2,t=r=m=i=1
:l
@if %1 geq %t% set/as+=r,t+=r+=1&goto l
@for /l %%i in (%s%,2,%1)do @set/ar-=1,m=m*r/i,i+=1
@echo %m%

0 indexé.

APL (Dyalog Classic) , 17 octets

⎕⊃∊i!⍨,\⌊.5×i←⍳99

Essayez-le en ligne!

Indexation basée sur 0

notez que (49!98) > 2*53, c.-à-d. que le coefficient binomial 98 sur 49 est supérieur à 2 ⁵³ , donc à ce point Dyalog a déjà commencé à perdre de la précision à cause du point flottant IEEE

05AB1E , 10 octets

0 indexé

ÝεDÝc{}˜sè

Essayez-le en ligne!

Explication

Ý             # push range [0 ... input]
 ε    }       # apply to each element
  DÝc         # N choose [0 ... N]
     {        # sort
       ˜      # flatten result to a list
        sè    # get the element at index <input>

Gelée , 11 octets

Ḷc€`Ṣ€Fḟ0ị@

Essayez-le en ligne!

Un lien monadique prenant l'index et renvoyant un entier - utilise une indexation basée sur 1.

Comment?

Effectue le défi à peu près tel qu'il est écrit, juste avec plus de la droite du triangle de Pascal (zéros) qui est ensuite jeté ...

Ḷc€`Ṣ€Fḟ0ị@ - Link: integer, i    e.g. 1   or    9
Ḷ           - lowered range            [0]       [0,1,2,3,4,5,6,7,8]
   `        - repeat left as right arg [0]       [0,1,2,3,4,5,6,7,8]
 c€         - binomial choice for €ach [[1]]     [[1,0,0,0,0,0,0,0,0],[1,1,0,0,0,0,0,0,0],[1,2,1,0,0,0,0,0,0],[1,3,3,1,0,0,0,0,0],[1,4,6,4,1,0,0,0,0],[1,5,10,10,5,1,0,0,0],[1,6,15,20,15,6,1,0,0],[1,7,21,35,35,21,7,1,0],[1,8,28,56,70,56,28,8,1]]
    Ṣ€      - sort €ach                [[1]]     [[0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,1,1],[0,0,0,0,0,0,1,1,2],[0,0,0,0,0,1,1,3,3],[0,0,0,0,1,1,4,4,6],[0,0,0,1,1,5,5,10,10],[0,0,1,1,6,6,15,15,20],[0,1,1,7,7,21,21,35,35],[1,1,8,8,28,28,56,56,70]]
      F     - flatten                  [1]       [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,2,0,0,0,0,0,1,1,3,3,0,0,0,0,1,1,4,4,6,0,0,0,1,1,5,5,10,10,0,0,1,1,6,6,15,15,20,0,1,1,7,7,21,21,35,35,1,1,8,8,28,28,56,56,70]
       ḟ0   - filter discard zeros     [1]       [1,1,1,1,1,2,1,1,3,3,1,1,4,4,6,1,1,5,5,111,1,6,6,15,15,21,1,7,7,21,21,35,35,1,1,8,8,28,28,56,56,70]
         ị@ - index into (sw@p args)    1         3 --------------^

Rouge , 206 octets

f: func[n][t: copy[[1]]l: 0
while[l < n][a: copy last t insert append a 0 0 b: copy[]repeat i k:(length? a)- 1[append b a/(i) + a/(i + 1)]append t reduce[b]l: l + k]foreach p t[sort p]pick split form t{ }n]

1 base

Essayez-le en ligne!

Explication:

f: func [n] [
    t: copy [[1]]                       ; start with a list with one sublist [1]
    l: 0                                ; there are 1 items overall
    while [l < n] [                     ; while the number of items is less than the argument
        a: copy last t                  ; take the last sublist 
        insert append a 0 0             ; prepend and append 0 to it  
        b: copy []                      ; prepare a list for the sums  
        repeat i k: (length? a) - 1 [   ; loop throught the elements of the list
            append b a/(i) + a/(i + 1)] ; and find the sum of the adjacent items
        append t reduce [b]             ; append the resulting list to the total list
        l: l + k                        ; update the number of the items
    ]
    foreach p t [sort p]                ; sort each sublist
    v: pick split form t { } n          ; flatten the list and take the n-th element
]

Perl, 48 octets

Comprend +1pourp

perl -pe '$_-=$%until$_<++$%;$./=$_/--$%for 1..$_/2;$_=$.' <<< 19

Utilise l'indexation base 0.

J, 46 41 octets

f=:](([-2!]){/:~@(i.!<:)@])[:<.2&!@,:^:_1

0 indexé

Essayez-le en ligne!

Remarques:

• <.2&!@,:^:_1donne le numéro de ligne pertinent du triangle de Pascal en arrondissant l'inverse de y choose 2.
• /:~@(i.!<:)@] calcule la ligne et la trie.
• [-2!] donne l'index dans la ligne.

Julia , 70 octets

f(x)=map(n->binomial(n-1,ceil(Int,x/2-(n^2-n)/4-1)),round(Int,√(x*2)))

1 base

Explication:

il trouve d'abord le numéro de ligne, puis le numéro de colonne, puis calcule le binôme

Gelée , 17 octets

1+2\1,1j$$СṢ€Ẏ⁸ị

Essayez-le en ligne!

Pyth, 15 octets

@u+GSm.cHdhHhQY

0 indexé

Essayez-le

Explication

@u+GSm.cHdhHhQY
 u          hQY   Reduce on [0, ..., input], starting with the empty list...
  +G              ... append to the accumulator...
    Sm.cHdhH      ... the sorted binomial coefficients.
@              Q  Take the 0-indexed element.

Nettoyer , 80 octets

import StdEnv

\n=flatten[sort[prod[j+1..i]/prod[1..i-j]\\j<-[0..i]]\\i<-[0..]]!!n

Essayez-le en ligne!

En tant que fonction lambda.

Rubis , 56 octets

->n{a=0;n-=a until n<a+=1;[*2..a].combination(n/2).size}

Basé sur 0

Obtenez d'abord la ligne et la colonne dans le triangle, puis calculez le coefficient binomial correspondant à cette position.

Essayez-le en ligne!

Réellement , 8 octets

Largement basé sur la réponse Jelly de Jonathan Allan . Utilise l'indexation 0.

;r♂╣♂SΣE

Essayez-le en ligne!

Ungolfing

          Implicit input n.
;         Duplicate n.
 r        Lowered range. [0..n-1].
  ♂╣      Pascal's triangle row of every number.
    ♂S    Sort every row.
      Σ   Sum each row into one array.
       E  Get the n-th element of the array (0-indexed).
          Implicit return.

Noix de coco , 69 octets

def g(n,r=[1])=r[n:]and r[n//2]or g(n-len(r),[*map((+),[0]+r,r+[0])])

Essayez-le en ligne!

Pari / GP , 47 octets

n->concat([vecsort(Vec((1+x)^i))|i<-[0..n]])[n]

Essayez-le en ligne!

C (gcc) , 140 123 octets

• Enregistré 17 octets grâce au plafond .

F(n){n=n?n*F(~-n):1;}f(n,j,k,c){for(c=j=0;j<n;j++)for(k=0;k<=j/2;k++)if(++c==n||j&1|k-j/2&&++c==n)return F(j)/F(k)/F(j-k);}

Essayez-le en ligne!