Stellen Sie sich ein Dreieck ABC vor, bei dem jede Seite eine ganzzahlige Länge hat (ein ganzzahliges Dreieck ). Definiert einen Median von ABC ein Liniensegment von einem Scheitel zu dem Mittelpunkt der gegenüberliegenden Seite zu sein. In der folgenden Abbildung repräsentieren die roten Liniensegmente die Mediane. Beachten Sie, dass jedes gegebene Dreieck drei Mediane hat.
Sei n eine positive ganze Zahl. Wie viele nicht entartete integrale Dreiecke mit einer Seitenlänge von n oder weniger haben mindestens einen integralen Median?
Herausforderung
Schreiben Sie ein Programm, um die Anzahl der integralen Dreiecke mit mindestens einem integralen Median für eine gegebene maximale Seitenlänge n zu berechnen . Die Reihenfolge der Seitenlängen spielt keine Rolle, dh <6,6,5> repräsentiert dasselbe Dreieck wie <5,6,6> und sollte nur einmal gezählt werden. Schließen Sie degenerierte Dreiecke wie <1,2,3> aus.
Wertung
Das größte n, für das Ihr Programm die Anzahl der Dreiecke in 60 Sekunden auf meinem Computer erzeugen kann, ist Ihre Punktzahl. Das Programm mit der höchsten Punktzahl gewinnt. Mein Computer ist ein Sony Vaio SVF14A16CLB, Intel Core i5, 8 GB RAM.
Beispiele
Lassen Sie T ( N ) das Programm mit dem Eingang N .
T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34
Es ist zu beachten, dass T (1) = T (2) = T (3) = T (4) = T (5) = 0 ist, da keine Kombination von integralen Seiten einen integralen Median ergibt. Sobald wir jedoch 6 erreicht haben, können wir sehen, dass einer der Mediane des Dreiecks <5,5,6> 4 ist, also ist T (6) = 1.
Beachten Sie auch, dass T (22) der erste Wert ist, bei dem die Doppelzählung zum Problem wird: Das Dreieck <16,18,22> hat die Mediane 13 und 17 (und 2sqrt (85)).
Berechnung der Mediane
Die Mediane eines Dreiecks können mit den folgenden Formeln berechnet werden:
Current top score: Sp3000 - 7000 points - C
quelle
Antworten:
C, rohe Kraft - n = 6080
Dies ist eher eine Ausgangsbasis als ein ernstzunehmender Konkurrent, aber es sollte zumindest den Anfang machen.
n = 6080 ist so hoch wie in einer Minute Laufzeit auf meinem eigenen Computer, einem MacBook Pro mit Intel Core i5. Das Ergebnis für diesen Wert ist:
Der Code ist reine Brute Force. Es listet alle Dreiecke innerhalb der Größenbeschränkung auf und prüft die Bedingung:
quelle
lrintf()
oder verwenden,(int)roundf()
anstatt 0.5f hinzuzufügen und die Standardkürzung zu verwenden. Manchmal müssen Sie es jedoch verwenden-ffast-math
, um eine einzelnecvtss2si
Anweisung zu kompilieren . gcc inlineslrintf()
undsqrtf
nur mit-fno-math-errno
, so dass Sie effizient asm bekommen: godbolt.org/g/E3hncQ . (Ich habe verwendet,-march=ivybridge
weil das die CPU des OP ist). Mit-ffast-math
clang wird der sqrt in eine rsqrt + Newton-Iteration umgewandelt. IDK, wenn das ein Gewinn ist.roundf
. Verwenden Sie(int)nearbyintf()
iflrintf()
nicht inline, da der aktuelle Rundungsmodus anstelle eines bestimmten seltsamen verwendet wird. stackoverflow.com/questions/37620659/…C, ungefähr
6650 bis6900Ich benutze C nicht wirklich oft, aber mit der Menge an Arithmetik schien es eine gute Wahl der Sprache zu sein. Der Kernalgorithmus ist Brute Force wie die Antwort von @ RetoKoradi , jedoch mit ein paar einfachen Optimierungen. Ich bin mir jedoch nicht sicher, ob unsere Werte vergleichbar sind, da der Computer von @ RetoKoradi schneller zu sein scheint als meiner.
Die größte Optimierung besteht darin, die
% 4
Prüfung vollständig zu umgehen . Ein ganzzahliges Quadratn*n
ist entweder 0 oder 1 Modulo 4, je nachdem, ob esn
sich um 0 oder 1 Modulo 2 handelt. Wir können uns also alle Möglichkeiten ansehen für(x, y, z) % 2
:Günstigerweise sind nur zwei Fälle zu berücksichtigen:
(0, 0, 0)
und(1, 1, 0)
was bei den ersten beiden Seitena, b
der dritten Seitec
mit Parität entsprichta^b
:a^b
ist die gleiche Parität wiea-b
, also anstattc = a-b+1
von 1 zu suchen und um 1 zuc = a-b+2
steigen , können wir von 2 zu suchen und um 2 zu steigen.Eine weitere Optimierung ergibt sich aus der Tatsache, dass
(1, 1, 0)
wir is_square für diesen Fall nur einmal aufrufen müssen, da nur eine Permutation funktioniert. Dies wird im Code durch Abwickeln der Suche besonders hervorgehoben.Die andere eingeschlossene Optimierung ist einfach ein Quickfail in der
is_square
Funktion.Die Zusammenstellung wurde mit durchgeführt
-std=c99 -O3
.(Vielen Dank an @RetoKoradi für den Hinweis, dass
0.5
in is_square sein muss0.5f
, um eine doppelte Konvertierung zu vermeiden.)quelle
0.5f
anstelle von0.5
in verwendenis_square()
.0.5
Ist eine Konstante vom Typdouble
, sodass der Ausdruck beim Hinzufügen einen doppelten Wert erzeugt0.5
, einschließlich der Typkonvertierung vonfloat
nachdouble
für den anderen Begriff.f
.Felix, unbekannt
Grundsätzlich ein Port der C-Antwort, aber es ist schneller als es, getestet mit
clang -O3
undicc -O3
. Felix und Nim sind buchstäblich die einzigen Sprachen, die ich kenne und die C und C ++ bei Benchmarks schlagen können. Ich arbeite an einer parallelen Version, aber es wird noch ein bisschen dauern, bis sie fertig ist. Deshalb habe ich mich entschlossen, dies im Voraus zu veröffentlichen.Ich habe auch "unknown" gesetzt, weil mein Computer nicht unbedingt der schnellste der Welt ist ...
Befehl zum Erstellen:
Das generierte C ++ ist ziemlich interessant anzusehen:
quelle
C # (ungefähr 11000?)
n
wird als Befehlszeilenargument verwendet.Erläuterung
Wir können umschreibenm = ( 2 a2+ 2 b2- c2) / 4---------------√ 2 a2+ 2 b2= 4 m2+ c2 c2 c c = 2 C ein2+ b2= 2 ( m2+ C2) ein2+ b2 ein b
quelle
n=5000
installieren , aber meine Zeit für die Antwort von Reto Koradi beträgt 67 Sekunden, für die Antwort von Sp3000 48 Sekunden und für meine Antwort 13 Sekunden.C, n = 3030 hier
Ergebnisse:
Der obige Code wäre die Übersetzung in C der Axiom-Antwort (wenn wir die isq () -Funktion nicht mitzählen).
Mein Compiler verknüpft keine Funktion, die andere verwenden sqrtf () ... hier gibt es keine sqrt-Funktion für float ... Sind sie sicher, dass es sich bei sqrtf um eine C-Standardfunktion handelt?
quelle
APL NARS, n =
239282 in 59 Sekunden(Ich übersetze das Axiom Antwort eins, in APL) Test:
quelle
Axiom, n = 269 in 59 s
Wenn a, b, cx die Länge der Seiten eines Dreiecks von maximaler Länge n sind ...
Wir würden wissen, dass m: = sqrt ((2 * (a ^ 2 + b ^ 2) -cx ^ 2) / 4)
Wie Peter Taylor gesagt hatte, 4 | (2 * (a ^ 2 + b ^ 2) -cx ^ 2) und weil 2 | 2 * (a ^ 2 + b ^ 2) als 2 | cx ^ 2 => cx = 2 * c. So wird es ab 1 sein
a und b müssen die gleiche Parität haben, damit wir b in Funktion von a schreiben können
als wir das haben
so kann die (1) umgeschrieben werden, siehe (2) (3) (4) als:
wo
Ergebnisse
quelle
VBA 15.000 in ZEHN Sekunden!
Ich habe nach diesen anderen Posts viel weniger erwartet. Auf einem Intel 7 mit 16 GB RAM bekomme ich 13-15.000 in zehn Sekunden. Auf einem Pentium mit 4 GB RAM erhalte ich in zehn Sekunden 5-7.000. Der Code ist unten. Hier ist das neueste Ergebnis auf dem Pentium
Es entstand ein Dreieck mit den Seiten 240, 239, 31 und einem Medium von 121. Die Anzahl der Medien beträgt 7.371.
quelle