Deskripsi

Ada beberapa tantangan lain mengenai angka-angka ini sebelumnya, dan saya harap yang ini tidak ada di antara mereka.

The n th angka segitiga sama dengan jumlah semua bilangan sampai n , hal-hal sederhana. Ada halaman wikipedia dan entri di OEIS , bagi mereka yang ingin menginformasikan diri mereka lebih lanjut.

Sekarang, Gauss menemukan bahwa setiap bilangan alami dapat dinyatakan sebagai jumlah dari tiga bilangan segitiga (ini termasuk 0), dan boleh saja memiliki satu bilangan lebih dari satu, misalnya 0 + 1 + 1 = 2.

Tantangan

Tugas Anda adalah menulis program atau fungsi, diberi nomor alami (termasuk 0), mencetak tiga angka segitiga yang meringkas argumen. Anda dapat mencetak angka-angka yang dipisahkan oleh spasi, sebagai array, atau dengan metode lain yang Anda suka. Namun, dilarang untuk menggunakan fungsi bawaan apa pun untuk secara langsung mendapatkan array, rentang atau bentuk koleksi lain yang berisi daftar angka segitiga (misalnya atom tunggal yang menghasilkan rentang).

Uji kasus

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

Catatan: Jika ada lebih dari satu kombinasi yang mungkin, Anda dapat mencetak salah satu atau semua, tetapi Anda harus mencetak kombinasi apa saja satu kali, menghilangkan semua kombinasi yang merupakan hasil pengaturan ulang kombinasi lainnya. Saya sangat menghargai tautan coba-coba dan penjelasannya, saya sangat senang melihat bagaimana Anda memecahkan masalah;)

Ini kode-golf , jadi celah standar berlaku. Semoga jawaban tersingkat dalam byte menang!

05AB1E , 10 byte

Kode:

ÝηO3ãʒOQ}¬

Penjelasan:

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

Menggunakan penyandian 05AB1E . Cobalah online!

Python 2 , 99 byte

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)

Cobalah online!

Saya cukup kagum ini lebih pendek dari itertoolsatau pemahaman daftar tiga! Itu (akhirnya) mengeluarkan jawaban acak setiap kali Anda menjalankannya.

Dua 102-an:

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 terlihat seperti 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]

Jelly , 12 byte

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

Cobalah online!

Bagaimana itu bekerja

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 byte

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

Cobalah online!

Bagaimana itu bekerja

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

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

Ini menghasilkan hasil pertama dalam urutan leksikografis.

Cobalah di MATL Online!

Penjelasan

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 byte

Terima kasih telah mengizinkan untuk mengeluarkan semua solusi, itu adalah pengalih perhatian yang menarik! Saya sangat senang tidak perlu mengekstraksi satu solusi dan hanya bisa memberikan semuanya sehingga saya tidak melihat biaya yang timbul dari menghindari solusi yang diijinkan. @ Lynn berkomentar bahwa untuk saya dan biarkan saya menghemat 7 byte.

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

Ini mengikat lebih dari cukup angka segitiga ke ldan memeriksa semua kombinasi.

Retina , 63 59 byte

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

Cobalah online! Tautan termasuk kasus uji. (1(?(1)\1))*adalah pencocokan angka segitiga umum, tetapi untuk angka segitiga pertama kita dapat menyimpan beberapa byte dengan menggunakan ^untuk pencocokan awal.

PHP , 351 byte

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

Cobalah online!

Python 3 , 119 byte

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*

Cobalah online!

Terima kasih kepada @WheatWizard karena telah menghemat 12 byte!

C / C ++ - 197 byte

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

Tiupan demi tiupan:

#include<stdio.h>

Dibutuhkan untuk printf. Dapat dieleksi untuk versi C tertentu

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

Hemat ruang untuk loop.

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

Evaluator segitiga rekursif.

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

Orang ini melakukan angkat berat. Tiga bersarang untuk loop iterasi a, b, c dari 0 hingga n, perhatikan bahwa b dan c setiap iterate dari nilai sebelumnya hingga n. Ini tidak sepenuhnya diperlukan untuk memotong iterasi seperti itu karena returnkedatangan dalam satu menit menyelesaikan masalah "duplikat".

Pada level bagian dalam, jika penjumlahan dari tiga angka segitiga ==nilai yang diinginkan, cetak segitiga dan kembali.

Anda dapat secara legal menghapus returnkata kunci dan mengonversi tipe kembalinya c menjadi void untuk menyimpan beberapa byte lagi dan mencetak semua solusi yang mungkin. Hal ini untuk alasan ini bahwa iterasi terbatas, jika semua loop berlari dari 0ke nitu akan menyebabkan duplikat.

Mathematica, 63 byte

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

CJam , 26 byte

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

Port jawaban MATL saya. Ini adalah blok anonim yang mengharapkan input pada stack dan menggantinya dengan array output.

Cobalah online!

R , 66 byte

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

Algoritma brute force; membaca ndari stdin dan mengembalikan bingkai data di mana setiap baris adalah kombinasi dari 3 angka segitiga yang dijumlahkan n. Jika perlu, saya hanya bisa mengembalikan baris pertama untuk +4 byte.

Cobalah online!

Java 8, 164 byte

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

Penjelasan:

Coba di sini.

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 byte

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

Penjelasan

x mewakili input

while(a<=x)r.push(a=i++*i/2) Membuat larik semua angka segitiga hingga x

The forLoop mencetak jumlah segitiga tertinggi kurang dari x, kemudian mengurangi nomor dari x, selama tiga iterasi. (pada dasarnya algoritma serakah)

Pyth, 19 byte

Saya sangat tidak berlatih dengan Pyth, itu tidak benar: /

hfqQsT.C*3+0msSdSQ3

Cobalah di sini .

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 byte

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

Cobalah online!

Ruby 61 57 55 byte

Terinspirasi oleh jawaban Python Lynn . Ini menghasilkan kembar tiga acak sampai jumlah yang diinginkan tercapai:

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

Itu membutuhkan Ruby 2.4. Di Ruby 2.3 dan yang lebih lama, ini merupakan kesalahan sintaksis, dan Range#sumtidak ditentukan. Versi yang lebih panjang ini (64 bytes) diperlukan untuk Ruby 2.3:

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

Inilah tes kecil:

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]

Cobalah online dengan Ruby 2.3!

Javascript (ES6), 108 byte - diperbaiki

Mengambil bilangan bulat sebagai input, mengeluarkan array yang [a, b, c]berisi daftar nomor segitiga yang diurutkan a + b + c = x, di mana ajumlah segitiga terbesar kurang dari atau sama dengan input, dan bmerupakan jumlah segitiga terbesar kurang dari atau sama dengan minus input 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}

Penjelasan

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>