J'ai deux chiffres, Y a-t-il un algorithme efficace pour cela?
Je crois qu'il est temps de reformuler mon problème et d'être plus clair . Ce n'est pas sur des entiers ...
Donc, dites que nous avons deux chiffres Je vous remercie tous pour votre temps et vos efforts, c'est vraiment gentil! x1 et x2 . Pour un numéro y , je veux calculer le diviseur commun de x1 et x2 aussi près que possible de y .
x1 et x2 . Dis, l'utilisateur entrait un numéro y . Ce que je veux trouver, c'est un numéro Y ' proche de y de sorte que x1% y' et x2% y '< / Code> sont très petits (plus petit que 0,02 , par exemple, mais permettent d'appeler ce numéro limite ). En d'autres termes, je n'ai pas besoin d'un algorithme optimal, mais une bonne approximation.
4 Réponses :
x1 code> et x2 code>. li>
- Si
gcd retourne gcd code> li>
- meilleure réponse actuelle est
gcd code>, avec une meilleure distance de GCD - Y CODE>. LI>
- itérale à travers tous les numéros Y +/- [0 ... Meilleur Distance] Li>
- renvoie le premier entier qui est un multiple des deux
x1 code> et x2 code> li>
Pour trouver le GCD P>
public int closestDivisor( int a, int b, int y ){
int gcd = getGCD( a, b );
if( gcd <= y ) return gcd;
int best = gcd - y;
for( int i = 0; i < best; i++ )
{
if( gcd % (i-y) == 0 ) return i - y;
if( gcd % (i+y) == 0 ) return i + y;
}
return gcd;
}
-1 Votre algorithme est essentiellement la simple solution de force brute, mais avec des étapes supplémentaires. Vous ne voulez que vérifier tous les numéros y + - n jusqu'à ce que vous en trouviez un.
@ Blueraja-dannypflughoeft si y est significativement supérieur à gcd (x1, x2) alors c'est une optimisation très pratique.
Je voudrais bien voir le raisonnement sur la raison pour laquelle je suis passé voté pour cette réponse. La solution fonctionne et il n'y a pas une solution simple plus efficace. S'attendre à une balle d'argent qui n'existe pas ne semble pas être une bonne raison de rejeter ma réponse.
Juste pour que vous sachiez, je n'ai pas voté (j'avais vraiment voté)! Il y a toujours beaucoup d'électeurs de bas sur ce site. Je suis très reconnaissant pour vous des efforts.
Je pense que vous pouvez le faire par algorithme gourmand, d'abord trouver GCD par des algorithmes communs Nom It d (qui est calculable dans le temps logarithmique) puis trouver des facteurs de d chacun Divisez le temps d au plus petit facteur disponible (Créer d ') et comparez | d'-y | avec | dy | < / code> si plus petit continue de cette manière (et remplacer d ' avec d ), sinon, multipliez d' avec le plus petit facteur éliminé, et encore comparer sa distance à y.
puis trouver des facteurs de d - Comment vous attendez-vous à le faire rapidement? Tant que nous prenons en compte, nous devrions prendre en compte les nombres plus petits ( x1 et x2 ), après quoi trouver le LCM est trivial.
@ Blueraja-DannyPflughoeft, peut-être que je ne peux pas comprendre votre question, mais trouver des facteurs de nombre spécifique n'est pas si difficile, cela nécessite juste une itération à SQRT (D), et je pense dans la plupart des cas d est petit nombre, de sorte que ce facteur n'est pas difficile, il peut également être fait plus rapidement avec un tamis comme l'algorithme.
@Saeed: Comment pouvez-vous assumer d est un petit nombre? L'affacturage est considéré comme un problème difficile - le cryptage public de RSA repose sur ce fait!
@ Blueraja-dannyypflughoeft, si vous voulez parler académiquement oui, cela semble être difficile, mais tout d'abord, ce site n'est pas à dessein scientifique, alors les algorithmes qui ne sont pas liés à la taille du bit n'est pas mauvais dans la plupart des cas, je ne le fais pas Think OP fonctionne avec des entiers de 200 chiffres, ce faisant que l'affacturage n'est pas un problème difficile dans ce cas, s'il s'agissait d'un problème scolaire diplômé, il devrait ajouter des informations sur les recherches sur les opérations de l'OPS dans ce domaine, mais semble que c'est comme une question sous-traitante, et il ne semble pas besoin de travailler dur. OP peut déterrer qu'il a 200 chiffres ou non.
@ Blueraja-dannyypflughoeft, j'espère que vous offrirez une meilleure réponse que la mienne, puis me dis que ma réponse est lente et je peux alors comprendre votre vote, votre bowvote est actuellement vraiment incroyable!
-1 Ce n'est pas un algorithme efficace, étant donné que tous les facteurs peuvent nécessiter un effort herculéen (prendre N comme un nombre composite formé par le produit de deux nombres premiers à 400 chiffres, par exemple, et il n'y a pas à peu près tout à fait va finir dans une période raisonnable)
@ Saeedamiri- Je m'excuse de vous avoir bouleversé, mais s'il vous plaît ne vous criez pas dessus. J'ai lu les commentaires et mon commentaire devait indiquer que même après avoir répondu au poste de Raja bleu que je suis en désaccord avec votre raisonnement. J'ai révélé cette réponse et non les autres parce que cela avait toujours un score non négatif, et je voulais préciser la communauté que je pensais que cette réponse était incorrecte.
@TemplatetyTypedef, "Ce n'est pas un algorithme efficace" de nouveau drôle, j'ai défié blueaja pour une meilleure solution il y a deux heures, et il n'a toujours pas offert une meilleure solution, mais je vous défie également de trouver une meilleure solution que la mienne puis dire "ceci L'algorithme efficace n'est-il pas efficace maintenant, car c'est mieux que d'autres algorithmes fournis ici, si vous pouvez trouver une meilleure réponse, vous venez bien venir.
@ SaeedamirI- La question de l'OP est de savoir si un algorithme efficace existe. Ceci est un problème ouvert. Produire un algorithme inefficace pour le problème ne répond pas à la question. Il vaut mieux que pas d'algorithme du tout, et je suis d'accord avec vous sur ce point, mais ce n'est pas une réponse à la question de l'OP.
Laissez-nous Continuer cette discussion en chat
@Saeedamiri J'ai suscité votre réponse parce que je crois que les gens abusent le vote en baisse sur cette question. Il n'y a pas d'algorithme parfait pour cela, mais votre solution réduit la complexité sur la solution de force brute simple.
Saeed Amiri, laissez-moi simplement dire que j'apprécie vraiment votre réponse et votre effort, et je vous ai précipité pour cela. Merci!
@Korion, merci, je pense que les bowvotes ici sont juste des malentendus.
@Korion, je veux dire GCD, j'ai écrit LCM, désolé pour cette erreur, maintenant je vois ça. (Ma nommée avait raison, d pour GCD mais la première ligne était incorrecte).
@Real: J'ai bownvoché parce que son algorithme d'origine était un ordre de grandeur plus lentement que ce qu'il a actuellement écrit
@Blueraja - Danny Pflughoeft, il était évident que je parlais de GCD non pas LCM, au moins je sélectionne d pour GCD non LCM et ceci était typo (comment je peux vous inviter à un défi quand mon algorithme est Slow?), mais peu importe, vous pouvez l'écrire avant de savoir non plus de 2 jours. Aussi maintenant, vous pouvez supprimer votre bowvote.
Je pense qu'il n'y a pas d'algorithme efficace (polynôme-time) connu pour ce problème car il existe une réduction de temps polynomial de Factorisation entière à ce problème. Comme il n'existe aucun algorithme de temps polynomial connu pour la factorisation entière, il ne peut y avoir d'algortihm connu pour votre problème non plus, car sinon, nous aurions effectivement un algorithme de temps polynomial pour la factorisation entière.
Pour voir comment cela fonctionne, supposons que vous ayez un numéro n que vous souhaitez facturer. Maintenant, en utilisant n'importe quel algorithme que vous souhaitez, trouvez le facteur commun de N et N le plus proche de √n. Étant donné qu'aucun diviseur non trivial de N ne peut être supérieur à √n, cela trouve soit (1) le plus grand entier qui divise N, ni (2) le nombre 1 si n est prime. Vous pouvez ensuite diviser n par ce numéro et répéter pour produire tous les facteurs de n. Étant donné que n peut avoir au maximum les facteurs (log n), cela nécessite au plus de nombreuses itérations du solveur pour votre problème, nous avons donc une réduction du temps polynomial de la factorisation entière à ce problème. Comme mentionné ci-dessus, cela signifie que, du moins dans la littérature ouverte, aucun algorithme classique efficace est connu pour résoudre ce problème. On pourrait exister, mais ce serait un résultat vraiment extrêmement important.
Désolé pour la réponse négative et espérons que cela vous aidera!
Le diviseur commun le plus proche de 0 est facile: 1 (sauf n = 0 );) Faites-le le diviseur le plus proche de n ^ 0,4 ou donc, alors vous avez un niveau généralement difficile. problème.
@ Danielfischer- ah, oui. J'ai supposé que le problème signifiait "diviseur non trivial". Je vais mettre à jour en conséquence.
Ce n'est pas une réponse à la question, c'est comme si vous parlez: il n'y a pas de manière rapide pour le TSP, alors surveillez votre moniteur et n'essayez rien. La relation de cette question et de cette integer la factorisation était évidente et je l'utilise dans ma réponse. C'est drôle que vous obteniez 5 uppote pour avoir dit rien (peut être une chose spéciale pour certains utilisateurs de savoir qu'il est lié à la factorisation entière! Ce que j'ai dit une heure avant de vous et que je l'utilise).
@ Saeedamiri- C'est en effet une réponse - la question de l'OP est "Y a-t-il un algorithme efficace?" Et j'ai fourni une preuve formelle que le problème est équivalent à un problème ouvert connu. Cela ne dit pas de ne pas essayer; Cela dit simplement que la tentative de résoudre ce problème est susceptible d'être difficile, tout comme une tentative de résoudre un problème complet de NP. De plus, cela ne vole pas votre réponse; Je suis indépendamment arrivé à cette conclusion et l'officialisa de manière à montrer comment la dureté transporte.
Non, ce n'est pas la réponse, si vous voulez avoir une réponse, vous pouvez vous reporter à des algorithmes les plus efficaces à la factorisation entière (peu importe ce n'est pas des solutions P), qui a également déclaré que la factorisation entière est la NPC? Ce n'est pas évident, c'est dans NP ou CO-NP, vous dites que c'est dans NPC?
@ Saeedamiri- Mes excuses - Je ne voulais pas insinuer que ceci est un problème complet (ce n'est pas). J'utilisais le NP-Compétenance comme une illustration. Plus important encore, je suis désolé de vous déranger. Je ne veux pas qu'il y ait des hostilités entre nous - je respecte votre intelligence et je suis très impressionné par la qualité de vos réponses sur ce site.
J'ai accepté cette réponse parce qu'elle répond à cette question. N'oubliez pas que j'ai demandé un algorithme d'approximation dans une question distincte: Stackoverflow.com/questions/9210664/...
Ceci est efficace, car je peux l'obtenir:
from fractions import gcd
primes=[i for i in range(2,1000) if all(i%j!=0 for j in range(2,i))] #ensure you have enough primes.. (can improve efficency here)
def f(x1,x2,y):
_gcd=gcd(x1,x2)
if _gcd==1:
return 1
factors=(i for i in range(2,_gcd+1) if _gcd%i==0) #can improve efficiency here.. e.g. only go up to root(gcd)
r1=999999999
r2=999999999
for i in factors:
r1=min(r1,y%i)
r2=min(r2,i-y%i)
return y-r1 if r1<=r2 else y+r2
print f(8,4,3)
print f(16,12,5)
print f(997,53,44)
print f(2300*2,2300*3,57)
"""
2
4
1
56
"""
Je pense qu'il vaut mieux le demander dans un nouveau fil.
Ok Saeed, j'ai fait ça: Stackoverflow.com/questions/9210664/...