Opis

Przed tymi liczbami było jeszcze wiele innych wyzwań i mam nadzieję, że nie ma ich wśród nich.

N th liczby trójkątnego jest równa sumie wszystkich liczb naturalnych aż do n , proste rzeczy. Istnieje strona wikipedia i wpis w OEIS , dla tych, którzy chcą się lepiej dowiedzieć.

Teraz Gauss odkrył, że każda liczba naturalna może być wyrażona jako suma trzech liczb trójkątnych (w tym 0), i dobrze jest mieć jedną liczbę więcej niż raz, np 0 + 1 + 1 = 2.

Wyzwanie

Twoim zadaniem jest napisanie programu lub funkcji, z podaniem liczby naturalnej (w tym 0), wypisuje trzy liczby trójkątne, które sumują się do argumentu. Możesz wydrukować liczby rozdzielone spacjami, tablicą lub inną metodą, którą lubisz. Jednakże, jest zakazane używać jakichkolwiek funkcji Builtin bezpośrednio uzyskać układ, zakres lub dowolną inną formę zbioru zawierającą listę numerów trójkątnych (na przykład pojedynczy atom, który otrzymuje się zakres).

Przypadki testowe

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

Uwaga: Jeśli istnieje więcej niż jedna możliwa kombinacja, możesz wydrukować dowolną lub wszystkie, ale musisz wydrukować dowolną kombinację tylko raz, eliminując wszystkie kombinacje wynikające z zmiany kolejności innych kombinacji. Byłbym wdzięczny za link do wypróbowania i wyjaśnienie. Naprawdę uwielbiam patrzeć, jak rozwiązujesz problem;)

To jest golf golfowy , więc obowiązują standardowe luki. Niech wygra najkrótsza odpowiedź w bajtach!

05AB1E , 10 bajtów

Kod:

ÝηO3ãʒOQ}¬

Wyjaśnienie:

Ý             # 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

Wykorzystuje kodowanie 05AB1E . Wypróbuj online!

Python 2 , 99 bajtów

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)

Wypróbuj online!

Jestem bardzo zaskoczony, że to jest krótsze niż itertools lub potrójne rozumienie listy! (Ostatecznie) wyrzuca losową odpowiedź za każdym razem, gdy ją uruchomisz.

Dwa 102:

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 wygląda na 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]

Galaretka , 12 bajtów

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

Wypróbuj online!

Jak to działa

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

Brachylog , 13 bajtów

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

Wypróbuj online!

Jak to działa

⟦⟦ᵐ+ᵐ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 bajtów

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

Daje to pierwszy wynik w porządku leksykograficznym.

Wypróbuj w MATL Online!

Wyjaśnienie

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

Dziękujemy za umożliwienie przedstawienia wszystkich rozwiązań, co było fascynującą rozrywką! Byłem tak szczęśliwy, że nie muszę wyodrębniać jednego rozwiązania i mogłem po prostu dać im wszystko, że nie zauważyłem kosztów związanych z unikaniem permutowanych rozwiązań. Uwaga Lynn wyjaśniła mi to i pozwól mi zaoszczędzić 7 bajtów.

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

Wiąże to więcej niż wystarczającą liczbę trójkątną l i sprawdza wszystkie kombinacje.

Siatkówka , 63 59 bajtów

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

Wypróbuj online! Link zawiera przypadki testowe. (1(?(1)\1))*jest uogólnionym dopasowaniem liczb trójkątnych, ale dla pierwszej liczby trójkątnej możemy zapisać kilka bajtów, używając ^do początkowego dopasowania.

PHP , 351 bajtów

$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);

Wypróbuj online!

Python 3 , 119 bajtów

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*

Wypróbuj online!

Dzięki @WheatWizard za zapisanie 12 bajtów!

C / C ++ - 197 bajtów

#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));}

Cios przez cios:

#include<stdio.h>

Potrzebny do printf. Można pominąć w przypadku niektórych wersji C.

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

Oszczędność miejsca dla pętli.

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

Oceniający rekurencyjny trójkąt.

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));}

Ten facet wykonuje ciężkie podnoszenie. Trzy zagnieżdżone dla pętli iterują a, b, c od 0 do n, zauważ, że każdy b i c iteruje od poprzedniej wartości do n. Od tego czasu nie jest absolutnie konieczne przycinanie iteracjireturn pojawienie się w ciągu minuty rozwiązuje problem „duplikowania”.

Na poziomie wewnętrznym, jeśli suma trzech liczb trójkątów == żądaną wartość, wydrukuj trójkąty i wróć.

Możesz legalnie usunąć returnsłowo kluczowe i przekonwertować zwrócony typ c na void, aby zaoszczędzić jeszcze kilka bajtów i wydrukować wszystkie możliwe rozwiązania. To z tego powodu, że iteracje są ograniczone, jeżeli wszystkie pętle trwał od 0do nniego spowodowałoby duplikatów.

Mathematica, 63 bajty

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

CJam , 26 bajtów

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

Port mojej odpowiedzi MATL. Jest to anonimowy blok, który oczekuje danych wejściowych na stosie i zastępuje je tablicą wyjściową.

Wypróbuj online!

R , 66 bajtów

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

Algorytm siły brutalnej; odczytuje nze standardowego wejścia i zwraca ramkę danych, w której każdy wiersz jest kombinacją 3 liczb trójkątnych, które się sumują n. W razie potrzeby mogę zwrócić tylko pierwszy wiersz dla +4 bajtów.

Wypróbuj online!

Java 8, 164 bajty

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;}

Wyjaśnienie:

Wypróbuj tutaj.

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

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--}

Wyjaśnienie

x reprezentuje dane wejściowe

while(a<=x)r.push(a=i++*i/2) Tworzy tablicę wszystkich liczb trójkątnych do x

forPętli drukuje najwięcej trójkątny poniżej x, a następnie odjęcie od tej liczby x, dla trzech powtórzeń. (w zasadzie chciwy algorytm)

Pyth, 19 bajtów

Tak bardzo nie ćwiczę z Pyth, to nieprawda: /

hfqQsT.C*3+0msSdSQ3

Wypróbuj tutaj .

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

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

Wypróbuj online!

Ruby 61 57 55 bajtów

Zainspirowany Lynn Python odpowiedź . Generuje losowe trojaczki, aż do osiągnięcia żądanej sumy:

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

Wymaga Ruby 2.4. W Ruby 2.3 i starszych jest to błąd składniowy i Range#sumnie jest zdefiniowany. Ta dłuższa wersja (64 bajty) jest potrzebna dla Ruby 2.3:

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

Oto mały test:

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]

Wypróbuj online z Ruby 2.3!

JavaScript (ES6), 108 bajtów - naprawione

Pobiera na wejściu liczbę całkowitą, wyprowadza tablicę [a, b, c]zawierającą posortowaną listę liczb trójkątów a + b + c = x, gdzie anajwiększa liczba trójkątów jest mniejsza lub równa wartości wejściowej i bjest największą liczbą trójkątów mniejszą lub równą minusowi wejścia 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}

Wyjaśnienie

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>