Descrição

Já houve alguns outros desafios com relação a esses números, e espero que este não esteja entre eles.

O n º número triangular é igual à soma de todos os números naturais até n , coisas simples. Há uma página da Wikipedia e uma entrada na OEIS , para aqueles que desejam se informar mais.

Agora, Gauss descobriu que todo número natural pode ser expresso como uma soma de três números triangulares (estes incluem 0), e é bom ter um número mais de uma vez, por exemplo 0 + 1 + 1 = 2.

Desafio

Sua tarefa é escrever um programa ou função, dado um número natural (inclusive 0), imprime três números triangulares que somam o argumento. Você pode imprimir os números separados por espaços, como uma matriz ou por outro método que desejar. No entanto, é proibido usar qualquer função interna para obter diretamente uma matriz, um intervalo ou qualquer outra forma de coleção que contenha uma lista de números triangulares (por exemplo, um único átomo que produz o intervalo).

Casos de teste

9 -> 6 + 3 + 0 or 3 + 3 + 3
12 -> 6 + 6 + 0 or 6 + 3 + 3 or 10 + 1 + 1
13 -> 6 + 6 + 1
1 -> 1 + 0 + 0
0 -> 0 + 0 + 0

Nota: Se houver mais de uma combinação possível, você poderá imprimir uma ou todas, mas deverá imprimir qualquer combinação apenas uma vez, eliminando todas as combinações resultantes da reorganização de outras combinações. Eu realmente aprecio um link try-it e uma explicação, eu realmente gosto de ver como você resolve o problema;)

Isso é código-golfe , então as brechas padrão se aplicam. Que vença a resposta mais curta em bytes!

05AB1E , 10 bytes

Código:

ÝηO3ãʒOQ}¬

Explicação:

Ý             # Compute the range [0 .. input]
 η            # Get the prefixes
  O           # Sum each prefix to get the triangle numbers
   3ã         # Cartesian repeat 3 times
     ʒ  }     # Keep elements that
      OQ      #   have the same sum as the input
         ¬    # Retrieve the first element

Usa a codificação 05AB1E . Experimente online!

Python 2 , 99 bytes

from random import*
n=input()
while 1:b=sample([a*-~a/2for a in range(n+1)]*3,3);n-sum(b)or exit(b)

Experimente online!

Estou surpreso que isso seja mais curto do que itertoolsou uma lista tripla de compreensão! (Eventualmente) cospe uma resposta aleatória toda vez que você a executa.

Dois 102s:

n=input();r=[a*-~a/2for a in range(n+1)];print[(a,b,c)for a in r for b in r for c in r if a+b+c==n][0]
def f(n):r=[a*-~a/2for a in range(n+1)];return[(a,b,c)for a in r for b in r for c in r if a+b+c==n][0]

itertools parece ser 106:

from itertools import*;lambda n:[x for x in product([a*-~a/2for a in range(n+1)],repeat=3)if sum(x)==n][0]

Gelatina , 12 bytes

0r+\œċ3S=¥Ðf

Experimente online!

Como funciona

0r+\œċ3S=¥Ðf   input: n
0r             [0 1 ... n]
  +\           cumsum
    œċ3        combinations of 3 elements, with repetition
          Ðf   filter on
       S          sum
        =         equals n

Braquilog , 13 bytes

⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧

Experimente online!

Como funciona

⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧  input: n
⟦              [0 1 ... n]
 ⟦ᵐ            [[0] [0 1] [0 1 2] ... [0 1 ... n]]
   +ᵐ          [0 1 3 ... n(n+1)/2]
     j₃        [0 1 3 ... n(n+1)/2 0 1 3 ... n(n+1)/2 0 1 3 ... n(n+1)/2]
       ⊇       is a superset of
        Ṫ      a list of three elements 
         .     which is the output
          +?   which sums up to be the input

MATL , 18 bytes

Q:qYs3Z^t!sG=fX<Y)

Isso gera o primeiro resultado em ordem lexicográfica.

Experimente no MATL Online!

Explicação

Q     % Implicitly input n. Add 1
:     % Range (inclusive, 1-based): gives [1 2 ... n+1]
q     % Subtract 1 (element-wise): gives [0 1 ... n]
Ys    % Cumulative sum
3Z^   % Cartesian power with exponent 3. Gives a matrix where each row is a
      % Cartesian tuple
t     % Duplicate
!s    % Sum of each row
G=    % Does each entry equal the input?
f     % Find indices that satisfy that condition
X<    % Minimum
Y)    % Use as row index into the Cartesian power matrix. Implicitly display

Haskell, 66 59 bytes

Obrigado por permitir a saída de todas as soluções, que foi uma distração fascinante! Fiquei tão feliz por não precisar extrair uma solução e poder dar a todos eles que não percebi o custo resultante de evitar soluções permutadas. A observação de @ Lynn explicou isso para mim e deixe-me economizar 7 bytes.

f n|l<-scanl(+)0[1..n]=[(a,b,c)|c<-l,b<-l,a<-l,a+b+c==n]!!0

Isso vincula números triangulares mais do que suficientes le verifica todas as combinações.

Retina , 63 59 bytes

.+
$*
^((^1|1\2)*)((1(?(4)\4))*)((1(?(6)\6))*)$
$.1 $.3 $.5

Experimente online! O link inclui casos de teste. (1(?(1)\1))*é um correspondente de número triangular generalizado, mas, para o primeiro número triangular, podemos salvar alguns bytes usando ^a correspondência inicial.

PHP , 351 bytes

$r=[];function f($a=[],$c=0){global$argn,$t,$r;if($c<3){$n=$argn-array_sum($a);$z=array_filter($t,$f=function($v)use($n,$c){return$v>=$n/(3-$c)&&$v<=$n;});foreach($z as$v){$u=array_merge($a,[$v]);if(($w=$n-$v)<1){if(!$w){$u=array_pad($u,3,0);sort($u);if(!in_array($u,$r)){$r[]=$u;}}}else f($u,$c+1);}}}for($t=[0];$argn>$t[]=$e+=++$i;);f();print_r($r);

Experimente online!

Python 3 , 119 bytes

lambda n:[l for l in combinations_with_replacement([(t**2+t)/2for t in range(n)],3)if sum(l)==n]
from itertools import*

Experimente online!

Obrigado a @WheatWizard por salvar 12 bytes!

C / C ++ - 197 bytes

#include<stdio.h>
#define f(i,l,u) for(int i=l;i<=u;i++)
int t(int n){return n>1?n+t(n-1):n;}
int c(int n){f(a,0,n)f(b,a,n)f(c,b,n)if(t(a)+t(b)+t(c)==n)return printf("%d %d %d\n",t(a),t(b),t(c));}

Golpe por golpe:

#include<stdio.h>

Necessário para printf. Pode ser escolhido para determinadas versões de C

#define f(i,l,u) for(int i=l;i<=u;i++)

Economia de espaço para loop.

int t(int n){return n>1?n+t(n-1):n;}

Avaliador de triângulo recursivo.

int c(int n){f(a,0,n)f(b,a,n)f(c,b,n)if(t(a)+t(b)+t(c)==n)return printf("%d %d %d\n",t(a),t(b),t(c));}

Esse cara faz o trabalho pesado. Três loops aninhados para iteram a, b, c de 0 a n, observe que b e c iteram do valor anterior até n. Não é estritamente necessário reduzir a iteração dessa maneira, uma vez que a returnchegada em um minuto resolve o problema "duplicado".

No nível interno, se a soma dos três triângulos numerar ==o valor desejado, imprima os triângulos e retorne.

Você pode remover legalmente a returnpalavra - chave e converter o tipo de retorno de c em anulado para economizar mais alguns bytes e imprimir todas as soluções possíveis. É por esta razão que as iterações são limitados, se todos os loops decorreu entre 0an causaria duplicatas.

Mathematica, 63 bytes

(t=#;#&@@Select[Table[i(i+1)/2,{i,0,t}]~Tuples~{3},Tr@#==t&]‌​)&

CJam , 26 bytes

{_),[{\_@+}*]3m*_{:+}%@#=}

Porta da minha resposta MATL. Este é um bloco anônimo que espera a entrada na pilha e a substitui pela matriz de saída.

Experimente online!

R , 66 bytes

n=scan();b=expand.grid(rep(list(cumsum(0:n)),3));b[rowSums(b)==n,]

Algoritmo de força bruta; lê nstdin e retorna um quadro de dados em que cada linha é uma combinação de 3 números triangulares que somam n. Se necessário, posso retornar apenas a primeira linha para +4 bytes.

Experimente online!

Java 8, 164 bytes

n->{int t[]=new int[n+1],i=0,j=0;for(;i<=n;)if(Math.sqrt(8*i+++1)%1==0)t[j++]=i-1;for(int a:t)for(int b:t)for(int c:t)if(a+b+c==n)return new int[]{c,b,a};return t;}

Explicação:

Experimente aqui.

n->{                     // Method with int parameter and int-array return-type
  int t[]=new int[n+1],  //  Create an int-array to store triangular numbers
      i=0,j=0;           //  Two index-integers
  for(;i<=n;)            //  Loop (1) from 0 to `n` (inclusive)
    if(Math.sqrt(8*i+++1)%1==0) 
                         //   If `i` is a triangular number
      t[j++]=i-1;        //    Add it to array `t`
                         //  End of for-loop (1) (implicit / single-line body)
  for(int a:t)           //  Loop (2) over the triangular numbers
    for(int b:t)         //   Inner loop (3) over the triangular numbers
      for(int c:t)       //    Inner loop (4) over the triangular numbers
        if(a+b+c==n)     //     If the three triangular numbers sum equal the input
          return new int[]{c,b,a};
                         //      Return these three triangular numbers as int-array
                         //    End of loop (4) (implicit / single-line body)
                         //   End of loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  return t;              //  Return `t` if no sum is found (Java methods always need a
                         //  return-type, and `t` is shorter than `null`;
                         //  since we can assume the test cases will always have an answer,
                         //  this part can be interpret as dead code)
}                        // End of method

JavaScript, 108 bytes

r=[],i=a=b=0
while(a<=x)r.push(a=i++*i/2)
for(a=0;a<3;){
b=r[i]
if(b<=x){
x-=b
a++
console.log(b)}
else i--}

Explicação

x representa a entrada

while(a<=x)r.push(a=i++*i/2) Cria uma matriz de todos os números triangulares até x

O forloop imprime o número triangular mais alto menor que x, e subtrai esse número de x, por três iterações. (basicamente um algoritmo ganancioso)

Pitão, 19 bytes

Estou tão sem prática com Pyth, é falso: /

hfqQsT.C*3+0msSdSQ3

Experimente aqui .

hfqQsT.C*3+0msSdSQ3  Implicit: Q=input()

                SQ   Range 1-n
            m        Map the above over d:
              Sd       Range 1-d
             s         Sum the above
                     Yields [1,3,6,10,...]
          +0         Prepend 0 to the above
        *3           Triplicate the above
      .C          3  All combinations of 3 of the above
 f                   Filter the above over T:
    sT                 Where sum of T
  qQ                   Is equal to input
h                    Take the first element of that list

J , 36 bytes

((2!1+$@]#:0({I.@,)=)]+/+/~)2!1+i.,]

Experimente online!

Ruby 61 57 55 bytes

Inspirado pela resposta Python de Lynn . Ele gera trigêmeos aleatórios até que a soma desejada seja alcançada:

->n{x=Array.new 3{(0..rand(n+1)).sum}until x&.sum==n;x}

Requer Ruby 2.4. No Ruby 2.3 e mais antigo, é um erro de sintaxe e Range#sumnão está definido. Esta versão mais longa (64 bytes) é necessária para o Ruby 2.3:

->n{x=Array.new(3){(a=rand(n+1))*-~a/2}until x&.inject(:+)==n;x}

Aqui está um pequeno teste:

f=->n{x=Array.new 3{(0..rand(n+1)).sum}until x&.sum==n;x}
# => #<Proc:0x000000018aa5d8@(pry):6 (lambda)>
f[0]
# => [0, 0, 0]
f[13]
# => [0, 3, 10]
f[5]
# => [3, 1, 1]
f[27]
# => [21, 3, 3]
f[27]
# => [0, 21, 6]
f[300]
# => [3, 21, 276]

Experimente online com Ruby 2.3!

Javascript (ES6), 108 bytes - corrigido

Pega um número inteiro como uma entrada, gera uma matriz que [a, b, c]contém uma lista classificada de números de triângulos a + b + c = x, onde aé o maior número de triângulos menor ou igual à entrada e bé o maior número de triângulos menor ou igual à entrada menos a.

x=>{t=[0],t.f=t.forEach,i=j=k=0;for(;j<x;t[i]=j+=i++);t.f(a=>t.f(b=>t.f(c=>a+b+c==x?k=[a,b,c]:0)));return k}

Explicação

x=>{
    t=[0],                               // initialize an array of triangle numbers
    t.f=t.forEach,                       // copy forEach method into t.f,
                                         // saves a net of 4 bytes
    i=j=k=0;
    for(;j<x;t[i]=j+=i++);               // populate t with all triangle numbers that
                                         // we could possibly need
    t.f(                                 // loop over all t
        a=>t.f(                          // loop over all t
            b=>t.f(                      // loop over all t
                c=>a+b+c==x?k=[a,b,c]:0  // if a+b+c = x, set k = [a,b,c], else noop
                                         // using a ternary here saves 1 byte vs
                                         // if statement
                                         // iterating over t like this will find all
                                         // permutations of [a,b,c] that match, but
                                         // we will only return the last one found,
                                         // which happens to be sorted in descending order
            )
        )
    );
    return k
}

const F = x=>{t=[0],t.f=t.forEach,i=j=k=0;for(;j<x;t[i]=j+=i++);t.f(a=>t.f(b=>t.f(c=>a+b+c==x?k=[a,b,c]:0)));return k};

$('#output').hide();
$('#run').click(() => {
  const x = parseInt($('#input').val(), 10);
  if (x >= 0) {
    $('#input').val(x);
    const values = F(x);
    $('#values').text(values.join(', '));
    $('#output').show();
  }
  else {
    $('#output').hide();
    alert('You must enter a positive integer');
  }
});

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Enter a value: <input type="text" id="input" />
<br />
<button id="run">Get triangle numbers</button>
<br />
<span id="output">Triangle numbers are: <span id="values"></span></span>