Algorithmique impérative/Somme des n premiers entiers

Un livre de Wikibooks.

[modifier] Problèmatique

Écrire un algorithme sous forme d'une fonction qui calcule la somme des n premiers entiers, n étant passé en paramètre.

Exemple : somme(5) calculera 1+2+3+4+5 et renverra donc 15

[modifier] Solution

Voici une première réponse acceptable :

Function somme(n : entier)
Lexique
  somme : entier (* la somme qu'on complète au fur et à mesure et qu'on retournera à la fin *)
Début
  somme:=0
  POUR i de 0 à n
    somme:=somme+i
  FP
  retourner somme
Fin

Pourquoi partir de 0 et pas 1 ? Cela sert tout simplement à gérer le cas n=0. Cela ne change rien pour les autres cas puisque (en reprenant l'exemple de la problématique) somme(5) va calculer 0+1+2+3+4+5, c'est à dire 1+2+3+4+5 (=15).

[modifier] Remarque

Essayons une analyse un peu plus mathématique du problème :

En fait notre fonction calcule pour n : . L'étude des séries nous apprend que

.

On peut en déduire que la fonction peut s'écrire

Function somme_directe(n : entier)
Début
  retourner (n*(n+1))/2
Fin

Ce qui d'une part est plus simple mais également, comme nous allons le voir, plus efficace.

Simplifions le fonctionnement d'une machine au maximum : supposons qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.

Supposons que nous voulions calculer somme(1000) : Avec somme() : nous allons effectuer :

• 1000 incrémentation de i
• 1000 sommes somme+i
• 1000 assignation

Soit au moins 3000 calculs.

Avec somme_directe() : nous allons effectuer

• une somme : n+1
• une multiplication n*(n+1)
• une division par 2

Soit 3 calculs.

Conclusion : 3000 calculs pour le premier algorithme, 3 calculs pour le second. La différence entre les deux : le mathématicien qui doit se retrouver en chaque algorithmicien.

Et dire que de nombreux étudiants en informatique sont souvent étonnés de la présence importante de mathématiques durant leur cursus...

(pour info : wikilivres propose des cours de mathématiques...)