Bienvenue à tous avec un autre problème à résoudre ! Aujourd'hui, nous allons parler des nombres triangulaires et de leurs diviseurs : surtout les plus grands !  Alors que nous pouvons admirer ma fabuleuse représentation artistique des nombres triangulaires dans la nature, ayons nos avertissements habituels :  Ce problème est fourni par le merveilleux site Web  , auquel vous pouvez vous abonner  ! Il y a plus de 800 problèmes de mathématiques et de codage à résoudre et une vaste archive de discussions à leur sujet. C'est littéralement l'outil parfait pour se gratter la tête et apprendre quelque chose de nouveau ! Allez le vérifier et essayez également de résoudre vos défis !   ProjetEuler.net   ici  Je ne suis pas un programmeur expert : juste un gars qui aime écrire sur ce genre de choses et aime partager ses clichés. Je suis sûr que ce ne sera pas la solution optimale, donc si vous en avez une meilleure ou une idée sur la façon de l'optimiser, vous êtes plus que bienvenu si vous souhaitez partager !  Assez parlé, voyons ce que le problème d'aujourd'hui a à offrir :   La séquence de nombres triangulaires est générée en ajoutant les nombres naturels. Ainsi, le numéro du 7e triangle serait 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Les dix premiers termes seraient : 1,3,6,10,15,21,28,36,45,55,…     Énumérons les facteurs des sept premiers nombres triangulaires :   Nous pouvons voir que 28 est le premier nombre de triangles à avoir plus de cinq diviseurs.   Quelle est la valeur du premier nombre de triangles ayant plus de cinq cents diviseurs ?  Le problème est assez simple : on nous demande de comprendre quel est le premier   qui a plus de 500   . Tout d'abord, regardons mieux ce qu'est un nombre triangulaire et ce qu'est un diviseur. nombre triangulaire diviseurs  Nombres triangulaires  Les nombres triangulaires sont un sous-ensemble particulier de nombres qui sont formés par la somme de tous les nombres naturels jusqu'à un certain. Ils sont appelés triangulaires car   . Voici quelques exemples:  vous pouvez toujours les disposer en triangle  Dans l'image ci-dessus, il s'agit des 3e, 4e et 5e nombres triangulaires. Ainsi, par exemple, le 3ème nombre est formé comme 1+2+3 = 6, le 4ème comme 1+2+3+4 = 10, et ainsi de suite. D'une manière générale, le nombre triangulaire nᵗʰ, Tₙ, est égal à  C'est, bien sûr, l'une des séries les plus célèbres en mathématiques, présentée également par   , qui a déclaré que la somme d'entiers consécutifs est égale à : Gauss  Donc, fondamentalement, si nous voulons calculer le 3ème nombre triangulaire, par exemple, nous calculons simplement 3*4/2 = 6. Cela sera très utile une fois que nous commencerons à écrire notre solution !   Les diviseurs  Pour donner une définition du   (ou   ) d'un nombre   c'est très simple : c'est   Par exemple, 3 est un diviseur de 18, car on peut multiplier 3 et 6 pour obtenir à nouveau 18. diviseur facteur n, un nombre   qui peut être multiplié par un autre entier   pour donner à nouveau   . j k n  Cependant, 5 n'est pas un diviseur de 18, car il n'y a pas de nombre   qui multiplié par 5 donne 18. k  Par la définition, on obtient aussi une propriété importante : si   est un diviseur de   car il peut être multiplié par   pour obtenir   alors aussi   est un diviseur de   car il peut être multiplié par   pour obtenir  j n k n, k n j n.    ( en fait,   peut toujours être 1 et   être   ). De cette façon, nous pouvons être sûrs qu'un nombre   a toujours au moins deux diviseurs   et  n j k j k n  Aussi, pour le dire autrement,   . Ainsi, par exemple, 18/3 = 6, et le reste est 0. un nombre   est un diviseur du nombre   si le reste de   est égal à 0 j n n / j  On peut mieux formaliser ce concept avec   en disant que   est un diviseur de   si   En d'autres termes, on obtient cette seconde propriété :  l'arithmétique modulaire j n n % j = 0.  La troisième et dernière propriété qui nous intéresse est qu'il   C'est assez simple à comprendre. D'après la première propriété, nous savons que les facteurs sont en quelque sorte « liés » entre eux dans l'intervalle 1,…,n. ne peut y avoir de diviseur d'un nombre   supérieur à   plutôt que   lui-même. n n/2, n  C'est parce que encore une fois, si   c'est parce que   Par conséquent, également   Reprenons 18 comme exemple, trouvons ses diviseurs et colorons-les pour refléter cette propriété.  j \ n, j * k = n. k \ n.  Ainsi, par exemple, si   et inversement si   cela signifie que le plus petit   que nous pouvons utiliser, en plus de 1, est 2, ce qui nous donne le plus grand   possible,   (9 dans notre cas)   Cela marche: j = 3, k = 6, j = 6, k = 3, j k n/2 .  pour les nombres pairs, auquel cas le plus grand facteur sera exactement égal à la moitié de  n ;  pour les nombres impairs : si on ne peut pas diviser   par 2 (car être impair nous donnera un nombre rationnel) ; cela signifie que nous ne pouvons utiliser   ce qui nous donnera toujours des résultats  n que j > 2, k < n/2.  Enfin,   Par exemple, lorsque   un facteur possible   produira un autre facteur   Nous discuterons plus en détail de ce cas plus tard dans la partie code. il n'y a qu'un seul cas où   et   peuvent être égaux : lorsque   est un nombre carré. j k n n = 36, j = 6 k = 6.  Ces concepts sont assez triviaux, bien sûr, mais ils seront très importants dans notre solution !   Le code  Le code sera écrit en   , car c'est vraiment un langage rapide qui maintient toujours un bon niveau de lisibilité. Nous allons diviser la solution en deux : d'abord, nous allons créer   . Go une fonction pour trouver les diviseurs d'un nombre, puis nous l'appliquerons aux nombres triangulaires  Voyons d'abord la fonction :   https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true  Nous créons notre fonction qui accepte un entier   et renvoie un tableau d'entiers   , qui contiendra nos diviseurs. Après cela, nous   aux facteurs triviaux, à savoir 1 et   lui-même. n out out n  Ensuite, nous commençons à boucler   de 2 à   (à partir de la deuxième propriété ; notez également que nous ne sommes pas intéressés par   lui-même car dans le cas où   est pair,   sera ajouté aux diviseurs par le   itération : c'est pourquoi on s'arrête à   et non   ). j n/2 n/2 n k = n/2 j = 2 j<n/2 j≤ n/2  De cette façon, nous ne pouvons vérifier les diviseurs que dans la première moitié de   , accélérant un peu le processus. n  A chaque boucle, on vérifie 3 choses :  La troisième instruction if vérifie en fait si   , en d'autres termes, si 0 ≡ n (mod j). Si oui, nous avons trouvé un facteur, et nous ajoutons   à la liste. On peut aussi ajouter son homologue   à la liste, en calculant   puis en passant au   suivant ; n%j==0 j k n/j j  La deuxième instruction if vérifie si   est un carré, et donc   est la racine de   . Si tel est le cas, un seul diviseur   sera ajouté à   , afin d'éviter les doublons, puis l'algorithme continue. n j n j out  Supposons   : si ce petit bloc manquait, la troisième instruction if serait déclenchée,   la réception   et   , créant ainsi un doublon. n = 36 out j = 6 k = n/j = 36/6 = 6  La première instruction if est la plus complexe : son but est de vérifier si nous commençons à avoir des paires   répétitives. Si tel est le cas, nous pouvons instantanément rompre la boucle, car notre facteur sera déjà présent dans   . jk out  Plus précisément sur ce troisième point, il y a deux cas à vérifier : si   ou   . out[len(out)-1] == j out[len(out)-2] == j  Le premier cas est le plus classique : prenons le nombre T₇ = 28 par exemple :  Lorsque   , il sera égal à la dernière valeur insérée. Par conséquent, nous pouvons rompre la boucle. j = 7  Le deuxième cas ne se produit que lorsque nous avons trouvé un carré   . Reprenez 36, par exemple : n  Lorsque   , il sera égal à la dernière valeur ajoutée avant la racine carrée de   , qui n'apparaît qu'une seule fois. Par conséquent, à ce stade, nous pouvons rompre la boucle. j = 9 n  Enfin, nous pouvons simplement   pour avoir nos diviseurs. return out   Application des résultats  Maintenant que nous avons notre fonction, nous pouvons l'appliquer à chaque nombre triangulaire. Nous allons créer un compteur   qui servira de générateur pour nos nombres triangulaires. Nous calculons le nombre triangulaire associé   avec l'équation de Gauss et vérifions combien de diviseurs il a. c tn  S'il est supérieur à 500, nous renvoyons ce   comme résultat. tn   https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go  Mais… il y a un hic !    en plus de présenter des énigmes et des problèmes mathématiques,   . ProjectEuler.net est vraiment un beau projet : leur objectif principal est de fournir un outil pour commencer à apprendre, à réfléchir et à raisonner sur les mathématiques  Et j'adore ça : ils sont tellement engagés qu'il est en fait interdit de publier des résultats et des guides pour leurs problèmes (c'est l'un des 100 premiers problèmes, donc je comprends que c'est autorisé).  Compte tenu de cela,   . Pour cette raison, je ne vous donne pas la vraie solution : essayez-la par vous-même et essayez de trouver un meilleur algorithme que le mien (il y en a beaucoup). Désolé les gars! 😅 je ne pense pas qu'il serait juste de donner simplement la solution pour copier-coller et obtenir le succès   Complexité temporelle  Je suis convaincu qu'il existe de nombreuses meilleures solutions car je pense que celle-ci est un coup assez terrible!  La fonction   s'exécute en temps linéaire : puisqu'elle dépend de la taille de l'instance   et qu'elle exécute également au plus   boucles ; on peut le considérer comme un O(n). FindDivisor n n/2  Cependant, nous devons d'abord calculer chaque nombre triangulaire, ce qui prend également un temps O(tn), où tn est le résultat (le dernier que nous calculons réellement). Compte tenu de cela, approximativement la complexité temporelle de l'ensemble de l'algorithme devrait être O(tn*n).  Puisque   devient l'argument ou notre fonction, et que nous exécutons au plus   boucles à l'intérieur, nous pouvons réécrire la complexité temporelle comme O(tn*tn/2) = O(tn²/2) = O(tn²). Donc une   , malheureusement ! tn n/2 solution en temps quadratique  J'ai été surpris que même si l'algorithme est d'environ ce genre de complexité, il fonctionne néanmoins assez rapidement. Pour donner un résultat sur ma machine (AMD Ryzen 5, moy. ck. 2700 MHz), il a fallu 322,564227 ms.  Essayer de trouver le premier nombre triangulaire dépassant 1000 diviseurs a cependant pris 3,827144472 secondes, il est donc clairement visible que la consommation de temps augmente rapidement.   Conclusion  Nous l'avons finalement fait! J'espère que vous avez apprécié l'article, et j'espère que vous pourrez en tirer quelque chose d'intéressant : si c'est le cas, veuillez laisser un applaudissement ou deux et partager l'article avec quelqu'un qui pourrait être intéressé par ce sujet !  Un grand bravo à ProjectEuler encore une fois pour le travail fantastique : je veux vraiment vous suggérer d'aller voir ce qu'ils peuvent offrir ; Je suis sûr que vous le trouverez super intéressant !  Et comme toujours, merci d'avoir lu.   Nicolas

Read My Stories

Cet audio est produit dans la langue originale de l'histoire !

Problème de codage quotidien : nombres triangulaires et grands diviseurs

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Vous voulez gagner un concours d’écriture HackerNoon ? Voici ce que recommandent les gagnants du concours #crypto-api

Libérer la puissance de l’IA. Une revue systématique des techniques de pointe : résumé et introduction

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Vous voulez gagner un concours d’écriture HackerNoon ? Voici ce que recommandent les gagnants du concours #crypto-api

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps