Différentes façons de calculer 1²+2²+…+n² en Python

La programmation, c’est comme l’amour : il y a plusieurs façons de pratiquer! Et aujourd’hui, j’avais envie d’explorer différentes façons de calculer la somme: $$S_n=1^2+2^2+\cdots+n^2=\sum_{k=1}^n k^2.$$

Méthode 1 : méthode mathématique

C’est la plus économe en terme de mémoire : la complexité en mémoire et en temps est imbattable. Il suffit d’utiliser la formule mathématique: $$S_n=\frac{n(n+1)(2n+1)}{6}$$ que l’on peut démontrer par récurrence (mais ce n’est pas l’objectif de cet article). On trouve alors pour n = 20 par exemple: $$S_{20}=\frac{20 \times 21 \times 41}{6}=2870.$$ Le programme Python est alors le suivant:

n = 20
print ( int( n * (n + 1) * (2*n + 1) / 6 ) )

Méthode 2 : calcul bourrin

Quand on n’est pas trop au fait des formules mathématiques (oui, oui ! vous avez le droit !), on peut faire un calcul itératif « bourrin ». Cela donne alors:

S, n = 0, 20

for k in range(1,n+1):
    S += k ** 2

print(S)

La complexité en mémoire est ici en O(n).

Méthode 3 : programmation fonctionnelle

On peut utiliser la fonction reduce() du module functools. Elle fait partie des outils de la programmation fonctionnelle que l’on voit en Spécialité NSI en Terminale, dès la rentrée 2020.

from functools import reduce
liste = [ k ** 2 for k in range(1,21) ]
print ( reduce(lambda a, x: a + x, liste) )

On construit d’abord une liste des valeurs à sommer, puis on affiche le résultat de la fonction reduce(), celle-ci admettant comme arguments une fonction à 2 arguments (ici, lambda, qui ajoute toutes les valeurs de la liste) ainsi qu’une liste.

Le principe de la fonction reduce() est celui-ci dans notre exemple : on parcourt la liste et on calcule la somme de l’élément sur lequel on est et de l’antécédent (a), qui est le résultat de la somme trouvé précédemment. Le problème avec cette « mécanique », c’est que le premier élément n’admet pas d’antécédent. Ainsi, la fonction reduce() assimile le premier élément à l’antécédent du deuxième… ce qui peut être problématique. Il faut donc créer une liste contenant directement les élements à ajouter (pour notre exemple).

Ainsi, le code suivant:

from functools import reduce

print ( reduce(lambda a, x: a + x ** 2 , range(1,21)) )

fonctionne correctement car 1² = 1 (que la fonction confonde 1 et 1² ne change donc pas le résultat), mais si on souhaite calculer: $$2^2+3^2+\cdots+20^2$$ le code suivant:

from functools import reduce

print ( reduce(lambda a, x: a + x ** 2 , range(2,21)) )

affiche « 2867 » et non « 2869 » comme attendu. En effet, ce dernier code calcule: $$2 + 3^2+ 4^2+ \cdots + 20^2.$$

Méthode 4 : récursivité

La récursivité consiste à définir une fonction dans laquelle on fait appel à cette fonction. Cela donne pour notre exemple:

def somme(n):
    if n == 1:
        return 1

    return n ** 2 + somme( n - 1 )

print( somme(20) )

Méthode 5 : diviser pour régner

Cette méthode consiste à subdiviser un problème en sous-problèmes plus faciles à traiter en utilisant la récursivité.

def somme(L):
    if len(L) == 1:
        return L[0]
    else:
        L1 = L[:len(L)//2]
        L2 = L[len(L)//2::]
        return somme(L1) + somme(L2)

print( somme( [k ** 2 for k in range(1,21) ] ) )

L’idée est ici de découper la liste en 2 sous-listes L1 et L2, et de faire appel à la fonction somme() jusqu’à ce que la liste passée en argument ne contienne qu’un seul élément.