Aller au contenu

Algorithmique impérative/Somme des n premiers entiers

Un livre de Wikilivres.
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 | modifier le wikicode]

É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

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

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