Travaux Dirigés : Algorithmique et
Programmation en C
Exercice 11 – Somme des carrés sans multiplication
Énoncé
On veut écrire un algorithme serie qui prend en entrée un entier
strictement positif ℓ, puis calcule et affiche la somme des ℓ premiers car-
rés, sans utiliser l’opérateur de multiplication ni la fonction d’élévation
au carré.
Objectif :
S(ℓ) = 12 + 22 + 32 + · · · + ℓ2
Exemple attendu : pour ℓ = 5, l’algorithme devra afficher :
S(5) = 1 + 4 + 9 + 16 + 25 = 55
1. Relation de récurrence
Pour tout entier k > 0, on peut exprimer le carré de k en fonction
du carré de k − 1 par la relation suivante :
k 2 = (k − 1)2 + 2k − 1
Justification :
k 2 − (k − 1)2 = 2k − 1
Cette relation permet de calculer les carrés successifs en partant de
12 = 1 et en accumulant les différences.
1
TD Algorithmique en C Exercice 11
2. Algorithme en pseudo-code
Entrée : un entier ℓ > 0
Sortie : la somme S(ℓ) des carrés de 1 à ℓ, et le détail des termes
Début
1. Lire ℓ
2. somme ← 1
3. carre ← 1
4. Afficher ”S(ℓ) = 1”
5. pour k de 2 à ℓ faire
– carre ← carre + 2 × k − 1
– somme ← somme + carre
– Afficher " + " et le carre
6. Afficher " = " et somme
Fin
3. Programme C ANSI
1 # include < stdio .h >
2
3 int main () {
4 int l ;
5 printf ( " Entrez ␣ un ␣ entier ␣ strictement ␣ positif ␣ : ␣ ") ;
6 scanf ( " % d " , & l ) ;
7
8 if ( l <= 0) {
9 printf ( " Erreur ␣ : ␣ l ␣ doit ␣ etre ␣ strictement ␣ positif .\ n
");
10 return 1;
11 }
12
13 int somme = 1;
14 int carre = 1;
15
16 printf ( " S (% d ) ␣ = ␣ 1 " , l ) ;
17
18 for ( int k = 2; k <= l ; k ++) {
19 carre += 2 * k - 1;
2
TD Algorithmique en C Exercice 11
20 somme += carre ;
21 printf ( " ␣ + ␣ % d " , carre ) ;
22 }
23
24 printf ( " ␣ = ␣ % d \ n " , somme ) ;
25 return 0;
26 }
Listing 1 – Somme des carrés sans multiplications
4. Exemple d’exécution
Entrez un entier strictement positif : 5
S(5) = 1 + 4 + 9 + 16 + 25 = 55
