Autorisation : Membre
Nb de messages : 5
Inscrit le : Lun 29 Sep 2014, 18:17
Posté le : Mar 04 Nov 2014, 22:06
Bonjour.
Aujourd'hui je vais vous présenter mon nouveau programme qui sert à obtenir la liste des diviseurs d'un nombre.
Voici le code:
Code
EffEcr
EffListe L1
0->C
Input "DIVISER ",A //9 espaces après "diviser"
For(B,A,1,-1
If non(partDéc(A/B
Then
C+1->C
B->L1(C
End
End
If dim(L1)=2
Disp "PREMIER
L1
Le programme est lent d’exécution si le nombre a diviser est long alors ne négligez pas la RAM de votre calculette
Autorisation : Membre
Nb de messages : 3767
Inscrit le : Lun 19 Oct 2009, 21:25
Posté le : Mar 04 Nov 2014, 23:28
Comme tu dis la durée d'exécution est catastrophique avec des grands nombres. La complexité est en fait d'ordre N (pour trouver les diviseurs de N).
C'est pour ce défaut que je suis tenté de proposer des améliorations pour satisfaire des gens qui passeraient par là sans connaître les autres algorithmes.
En voici un qui utilise la frontière racine carrée pour arrêter le crible. La complexité est donc d'ordre racine carrée de N. Cela croît beaucoup moins vite que N. http://tout82.forumactif.org/t81-trouver-tous-les-diviseurs-d-un-nombre-entier-spe-maths-ts
Le principe est de considérer qu'autant de diviseurs sont supérieurs à la racine carrée que d'autres sont inférieurs. Donc on peut s'arrêter à la racine carrée et déterminer les facteurs qui correspondent au delà. Pour un diviseur A de N, on a forcément le diviseur N/A de N. Et dans une calculatrice TI, les boucles restent assez longues à exécuter, alors on peut préférer calculer les diviseurs manquants d'un seul coup avec une division utilisant la liste d'un seul coup.
Songez cependant que si la racine carrée si est entière, elle est alors un des diviseurs, qui apparaîtra deux fois. Si vous voulez les compter, ne vous trompez pas.
Mais comme certaines des manipulations de m@thieu41 dans la source précédente me semblent superflues. Par exemple se passer d'une variable compteur et lire la dimension de la liste, ou encore déterminer les diviseurs négatifs.
Je propose plutôt cela. C'est le même algorithme, mais je l'implémente en enlevant les choses qui me semblent superflues.
Code
Prompt N
ClrList L1
0->I
// ici sqrt n'est calculée qu'une fois, seulement en langage TI-Basic
For(A,1,sqrt(N //sqrt=squareroot=racinecarrée
If not(fPart(N/A //fPart=partDéc
Then
I+1->I
A->L1(I
End
End
augment(L1,N/L1->L1 // calcul de N/L1 et concaténation, augment()=chaîne()
SortA(L1 // TriCroi(L1)
L1 // écrivez "Pause L1" si ce n'est pas la fin du programme
Le calcul de sqrt est effectué une seule fois parce qu'en TI-Basic les paramètres de For ne sont pas réévalués. Ce n'est pas possible dans d'autres langages. Citons le C pour rester très général. Dans d'autres langages vous utiliserez une variable calculée avant et lue ensuite à la place.
Si on met bien L1 sur la dernière ligne, pas besoin de fonction "Pause L1".
On pourrait chipoter sur l'ordre d'exécution entre concaténer et trier, mais je pense que cela ne changera rien avec des listes de seulement 99 ou 999 termes. (99 sur ti82, 999 sur ti82stats)
---------------------- ti82statfr: 2008, inscrit: 2009, ti84pocketfr: noël2011, ti30xbmultiview: iut 2012-2014
Perfectionniste, manque tact. Pas le temps de tout publier depuis 2011. Répond toujours aux questions. (rédigé juin 2014)
