Initiation à la programmation

On peut calculer la somme des entiers de 1 à n à l'aide d'une structure itérative tant que et de deux variables : i pour énumérer les entiers successifs de 1 à n et S pour les cumuler.

Algorithme 5.1 Calcul de la somme des n premiers nombres entiers.

Entrée : kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp un entier positif ou nul
Sortie : kitxmlcodeinlinelatexdvps = \sum_{k=1}^n kfinkitxmlcodeinlinelatexdvp
  initialiser kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à 0
  initialiser kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp à 1
  {on a bien kitxmlcodeinlinelatexdvps = \sum_{k=1}^{i-1} kfinkitxmlcodeinlinelatexdvp}
  tant que kitxmlcodeinlinelatexdvpi \le nfinkitxmlcodeinlinelatexdvp faire
      ajouter kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp
      incrémenter kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp
      {notons que l’on a toujours kitxmlcodeinlinelatexdvps = \sum_{k=1}^{i-1} kfinkitxmlcodeinlinelatexdvp}
  fin tant que
  {la même égalité est satisfaite avec kitxmlcodeinlinelatexdvpi = n + 1finkitxmlcodeinlinelatexdvp}
  renvoyer kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp

Compte tenu de la condition, il est possible de dire avant l'exécution de cet algorithme que la séquence d'instructions contenue dans la boucle tant que sera effectuée n fois.

De manière plus générale, si un algorithme s'écrit de cette façon

initialiser kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp
tant que kitxmlcodeinlinelatexdvpi \le bfinkitxmlcodeinlinelatexdvp faire
séquence d'instructions ne modifiant pas i
incrémenter kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp
fin tant que

et que la séquence d'instructions précédant l'incrémentation de la variable kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp ne modifie pas la valeur de cette variable, alors le nombre de fois que la séquence d'instructions sera exécutée est égal à kitxmlcodeinlinelatexdvpb − a + 1finkitxmlcodeinlinelatexdvp.

De telles itérations dont le nombre d'étapes est déterminé par une variable qui parcourt l'ensemble des valeurs comprises entre deux bornes sont appelées une boucle pour, et la variable kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp est appelée indice de la boucle.

On peut réécrire le calcul de la somme des entiers compris entre 1 et n en utilisant une boucle pour.

Algorithme 5.2 Calcul de la somme des n premiers nombres entiers avec une boucle pour

Entrée : kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp un entier positif ou nul
Sortie : kitxmlcodeinlinelatexdvpS = \sum_{k =1}^n kfinkitxmlcodeinlinelatexdvp
  initialiser kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp à 0
  pour kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp variant de 1 à kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp faire
    ajouter kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp à kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp
    {on a kitxmlcodeinlinelatexdvpS = \sum_{k =1}^i kfinkitxmlcodeinlinelatexdvp}
  fin pour
  renvoyer kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp

5-2-1. Syntaxe de la boucle pour▲

Toute séquence de deux instructions de la forme

Sélectionnez

1.
2.
3.
4.
5.
6.

let i = ref a
in
while !i <= b do
  (* sequence d'instructions *)
  i := !i + 1
done

peut être remplacée par une boucle pour

Syntaxe : Boucle pour

Sélectionnez

1.
2.
3.

for i = a to b do
  (* sequence d'instructions *)
done

Exemple 1 :

Calcul de la somme des entiers de 1 à 100

Sélectionnez

1.
2.
3.
4.
5.
6.
7.

# let s = ref 0
  in
    for i = 1 to 100 do
      s := !s + i
    done;
    !s ;;
- : int = 5050

5-2-2. Remarque sur l'indice de boucle▲

L'indice d'une boucle for en Caml est une variable locale à la boucle qui n'a pas besoin d'être déclarée(12). Cette variable n'est définie que dans l'environnement de la boucle. Elle n'existe pas dans l'environnement englobant.

Sélectionnez

1.
2.
3.
4.
5.
6.

# for i = 1 to 5 do
    print_int(i);
    print_newline()
  done;
  print_int(i);;
Unbound value i

De plus, ce n'est pas une variable mutable, et on ne peut donc pas modifier la valeur de cet indice dans la séquence d'instructions du corps de la boucle.

5-2-3. Boucle pour à indice décroissant▲

Toute séquence de deux instructions de la forme

Sélectionnez

1.
2.
3.
4.
5.
6.

let i = ref a
in
while !i >= b do
  (* sequence d'instructions *)
  i := !i - 1
done

peut être remplacée par une boucle pour

Syntaxe : Boucle pour à indice décroissant

Sélectionnez

1.
2.
3.

for i = a downto b do
  (* sequence d'instructions *)
done

Exemple 2 :

Calcul de la somme des entiers de 1 à 100

Sélectionnez

1.
2.
3.
4.
5.
6.
7.

# let s = ref 0
  in
    for i = 100 downto 1 do
      s := !s + i
    done;
    !s ;;
- : int = 5050

Soit kitxmlcodeinlinelatexdvp(u_n)_{n \in \mathbb{N}}finkitxmlcodeinlinelatexdvp une suite de nombres réels définie par son premier terme kitxmlcodeinlinelatexdvpu_0 = afinkitxmlcodeinlinelatexdvp (kitxmlcodeinlinelatexdvpa \in \mathbb{R}finkitxmlcodeinlinelatexdvp) et pour tout kitxmlcodeinlinelatexdvpn \ge 0finkitxmlcodeinlinelatexdvp une relation de récurrence de la forme

kitxmlcodelatexdvpu_{n+1} = f(u_n)finkitxmlcodelatexdvp

où kitxmlcodeinlinelatexdvpffinkitxmlcodeinlinelatexdvp est une fonction réelle d'une variable réelle.

Par exemple, on peut considérer la suite de réels définie par

kitxmlcodelatexdvp\begin{matrix} u_0 = & 1 \\ u_{n+1} = & \frac{u_n}{2} + \frac{1}{u_n} \end{matrix}finkitxmlcodelatexdvp

on a ici kitxmlcodeinlinelatexdvpa = 1finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpf(x) = \frac{x}{2} + \frac{1}{x}finkitxmlcodeinlinelatexdvp

5-3-1. Calcul du terme d'indice n▲

On veut calculer le terme kitxmlcodeinlinelatexdvpu_nfinkitxmlcodeinlinelatexdvp lorsqu'est donné l'indice kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp.

Algorithme 5.3 Calcul du terme d'indice n d'une suite récurrente

Entrée : kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp un nombre réel, kitxmlcodeinlinelatexdvpafinkitxmlcodeinlinelatexdvp un réel et kitxmlcodeinlinelatexdvpf: \mathbb{R} \rightarrow \mathbb{R}finkitxmlcodeinlinelatexdvp une fonction.
Sortie : le terme kitxmlcodeinlinelatexdvpu_nfinkitxmlcodeinlinelatexdvp de la suite
  kitxmlcodeinlinelatexdvpu_0 \leftarrow afinkitxmlcodeinlinelatexdvp
  pour kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp variant de 1 à kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp faire
    kitxmlcodeinlinelatexdvpu_i \leftarrow f(u_{i-1})finkitxmlcodeinlinelatexdvp
  fin pour
  renvoyer kitxmlcodeinlinelatexdvpu_nfinkitxmlcodeinlinelatexdvp

Pour réaliser cet algorithme en Caml, il suffit d'utiliser une seule variable pour mémoriser les valeurs successives des termes de la suite.

Sélectionnez

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.

(* on suppose déclarées ici trois variables
 - a de type float
 - f de type float− > float
 - n de type int
*)
let u = ref a
in
begin
  for i = 1 to n do
    u := f(!u)
  done;
  !u
end

5-3-2. Calcul et affichage des termes d'indice 0 à n▲

On veut afficher la valeur de tous les termes de la suite (kitxmlcodeinlinelatexdvpu_nfinkitxmlcodeinlinelatexdvp) dont les indices sont compris entre 0 et kitxmlcodeinlinelatexdvpnfinkitxmlcodeinlinelatexdvp.

Il suffit de calculer successivement chaque terme de la suite et afficher immédiatement sa valeur.

Sélectionnez

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

(* on suppose déclarées ici trois variables
 - a de type float
 - f de type float− > float
 - n de type int
*)
let u = ref a
in
begin
  print_float(!u);
  print_newline();
  for i = 1 to n do
    u := f(!u);
    print_float(!u);
    print_newline()
  done
end

5-3-3. Calcul du premier terme satisfaisant une condition▲

On peut aussi vouloir chercher le premier terme de la suite qui satisfait une condition donnée. Cette condition peut porter sur le dernier terme calculé, ou bien sur plusieurs termes déjà calculés.

Algorithme 5.4 Calcul du premier terme satisfaisant une condition

kitxmlcodeinlinelatexdvpu \leftarrow afinkitxmlcodeinlinelatexdvp
tant que kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp ne satisfait pas la condition voulue faire
on calcule le terme suivant kitxmlcodeinlinelatexdvpu \leftarrow f(u)finkitxmlcodeinlinelatexdvp
fin tant que
renvoyer kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp

Remarque : si aucun terme de la suite ne satisfait la condition donnée, la boucle est infinie (le programme ne s'arrête pas). Aussi avant de concevoir de tels programmes il est important de s'assurer qu'au moins un terme de la suite vérifie la condition.

5-3-4. Autres suites récurrentes▲

Suites récurrentes d'ordre plus élevé

Ordre 2 : la suite de Fibonacci définie par ses deux premiers termes et une relation de récurrence d'ordre 2

kitxmlcodelatexdvp\begin{matrix} u_0 = & 0\\ u_1 = & 1\\ u_{n+2} = & u_{n+1} + u_{n}\ \forall n \in \mathbb{N} \end{matrix}finkitxmlcodelatexdvp

Facile à programmer.

Ordre total : la suite des nombres de Catalan définie par son premier terme et une relation de récurrence s'appuyant sur tous les termes qui précèdent

kitxmlcodelatexdvp\begin{matrix} u_0 = & 0\\ u_{n+1} = & \sum\limits_{k=0}^n u_ku_{n-k}\ \forall n\in\mathbb{N} \end{matrix}finkitxmlcodelatexdvp

Difficile à programmer sans tableaux (cf cours d'API1).

Exercice 5-1 downto n'est pas indispensable

Question 1 : À l'aide d'une boucle à indices croissants, réécrivez l'instruction qui suit de sorte que l'affichage soit identique.

Sélectionnez

1.
2.
3.
4.

for i = n downto 1 do
  print_int(i);
  print_newline()
done

Question 2 : En supposant que l'instruction action(i) accomplisse une certaine tâche qui dépend de i, comment réécrire l'instruction

Sélectionnez

1.
2.
3.

for i = b downto a do
  action(i)
done

avec une boucle à indices croissants ?

Exercice 5-2 Tables de multiplication

Réalisez un programme qui affiche une table de multiplication par un nombre donné. Une trace d'exécution du programme demandé est donnée ci-dessous pour la table par 7 :

Sélectionnez

1.
2.
3.
4.
5.

1 x 7 = 7
2 x 7 = 14
3 x 7 = 21
…
10 x 7 = 70

Exercice 5-3 Calcul de puissances

Réalisez un programme qui calcule la valeur de l'entier aⁿ pour deux entiers a et n.

Exercice 5-4 Calcul de factorielles

Réalisez un programme qui calcule l'entier n!, n étant donné.

Exercice 5-5

Boucles imbriquées pour stars académiques

Question 1

Réalisez un programme qui affiche à l'écran une ligne de n étoiles, l'entier n étant donné.

L'affichage du programme demandé est donné ci-dessous pour n = 5 :

Sélectionnez

1.

*****

Question 2 : Réalisez un programme qui affiche à l'écran un carré de n × n étoiles, l'entier n étant donné.

L'affichage du programme demandé est donné ci-dessous pour n = 5 :

Sélectionnez

1.
2.
3.
4.
5.

*****
*****
*****
*****
*****

Question 3 : Réalisez un programme qui affiche à l'écran un triangle (isocèle) de hauteur n, l'entier n étant donné.

L'affichage du programme demandé est donné ci-dessous pour n = 5 :

Sélectionnez

1.
2.
3.
4.
5.

*
**
***
****
*****

Question 4 : Réalisez un programme qui affiche à l'écran un triangle (isocèle) de hauteur n pointe en bas, l'entier n étant donné.

Une trace d'exécution du programme demandé est donnée ci-dessous :

Sélectionnez

1.
2.
3.
4.
5.

*****
****
***
**
*

Exercice 5-6 : Calcul de la suite de Heron

La suite de Heron est la suite récurrente de nombres réels définie par

kitxmlcodelatexdvp\begin{matrix} u_0 = & a\\ u_{n+1} = & \frac{u_n}{2} + \frac{B}{2u_n} \end{matrix}finkitxmlcodelatexdvp

où a et B sont deux réels positifs.

Question 1 : Programmez le calcul du terme d'indice n de cette suite avec a = 1 et B = 2.

Question 2 : Modifiez votre programme pour qu'à l'exécution on obtienne un affichage de tous les termes demandés, à raison d'un par ligne.

Par exemple, l'affichage produit aura la forme qui suit pour a = 1, B = 2 et n = 5.

Sélectionnez

1.
2.
3.
4.
5.

u(1) = 1.5
u(2) = 1.41666666667
u(3) = 1.41421568627
u(4) = 1.41421356237
u(5) = 1.41421356237

Question 3 : Utilisez votre programme pour différentes valeurs de a et B.

Exercice 5-7 : Suite de Fibonacci

Question 1 : Programmez le calcul des premiers termes de la suite de Fibonacci. Faites-le en utilisant le type int, puis le type float. Calculez les termes jusqu'à l'indice 50. Comparez les résultats selon le type utilisé.

Question 2 : Cette suite est croissante et tend vers kitxmlcodeinlinelatexdvp+\inftyfinkitxmlcodeinlinelatexdvp lorsque n tend vers kitxmlcodeinlinelatexdvp+\inftyfinkitxmlcodeinlinelatexdvp. Écrivez une fonction qui calcule l'indice du premier terme supérieur ou égal à un réel positif s passé en paramètre.

Cours complet d’initiation à la programmation

Chapitre 5 - La boucle pour▲

5-1. La boucle Pour▲

5-2. La boucle Pour en Caml▲

5-2-1. Syntaxe de la boucle pour▲

5-2-2. Remarque sur l'indice de boucle▲

5-2-3. Boucle pour à indice décroissant▲

5-3. Suites récurrentes▲

5-3-1. Calcul du terme d'indice n▲

5-3-2. Calcul et affichage des termes d'indice 0 à n▲

5-3-3. Calcul du premier terme satisfaisant une condition▲

5-3-4. Autres suites récurrentes▲

5-4. Exercices▲