Quel est le moyen le plus rapide de le faire?
My simple Aproach: p>
function findBCs(A) {
if (A / 2 != Math.floor(A / 2)) return [];
var solution = [];
var i;
var SR3 = Math.pow(A, 1 / 3);
for (i = 1; i <= SR3; i++) {
var B, C;
C = i;
B = A / (C * (C + 1));
if (B == Math.floor(B)) {
solution.push([B, C]);
}
B = i;
C = (-1 + Math.sqrt(1 + 4 * A / B)) / 2;
if (C == Math.floor(C)) {
solution.push([B, C]);
}
}
return solution;
}
3 Réponses :
Il peut être fait dans de (racine cube (a))
En effet, l'un de vos numéros B et C doit être inférieur à racine cube (a)
Je ne comprends pas cela apparemment trivial O (cube_root (a)) solution ... Pouvez-vous élaborer mieux en donnant de la pseudocode?
Ce python semble fonctionner:
a: 2 -> (b, c): [(1, 1)] a: 4 -> (b, c): [(2, 1)] a: 6 -> (b, c): [(1, 2), (3, 1)] a: 8 -> (b, c): [(4, 1)] a: 10 -> (b, c): [(5, 1)] a: 12 -> (b, c): [(1, 3), (2, 2), (6, 1)] a: 14 -> (b, c): [(7, 1)] a: 16 -> (b, c): [(8, 1)] a: 18 -> (b, c): [(3, 2), (9, 1)] a: 20 -> (b, c): [(1, 4), (10, 1)] a: 22 -> (b, c): [(11, 1)] a: 24 -> (b, c): [(2, 3), (4, 2), (12, 1)] a: 26 -> (b, c): [(13, 1)] a: 28 -> (b, c): [(14, 1)] a: 30 -> (b, c): [(1, 5), (5, 2), (15, 1)] a: 32 -> (b, c): [(16, 1)] a: 34 -> (b, c): [(17, 1)] a: 36 -> (b, c): [(3, 3), (6, 2), (18, 1)] a: 38 -> (b, c): [(19, 1)] a: 40 -> (b, c): [(2, 4), (20, 1)] a: 42 -> (b, c): [(1, 6), (7, 2), (21, 1)] a: 44 -> (b, c): [(22, 1)] a: 46 -> (b, c): [(23, 1)] a: 48 -> (b, c): [(4, 3), (8, 2), (24, 1)] a: 50 -> (b, c): [(25, 1)]
Cela ressemble à une solution O (a).
Étape 1: facteur A
Étape 2: Trouvez le jeu de tous les diviseurs des principaux facteurs d'un.
Étape 3: Pour chaque diviseur C en S, vérifiez si C + 1 divise également. Si cela le fait, B = A / (C * (C * (C * (C + 1)) est une solution. (Cela utilise que C et C + 1 sont coprimiques. Ainsi, si C et C + 1 divisent ALORS C * (C + 1)).
La complexité de cela dépend de la méthode utilisée pour le facteur AEG, si vous mettez en œuvre par exemple Pollard-Rho (qui est relativement simple), la complexité de la mise en œuvre concerne O (A ^ 0.25) dans le pire des cas . Et ce n'est toujours pas la meilleure réponse possible. Il y a bien sûr un meilleur algorithme d'affacturage. De plus, si votre contribution est un cas particulier avec beaucoup de diviseurs, l'affacturage peut être facile et le nombre de diviseurs est le problème de limitation.
L'avantage de cette méthode est bien sûr que vous passerez votre temps sur une fonction généralement utile (c'est-à-dire la factorisation), ce qui simplifiera la résolution d'autres problèmes similaires. Ma propre mise en œuvre de Pollard-Rho à Python a besoin d'un total de 0,03 s pour les 20 exemples de 15 chiffres postés par 6502, qui est déjà au moins une accélération d'un facteur 1000. Des implémentations plus sophistiquées devraient entraîner d'importantes améliorations.
Pour la comparaison, une mise en oeuvre de Python rapide et sale de la méthode O (A ^ (1/3)) proposée par Egor Skriptumoff nécessite des besoins 0.7 pour la même liste. Ceci est bien sûr un bon résultat pour une méthode facile à mettre en œuvre.
Non-sens, le nombre de diviseurs d'un nombre est O (A ^ (C / Loglog (A)) (pour une petite constante C) qui est inférieure à O (A ^ 0,25).
Je ne pense pas que cela fonctionne b ne change jamais
1. Il semble difficile de croire qu'il y a plus de paires répondant à cette exigence. 2. Vous ne pouvez rechercher que ces paires via les diviseurs d'A, mais cela prendrait toujours O (SQRT (A)).
Vous pouvez immédiatement sauter avec un ensemble vide si un numéro impair
@Cisty A = 6 a des solutions (1,2) et (3,1)
@HENRY, oui vous avez raison. Mais y a-t-il d'autres numéros plus importants pour avoir plusieurs solutions?
@Cisty a = 30: (1,5), (5,2), (15,1); Je suppose qu'il y a infiniment de nombreux exemples
Tous les nombres pairs ont une solution C = 1 pour B = A / 2, et pour toute équation, a, 2a, 3a, 4a, ... également satisfaire à un ajustement de B.
Je pense que vous devriez également essayer également Mathematics Stack Exchange.
A = N! A une solution pour C prendre chaque valeur de 1 à N-1, il n'y a donc pas de limite supérieure finie sur le nombre de solutions.
Avez-vous besoin d'effectuer ceci uniquement pour un numéro
A ou sera-ils multiple?@Borisstrandjev J'ai vraiment besoin de beaucoup, mais la question est juste pour une pour la simplifier.
@jbaylina Ce type de simplification est un peu dangereux lors de la poser des questions algorithmiques. Il existe une telle chose que la complexité d'algorithmes amorties - essentiellement en série de requêtes, vous pouvez vous permettre une précalculation de longue durée qui diminuera ensuite la complexité de chaque requête. Quelle est la limite pour la valeur de
a ?@Borisstrandjev Je suis d'accord avec votre commentaire. Dans ce problème, A n'est pas limité et chacun A n'a aucun rapport avec l'autre. C'est pourquoi j'ai simplifié la question. De toute façon, si vous avez une bonne solution pour un ensemble de A