Описание

Раньше было довольно много других проблем, связанных с этими цифрами, и я надеюсь, что этого нет среди них.

П е треугольное число равно сумме всех натуральных чисел вплоть до п , простые вещи. Есть страница википедии и запись в OEIS , для тех, кто хочет узнать больше.

Теперь Гаусс обнаружил, что каждое натуральное число может быть выражено как сумма трех треугольных чисел (включая их 0), и хорошо иметь одно число более одного раза, например 0 + 1 + 1 = 2.

Вызов

Ваша задача - написать программу или функцию, учитывая натуральное число (включая 0), и печатать три треугольных числа, которые суммируют до аргумента. Вы можете распечатать числа, разделенные пробелами, в виде массива или другим способом, который вам нравится. Однако запрещено использовать любые встроенные функции для непосредственного получения массива, диапазона или любой другой формы коллекции, содержащей список треугольных чисел (например, один атом, который возвращает диапазон).

Контрольные примеры

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

Примечание. Если существует более одной возможной комбинации, вы можете напечатать любую или все, но вы должны напечатать любую комбинацию только один раз, исключив все комбинации, которые являются результатом перестановки других комбинаций. Я был бы очень признателен за ссылку и объяснение, я очень люблю видеть, как вы решаете проблему;)

Это код-гольф , поэтому применяются стандартные лазейки. Пусть победит самый короткий ответ в байтах!

05AB1E , 10 байтов

Код:

ÝηO3ãʒOQ}¬

Объяснение:

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

Использует кодировку 05AB1E . Попробуйте онлайн!

Python 2 , 99 байт

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)

Попробуйте онлайн!

Я очень удивлен, что это короче itertoolsили тройное понимание списка! Он (в конце концов) выплевывает случайный ответ каждый раз, когда вы запускаете его.

Два 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 выглядит 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]

Желе , 12 байт

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

Попробуйте онлайн!

Как это устроено

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

Брахилог , 13 байт

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

Попробуйте онлайн!

Как это устроено

⟦⟦ᵐ+ᵐ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 байт

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

Это выводит первый результат в лексикографическом порядке.

Попробуйте это в MATL Online!

объяснение

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 байт

Спасибо за то, что позволили вывести все решения, это было отвлекательно! Я был так счастлив, что мне не нужно было извлекать одно решение и иметь возможность просто дать им все, что я не заметил, сколько стоит отказ от перестановочных решений. Замечание @ Линн объяснило мне это и позволило мне сэкономить 7 байтов.

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

Это связывает более чем достаточно треугольных чисел lи проверяет все комбинации.

Retina , 63 59 байт

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

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. (1(?(1)\1))*является обобщенным сопоставителем треугольных чисел, но для первого треугольного числа мы можем сохранить несколько байтов, используя ^для начального совпадения.

PHP , 351 байт

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

Попробуйте онлайн!

Python 3 , 119 байт

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*

Попробуйте онлайн!

Спасибо @WheatWizard за сохранение 12 байтов!

C / C ++ - 197 байт

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

Удар за ударом:

#include<stdio.h>

Необходим для печати. Может быть исключено для определенных версий C

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

Этот парень делает тяжелую работу. Три вложенных цикла for выполняют итерацию a, b, c от 0 до n, обратите внимание, что каждая из b и c выполняет итерацию от предыдущего значения до n. Строго не нужно обрезать итерацию подобным образом, поскольку returnприход через минуту решает проблему «дублирования».

На внутреннем уровне, если сумма трех треугольников нумерует ==желаемое значение, выведите треугольники и вернитесь.

Вы можете юридически удалить returnключевое слово и преобразовать возвращаемый тип c в void, чтобы сохранить еще несколько байтов и распечатать все возможные решения. Именно по этой причине , что итерации ограничены, если все петли выбежали из 0к nней может вызвать дубликаты.

Mathematica, 63 байта

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

CJam , 26 байт

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

Порт моего MATL ответа. Это анонимный блок, который ожидает входные данные в стеке и заменяет их выходным массивом.

Попробуйте онлайн!

R , 66 байт

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

Алгоритм грубой силы; читает nиз стандартного ввода и возвращает фрейм данных, где каждая строка представляет собой комбинацию из трех треугольных чисел, которые складываются в n. При необходимости я могу вернуть только первую строку для +4 байта.

Попробуйте онлайн!

Java 8, 164 байта

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

Объяснение:

Попробуй это здесь.

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 байт

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

объяснение

x представляет вход

while(a<=x)r.push(a=i++*i/2) Создает массив всех треугольных чисел до х

forЦикл печатает самое высокое треугольное число меньше x, затем вычитает это число от x, в течение трех итераций. (в основном жадный алгоритм)

Pyth, 19 байт

Я так потренировался с Пифом, это неправда: /

hfqQsT.C*3+0msSdSQ3

Попробуйте это здесь .

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 байт

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

Попробуйте онлайн!

Рубин 61 57 55 байт

Вдохновленный ответом Линн на Python . Он генерирует случайные тройки, пока не будет достигнута желаемая сумма:

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

Требуется Ruby 2.4. В Ruby 2.3 и старше это синтаксическая ошибка, и Range#sumона не определена. Эта более длинная версия (64 байта) необходима для Ruby 2.3:

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

Вот небольшой тест:

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]

Попробуйте онлайн с Ruby 2.3!

Javascript (ES6), 108 байт - исправлено

Принимает целое число в качестве входных данных, выводит массив, [a, b, c]содержащий отсортированный список номеров треугольников a + b + c = x, где aнаибольшее число треугольников меньше или равно входному значению, а bнаибольшее число треугольников меньше или равно входному минусу 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}

объяснение

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>