Calcul de séries avec boucles (factorielle, Fibonacci)

Introduction

Aujourd'hui, nous allons mettre en application toute votre maîtrise des boucles (Pour, Tant que, boucles imbriquées) pour résoudre une nouvelle catégorie de problèmes : le calcul de séries et de suites mathématiques. C'est une application très courante des boucles en algorithmique et en programmation.

L'objectif de cette leçon est de vous rendre capable de résoudre un problème de calcul de série en utilisant une boucle. Nous nous concentrerons sur deux exemples classiques et fondamentaux : le calcul de la factorielle d'un nombre et la génération de la suite de Fibonacci. En maîtrisant ces exemples, vous développerez une méthode de pensée qui vous permettra de résoudre de nombreux autres problèmes similaires.

Cette leçon conclut notre module sur les structures répétitives et consolide tout ce que vous avez appris avant de passer à un tout nouveau concept.

1. Qu'est-ce qu'une Série ou une Suite en Algorithmique ?

En algorithmique, une série ou une suite est simplement une séquence de nombres qui suivent une règle de génération. Notre but est souvent de :

1. Calculer une somme ou un produit de termes : Par exemple, calculer $S=1+2+3+...+N$. Cela repose sur le concept d'accumulateur que nous avons déjà vu.
2. Calculer le N-ième terme d'une suite : C'est le cas lorsque chaque terme dépend du ou des précédents. La suite de Fibonacci en est l'exemple parfait.

Pour résoudre ces problèmes, nous devons "traduire" la règle mathématique en une logique de boucle. La clé est d'identifier :

• Quelles variables sont nécessaires pour conserver l'état d'une itération à l'autre ?
• Comment ces variables doivent-elles être initialisées avant la boucle ?
• Comment doivent-elles être mises à jour à chaque tour de boucle ?

Commençons avec notre premier exemple.

2. Exemple 1 : Le Calcul de la Factorielle

La factorielle d'un entier non négatif $n$, notée $n!$, est le produit de tous les entiers positifs inférieurs ou égaux à $n$.
Par exemple, $5!=5\times 4\times 3\times 2\times 1=120$.
Par convention, $0!=1$.

Pour calculer cela avec un algorithme, nous avons besoin d'un accumulateur de produit.

Analysons la logique pour un nombre n supérieur à 0 :

1. Initialisation : Nous avons besoin d'une variable pour stocker le produit en cours. Appelons-la produit. On ne peut pas l'initialiser à 0 (car tout serait 0), donc on l'initialise à l'élément neutre de la multiplication : 1. produit ← 1.
2. Itération : Nous devons multiplier produit successivement par 1, 2, 3, ..., jusqu'à n. Une boucle Pour est parfaite pour cela.
3. Mise à jour : À chaque tour de boucle, avec un compteur i allant de 1 à n, nous mettons à jour notre accumulateur : produit ← produit * i.

Voici l'algorithme complet en pseudo-code utilisant une boucle Pour :

Algorithme Factorielle
Variables
  n : Entier // Le nombre dont on veut la factorielle
  i : Entier // Le compteur de la boucle
  produit : Entier // L'accumulateur pour le résultat

Début
  Écrire "Entrez un entier positif :"
  Lire n

  Si n < 0 Alors
    Écrire "Erreur : la factorielle n'est pas définie pour les nombres négatifs."
  Sinon Si n = 0 Alors
    Écrire "0! = 1"
  Sinon
    produit ← 1
    Pour i allant de 1 à n Faire
      produit ← produit * i
    FinPour
    Écrire n + "! = " + produit
  FinSi
Fin

Cette structure est un modèle pour tous les problèmes de calcul de produit.

3. Exemple 2 : La Suite de Fibonacci

La suite de Fibonacci est une séquence où chaque nombre est la somme des deux précédents. Elle commence généralement par 0 et 1.

La définition mathématique est :

• $F_0=0$
• $F_1=1$
• $F_n=F_{n-1}+F_{n-2}$ pour $n>1$

Comment calculer le N-ième terme ? Supposons que nous voulions calculer $F_7$.
Nous ne pouvons pas le faire directement. Nous devons calculer $F_2,F_3,F_4,\dots$ jusqu'à $F_7$.
La difficulté ici est que, pour calculer le terme actuel, nous avons besoin de conserver les deux derniers termes calculés.

Voici la logique :

1. Initialisation : Nous avons besoin de trois variables. Disons a et b pour les deux termes précédents, et suivant pour le terme que nous calculons. Pour commencer, a contiendra $F_0$ et b contiendra $F_1$.
   a ← 0
b ← 1
2. Itération : Nous allons boucler de 2 jusqu'à n (car les termes 0 et 1 sont déjà connus).
3. Mise à jour (l'étape clé) : À chaque tour de boucle, nous faisons trois choses dans le bon ordre :
   a. Calculer le terme suivant : suivant ← a + b.
   b. Mettre à jour les "précédents" pour la prochaine itération. L'ancien b devient le nouveau a, et la valeur que nous venons de calculer (suivant) devient le nouveau b.
   a ← b
b ← suivant

C'est comme faire "glisser" les valeurs :

Voici l'algorithme pour trouver le N-ième terme :

Algorithme Fibonacci
Variables
  n : Entier // Le rang du terme à calculer
  i : Entier // Le compteur de boucle
  a, b, suivant : Entier

Début
  Écrire "Entrez le rang du terme de Fibonacci à calculer (n >= 0) :"
  Lire n

  Si n = 0 Alors
    Écrire "F(0) = 0"
  Sinon Si n = 1 Alors
    Écrire "F(1) = 1"
  Sinon
    a ← 0
    b ← 1
    Pour i allant de 2 à n Faire
      suivant ← a + b
      a ← b
      b ← suivant
    FinPour
    // À la fin de la boucle, 'b' contient le N-ième terme
    Écrire "F(" + n + ") = " + b
  FinSi
Fin

Cette logique de "glissement" de variables est fondamentale pour résoudre toutes les suites récurrentes.

4. Mise en Pratique : Analyser des Algorithmes de Suites

Le document suivant propose des exercices corrigés qui sont parfaits pour renforcer votre compréhension. Nous allons analyser un exemple ensemble.

Analysons ensemble l'algorithme de l'Exercice 6 :
E = (1+2) x (1+2+3) x … x (1+2+3+…+N)

Ce problème a deux niveaux :

1. Un produit de plusieurs termes (la multiplication des parenthèses).
2. Chaque terme est lui-même une somme.

Cela suggère une structure de boucles imbriquées, un concept que vous avez vu dans une leçon précédente.

Algorithme SommeE // Analyse de la solution de l'exercice 6
Variables
  I, J, N, E, S : Entier

Début
  Lire(N)
  E ← 1  // Accumulateur du PRODUIT final. Initialisé à 1.
  S ← 1  // Accumulateur de la SOMME intérieure.

  Pour I allant de 2 à N Faire
    // À chaque tour de la boucle externe, on calcule le terme suivant de la série.
    
    // 1. Mise à jour de la somme intérieure
    S ← S + I // S valait (1+...+I-1), il vaut maintenant (1+...+I)
    
    // 2. Mise à jour du produit final
    E ← E * S // On multiplie le produit global par la nouvelle somme
  Fait
  
  Ecrire(‘E=’, E)
Fin

La solution proposée est très astucieuse. Au lieu d'utiliser une boucle imbriquée, elle réutilise le résultat de la somme précédente.

• Quand I vaut 2, S devient 1+2. E devient 1 * (1+2).
• Quand I vaut 3, S devient (1+2) + 3. E devient (1*(1+2)) * (1+2+3).
• Et ainsi de suite.

Cette optimisation montre comment une bonne analyse du problème peut rendre un algorithme plus efficace. C'est un excellent exemple de "clean code" : non seulement il fonctionne, mais il est aussi intelligent.

5. À vous de jouer !

Maintenant, mettez en pratique ce que vous avez appris. Essayez de concevoir un algorithme pour le problème suivant.

Problème : Calculer la somme de la série alternée $S=1-2+3-4+\cdots \pm N$.
Par exemple, si N=4, S = 1 - 2 + 3 - 4 = -2.
Si N=5, S = 1 - 2 + 3 - 4 + 5 = 3.

Indices :

• Vous aurez besoin d'un accumulateur pour la somme.
• Dans votre boucle Pour de 1 à N, comment pouvez-vous savoir si vous devez additionner ou soustraire le nombre i ?
• Pensez à l'opérateur MOD (modulo). Un nombre i est pair si i MOD 2 = 0.

Algorithme SerieAlternee
Variables
  N : Entier
  i : Entier
  Somme : Entier

Début
  Écrire "Entrez la limite N :"
  Lire N
  
  Somme ← 0
  
  Pour i allant de 1 à N Faire
    // Si i est impair, on l'ajoute
    Si (i MOD 2) <> 0 Alors
      Somme ← Somme + i
    // Sinon (si i est pair), on le soustrait
    Sinon
      Somme ← Somme - i
    FinSi
  FinPour
  
  Écrire "La somme de la série est : " + Somme
Fin

Conclusion

Félicitations ! Vous avez appliqué avec succès les boucles pour résoudre des problèmes de calcul de séries, un exercice fondamental en algorithmique.

Points clés à retenir :

• Les boucles sont l'outil naturel pour calculer des sommes, des produits, ou les termes d'une suite.
• La clé est de bien initialiser vos variables (accumulateurs, termes précédents) avant la boucle.
• La logique de mise à jour à l'intérieur de la boucle est ce qui "traduit" la règle mathématique en algorithme.
• Pour les suites récurrentes comme Fibonacci, pensez au "glissement" de variables pour conserver l'historique nécessaire.

Et après ?

Nous avons maintenant achevé notre exploration approfondie des structures de contrôle. Vous disposez des briques logiques essentielles pour construire le squelette de n'importe quel algorithme.

Dans la prochaine leçon, nous allons enfin ouvrir un nouveau chapitre majeur : les structures de données. Nous commencerons par la plus fondamentale d'entre elles : le tableau. Vous apprendrez à déclarer une variable capable de stocker et d'organiser non pas une, mais toute une collection de valeurs. Cela décuplera la puissance de vos algorithmes et vous permettra de résoudre des problèmes bien plus complexes, comme le tri ou la recherche de données.