Quadratische Zahlen sind solche, bei n^2
denen n eine ganze Zahl ist. Diese werden auch als perfekte Quadrate bezeichnet, da Sie eine ganze Zahl erhalten, wenn Sie ihre Quadratwurzel ziehen.
Die ersten 10 Quadratzahlen sind: ( OEIS )
0, 1, 4, 9, 16, 25, 36, 49, 64, 81
Dreieckszahlen sind Zahlen, die ein gleichseitiges Dreieck bilden können. Die n-te Dreieckszahl ist gleich der Summe aller natürlichen Zahlen von 1 bis n.
Die ersten 10 Dreieckszahlen sind: ( OEIS )
0, 1, 3, 6, 10, 15, 21, 28, 36, 45
Quadratische Dreieckszahlen sind Zahlen, die sowohl quadratisch als auch dreieckig sind.
Die ersten 10 quadratischen Dreieckszahlen sind: ( OEIS )
0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881, 55420693056, 1882672131025, 63955431761796
Es gibt unendlich viele quadratische Zahlen, Dreieckszahlen und quadratische Dreieckszahlen.
Schreiben Sie ein Programm oder eine benannte Funktion, die eine Eingabe- (Parameter- oder Standard-) Nummer angibt n
, die n
dreieckige Zahl im Quadrat berechnet und ausgibt / zurückgibt, wobei n eine positive Zahl ungleich Null ist. (Für n = 1 0 zurückgeben)
Damit das Programm / die Funktion eine gültige Übermittlung ist, sollte es in der Lage sein, mindestens alle quadratischen Dreieckszahlen zurückzugeben, die kleiner als 2 ^ 31-1 sind.
Bonus
-4 Bytes für die Ausgabe aller quadratischen Dreieckszahlen kleiner als 2 ^ 63-1
-4 Bytes, um theoretisch quadratische Dreieckszahlen beliebiger Größe ausgeben zu können.
+8 Byte Strafe für Lösungen, die nicht polynomielle Zeit benötigen.
Bonusstapel.
Dies ist eine Code-Golf-Herausforderung, daher gewinnt die Antwort mit den wenigsten Bytes.
n
Schritte gibt, und in jedem Schritt nimmt die Arithmetik lineare Zeit in Anspruch, weil die Anzahl der Ziffern linear wächstn
. Ich denke nicht, dass lineare Zeit möglich ist. Es sei denn, Sie sagen, arithmetische Operationen sind konstante Zeit?Antworten:
CJam,
128 BytesVerwendet die Wiederholungsrelation aus dem Wikipedia-Artikel.
Der Code ist 16 Byte lang und qualifiziert sich für beide Boni.
Probieren Sie es online im CJam-Interpreter aus .
Wie es funktioniert
Mein Code erwies sich in jeder Hinsicht als identisch mit dem von xnor, außer dass ich den Stapel von CJam anstelle von Variablen verwende.
quelle
Python 2, 45 - 4 - 4 = 37
Iteriert mit der Wiederholung
Theoretisch unterstützt dies Zahlen jeder Größe, läuft jedoch in exponentieller Zeit, sodass es sich nicht für die Boni qualifizieren sollte. Sollte für Zahlen jeder Größe funktionieren. Zum Beispiel für 100 gibt
Eine rekursive Lösung verwendet 41 Zeichen, sollte sich jedoch nicht qualifizieren, da dies exponentiell dauert.
quelle
exec
Lösung verbunden wäre. Wenn Sie das Rekursionslimit ändern dürfen, kann es auch eine quadratische Dreieckszahl beliebiger Größe berechnen und für # 2 qualifizieren. Ich bin mir jedoch nicht sicher, ob dies qualifiziert ist (@Rodolvertice).Pyth, 16 - 4 - 4 = 8 Bytes
Verwendet die rekursive Formel aus dem OEIS-Artikel.
Es verwendet den Post-Assign-Befehl, der ziemlich neu ist und wirklich cool erscheint. Die Verwendung wird
n-1
aufgrund der 1-basierten Indizierung auf Iterationszeiten reduziert .Scheint polynomisch zu sein, weil es n-mal wiederholt wird und jede Iteration mathematisch und zuweisend ausführt, aber ich bin kein Informatiker. Beendet n = 10000 fast sofort.
Probieren Sie es hier online aus .
quelle
b
.Oasis , 7 - 4 - 4 = -1 (nicht konkurrierend)
Probieren Sie es online aus!
Verwendet
a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2
Oasis unterstützt Ganzzahlen mit beliebiger Genauigkeit, daher sollte es in der Lage sein, eine beliebige Anzahl zu erreichen, solange kein Stapelüberlauf auftritt. Lassen Sie mich wissen, wenn dies aufgrund eines Stapelüberlaufs nicht für den Bonus zählt. Es ist auch möglich, dass dieser spezielle Algorithmus nicht polynomisch ist, und lassen Sie mich wissen, ob dies der Fall ist.
Nicht konkurrierend, weil die Postdates der Sprache eine Herausforderung darstellen.
Erläuterung:
Alternative Lösung:
Verwendet stattdessen
a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)
quelle
For n=1 return 0
, aber dies gibt 1 zurück. Dies kann durch Hinzufügen der Option -O behoben werden .JavaScript (ES6), 29-4 = 25 Bytes
5 Bytes dank @IsmaelMiguel gespart !
Ich musste die 0, 1 und die Negative fest codieren, um eine unendliche Rekursion zu vermeiden.
Konsole, ich habe die Funktion benannt ,
f
:BEARBEITEN : Es stellt sich heraus, dass JavaScript die Zahlen auf 16 (15) Stellen (Spezifikation) rundet, da diese Zahlen zu groß sind und einen Überlauf verursachen. Fügen Sie 714341252076979033 in Ihre JavaScript-Konsole ein und überzeugen Sie sich selbst. Es ist eher eine Einschränkung von JavaScript
quelle
f(15)
sollte zurückkehren85170343853180456676
, nicht85170343853180450000
.n=>n?n<2?0:34*f(n-1)-f(n-2)+2:1
(31 Bytes). Ich habe bis zur 5. Nummer getestet.n=>n>1?34*f(n-1)-f(n-2)+2:!!n
. Es kehrtfalse
weiter0
,true
weiter1
und36
weiter2
. Wenn Sie es wollen , eine Reihe zurückkehren, können Sie ersetzen!!n
mit+!!n
.n=>n>1?34*f(n-1)-f(n-2)+2:n|0
(gleiche Byteanzahl, gibt jetzt immer Zahlen zurück)Excel VBA - 90 Bytes
Verwenden der Wiederholungsrelation von der Wikipedia-Seite:
Wenn Sie ausgeführt werden, werden Sie zur Eingabe von n aufgefordert, und die Sequenz bis einschließlich n wird in Spalte A ausgegeben:
Es kann bis einschließlich n = 202 ausgeführt werden, bevor ein Überlauffehler auftritt.
quelle
[Nicht konkurrierend] Pyth (14 - 4 - 4 = 6 Bytes)
Verwendet die erste Wiederholung von OEIS , dass nach 0,1,36 A n = (A n-1 -1) 2 / A n-2 gefunden werden kann . A Nicht konkurrierend, da diese Lösung bei 36 beginnt. Wenn Sie nach unten gehen, dividieren Sie durch Null (die Eingabe von 0 ergibt also 36). Musste auch 36 fest codieren.
Probieren Sie es hier aus
quelle
Java, 53 - 4 = 49 Bytes
Es ist eine weitere einfache Rekursion, aber ich kann Java nicht oft mit einer Punktzahl von <50 posten, also ...
Für etwas Nicht- Rekursives wird es jetzt ziemlich viel länger. Dieser ist sowohl länger (112-4 = 108) als auch langsamer, daher bin ich mir nicht sicher, warum ich ihn poste, außer um etwas Iteratives zu haben:
quelle
Julia, 51 Bytes - 4 - 4 = 43
Hierbei wird die erste auf der Wikipedia-Seite aufgeführte Wiederholungsrelation für quadratische Dreieckszahlen verwendet. Es berechnet n = 1000 in 0,006 Sekunden und n = 100000 in 6,93 Sekunden. Es ist ein paar Bytes länger als eine rekursive Lösung, aber es ist viel schneller.
Ungolfed + Erklärung:
Beispiele:
quelle
PHP,
655956-4 = 52 BytesWiederholen, bis die Quadratwurzel von
$s
∈ℤ ist: Addiere$f
zur Summe$s
, inkrementiere$f
;Wiederholungszeiten
$argv[1]
.Ausgangssumme.
quelle
Prolog,
7074 - 4 - 4 = 66Laufende
n(100,R)
Ausgaben:Die Ausführung
n(10000,X)
auf meinem Computer dauert ca. 1 Sekunde .Bearbeiten : Die 66-Version ist schwanzrekursiv. Die vorherige nicht rekursive Version ist die folgende:
Sie haben die gleiche Länge in Bytes, aber das nicht-rekursive Regenerieren erzeugt Stapelüberläufe ab einem bestimmten Punkt (auf meinem Computer um 20500).
quelle
Javascript ES6,
777571 ZeichenPrüfung:
quelle
C 68 Bytes
Dies war eine lustige Herausforderung mit C.
main(o,k){o==1?k=0:0;k<9e9&&k>=0&&main(34*o-k+2,o,printf("%d,",k));}
Sehen Sie, wie es hier läuft: https://ideone.com/0ulGmM
quelle
Gelee , 13 - 8 = 5 Bytes
Dies gilt für beide Boni.
Probieren Sie es online aus!
Geschehen neben Caird Coinheringaahing im Chat .
Erläuterung
quelle
Perl 6 , 25 - 8 = 17 Bytes
Probieren Sie es online aus!
quelle
05AB1E , 10 - 8 = 2 Bytes
Probieren Sie es online aus!
quelle
APL (NARS), 67 Zeichen, 134 Bytes
Prüfung:
f würde in quadratischer Reihenfolge die Elemente suchen, die auch eine dreieckige Zahl sind, daher müssen sie der dreieckigen Prüfformel in APLs folgen: 0 = 1∣√1 + 8 × m mit der zu prüfenden Zahl m.
quelle