Meine Aufgabe ist es, Kieselsteine ​​in dreieckige Stapel zu stapeln. Ich mache das erst seit einem Jahrhundert und es ist schon ziemlich langweilig. Das Schlimmste ist, dass ich jeden Stapel beschrifte. Ich weiß, wie man Kieselsteine ​​in Stapel maximaler Größe zerlegt , aber ich möchte die Anzahl der Stapel minimieren. Kannst du helfen?

Aufgabe

Zerlegen Sie eine gegebene Ganzzahl in die minimale Anzahl dreieckiger Zahlen und geben Sie diese minimale Anzahl aus.

Dreieckszahlen

Eine dreieckige Zahl ist eine Zahl, die nfür einen bestimmten Wert als Summe der ersten natürlichen Zahlen ausgedrückt werden kann n. Somit sind die ersten paar Dreieckszahlen

1 3 6 10 15 21 28 36 45 55 66 78 91 105

Beispiel

Nehmen wir als Beispiel an, die Eingabe ist 9. Es ist keine Dreieckszahl, daher kann es nicht als Summe der 1Dreieckszahlen ausgedrückt werden . Somit ist die minimale Anzahl von Dreieckszahlen 2, die mit erhalten werden kann [6,3], was die korrekte Ausgabe von ergibt 2.

Nehmen wir als weiteres Beispiel an, die Eingabe ist 12. Die naheliegendste Lösung besteht darin, einen gierigen Algorithmus zu verwenden und jeweils die größte Dreieckszahl zu entfernen, wobei sich [10,1,1]eine Ausgabe von ergibt 3. Es gibt jedoch eine bessere Lösung: [6,6]die korrekte Ausgabe von 2.

Testfälle

in out
1 1
2 2
3 1
4 2
5 3
6 1
7 2
8 3
9 2
10 1
11 2
12 2
13 2
14 3
15 1
16 2
17 3
18 2
19 3
20 2
100 2
101 2
5050 1

Regeln

• Die Eingabe-Ganzzahl liegt zwischen 1 und der maximalen Ganzzahl Ihrer Sprache.
• Ich kann mit meinen Kieselsteinen jede Sprache emulieren , und ich möchte, dass Ihr Code so klein wie möglich ist, da ich nur Kieselsteine ​​habe, um den Überblick zu behalten. Das ist also Code-Golf , also gewinnt der kürzeste Code in jeder Sprache .

Netzhaut , 57 49 Bytes

.+
$*
(^1|1\1)+$
1
(^1|1\1)+(1(?(2)\2))+$
2
11+
3

Probieren Sie es online aus! Basierend auf meiner Antwort auf drei Dreieckszahlen . Ändern Sie die dritte Zeile in ^(^1|1\1)*$, um die Null-Eingabe zu unterstützen. Bearbeiten: Dank @MartinEnder wurden 8 Bytes gespeichert (sollten aber wahrscheinlich mehr sein).

Mathematica, 53 Bytes

Min[Plus@@@Table[$($+1)/2,{$,#+1}]~FrobeniusSolve~#]&

Dieser Code ist sehr langsam. Wenn Sie diese Funktion testen möchten, verwenden Sie stattdessen die folgende Version:

Min[Plus@@@Table[$($+1)/2,{$,√#+1}]~FrobeniusSolve~#]&

Probieren Sie es auf Wolfram Sandbox

Erläuterung

Min[Plus@@@Table[$($+1)/2,{$,#+1}]~FrobeniusSolve~#]&  (* input: n *)

           Table[$($+1)/2,{$,#+1}]                     (* Generate the first n triangle numbers *)
                                  ~FrobeniusSolve~#    (* Generate a Frobenius equation from the *)
                                                       (* triangle numbers and find all solutions. *)
    Plus@@@                                            (* Sum each solution set *)
Min                                                    (* Fetch the smallest value *)

Gelee ( Gabel ), 9 Bytes

æFR+\$S€Ṃ

Dies beruht auf einer Gabelung, bei der ich ein ineffizientes Frobenius-Lösungsatom implementiert habe. Ich kann nicht glauben, dass es schon ein Jahr her ist, seit ich es das letzte Mal berührt habe.

Erläuterung

æFR+\$S€Ṃ  Input: n
æF         Frobenius solve with
     $     Monadic chain
  R          Range, [1, n]
   +\        Cumulative sum, forms the first n triangle numbers
      S€   Sum each
        Ṃ  Minimum

R , 69 58 Bytes

function(n)3-n%in%(l=cumsum(1:n))-n%in%outer(c(0,l),l,"+")

Probieren Sie es online aus!

Erläuterung:

function(n){
 T <- cumsum(1:n)             # first n triangular numbers  [1,3,6]
 S <- outer(c(0,T),T,"+")     # sums of the first n triangular numbers,
                              # AND the first n triangular numbers [1,3,6,2,4,7,4,6,9,7,9,12]
 3 - (n %in% S) - (n %in% T)  # if n is in T, it's also in S, so it's 3-2: return 1
                              # if n is in S but not T, it's 3-1: return 2
                              # if n isn't in S, it's not in T, so 3-0: return 3
}

Gelee , 15 Bytes

0rSƤṗ⁸S⁼¥Ðf⁸ḢTL

Probieren Sie es online aus!

JavaScript (ES6), 75 63 61 Byte

f=(n,x=y=0)=>y<n+2?x*x+y*y-8*n-2+!y?f(n,x<n+2?x+1:++y):2-!y:3

Wie?

Wir verwenden die folgenden Eigenschaften:

• Nach dem Satz der polygonalen Zahlen von Fermat kann jede positive ganze Zahl als die Summe von höchstens drei Dreieckszahlen ausgedrückt werden.
• Eine Zahl t ist genau dann dreieckig, wenn 8t + 1 ein perfektes Quadrat ist (dies kann leicht durch Lösen von t = n (n + 1) / 2 bewiesen werden ).

Bei einer positiven ganzen Zahl n reicht es zu testen, ob wir Folgendes finden können:

• x> 0, so dass 8n + 1 = x² ( n selbst ist dreieckig)
• oder x> 0 und y> 0, so dass 8n + 2 = x² + y² ( n ist die Summe von 2 Dreieckszahlen)

Wenn beide Tests fehlschlagen, muss n die Summe von 3 Dreieckszahlen sein.

f = (n, x = y = 0) =>                 // given n and starting with x = y = 0
  y < n + 2 ?                         // if y is less than the maximum value:
    x * x + y * y - 8 * n - 2 + !y ?  //   if x² + y² does not equal 8n + 2 - !y:
      f(                              //     do a recursive call with:
        n,                            //       - the original input n
        x < n + 2 ? x + 1 : ++y       //       - either x incremented or
      )                               //         y incremented and x set to y
    :                                 //   else:
      2 - !y                          //     return either 1 or 2
  :                                   // else:
    3                                 //   return 3

Testfälle

f=(n,x=y=0)=>y<n+2?x*x+y*y-8*n-2+!y?f(n,x<n+2?x+1:++y):2-!y:3

;[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 100, 101, 5050 ]
.forEach(n => console.log(n + ' --> ' + f(n)))

MATL , 15 Bytes

`G:Ys@Z^!XsG-}@

Probieren Sie es online aus!

Erläuterung

`         % Do...while
  G:      %   Push range [1 2 3 ... n], where n is the input
  Ys      %   Cumulative sum: gives [1 3 6 ... n*(n+1)/2]
  @Z^     %   Cartesian power with exponent k, where k is iteration index
          %   This gives a k-column matrix where each row is a Cartesian tuple
  !Xs     %   Sum of each row. Gives a column vector
  G-      %   Subtract input from each entry of that vector. This is the loop 
          %   condition. It is truthy if it only contains non-zeros
}         % Finally (execute before exiting the loop)  
  @       %   Push iteration index, k. This is the output
          % End (implicit). Proceeds with next iteration if the top of the
          % stack is truthy

Kotlin , 176 154 Bytes

Einreichung

{var l=it
var n=0
while(l>0){n++
val r=mutableListOf(1)
var t=3
var i=3
while(t<=l){r.add(t)
t+=i
i++}
l-=r.lastOrNull{l==it|| r.contains(l-it)}?:r[0]}
n}

Verschönert

{
    // Make a mutable copy of the input
    var l=it
    // Keep track of the number of items removed
    var n=0
    // While we still need to remove pebbles
    while (l > 0) {
        // Increase removed count
        n++
        // BEGIN: Create a list of triangle numbers
        val r= mutableListOf(1)
        var t = 3
        var i = 3
        while (t<= l) {
            // Add the number to the list and calculate the next one
            r.add(t)
            t+=i
            i++
        }
        // END: Create a list of triangle numbers
        // Get the fitting pebble, or the biggest one if none fit or make a perfect gap
        l -= r.lastOrNull {l==it|| r.contains(l-it)} ?: r[0]
    }
    //Return the number of pebbles
    n
}

Prüfung

var r:(Int)->Int =
{var l=it
var n=0
while(l>0){n++
val r=mutableListOf(1)
var t=3
var i=3
while(t<=l){r.add(t)
t+=i
i++}
l-=r.lastOrNull{l==it|| r.contains(l-it)}?:r[0]}
n}

data class TestData(val input:Int, val output:Int)

fun main(args: Array<String>) {
    val tests = listOf(
            TestData(1,1),
            TestData(2,2),
            TestData(3,1),
            TestData(4,2),
            TestData(5,3),
            TestData(6,1),
            TestData(7,2),
            TestData(8,3),
            TestData(9,2),
            TestData(10,1),
            TestData(11,2),
            TestData(12,2),
            TestData(13,2),
            TestData(14,3),
            TestData(15,1),
            TestData(16,2),
            TestData(17,3),
            TestData(18,2),
            TestData(19,3),
            TestData(20,2),
            TestData(100,2),
            TestData(101,2),
            TestData(5050,1)
    )
    tests.map { it to r(it.input) }.filter { it.first.output != it.second }.forEach { println("Failed for ${it.first}, output ${it.second} instead") }
}

TryItOnline