Bei einer positiven Ganzzahl N müssen Sie die Anzahl der Schritte zurückgeben, die der folgende Algorithmus benötigt, um N zu erreichen :

1. Finden Sie die kleinste Dreieckszahl T _i, so dass T _i  ≥ N ist . Erstellen Sie die entsprechende Liste L = [1, 2, ..., i] .

2. Entfernen Sie den ersten Begriff aus der Liste, während die Summe der Begriffe von L größer als N ist.

3. Wenn die Summe der Terme von L jetzt kleiner als N ist , erhöhe i und hänge sie an die Liste an. Fahren Sie mit Schritt 2 fort.

Wir halten an, sobald N erreicht ist. Nur der erste Schritt wird systematisch ausgeführt. Die Schritte 2 und 3 werden möglicherweise überhaupt nicht verarbeitet.

Beispiele

Unten ist ein Beispiel für N = 11 :

Die erwartete Ausgabe für N = 11 ist also 4 .

Andere Beispiele:

• N = 5 - Wir beginnen mit T ₃ = 1 + 2 + 3 = 6 , gefolgt von 2 + 3 = 5 . Erwartete Leistung: 2 .
• N = 10 - Nur der erste Schritt ist erforderlich, da 10 eine Dreieckszahl ist: T ₄ = 1 + 2 + 3 + 4 = 10 . Erwartete Leistung: 1 .

Erste 100 Werte

Unten sind die Ergebnisse für 1 ≤ N ≤ 100 :

  1,  2,  1,  4,  2,  1,  2, 10,  2,  1,  4,  2,  6,  2,  1, 22,  8,  2, 10,  2,
  1,  2, 12,  6,  2,  4,  2,  1, 16,  2, 18, 50,  2,  6,  2,  1, 22,  6,  2,  4,
 26,  2, 28,  2,  1,  8, 30, 16,  2,  6,  4,  2, 36,  2,  1,  2,  4, 12, 40,  2,
 42, 14,  2,108,  2,  1, 46,  2,  6,  4, 50,  2, 52, 18,  2,  4,  2,  1, 56, 12,
  2, 20, 60,  4,  2, 22, 10,  2, 66,  2,  1,  4, 10, 24,  2, 40, 72,  8,  2,  6

Regeln

• Sie können entweder ein vollständiges Programm oder eine Funktion schreiben, die das Ergebnis entweder ausgibt oder zurückgibt.
• Sie sind erforderlich , alle verarbeiten N ≤ 65536 auf Mid-Range - Hardware in weniger als eine Minute.
• Mit genügend Zeit, Ihr Programm / Funktion sollte theoretisch für jeden Wert von Arbeit N , die nativ von Ihrer Sprache unterstützt wird. Wenn nicht, erläutern Sie bitte in Ihrer Antwort, warum.
• Das ist Codegolf, also gewinnt die kürzeste Antwort in Bytes!

Jelly , 29 31 Bytes

ÆDµ’H+Ṛ%1$ÐḟṂ
>TḢ_@Ç}‘Ḥ
R+\ðċȯç

Eine monadische Verbindung, die das Ergebnis zurückgibt (N = 65536 dauert weniger als zwei Sekunden).

Probieren Sie es online!

Wie?

Für eine gründliche Erklärung des Algorithmus siehe den fantastischen Beitrag von Martin Ender .

ÆDµ’H+Ṛ%1$ÐḟṂ - Link 1, smallest natural number, M, that satisfies the below*, N
              - * N = T(M) - T(i) for some non-negative integer i <= M
ÆD            - divisors of N
  µ           - monadic chain separation, call that d
   ’          - increment d (vectorises)
    H         - halve (vectorises
      Ṛ       - reverse d
     +        - add (vectorises)
          Ðḟ  - filter discard if:
       %1$    -   modulo one is truthy (those which are the result of even divisors)
            Ṃ - minimum

>TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N
>         - T(i) > N
 T        - truthy indexes
  Ḣ       - head (yields the first i for which T(i) > N)
     Ç}   - call last link (1) as a monad converted to a dyad using the right argument
   _@     - subtract with reverse @rguments
       ‘  - increment
        Ḥ - double 

R+\ðċȯç - Main link: N
R       - range -> [1,2,...,N]
 +\     - reduce with addition -> [1,3,6,10,...T(N)]
   ð    - dyadic chain separation, call that t
    ċ   - count occurrences of N in t (1 if N is triangular else 0)
      ç - call last link (2) as a dyad(t, N)
     ȯ  - or

Die 29-Byte-Vollprogrammimplementierung, die ich mit dem beschriebenen Algorithmus erstellt habe, dauert 4 Minuten 30 für N = 65536 auf meinem Laptop, daher denke ich, dass sie nicht zählt.

Ṁ‘ṭµS<³µ¿
ḊµS>³µ¿
0®Ḃ‘©¤ĿÐĿL’

Die Verwendung einer while-Schleife für jeden Schritt 3 und deren Wiederverwendung als Schritt 1 entspricht der Länge, die ich mit der Initialisierung der Liste erreichen kann, da keine Überprüfung in Schritt 3 bedeutet, eine Liste zu erstellen, bis nichts mehr übrig ist, und dann den ersten Index des Werts zu finden:

ḊµS>³µ¿
Ṁ‘ṭ
Ḥ½_.ĊR®Ḃ‘©¤ĿÐĿS€i

Mathematica, 79 Bytes

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&

Erläuterung

Ich konnte nicht die Mühe machen, den Algorithmus in der Herausforderung zu implementieren, deshalb wollte ich nach einer Verknüpfung zur Lösung suchen. Obwohl ich eine gefunden habe, übertrifft sie leider nicht die Mathematica-Antwort, die den Algorithmus implementiert. Trotzdem bin ich mir sicher, dass dies noch nicht optimal ist, und es könnte andere Sprachen geben, die von diesem Ansatz oder einigen der dabei gewonnenen Erkenntnisse profitieren können.

Also behaupte ich, dass die Sequenz, die wir berechnen sollen, ist:

f (n) = 2 * ( A212652 (n) - A002024 (n)) + 1 + A023532 (n-1)

Alternativ ist f (n) = 1, wenn n eine Dreieckszahl ist, und f (n) = 2 * ( A212652 (n) - A002024 (n) + 1), andernfalls.

Im ersten Ausdruck codiert A023532 einfach diese beiden unterschiedlichen Fälle. Die beiden anderen Folgen (plus 1) sind die Differenz zwischen der größten ganzen Zahl k bei der längsten Zerlegung von n in aufeinanderfolgende ganze Zahlen (k-i + 1) + (k-i + 2) + ... + k = n und die größte ganze Zahl j, so dass 1 + 2 + ... + j <n ist .

In etwas einfacheren Worten finden wir hier die Antwort für nicht dreieckige Zahlen: Erstens finden wir die größte dreieckige Zahl T _j, die kleiner als n ist . Dann ist j die vorletzte Ganzzahl, die in Schritt 1 hinzugefügt wird (da wir nach der Addition von j + 1 n überschritten haben ). Zerlegen Sie dann n in so viele (oder so kleine) aufeinanderfolgende ganze Zahlen wie möglich und nennen Sie das Maximum unter diesen Zahlen k . Das Ergebnis ist einfach 2 * (kj) . Der intuitive Grund dafür ist, dass das Maximum in der Zerlegung mit jedem zweiten Schritt um 1 wächst und wir aufhören, wenn wir erreichenk .

Wir müssen vier Dinge zeigen, um zu beweisen, dass dies funktioniert:

1. f (n) = 1 für Dreieckszahlen. Dies ist trivial, weil der erste Schritt einfach alle Dreieckszahlen durchläuft. Wenn wir während dieses Vorgangs genau n drücken, sind wir fertig und es war nur ein Schritt zu berechnen.
2. Bei allen anderen Nummern enden wir immer nach einem Löschschritt, niemals nach einem Einfügeschritt. Das heißt, alle anderen f (n) sind gerade.
3. In jedem Einfügeschritt nach dem ersten fügen wir nur eine einzelne Zahl hinzu. Dies garantiert, dass wir eine Zerlegung einschließlich k nach kj Stufenpaaren erreichen .
4. Die endgültige Zerlegung von n , die wir erhalten, ist immer die längste mögliche Zerlegung von n in aufeinanderfolgende ganze Zahlen, oder mit anderen Worten, es ist immer die Zerlegung von n mit dem niedrigsten Maximum unter den summierten Zahlen. Mit anderen Worten, die letzte Zahl, die wir zur Summe hinzufügen, ist immer A212652 (n) .

Wir haben bereits gezeigt, warum (1) wahr ist. Als nächstes beweisen wir, dass wir nicht mit einem Einfügungsschritt enden können, außer dem ersten (was bei nicht dreieckigen Zahlen nicht der Fall ist).

Angenommen, wir haben mit einem Einfügungsschritt geendet und n erreicht, nachdem der Summe ein Wert p hinzugefügt wurde . Das bedeutet, dass der Wert vor diesem Einfügungsschritt np war ( oder weniger, wenn wir mehrere Werte gleichzeitig hinzugefügt haben). Diesem Einfügeschritt ging jedoch ein Löschschritt voraus (da wir in Schritt 1 n nicht gedrückt haben konnten ). Der letzte Wert q, den wir während dieses Löschschritts entfernt haben, war aufgrund der Funktionsweise des Algorithmus notwendigerweise kleiner als p . Aber das heißt, bevor wir q entfernt haben, hatten wir n-p + q ( oder weniger ), das ist weniger als n. Aber das ist ein Widerspruch, denn wir hätten aufhören müssen, Ganzzahlen zu entfernen, wenn wir n-p + q gedrückt hätten, anstatt ein anderes q zu entfernen . Dies beweist Punkt (2) oben. Jetzt wissen wir also, dass wir immer mit einem Löschschritt enden und dass daher alle nicht dreieckigen Zahlen gerade Ausgaben haben.

Als nächstes beweisen wir (3), dass jeder Einfügeschritt nur einen Wert einfügen kann. Dies ist im Wesentlichen eine Folgerung aus (2). Wir haben gezeigt, dass wir nach dem Addieren eines Wertes nicht genau n treffen können und da der Beweis eine Ungleichung verwendet, können wir auch nicht unter n enden (da dann n-p + q immer noch kleiner als n wäre und wir nicht hätten entfernen dürfen so viele Werte überhaupt). Wenn wir also einen einzelnen Wert hinzufügen, werden wir garantiert n überschreiten, da wir durch Entfernen eines kleineren Werts unter n gesunken sind. Daher wissen wir, dass das obere Ende der Summe mit jedem zweiten Schritt um 1 wächst . Wir kennen den Anfangswert dieses oberen Endes (es ist das kleinste m, so dassT _m > n ). Jetzt müssen wir nur noch dieses obere Ende herausfinden, sobald wir die Endsumme erreicht haben. Dann ist die Anzahl der Schritte einfach doppelt so groß wie die Differenz (plus 1).

Dazu beweisen wir (4), dass die Endsumme immer die Zerlegung von n in so viele ganze Zahlen wie möglich ist, oder die Zerlegung, bei der das Maximum in dieser Zerlegung minimal ist (dh es ist die frühestmögliche Zerlegung). Wir werden das im Widerspruch wieder tun (die Formulierung in diesem Teil könnte etwas strenger sein, aber ich habe bereits viel zu viel Zeit damit verbracht ...).

Angenommen, die frühestmögliche / längste mögliche Zerlegung von n ist etwas a + (a + 1) + ... (b-1) + b , a ≤ b , und der Algorithmus überspringt sie. Das bedeutet , dass zu dem Zeitpunkt, b hinzugefügt wird, ein längeres muss keinen Teil der Summe sein. Wenn a Teil der Summe s wäre , hätten wir in diesem Moment n ≤ s . Also entweder die Summe enthält nur die Werte von a bis b , die gleich n und wir stoppen (daher haben wir diese Zersetzung nicht überspringen), oder es ist zumindest ein Wert kleiner als ein in der Summe, gewinnen den Fall n <sund dieser Wert würde entfernt werden, bis wir die genaue Summe erreicht haben (die Zerlegung wurde wiederum nicht übersprungen). So würden wir davon haben , um loszuwerden , ein vor der Zugabe von b . Das heißt aber, wir müssten eine Situation erreichen, in der a die kleinste Komponente der Summe ist und die größte noch nicht b ist. Doch an diesem Punkt können wir nicht entfernen ein , weil die Summe weniger eindeutig als n (da b fehlt), so dass wir die erforderlichen Werte hinzufügen zuerst , bis wir hinzufügen b und drücken Sie n genau. Dies beweist (4).

Nehmen wir also diese Dinge zusammen: Wir wissen, dass das erste Paar von Schritten uns einen Maximalwert von A002024 (n) gibt . Wir wissen, dass der Maximalwert der endgültigen Zersetzung ist A212652 (n) ist . Und wir wissen, dass dieses Maximum in jedem Schrittpaar einmal erhöht wird. Daher ist der endgültige Ausdruck 2 * ( A212652 (n) - A002024 (n) + 1) . Diese Formel funktioniert fast für Dreieckszahlen, außer dass wir für diese nur 1 Schritt anstelle von 2 benötigen, weshalb wir das Ergebnis mit der Indikatorfunktion der Dreieckszahlen korrigieren (oder umgekehrt, je nachdem, was praktischer ist).

Zum Schluss noch was die Umsetzung betrifft. Für die erste Sequenz verwende ich die Formel MIN (ungerade d | n; n / d + (d-1) / 2) von OEIS. Es stellt sich heraus, dass ein paar Bytes gespart werden, wenn wir den Faktor 2 in diesen Ausdruck aufnehmen, um zu erhalten MIN (ungerades d | n; 2n / d + d-1) , weil dieses -1 dann mit dem +1 in meiner ersten Version aufhört von f (n), die die beiden Fälle für dreieckige und nicht dreieckige Zahlen direkt codiert. Im Code ist dies:

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]

Für die letztere Sequenz ( 1, 2, 2, 3, 3, 3, ...) können wir eine einfache geschlossene Form verwenden:

⌊(2#)^.5+.5⌋

Und schließlich ist die inverse Indikatorfunktion der Dreieckszahlen immer dann 0, wenn 8n + 1 ein perfektes Quadrat ist. Dies kann in Mathematica ausgedrückt werden als

⌈Sqrt[8#+1]~Mod~1⌉

Es gibt viele Möglichkeiten, diese beiden letzten Sequenzen auszudrücken und einen konstanten Versatz zwischen ihnen zu verschieben. Daher bin ich mir sicher, dass dies noch keine optimale Implementierung ist, aber ich hoffe, dass dies anderen einen Ausgangspunkt bietet, um neue Ansätze in zu untersuchen ihre eigenen Sprachen.

Da ich mich um all diese Mühe gekümmert habe, ist hier eine Handlung der Sequenz bis zu n = 1000 (ich könnte auch 100 k in ein paar Sekunden berechnen, aber es zeigt keine zusätzlichen Erkenntnisse):

Es mag interessant sein, die Variationen über diese sehr geraden Linien zu untersuchen, aber ich überlasse das jemand anderem ...

Mathematica, 72 Bytes

(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&

Reine Funktion, die ein ganzzahliges Argument verwendet.

Wie es funktioniert

For[ ... ]

Eine ForSchleife.

l=u=c=k=0

Initialisierung; setze l(untere), u(obere), c(Zähler) und k(Summe) auf 0.

k!=#

Bedingung; wiederholen, solange knicht gleich der Eingabe ist.

c++

Zuwachs; Inkrementiere den Zähler c.

If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]

Karosserie

If[#>k, ... ]

Wenn die Eingabe größer ist als k:

While[#>k,k+=++u]

Während die Eingabe größer als ist k, erhöhen uund erhöhen Sie kum u.

Wenn die Eingabe nicht größer ist als k:

While[#<k,k-=l++]

Während die Eingabe kleiner als ist k, wird kum lund inkrementiert l.

( ... ;c)

Rückkehr cnach der Schleife.

Python 2 , 104 Bytes

N=input();i=s=0;l=()
while N!=sum(l):exec'while sum(l)'+['<N:i+=1;l+=i,','>N:l=l[1:]'][s%2];s+=1
print s

Probieren Sie es online!

Wechselt zwischen dem Hinzufügen von Begriffen am Ende der Liste und dem Entfernen von Begriffen am Anfang.

Haskell , 70 63 68 64 Bytes

BEARBEITEN:

• -7 Bytes: Leerzeichen, zwei Zeichen und einige Klammern wurden entfernt, indem der Sinn von negiert wurde a. Off-by-One-Fehler in der Erklärung behoben.
• +5 Bytes: Argh, hat die 65536-Anforderung komplett verfehlt, und es stellt sich heraus, dass (1) Potenzen von 2 besonders teuer sind, weil sie nur getroffen werden, wenn Sie die Zahl selbst (2) erreichen, also lange Reichweiten summieren (das umbrechen) um Null) die ganze Zeit. Ersetzte die Summe durch eine mathematische Formel.
• -4 Bytes: Angepasst aund blinear, um Terme in der Summenformel zu stornieren.

1#1 ist eine anonyme Funktion, die eine Ganzzahl annimmt und zurückgibt.

Verwenden Sie als (1#1) 100.

1#1
(a#b)n|s<-a*a-b*b=sum$[a#(b+2)$n|s>8*n]++[(b#a)(-n)+1|s<8*n]

Probieren Sie es online!

Wie es funktioniert

• (a#b)nrepräsentiert den aktuellen Berechnungsschritt. a, bsind Zahlen in 1, 3, 5, .., währendn sie je nach Schritt entweder positiv oder negativ sein können.
  • In Schritt 1 oder 3 wird die Liste dargestellt [(a+1)/2,(a+3)/2..(b-1)/2] und die Zielnummer angezeigt -n.
  • In Schritt 2 werden die Liste [(b+1)/2,(b+3)/2..(a-1)/2]und die Zielnummer angezeigt n.
• Die seltsame Entsprechung zwischen a, bund den Listen besteht darin, mit dem kurzen Ausdruck summieren zu könnens=a*a-b*b .
  • In Schritt 1 und 3 ist dies dasselbe wie s= -8*sum[(a+1)/2..(b-1)/2] .
  • In Schritt 2 ist dies dasselbe wie s=8*sum[(b+1)/2..(a-1)/2].
• Die Verzweigung erfolgt, indem Listenverständnisse erstellt werden, die jeweils nur in einem Fall Elemente ergeben, und die Ergebnisse summiert werden.
  • Wenn ja s>8*n, dannb wird vor der Rekursion um 2 erhöht.
    • In Schritt 1 und 3 vergrößert dies die Liste, während dies in Schritt 2 die Liste verkleinert.
  • Wenn s<8*nja, ändert die Rekursion den Schritt durch Vertauschen von aund bund Negierenn Hinzufügen von 1 zum Ergebnis.
  • Wenn s==8*ndann keines der beiden Listenverständnisse ein Element ergibt, so ist die Summe 0.
• (1#1) nStellt einen Dummy "Stufe 2" vor dem Start dar, der sofort zu Schritt 1 geändert wird und aus dem die Liste erstellt wird [1..0]=[].

PHP> = 7.0, 74 Bytes

while($i=$r<=>$argn)for($s++;($r<=>$argn)==$i;)$r+=$i+1?-++$y:++$x;echo$s;

Verwenden Sie den Raumschiff-Operator

Probieren Sie es online!

Erweitert

while($i=$r<=>$argn) # if input is not equal sum of array
  for($s++;  # raise count steps
  ($r<=>$argn)==$i;)
  # so long as value compare to input has not change to lower/higher to higher/lower or equal  
    $r+=$i+1
      ?-++$y # if $i was higher remove the first integer
      :++$x;} # if $i was lower add the next highest integer     
echo$s; # Output steps

C, 94 91 Bytes

Versuchen Sie es online

c;s;m;M;f(n){while(s-n){while(s<n)s+=++M;c++;if(s==n)break;while(s>n)s-=++m;c++;}return c;}

JavaScript (ES6), 82 Byte

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

Testschnipsel

D=(o,a=0,b=1,d=1,c=0)=>a<o?D(o,a+=b,b+1,d,c+(a>=o)):a>o?D(o,a-=d,b,d+1,c+(a<=o)):c

<input type="number" oninput="o.textContent=D(this.value)"></input>
<pre id='o'></pre>

Gleichstrom , 61 Bytes

dsN[ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx]dsFxz2-

Probieren Sie es online!

Erläuterung

Hauptrekursives Makro:

ddd9k4*d2*1+dv-0k2/-d1+*2/-d[q]s.0=.-lN-0lN-sNlFx
   9k4*d2*1+dv-0k2/-                              # Compute triangular root
                    d1+*2/                        # Compute triangular number
  d                       -d[q]s.0=.              # Check if sum is exact
 d                                  -lN-          # Compute S-N or S+N
                                        0lN-sN    # Update N := -N
d                                             lFx # Leave the trail and recurse

Dieses Makro:

1. Findet die minimale Dreieckszahl, die die aktuelle Zahl auf dem Stapel überschreitet (unter Verwendung der modifizierten Dreiecksgrundformel ).
2. Überprüft, ob die dreieckige Summe Sgenau die aktuelle Zahl darstellt. Wird beendet, wenn dies der Fall ist.
3. Fährt mit Schritt 1 fort, entweder mit S+N(Über-) oder S-N(Unter-Näherung). Die Auswahl wechselt zwischen den Iterationen.

Wenn es beendet wird, teilt der Pfad, der auf dem Stapel verbleibt, dem Hauptprogramm mit, wie viele Iterationen es benötigte.

Python 3 150 138 Bytes

n=int(input())
S=sum
l=[1]
i=s=1
while S(l)<n:i+=1;l+=[i]
while S(l)!=n:
 while S(l)>n:l.pop(0)
 s+=1
 if S(l)<n:i+=1;l+=[i];s+=1
print(s)

Änderungsprotokoll:

• Anhängen an + = geändert, sonst entfernt (danke musicman523, Loovjo; -12 Bytes)

Batch, 126 Bytes

@echo off
set/an=s=l=u=0
:l
if %s% lss %1 set/as+=u+=1,n+=!!l&goto l
if %s% gtr %1 set/as-=l+=1&goto l
cmd/cset/an+n+2-!l

Erläuterung: lIst Null, wenn Schritt 2 noch nie ausgeführt wurde. Dies ermöglicht es n, die Anzahl der Iterationen von Schritt 3 zu verfolgen. Da der Algorithmus niemals bei Schritt 3 anhält, muss er daher Schritt 1 einmal und Schritt 2 n+1mal für insgesamt n+n+2Schritte ausgeführt haben. Wenn der Parameter jedoch eine Dreieckszahl ist, wird Schritt 2 niemals ausgeführt, sodass ein Schritt subtrahiert werden muss.

Python 2, 86 81 Bytes

n=input()
l=u=i=s=0
while n:k=n>0;i+=k^s;s=k;l+=k;n-=l*k;u+=k^1;n+=u*-~-k
print i

Probieren Sie es online!

Berechnet den 65536- Testfall 0.183sfür TIO.

Diese rekursive Version mit 84 Bytes kann nicht alle Werte bis 65536 berechnen:

def f(n,l=[0],m=1):k=n>sum(l);return n==sum(l)or f(n,[l[1:],l+[l[-1]+1]][k],k)+(m^k)

Probieren Sie es online!

Mathematica, 92 Bytes

(For[q=a=b=0;t={},t~AppendTo~q;q!=#,If[q<#,q+=++b,q-=++a]];Length@Split@Sign@Differences@t)&

Reine Funktion, die ein ganzzahliges Argument verwendet und eine ganze Zahl zurückgibt.

Die Variablen aund bstehen für die (sich ständig ändernden) Anfangs- und Endnummern in der betrachteten Summe, während sie qfür die laufende Summe (der Nummern von a+1bis b) stehen; tVerfolgt alle Werte von bisher qangetroffen. Nach der Initialisierung dieser Variablen wird die ForSchleife weiter ausgeführtIf[q<#,q+=++b,q-=++a] , wobei entweder eine neue Nummer am Ende hinzugefügt oder die durch die Spezifikation vorgegebene Nummer vorne abgezogen wird, bisq der Eingabe entspricht.

Jetzt müssen wir nur noch die Anzahl der Schritte aus tder Liste der qWerte extrahieren , die auf dem Weg gefunden wurden. Wenn der Eingang beispielsweise ist 11, wird die ForSchleife mit tGleichheit beendet {0,1,3,6,10,15,14,12,9,15,11}. Der beste Weg, die Anzahl der Schritte zu berechnen, ist zu zählen, wie oft die Unterschiede von hoch nach unten wechseln. Das ist, was der ausführliche Befehl Length@Split@Sign@Differences@ttut, aber ich vermute, dass das verbessert werden kann.

C (tcc), 71 Bytes (61 + 10)

Befehlszeilenargumente (einschließlich Leerzeichen):

-Dw=while

Quelle:

c,m,M,s;f(n){w(++c,s-n){w(c&s<n)s+=++M;w(~c&s>n)s-=m++;}--c;}

Wie es funktioniert:

czählt die Anzahl der Schritte. mund Mspeichern Sie das Minimum und Maximum des Bereichs, sdie Summe. Anfangs sind sie alle Null.

Kontinuierlich cwird erhöht und smit verglichen n. Solange sie ungleich sind:

• Wenn cungerade ist s<n, fügen Sie so lange eine ganze Zahl an das Ende des Bereichs an: Erhöhen Sie Mum eins und sum M.

• Wenn gerade cist s>n, entfernen Sie eine ganze Zahl vom Anfang des Bereichs: Verringern sum mund Erhöhen mum eins.

Wenn die Schleife beendet wird, cwurde sie zu oft erhöht. Wenn Sie es dekrementieren, erhalten Sie das richtige Ergebnis, und es wird zufällig im richtigen Register berechnet, um als Rückgabewert zu fungieren.

Amüsanterweise werden genau die gleichen Variablennamen wie in Khaled.Ks C-Antwort verwendet . Sie werden nicht kopiert.

Perl 6 , 114 Bytes

{((0,0,1),->(\a,\b,\c){b,(a..*).first(->\d{(d,b).minmax.sum*c>=$_*c}),-c}...->(\a,\b,\c){(a,b).minmax.sum==$_})-1}

(inspiriert von einer früheren Haskell- Implementierung)

Probieren
Sie es aus Es läuft mit einer Eingabe von 65536 in weniger als 45 Sekunden auf meinem Computer, aber ich konnte es mit TIO.run nicht in weniger als 60 Sekunden zum Laufen bringen.
Ich habe Rakudo v2017.04 +, wo es v2017.01 hat .
Rakudo / NQP / MoarVM werden fast täglich optimiert, sodass es in der Zwischenzeit eine beliebige Anzahl von Optimierungen geben kann, die erforderlich sind, um das Problem rechtzeitig zu beheben.

Erweitert

{
  (

    # generate a sequence

    (0,0,1),           # initial value 

    -> (\a,\b,\c) {
      b,               # swap the first two values

      (a..*)
      .first(          # find the first number that brings us to or past the input

        -> \d {
          (d,b).minmax # get a Range object regardless of which is larger
          .sum * c     # sum it, and negate it every other time

          >=           # is it equal to or greater than

          $_ * c       # negate the original input every other time
        }

      ),

      -c               # invert for next round
    }

    ...                # keep doing that until

    -> (\a,\b,\c) {
     (a,b).minmax.sum == $_ # it finally reaches the input
    }

  ) - 1 # count the number of elements in the sequence
        # and subtract one for the initializer
}

Beachten Sie, dass Rakudo über eine Optimierung verfügt, Range.sumsodass nicht alle Werte durchlaufen werden müssen.