Algorithmique impérative/Somme des n premiers entiers

Algorithmique impérative
PyQt
PyQt
Sommaire
Théorie de l'algorithmique impérative
  1. Qu'est ce qu'un algorithme impératif Fait à environ 50 %
  2. Les types, les opérateurs et les expressions Fait à environ 50 %
  3. Les constantes, les variables Fait à environ 50 %
  4. Les instructions, les blocs d'instructions Fait à environ 50 %
  5. L'assignation Fait à environ 50 %
  6. Les exécutions conditionnelles Fait à environ 50 %
  7. Les structures itératives Fait à environ 50 %
  8. Les tableaux Fait à environ 50 %
  9. Les procédures et les fonctions Ébauche
  10. Le type enregistrement Fait à environ 50 %
  11. L'algorithme au final : vue d'ensemble En cours
  12. Exercices En cours
Outils de travail
Problèmes posés, analysés, résolus et commentés
Annexes
Modifier ce modèle ce sommaire

Problématique

modifier

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

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

Solution

modifier

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).

Cependant, la boucle peut partir de 1 si elle ne s’exécute pas pour n=0. Dans ce cas, la somme sera 0 (valeur initiale de la variable somme).

Remarque

modifier

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...)