Discussion :

[Jim69]

Bonjour à tous,

Je suis actuellement en prépa scientifique et je débute donc la programmation sur Python.
J'ai un exercice à faire et je n'arrive pas à le mener à terme.

L'exercice :

On pose u[0]=1 et, pour tout n dans N,

u[n+1] = 0.5* (u[n] + (n+1)/(u[n]))
et v[n] = somme de : 1/(u[k])^5 pour k allant de 0 à n

Ecrire une fonction f(n) retournant la valeur de v[n]. On fera attention à ce que le calcul de f[n] ne demande pas trop de (re)calculs inutiles. Ainsi, f(10**6) doit être calculer en largement moins d'une minute.


Ce que j'ai déjà fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def suite_u(n): 
    u = 1
    for k in range(n):
         u = 0.5*(u + (k+1)/u)
    return u

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def f(n):
    v = 0
    for t in range(n+1):
         v += 1/(suite_u(t))**5
    return v

Cependant, mon problème est que ces algorithmes ne sont pas assez optimisés pour répondre à la nécessité temporelle associée au calcul de f(10**6).
Pourriez-vous donc m'indiquer des techniques de les optimiser ???
Je suis très novice dans la matière.


MERCI !

[tyrtamos]

Bonjour,

Si j'ai bien compris les 2 formules, le code présenté a 3 problèmes:
- dans la fonction suite_u, il faut que range aille jusqu'à n+1 pour atteindre n
- dans les 2 fonctions, si on part de u0 et v0, la boucle doit commencer à 1 et non 0.
- dans la fonction f, v0=1 et non 0.

Pour optimiser, il y a quelque chose de facile à faire: éviter de recalculer suite_u(n) à chaque boucle pour v.

Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
def fn(n):
    u, v = 1, 1
    for k in range(1, n+1):
        u = 0.5*(u + (k+1)/u)
        v += 1/u**5
    return v

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
n = 5
print(n, "=>", fn(n))
5 => 1.251062944898583

On peut vérifier que ça donne la même chose que les 2 fonctions présentées après les 3 corrections ci-dessus, mais la quantité de calculs est moins grande.

[Jim69]

Je te remercie pour ta réponse. Elle est la clé du succès.