Beschreibung

Es gab schon einige andere Herausforderungen in Bezug auf diese Zahlen, und ich hoffe, dass diese nicht darunter ist.

Die n- te Dreieckszahl entspricht der Summe aller natürlichen Zahlen bis zu n einfachen Sachen. Für diejenigen, die sich weiter informieren möchten, gibt es eine Wikipedia-Seite und einen Eintrag bei OEIS .

Nun fand Gauß heraus, dass jede natürliche Zahl als Summe von drei Dreieckszahlen (einschließlich 0) ausgedrückt werden kann , und es ist in Ordnung, eine Zahl mehr als einmal zu haben, z 0 + 1 + 1 = 2.

Herausforderung

Ihre Aufgabe ist es, ein Programm oder eine Funktion mit einer natürlichen Zahl (einschließlich 0) zu schreiben, die drei Dreieckszahlen ausgibt, die das Argument ergeben. Sie können die durch Leerzeichen getrennten Zahlen als Array oder nach einer anderen Methode ausdrucken. Es ist jedoch verboten , eingebaute Funktionen zu verwenden, um direkt ein Array, einen Bereich oder eine andere Form der Sammlung abzurufen, die eine Liste dreieckiger Zahlen enthält (zum Beispiel ein einzelnes Atom, das den Bereich ergibt).

Testfälle

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

Hinweis: Wenn es mehr als eine mögliche Kombination gibt, können Sie eine oder alle drucken, aber Sie müssen jede Kombination nur einmal drucken, um alle Kombinationen zu entfernen, die das Ergebnis einer Neuanordnung anderer Kombinationen sind. Ich würde mich sehr über einen Try-It-Link und eine Erklärung freuen. Ich freue mich sehr zu sehen, wie Sie das Problem lösen.

Dies ist Code-Golf , daher gelten Standard-Regelungslücken. Möge die kürzeste Antwort in Bytes gewinnen!

05AB1E , 10 Bytes

Code:

ÝηO3ãʒOQ}¬

Erläuterung:

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

Verwendet die 05AB1E- Codierung. Probieren Sie es 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)

Probieren Sie es online!

Ich bin ziemlich erstaunt, dass dies kürzer ist als itertoolsoder ein dreifaches Listenverständnis! Es spuckt (irgendwann) jedes Mal eine zufällige Antwort aus, wenn Sie es ausführen.

Zwei 102er:

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 sieht aus wie 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]

Gelee , 12 Bytes

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

Probieren Sie es online!

Wie es funktioniert

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 Bytes

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

Probieren Sie es online!

Wie es funktioniert

⟦⟦ᵐ+ᵐ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)

Dies gibt das erste Ergebnis in lexikografischer Reihenfolge aus.

Probieren Sie es bei MATL Online!

Erläuterung

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

Vielen Dank, dass Sie alle Lösungen ausgeben konnten, das war eine faszinierende Ablenkung! Ich war so froh, nicht eine Lösung extrahieren zu müssen und in der Lage zu sein, ihnen alles zu geben, dass ich die Kosten, die durch die Vermeidung von permutierten Lösungen entstehen, nicht bemerkte. @Lynns Bemerkung erklärte mir das und ließ mich 7 Bytes sparen.

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

Dies bindet mehr als genug Dreieckszahlen an lund überprüft alle Kombinationen.

Retina , 63 59 Bytes

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

Probieren Sie es online! Link enthält Testfälle. (1(?(1)\1))*ist ein verallgemeinerter Dreieckszahlenvergleicher, aber für die erste Dreieckszahl können wir ein paar Bytes einsparen, indem wir ^für die anfängliche Übereinstimmung verwenden.

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

Probieren Sie es 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*

Probieren Sie es online!

Vielen Dank an @WheatWizard für das Speichern von 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));}

Schlag für Schlag:

#include<stdio.h>

Benötigt für printf. Könnte für bestimmte Versionen von C entfallen

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

Platzsparend für Schleife.

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

Rekursiver Dreiecksauswerter.

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

Dieser Typ macht das schwere Heben. Drei verschachtelte for-Schleifen iterieren a, b, c von 0 bis n. Beachten Sie, dass b und c jeweils vom vorherigen Wert bis zu n iterieren. Es ist nicht unbedingt erforderlich, die Iteration auf diese Weise zu trimmen, da das returnProblem des "Duplizierens" durch das Kommen in einer Minute behoben wird.

Wenn die Summe der drei Dreiecke auf der inneren Ebene ==den gewünschten Wert ergibt, drucken Sie die Dreiecke aus und kehren Sie zurück.

Sie können das returnSchlüsselwort legal entfernen und den Rückgabetyp von c in void konvertieren, um ein paar weitere Bytes zu sparen und alle möglichen Lösungen zu drucken. Aus diesem Grund sind die Iterationen begrenzt, wenn alle von ihr ausgeführten Schleifen 0zu nDuplikaten führen würden.

Mathematica, 63 Bytes

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

CJam , 26 Bytes

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

Port meiner MATL-Antwort. Dies ist ein anonymer Block, der die Eingabe auf dem Stapel erwartet und durch das Ausgabearray ersetzt.

Probieren Sie es online!

R , 66 Bytes

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

Brute-Force-Algorithmus; liestn aus stdin und gibt einen Datenrahmen zurück, in dem jede Zeile eine Kombination von 3 Dreieckszahlen ist, die sich summieren n. Bei Bedarf kann ich nur die erste Zeile für +4 Bytes zurückgeben.

Probieren Sie es 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;}

Erläuterung:

Probieren Sie es hier aus.

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

Erläuterung

x repräsentiert die Eingabe

while(a<=x)r.push(a=i++*i/2) Erstellt ein Array aller Dreieckszahlen bis zu x

Die forSchleife druckt die höchste dreieckige Zahl kleiner als xund subtrahiert diese Zahl dann xfür drei Iterationen. (im Grunde ein gieriger Algorithmus)

Pyth, 19 Bytes

Ich bin so aus der Übung mit Pyth, es ist falsch: /

hfqQsT.C*3+0msSdSQ3

Probieren Sie es hier aus .

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.,]

Probieren Sie es online!

Rubin 61 57 55 Bytes

Inspiriert von Lynns Python- Antwort . Es werden zufällige Triplets erzeugt, bis die gewünschte Summe erreicht ist:

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

Es benötigt Ruby 2.4. In Ruby 2.3 und älteren Versionen handelt es sich um einen Syntaxfehler, der Range#sumnicht definiert ist. Diese längere Version (64 Bytes) wird für Ruby 2.3 benötigt:

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

Hier ist ein kleiner 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]

Probieren Sie es online mit Ruby 2.3!

Javascript (ES6), 108 Bytes - behoben

Nimmt eine Ganzzahl als Eingabe, gibt ein Array [a, b, c]mit einer sortierten Liste von Dreiecksnummern aus a + b + c = x, wobei adie größte Dreiecksnummer kleiner oder gleich der Eingabe ist und bdie größte Dreiecksnummer kleiner oder gleich dem Eingabe-Minus ist 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}

Erläuterung

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>