Inscription / Connexion Nouveau Sujet
produits de diviseurs
Bonjour
Etant donner un nombre N et ses diviseurs:{d1;d2;d3;...dn} dans l'ordre, on écarte 1 et N
Le but est de progrmmer à la calculette les produits à deux diviseurs, à trois diviseurs, etc... qui donnent N
exemple:d6*d5=N; d1*d4*d9=N etc...
Y a t-il un théoreme ou une regle mathématiques ou quelquechose comme ça qui permet de d'arrêter la recherche aux produit à trois diviseurs ou à quatre diviseurs etc...
Ce que je veux dire, trouver les produits à p diviseurs qui dépassent N
Merci pour vos commentaires
Bonjour
si N a p diviseurs entiers alors leur produit ne peut depasser N
Je n'ai pas compris le sens ou plutot je l'ai compris comme suit:
diviseurs de 12:{2;3;4;6} on écarte 1 et 12
2*3*4*6>12
le produit des 4 diviseurs dépasse 12 ?
Bonjour,
la question est en fait assez mal posée parce que le diviseur 3 et le diviseur 4 ou 6 par exemple ne sont pas "de même nature"
3 est un diviseur premier de 12
4 ou 6 est un diviseur de 12 mais qui n'est pas premier
étalons en ligne tous les diviseurs premiers de N dans un ordre quelconque
supposons qu'il y ait n diviseurs premiers en tout
ainsi 12 possède 2 diviseurs premiers : 2 et 3 mais le 2 est compté deux fois de sorte qu'ici on va considérer les diviseurs premiers 2, 2 et 3 ce qui fait pour mon propos 3 diviseurs premiers.
il y a entre ces trois diviseurs premiers 2 "séparations" et donc 22 = 4 façons de "grouper" ces diviseurs premiers en mettant ou non et indépendamment ces séparations
2*2*3 (je groupe en un seul diviseur qui est 12, aucune séparation)
2 et 2*3 (je groupe en deux diviseurs 2 et 6, la première séparation seule)
2*2 et 3 (je groupe en deux diviseurs 4 et 3, la seconde séparation seule)
2, 2 et 3 (les deux séparations et 3 diviseurs)
choisir un autre ordre pour ranger les diviseurs premiers au départ donnera ou pas des décompositions différentes.
si le nombre N se décompose ainsi en facteurs premiers pi d'exposants ei le nombre totale de facteurs premiers qui sont à considérer dans ce procédé est la somme des exposants de tous ces facteurs premiers
12 = 22
31 somme des exposants 2+1, on s'arrêtera à un produit de 3 facteurs
72 = 2332, on s'arrêtera à un produit de 3+2 = 5 facteurs
reste que les diviseurs à choisir ne sont pas n'importe quoi puisque il faut prendre dans le principe énoncé précédemment chaque facteur premier "individuel" une fois et une seule en tout !
dans le cadre de l'exo, on ne sait rien du tout des diviseurs premiers de N, on a juste la liste de ses diviseurs, de sorte que ces considérations sont inutiles de toute façon.
on choisit de toutes les façons possibles 1 seul, 2, 3, 4, 5, etc etc diviseurs de la liste et on teste si le produit est N ou pas
(on rejette ce choix si c'est différent de N, et ce sans état d'ame aucun)
donc ta limite ce sera .. brutalement et sauvagement le nombre de diviseurs de la liste
après que l'on cherche à améliorer cet algorithme par application du principe de choix intelligent des diviseurs premiers pourquoi pas, mais c'est à mon avis aller bien au dela de ce qui est demandé.
salut
si d est un diviseur de n alors n = d * (n/d) donne tous les produits à deux diviseurs de n
il suffit de ne pas prendre d = 1 ou d = n
généralisation : produit de k diviseurs donnant n
on peut supposer les diviseurs de n ranger dans une liste d()
1 :: choisir un diviseur de n d (différent de 1 et n)
2 :: choisir un diviseur de n/d (différent de 1)
3 :: répéter k - 2 fois l'opération 2 ::
4 :: si ça ne marche pas retourner en 1 ::
alors le produit ce ces k nombres donne n ...
le défaut de cette méthode est là :
choisir un diviseur de n/d
on ne dispose pas de cette table des diviseurs de n/d, seulement de la table des diviseurs de n
donc il faut la "fabriquer"
ou alors changer complètement notre fusil d'épaule et ne PAS utiliser la table des diviseurs de N du tout
(elle est donnée, elle n'est pas calculée par l'algorithme !!)
c'est à dire qu'on la calcule elle aussi au fur et à mesure, exactement par le même algorithme utilisé en même temps pour calculer les diviseurs de n/d, récursivement.
à noter toutefois que ce "récursivement" fait qu'il est impossible de savoir quand on va s'arrêter, ni combien de diviseurs on prend et que toutes les boucles imbriquées seront des "tant que"
avec en plus une gestion dynamique d'un tableau listant tous les diviseurs pris au fur et à mesure de leur "choix" et du retour en arrière pour un autre choix d'un diviseur de n/d
(la "pile" de la récursion en fait)
évidemment par rapport à la méthode "bourrin" de choisir brutalement des diviseurs dans la liste donnée et de les multiplier "pour voir", l'algorithme est bien plus efficace, mais au prix d'une complication bien plus grande !!
(ta description planque bien trop de détails pour qu'on puisse en juger, mais réaliser pratiquement ton algorithme fera mettre le doigt sur toute ces histoires de récursion)
certes oui .... c'est très théorique et ça peut cacher des choses ....
considérons que nous ayons la liste des diviseurs (qu'il n'est pas difficile de programmer de toute façon) et qui ne pose aucun pb ...
comme tu l'as remarqué il est important d'avoir les premiers on peut aussi programmer la décomposition d'un entier en produit de facteurs premiers .... on 'arrête à aux premiers < et du moins obtenir ces premiers effectivement ...
en considérant 2 et 3 puis les entiers et leur puissance correspondante (je l'ai fait avec mes spe)
on peut donc au départ avoir ou construire :
la table des diviseurs
la table des facteurs premiers avec leur exposant ...
.... (temps de réflexion)
en fait non je ne vois pas où est le pb :: tout diviseur de n/d est un diviseur de n !!!!
il suffit donc de le choisir dans la table avec la condition < n/d ....
pardon je me suis mal exprimé :
dans la table des diviseurs de n il y a des diviseurs de n/d ... sauf si n/d est premier ...
dans la table des diviseurs de n il y a des diviseurs de n/d
on prend un élément de cette table et il est tout de même indispensable de s'assurer que c'est bien un diviseur de n/d
ça accélère la recherche des diviseurs de n/d puisque au lieu de chercher tous les "candidats" diviseurs de n/d parmi l'ensemble des nombres entiers (plus ou moins, et jusqu'à
(n/d)) on restreint cette recherche à des nombres dans une table qu'on connait déja...
de toute façon tu n'avais pas mis les détails
je ne critique pas ton algorithme en lui-même c'est une très bonne idée dans l'absolu. juste que justement c'est "ces détails" qui vont le rendre plus compliqué que nécessaire par rapport à un truc brut de décoffrage qui consiste à prendre des diviseurs tout court de la table donnée sans trop d'état d'ame...
même si un tel algorithme "brutal" va calculer des "essais" nombreux et infructueux en plus des bons
écrire un algorithme qui ne donne directement que les bonnes décompositions sans jamais en essayer de "mauvaises" n'est pas simple du tout.
et ça passe par une décomposition en nombres premiers et pas juste par ce qui est donné dans l'énoncé : la table des diviseurs tout court de n, qui deviendrait alors inutile.
Bonjour et merci pour vos réponses
J'ai lu un peu vos réponses mais c'est un peu plus théorique pour moi mais je prendrai du temps pour essayer de comprendre.
Vous avez fait allusion à la liste donnée des diviseurs de N, cette liste je l'obtiens facilement par un algorithme un peu "brutal" tout simplement en divisant N par 2, 3 ,4 etc... jusqu'à N/2
Si on peut s'en passer cela n'e présente aucun problème pour moi.
bien sur qu'il faut faire un test pour un diviseur de d/n ... mais ce n'est pas si long .... puisqu'on en cherche dans les diviseurs de n ....
et bien sur je ne voulais pas mettre tous les détails ... seulement le principe ...
mais l'idée est simple et à mon très efficace voire même tout aussi efficace sinon plus qu'avec la décomposition en nombre premier ....
on choisit un diviseur d dans la liste
on choisit un diviseur d' dans la liste distinct de d
on vérifie qu'il divise d/n .... sinon on en choisit un autre ...
et ainsi de suite ...
maintenant pour le choix il y a deux cas : on le fait au hasard ... et ça peut être très long ...
ou on le fait avec de l'ordre ...
on choisit un diviseur d' dans la liste distinct de d
avec 12, on oublierait ainsi le produit 2
23
une possibilité de déroulement d'un algorithme basé sur ce principe :
liste des diviseurs de 12, 1 et 12 exclus : 2, 3, 4, 6, triés par ordre croissant
1er diviseur = 1er choix = 2, reliquat n/d = 12/2 = 6
2ème diviseur = 2 aussi (on part du même !!) il divise 6, reliquat n/d = 6/2 = 3
3ème diviseur = 2 encore, il ne divise par 3
3ème diviseur = suivant = 3, il divise 3, reliquat 3/3 = 1, solution : on a un produit de trois diviseurs 2x2x3
pas d'autre choix possible pour le 3ème diviseur car le reliquat serait < 1, on remonte au 2ème diviseur
2ème diviseur = choix suivant = 3, reliquat = 6/3 = 2
impossible de chercher des diviseurs suivants car 3 est > reliquat
2ème diviseur = choix suivant = 4, ne divise pas 6
2ème diviseur = choix suivant = 6, divise 6, reliquat = 1, solution : produit de deux diviseurs 2x6
pas d'autre choix possible pour le 2ème diviseur (le reliquat deviendrait < 1)
1er diviseur = choix suivant = 3 reliquat = 12/3 = 4
2ème diviseur = 3 aussi ne divise par 4
2ème diviseur = choix suivant = 4 divise 4, reliquat = 1, solution : produit de deux diviseurs 3x4
pas d'autre choix possible pour le 2ème diviseur (le reliquat deviendrait < 1)
1er diviseur = choix suivant = 4, reliquat = 12/4 = 3
impossible de chercher des diviseurs suivants car 4 est > reliquat
fin de l'algorithme (plus de choix possible pour le 1er diviseur et il n'y a pas de diviseurs avant le 1er)
on a toutes les solutions une fois et une seule, et "triée par ordre lexicographique"
Annuler
connectez vous