La tâche est de trouver la somme de l'équation donnée n et a . Donc pour l'équation 1a + 2a ^ 2 + 3a ^ 3 + ... + na ^ n , nous pouvons trouver le n-ième élément de la séquence avec la formule suivante (à partir de l'observation): < / p>
n-ième élément = a ^ n * (n- (n-2) / n- (n-1)) * (n- (n-3) / n- (n-2)) * ... * (n / (n-1))
Je pense qu'il est impossible de simplifier la somme de n éléments en modifiant la formule ci-dessus en une formule de somme. Même si c'est possible, je suppose que cela impliquera l'utilisation de l'exposant n , qui introduira une boucle à n temps; amenant ainsi la solution à ne pas être O (log n). La meilleure solution que je puisse obtenir est simplement de trouver le rapport de chaque élément, qui est a (n + 1) / n et de l'appliquer à l'élément n-1 pour trouver l'élément n-ième .
Je pense qu'il me manque peut-être quelque chose. Quelqu'un pourrait-il me fournir des solutions?
3 Réponses :
a ^ n peut en effet être calculé dans O (log n) .
La méthode est appelée Exponentiation par quadrillage et l'idée principale est que si vous connaissez a ^ n vous le savez aussi a ^ (2 * n) qui est simplement a ^ n * a ^ n .
Donc, si vous voulez calculer a ^ n (si n est pair), vous pouvez simplement calculer a ^ (n / 2) et multiplier le résultat avec lui-même: a ^ n = a ^ (n / 2) * a ^ (n / 2) . Donc, au lieu d'avoir une boucle jusqu'à n , vous n'avez maintenant qu'une boucle jusqu'à n / 2 . Mais n / 2 est juste un autre nombre, et peut être calculé de la même manière, ne faisant ainsi que la moitié des opérations. Réduire de moitié le nombre d'opérations à chaque fois conduit à la complexité logarithmique.
Comme mentionné par @Sopel dans le commentaire, la série peut être écrite comme une simple équation / fonction :
a * (n * a^(n+1) - (n+1) * a^n + 1)
f(a,n) = ------------------------------------
(a- 1) ^ 2
J'ai supposé qu'une fois que vous savez cela, vous pouvez l'appliquer à la forme simplifiée de la série ci-dessus. Est-ce que le contrevenant pourrait expliquer la raison du vote négatif, ai-je dit quelque chose d'incorrect?
Cela ne répond pas à la question qui a été posée
@MattTimmermans Comment ça ne marche pas? La formule de somme est une question mathématique hors sujet pour ce site. Le plus gros problème, et la vraie question à mes yeux, était que OP pensait que a ^ n ne pouvait être calculé qu'en temps linéaire. Je ne pense pas que les réponses soient censées écrire l'intégralité de l'implémentation d'une question, mais simplement donner des pointeurs sur où chercher / aller ensuite pour que l'OP puisse mieux comprendre la solution: " Même si c'est possible, je suppose que cela impliquera l'utilisation de l'exposant n, qui introduira une boucle à n temps, faisant ainsi que la solution ne soit pas O (log n). "
Et la formule était également liée dans le commentaire de WolframAlpha.
Votre réponse ne fournit que l'une des au moins 2 informations essentielles nécessaires pour résoudre ce problème. Comment vous pouvez appliquer l'exponentiation en quadrillant pour générer la séquence requise n'est pas du tout évidente - surtout pas évidente pour quelqu'un qui ne sait pas comment faire l'exponentiation en quadrillant. Vous avez répondu à une question à laquelle vous saviez comment répondre, mais ce n'est pas la question qui a été posée.
Je suppose que a, n sont des entiers non négatifs. La formule explicite pour a> 1 est
0 <-> 0 0 <-> 0 0 <-> 0 0 <-> 0 0 <-> 0 0 <-> 0 0 <-> 0 1 <-> 1 3 <-> 3 6 <-> 6 10 <-> 10 15 <-> 15 0 <-> 0 2 <-> 2 10 <-> 10 34 <-> 34 98 <-> 98 258 <-> 258 0 <-> 0 3 <-> 3 21 <-> 21 102 <-> 102 426 <-> 426 1641 <-> 1641 0 <-> 0 4 <-> 4 36 <-> 36 228 <-> 228 1252 <-> 1252 6372 <-> 6372 0 <-> 0 5 <-> 5 55 <-> 55 430 <-> 430 2930 <-> 2930 18555 <-> 18555
Elle peut être évaluée efficacement dans O (log (n)) en utilisant
carré et multiplier pour a ^ n .
Pour dériver la formule, vous pouvez utiliser les ingrédients suivants:
a = 1 . Vous pouvez maintenant simplement calculer:
for (a <- 0 to 5; n <- 0 to 5) {
println(s"${slow(a, n)} <-> ${fast(a, n)}")
}
Ceci est juste une simple expression arithmétique avec a ^ n , qui peut être évalué en O (log (n)) temps en utilisant le carré et multiplier.
Cela ne fonctionne pas pour a = 0 ou a = 1 , il faut donc traiter ces cas spécialement: pour a = 0 il suffit de renvoyer 0 immédiatement, pour a = 1 , vous renvoyez n * (n + 1) / 2 .
Scala pour tester la formule:
def slow(a: Int, n: Int): Int = {
def slowPow(a: Int, n: Int): Int = if (n == 0) 1 else slowPow(a, n - 1) * a
(1 to n).map(i => i * slowPow(a, i)).sum
}
Version plus lente, mais plus simple, à titre de comparaison:
def fast(a: Int, n: Int): Int = {
def pow(a: Int, n: Int): Int =
if (n == 0) 1
else if (n == 1) a
else {
val r = pow(a, n / 2)
if (n % 2 == 0) r * r else r * r * a
}
if (a == 0) 0
else if (a == 1) n * (n + 1) / 2
else {
val aPowN = pow(a, n)
val d = a - 1
a * (n * aPowN * a - (n + 1) * aPowN + 1) / (d * d)
}
}
Je ne sais pas comment obtenir la formule pour a> 1 . Je comprends l'exponentiation en quadrillant maintenant, mais je ne sais pas comment obtenir la formule ci-dessus. Je ne peux pas utiliser directement une formule de somme de séries géométriques car le rapport est différent pour chaque élément.
Oh, la formule est-elle obtenue en manipulant l'équation? J'ai multiplié les deux côtés par (1 - a) pour obtenir la formule que vous avez donnée. Est-ce la bonne façon cependant? J'ai l'impression que c'est plutôt une coïncidence que je puisse obtenir la formule en multipliant les deux côtés avec (1-a) et en simplifiant l'équation à partir de là. Je veux dire, comment savoir que d'autres problèmes devront peut-être être multipliés par d'autres choses et non par (1-a) ?
@Richard La formule est obtenue par simple calcul. Vous commencez avec la somme d'origine sur la gauche, puis vous effectuez les étapes [1] - [5], et enfin vous obtenez une expression arithmétique simple qui donne exactement les mêmes nombres que la formule de somme d'origine. Je n'ai utilisé (1-a) nulle part, il semble que ce soit juste un facteur qui apparaît dans le dénominateur après avoir appliqué la formule de série géométrique. Si vous ne comprenez pas certaines des étapes, vous devrez spécifier lesquelles ([1] - [5]). Désolé, StackOverflow ne prend pas en charge les formules LaTeX, il est donc typographiquement sous-optimal.
Je ne comprends pas la partie où vous passez de l'étape [3] à l'étape [4]. Formule de série géométrique: a * (r ^ n - 1) / (r-1) , non? Donc, dans la série ci-dessus, nous avons a ^ 0 ie 1 + a ^ 1 + a ^ 2 + a ^ 3 + ... + a ^ n - 1 , et en biffant le 1 s, nous avons a ^ 1 + a ^ 2 + ... + a ^ n . Par conséquent, un c'est-à-dire le premier élément est un et le ratio est également un . Nous devrions avoir la formule a * (a ^ n - 1) / (a-1) ? Le vôtre est différent du mien, je me suis embrouillé là-bas.
J'ai obtenu votre formule en utilisant une méthode différente: celle qui inclut la multiplication de (1-a) . J'ai terminé l'exercice et posté mon code ici: gist.github.com/TakeNoteIAmHere/… . Le calcul de la formule se trouve à la ligne 23-29.
@Richard Je pense que vous confondez le a de votre formule avec le a de la formule de wikipedia: votre a voici leur r là-bas. La formule de la série géométrique est sum_ {i = 0} ^ na ^ i = (a ^ {n + 1} - 1) / (a - 1) , c'est ce que j'utilise entre les étapes [3] et [4]. Notez que la formule commence à i = 0 , nous avions donc besoin de a ^ 0 = 1 quelque part. Heureusement, nous pouvons simplement ajouter cette constante de nulle part, car sous la différenciation d / da , les constantes n'ont tout simplement pas d'importance. J'ai essayé de l'exprimer en ajoutant +1 , puis en soustrayant immédiatement -1 , puis en différenciant la constante.
Je vois! D'accord, je comprends maintenant. Je pense que vous auriez dû toujours inclure la partie -1 pour l'étape [4] et la faire disparaître après la dérivation à l'étape [5] sur votre réponse avant-modifiée. Cela m'a dérouté. Bref, je comprends le concept, merci! Qu'en est-il de ma façon de formuler l'équation, est-elle fiable (c'est-à-dire est-ce un bon moyen de former une équation comme celle-ci)?
@Richard Je suis revenu au + 1 - 1 avec l'élimination ultérieure de -1 par d / da . C'est surtout une question de goût - tout est égal de toute façon.
Vous pouvez résoudre ce problème, et beaucoup de problèmes similaires, avec l'exponentiation matricielle.
Commençons par cette séquence:
import numpy as np
def getSum(a,n):
# A[n] = a + a^2 + a^3...a^n
# B[n] = a + 2a^2 + 3a^3 +. .. na^n
# V[n] = [B[n],A[n],1]
M = np.matrix([
[a, a, a], # B[i] = B[i-1]*a + A[i-1]*a + a
[0, a, a], # A[i] = A[i-1]*a + a
[0, 0, 1]
])
# calculate MsupN = M^(n-1)
n-=1
MsupN=np.matrix([[1,0,0],[0,1,0],[0,0,1]]);
while(n>0):
if n%2 > 0:
MsupN *= M
n-=1
M*=M
n=n/2
# calculate V[n] = MsupN*V
Vn = MsupN*np.matrix([a,a,1]).T;
return Vn.item(0,0);
Cette séquence peut être générée avec une formule simple:
V[n] = (M^(n-1))V[1]
Maintenant, si nous considérons votre séquence:
V[i] = M*V[i-1]
Nous pouvons générer cela avec une formule qui fait utilisation du précédent:
V[n] = (B[n], A[n], 1)
Si nous faisons une séquence de vecteurs contenant tous les composants dont nous avons besoin:
B[i] = (B[i-1] + A[i-1] + 1) * a
Ensuite, nous pouvons construire une matrice M pour que:
B[n] = a + 2a^2 + 3a^3 ... + na^n
Et ainsi:
A[i] = a*(A[i-1] + 1)
La taille de la matrice étant fixée à 3x3, vous pouvez utiliser exponentiation en quadrillant sur la matrice elle-même pour calculer M ^ (n-1) en O (log n) temps, et la multiplication finale prend un temps constant.
Voici une implémentation en python avec numpy (donc je n'ai pas à inclure de code de multiplication matricielle):
A[n] = a + a^2 + a^3 ... + a^n
Salut Matt, je pense que tu m'as perdu sur la dernière ligne. Je peux obtenir la bonne réponse en utilisant l'autre méthode, mais je me trompe quelque part avec la vôtre. Mon M est une matrice triangulaire supérieure 3x3 de a , et mon V [1] = (a, a, 1) . Où ai-je gâché?
@beaker close, mais le M (3,3) == 1. J'ai ajouté une implémentation.
Ah! Cela a réglé le problème. Merci :)
Les opérations * et * = sont des multiplications élémentaires. Je pense que @ devrait être utilisé à la place.
@ GZ0 Si vous utilisez le type de matrice réel de np.matrix, vous obtenez une multiplication matricielle pour ceux-ci. J'ai testé cela.
@Matt je ne m'en suis pas rendu compte. Merci pour l'explication.
https://www.wolframalpha.com/input/?i=sum+j*a%5Ej,+j%3D1+to+ n. Et vous pouvez faire l'exponentiation dansO (log n)