Willkommen zurück, alle, die ein anderes Problem zu lösen haben! Heute sprechen wir über Dreieckszahlen und ihre Teiler: insbesondere über große!  Während wir meine fabelhafte künstlerische Darstellung von Dreieckszahlen in der Natur bewundern können, lassen Sie uns unsere üblichen Haftungsausschlüsse vornehmen:  Dieses Problem wird von der wunderbaren Website bereitgestellt  , den Sie abonnieren können  ! Es gibt mehr als 800 Mathematik- und Programmieraufgaben zu lösen und ein umfangreiches Archiv an Diskussionen darüber. Es ist im wahrsten Sinne des Wortes das perfekte Werkzeug, um den Kopf zu zerbrechen und etwas Neues zu lernen! Probieren Sie es aus und versuchen Sie, auch Ihre Herausforderungen zu lösen!   ProjektEuler.net   Hier  Ich bin kein erfahrener Programmierer, sondern nur ein Typ, der gerne über solche Dinge schreibt und seine Aufnahmen gerne teilt. Ich bin mir sicher, dass dies nicht die optimale Lösung ist. Wenn Sie also eine bessere Lösung oder eine Idee zur Optimierung haben, sind Sie herzlich willkommen, wenn Sie diese mit uns teilen möchten!  Genug geredet, mal sehen, was das heutige Problem zu bieten hat:   Die Folge der Dreieckszahlen entsteht durch Addition der natürlichen Zahlen. Die Zahl des siebten Dreiecks wäre also 1+2+3+4+5+6+7=28. Die ersten zehn Begriffe wären:1,3,6,10,15,21,28,36,45,55,…     Lassen Sie uns die Faktoren der ersten sieben Dreieckszahlen auflisten:   Wir können sehen, dass 28 die erste Dreieckszahl ist, die mehr als fünf Teiler hat.   Welchen Wert hat die erste Dreieckszahl mit mehr als fünfhundert Teilern?  Das Problem ist ganz einfach: Wir sollen verstehen, was die erste   ist, die mehr als 500   hat. Schauen wir uns zunächst einmal genauer an, was eine Dreieckszahl und ein Teiler ist. Dreieckszahl Teiler  Dreieckszahlen  Dreieckszahlen sind eine bestimmte Teilmenge von Zahlen, die durch die Summe aller natürlichen Zahlen bis zu einer bestimmten Zahl gebildet werden. Sie werden dreieckig genannt, weil   . Hier sind einige Beispiele:  man sie immer als Dreieck anordnen kann  Im Bild oben sind es die 3., die 4. und die 5. Dreieckszahl. So wird beispielsweise die 3. Zahl als 1+2+3 = 6 gebildet, die 4. als 1+2+3+4 = 10 und so weiter. Im Allgemeinen ist die nᵗʰ-Dreieckszahl Tₙ gleich  Dies ist natürlich eine der berühmtesten Reihen in der Mathematik, die auch von   vorgestellt wurde, der feststellte, dass die Summe aufeinanderfolgender ganzer Zahlen gleich ist: Gauß  Wenn wir also zum Beispiel die dritte Dreieckszahl berechnen wollen, berechnen wir einfach 3*4/2 = 6. Das wird sehr hilfreich sein, wenn wir mit dem Schreiben unserer Lösung beginnen!   Die Teiler  Den   (oder   ) einer Zahl   ist ganz einfach: Es handelt   Beispielsweise ist 3 ein Teiler von 18, da wir 3 und 6 multiplizieren können, um wieder 18 zu erhalten. Teiler Faktor n zu definieren, sich um eine Zahl   , die mit einer anderen ganzen Zahl   multipliziert werden kann, um wieder   zu erhalten. j k n  Allerdings ist 5 kein Teiler von 18, da es keine Zahl   gibt, die multipliziert mit 5 18 ergibt. k  Durch die Definition erhalten wir auch eine wichtige Eigenschaft: Wenn   ein Teiler von   ist, weil es mit   multipliziert werden kann, um   dann ist auch   ein Teiler von   , weil es mit   multipliziert werden kann, um  j n k n zu erhalten, k n j n zu erhalten.    (tatsächlich kann   immer 1 und   immer   sein). Auf diese Weise können wir sicher sein, dass eine Zahl   immer mindestens zwei Teiler   und   hat n j k j k n  Anders ausgedrückt   . Also zum Beispiel 18/3 = 6 und der Rest ist 0. ist eine Zahl   ein Teiler der Zahl   , wenn der Rest von   gleich 0 ist j n n / j  Wir können dieses Konzept mit   besser formalisieren und sagen, dass   ein Teiler von   ist, wenn   Mit anderen Worten, wir erhalten diese zweite Eigenschaft:  modularer Arithmetik j n n % j = 0.  Die dritte und letzte Eigenschaft, die uns interessiert, ist, dass   Das ist ziemlich einfach zu verstehen. Aus der ersten Eigenschaft wissen wir, dass Faktoren im Bereich 1,…,n irgendwie „verknüpft“ sind. es außer   selbst keinen Teiler einer Zahl   größer als   geben kann. n n n/2  Dies liegt wiederum daran, dass, wenn     Daher auch   Nehmen wir noch einmal 18 als Beispiel, finden seine Teiler und färben sie ein, um diese Eigenschaft widerzuspiegeln.  j \ n, j * k = n ist. k\n.  Wenn also beispielsweise   und umgekehrt, wenn   bedeutet dies, dass das kleinste   das wir verwenden können, neben 1 2 ist, was uns das größte   ergibt möglich,   (9 in unserem Fall)   Das funktioniert: j = 3, k = 6 j = 6, k = 3, j, k n/2 .  für gerade Zahlen, in diesem Fall ist der größte Faktor genau gleich der Hälfte von  n;  für ungerade Zahlen: wenn wir   nicht durch 2 teilen können (weil ungerade eine rationale Zahl ergibt); das bedeutet, dass wir nur   was uns immer Ergebnisse  n j > 2 verwenden können, k < n/2 liefert.  Schließlich   Wenn beispielsweise   erzeugt ein möglicher Faktor   einen weiteren Faktor   Wir werden diesen Fall später im Codeteil näher besprechen. gibt es nur einen Fall, in dem   und   gleich sein können: wenn   eine Quadratzahl ist. j k n n = 36 ist, j = 6 k = 6.  Diese Konzepte sind natürlich ziemlich trivial, aber sie werden für unsere Lösung sehr wichtig sein!   Der Code  Der Code wird in   geschrieben, da es sich wirklich um eine schnelle Sprache handelt, die dennoch ein hohes Maß an Lesbarkeit beibehält. Wir werden die Lösung in zwei Teile aufteilen: Zuerst erstellen wir   . Go eine Funktion, um die Teiler einer Zahl zu finden, und dann wenden wir sie auf die Dreieckszahlen an  Schauen wir uns zunächst die Funktion an:   https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true  Wir erstellen unsere Funktion, die eine Ganzzahl   akzeptiert und ein Array von Ganzzahlen   , das unsere Teiler enthält. Danach hängen wir die trivialen Faktoren   , nämlich 1 und   selbst. n out out n  Dann beginnen wir mit der Schleife   von 2 bis   (von der zweiten Eigenschaft aus; beachten Sie auch, dass wir nicht an   selbst interessiert sind, da für den Fall, dass   gerade ist,   durch   zu den Teilern addiert wird   Iteration: Deshalb stoppen wir bei   und nicht   ). j n/2 n/2 n k = n/2 j = 2 j = 2 j<n/2 j≤ n/2  Auf diese Weise können wir nur in der ersten Hälfte von   nach Teilern suchen, was den Prozess erheblich beschleunigt. n  Bei jeder Schleife prüfen wir drei Dinge:  Die dritte if-Anweisung prüft tatsächlich, ob   , mit anderen Worten, ob 0 ≡ n (mod j). Wenn ja, haben wir einen Faktor gefunden und fügen   zur Liste hinzu. Wir können auch sein Gegenstück   an die Liste anhängen, indem wir   berechnen und dann mit dem nächsten   fortfahren; n%j==0 j k n/j j  Die zweite if-Anweisung prüft, ob   ein Quadrat ist und   also die Wurzel von   ist. Wenn ja, wird nur ein Teiler   zu   hinzugefügt, um Duplikate zu vermeiden, und dann geht der Algorithmus weiter. n j n j out  Angenommen,   : Wenn dieser kleine Block fehlen würde, würde die dritte if-Anweisung ausgelöst, wodurch     und   empfangen würde und somit ein Duplikat erstellt würde. n = 36 out j = 6 k = n/j = 36/6 = 6  Die erste if-Anweisung ist die komplexeste: Ihr Zweck besteht darin, zu überprüfen, ob wir beginnen, sich wiederholende   Paare zu haben. Wenn ja, können wir die Schleife sofort durchbrechen, da unser Faktor bereits in   vorhanden ist. JK- out  Speziell zu diesem dritten Punkt müssen zwei Fälle überprüft werden: ob   oder   . out[len(out)-1] == j out[len(out)-2] == j  Der erste Fall ist der klassische: Nehmen wir zum Beispiel die Zahl T₇ = 28:  Wenn   ist, entspricht es dem zuletzt eingefügten Wert. Daher können wir die Schleife durchbrechen. j = 7  Der zweite Fall tritt nur auf, wenn wir ein Quadrat   gefunden haben. Nehmen Sie zum Beispiel noch einmal 36: n  Wenn   ist, entspricht es dem letzten Wert, der vor der Quadratwurzel von   angehängt wird, die nur einmal vorkommt. Daher können wir an dieser Stelle die Schleife durchbrechen. j = 9 n  Schließlich können wir einfach   , um unsere Teiler zu erhalten. return out   Anwenden der Ergebnisse  Da wir nun unsere Funktion haben, können wir sie auf jede Dreieckszahl anwenden. Wir werden einen Zähler   erstellen, der als Generator für unsere Dreieckszahlen dient. Wir berechnen die zugehörige Dreieckszahl   mit der Gauß-Gleichung und prüfen, wie viele Teiler sie hat. c tn  Wenn es mehr als 500 ist, geben wir diesen   als Ergebnis zurück. tn   https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go  Aber da ist ein Fang!    Neben der Präsentation von Mathe-Rätseln und -Problemen   . ProjectEuler.net ist wirklich ein schönes Projekt: liegt ihr Hauptaugenmerk darauf, ein Werkzeug bereitzustellen, mit dem man mit dem Lernen, Nachdenken und Nachdenken über Mathematik beginnen kann  Und ich liebe das: Sie sind so engagiert, dass die Veröffentlichung von Ergebnissen und Leitfäden für ihre Probleme eigentlich verboten ist (dies ist eines der ersten 100 Probleme, daher ist es meines Wissens erlaubt).  Vor diesem   . Aus diesem Grund gebe ich Ihnen nicht die eigentliche Lösung: Probieren Sie es selbst aus und versuchen Sie, einen besseren Algorithmus als meinen zu finden (davon gibt es viele). Tut mir leid, Leute! 😅 Hintergrund halte ich es nicht für fair, die Lösung einfach zum Kopieren und Einfügen herauszugeben und den Erfolg zu erhalten   Zeitkomplexität  Ich bin zuversichtlich, dass es viele bessere Lösungen gibt, denn meiner Meinung nach ist dies ein ziemlich schrecklicher Schuss!  Die   Funktion wird in linearer Zeit ausgeführt: da sie von der Größe der Instanz   abhängt und außerdem höchstens   Schleifen ausführt; wir können es als ein O(n) betrachten. FindDivisor n n/2  Allerdings müssen wir zuerst jede Dreieckszahl berechnen, was ebenfalls O(tn) Zeit in Anspruch nimmt, wobei tn das Ergebnis ist (das letzte, das wir tatsächlich berechnen). Vor diesem Hintergrund sollte die zeitliche Komplexität des gesamten Algorithmus ungefähr O(tn*n) betragen.  Da   zum Argument oder unserer Funktion wird und wir höchstens   Schleifen darin ausführen, können wir die Zeitkomplexität als O(tn*tn/2) = O(tn²/2) = O(tn²) umschreiben. Also leider eine   ! tn n/2 quadratische Zeitlösung  Ich war jedoch überrascht, dass der Algorithmus trotz dieser Komplexität dennoch ziemlich schnell läuft. Um auf meinem Rechner (AMD Ryzen 5, durchschnittlich 2700 MHz) ein Ergebnis auszugeben, dauerte es 322,564227 ms.  Der Versuch, die erste Dreieckszahl zu finden, die 1000 Teiler überschreitet, dauerte jedoch 3,827144472 Sekunden, sodass deutlich zu erkennen ist, dass der Zeitverbrauch rapide ansteigt.   Abschluss  Wir haben es endlich geschafft! Ich hoffe, euch hat der Artikel gefallen und ich hoffe, dass ihr etwas Interessantes daraus mitnehmen könnt: Wenn ja, lasst bitte ein oder zwei Klatscher da und teilt den Artikel mit jemandem, der an diesem Thema interessiert sein könnte!  Nochmals ein großes Lob an ProjectEuler für die fantastische Arbeit: Ich möchte Ihnen wirklich empfehlen, sich anzusehen, was sie zu bieten haben. Ich bin mir sicher, dass du es super interessant finden wirst!  Und wie immer vielen Dank fürs Lesen.   Nicola

Read My Stories

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Zu lang; Lesen

Make resilience your competitive advantage

Tägliches Codierungsproblem: Dreieckszahlen und große Teiler

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

HackerNoon Decoded 2024: Celebrating Our AI Community!

HackerNoon Decoded 2024: Celebrating Our Tech Stories Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

Welcome to HackerNoon Decoded: The Best of 2024 Tech Blogging

HackerNoon Decoded 2024: Celebrating Our AI Community!

HackerNoon Decoded 2024: Celebrating Our Tech Stories Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

Welcome to HackerNoon Decoded: The Best of 2024 Tech Blogging

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps