formations/algo/algorithmique/cours/control.txt

295 lines
7.1 KiB
Plaintext
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Les structures de contrôle
==========================
L'instruction de saut
----------------------
.. raw:: latex
\begin{algorithm}
\caption{Exemple de saut conditionnel}\label{saut}
\begin{algorithmic}[1]
\Procedure{Euclide}{} \Comment{c'est l'algorithme d'Euclide}
\State $\textit{stringlen} \gets \text{length of }\textit{string}$
\State $i \gets \textit{patlen}$
\BState \emph{top}:
\If {$i > \textit{stringlen}$} \Return false
\EndIf
\State $j \gets \textit{patlen}$
\BState \emph{loop}: \Comment{C'est le label (l'étiquette)} \label{etiquette}
\If {$\textit{string}(i) = \textit{path}(j)$}
\State $j \gets j-1$.
\State $i \gets i-1$.
\State \textbf{goto} \emph{loop}. \label{goto}
\State \textbf{close};
\EndIf
\State $i \gets
i+\max(\textit{delta}_1(\textit{string}(i)),\textit{delta}_2(j))$.
\State \textbf{goto} \emph{top}. \Comment{C'est l'instruction de saut}
\EndProcedure
\end{algorithmic}
\end{algorithm}
.. raw:: latex
Ligne \ref{etiquette}, le bloc `loop` est aussi un label (une étiquette),
c'est-à-dire une marque posée qu'il est possible de retrouver dans le programme. \\
.. raw:: latex
Ligne \ref{goto}, l'instruction \texttt{goto} (aller à ) est le saut vers le label. \\
Description générique d'une instruction de saut::
Instruction 1
Saut Label1
Instruction 2
...
Label1:
Instruction n
.. important:: les sauts conditionnels sont à éviter, même s'ils sont implémentés
dans le langage cible, car c'est le meilleur moyen d'aboutir à
du **code spaghetti**.
L'instruction de branchement conditionnel
------------------------------------------
On appelle structure conditionnelle les instructions qui permettent de tester si une condition est vraie ou non.
.. raw:: latex
\begin{algorithm}
\caption{Exemple d'instruction de test}
\begin{algorithmic}[1]
\BState \emph{entrée}: $quality\gets 0$ \Comment{C'est cette valeur qui sera testée}
\BState \emph{locale}: $a\gets ""$
\BState \emph{sortie}: $a$ \Comment{La sortie est la valeur de $a$}
\BState \emph{corps}:
\If{$quality\ge 9$}
\State $a\gets perfect$
\ElsIf{$quality\ge 7$}
\State $a\gets good$
\ElsIf{$quality\ge 5$}
\State $a\gets medium$
\ElsIf{$quality\ge 3$}
\State $a\gets bad$
\Else
\State $a\gets unusable$
\EndIf
\end{algorithmic}
\end{algorithm}
.. ifconfig:: exercice
**Exercice** : Compacter l'algorithme suivant en une seule condition de test::
Si il fait trop chaud Alors
Si il ne pleut pas Alors
Ouvrir la fenêtre
Sinon
Fermer la fenêtre
Finsi
Sinon
Fermer la fenêtre
Finsi
.. ifconfig:: correction
**Correction** :
::
Si il fait trop chaud ET il ne pleut pas Alors
Ouvrir la fenêtre
Sinon
Fermer la fenêtre
Finsi
L'instruction switch
--------------------
L'instruction switch permet de faire plusieurs tests de valeurs sur le contenu d'une même variable.
Ce branchement conditionnel simplifie beaucoup le test de plusieurs valeurs d'une variable.
Les instructions d'itérations (boucles)
---------------------------------------
.. important:: Toutes les boucles concernent le paradigme de programmation impératif
et ne sont pas valides dans le paradigme de programmation fonctionnel
(puisque l'ordre d'évaluation importe)
- arrêt conditionnel (break)
- passage d'un pas (continue)
Répéter ... jusqu'à
~~~~~~~~~~~~~~~~~~~
.. raw:: latex
\begin{algorithm}
\caption{Exemple de répéter ... jusqu'à}
\begin{algorithmic}[1]
\BState \emph{locales}: $i \gets 1$ \Comment{déclaration et initialisation de i}
\Repeat \Comment{c'est le label de début du répéter}
\State $i \gets \textit{i+1}$
\Until{i == 100} \Comment{condition de fin de la boucle}
\end{algorithmic}
\end{algorithm}
La boucle **pour** (for)
~~~~~~~~~~~~~~~~~~~~~~~~
.. raw:: latex
\begin{algorithm}
\caption{Exemple de boucle for}
\begin{algorithmic}[1]
\BState \emph{locales}: $sum\gets 0$
\For{$i\gets 1, n$}
\State $sum\gets sum+i$
\EndFor
\end{algorithmic}
\end{algorithm}
.. ifconfig:: exercice
**Exercice** : Ecrire un algorithme qui demande successivement 20 nombres à lutilisateur,
et qui lui dise ensuite quel était le plus grand parmi ces 20 nombres
.. ifconfig:: correction
**Correction** :
::
Variables N, i, PG en Entier
Debut
PG <- 0
Pour i <- 1 à 20
Ecrire "Entrez un nombre : "
Lire N
Si i = 1 ou N > PG Alors
PG <- N
FinSi
Ecrire "Le nombre le plus grand était : ", PG
Fin
.. attention:: ne jamais manipuler le compteur dans une boucle
::
Variable Truc en Entier
Début
Pour Truc <- 1 à 15
Truc <- Truc * 2
Ecrire "Passage numéro : ", Truc
Truc Suivant
Fin
La boucle tant que (while)
~~~~~~~~~~~~~~~~~~~~~~~~~~
.. raw:: latex
\begin{algorithm}
\caption{Exemple de boucle while}
\begin{algorithmic}[1]
\BState \emph{locales}: $sum\gets 0$
\State $i\gets 1$
\While{$i\le n$}
\State $sum\gets sum+i$
\State $i\gets i+1$
\EndWhile
\end{algorithmic}
\end{algorithm}
.. ifconfig:: exercice
**Exercice** : Ecrire un algorithme de validation d'une entrée utilisateur
::
"Voulez vous un café ? (O/N)"
.. ifconfig:: correction
**Correction** : deux solutions possibles, une
::
Variable Rep en Caractère
Début
Rep <- ""
Ecrire "Voulez vous un café ? (O/N)"
TantQue Rep <> "O" et Rep <> "N"
Lire Rep
Si Rep <> "O" et Rep <> "N" Alors
Ecrire "Saisie Erronée, Recommencez"
FinSi
FinTantQue
Fin
::
Variable Rep en Caractère
Début
Ecrire "Voulez vous un café ? (O/N)"
Lire Rep
TantQue Rep <> "O" et Rep <> "N"
Ecrire "Vous devez répondre par O ou N. Recommencez"
Lire Rep
FinTantQue
Ecrire "Saisie acceptée"
Fin
.. ifconfig:: exercice
**Exercice** : "C'est plus, C'est moins", c'est-à-dire Ecrire un algorithme qui demande à lutilisateur
un nombre compris entre a et b jusquà ce que la réponse convienne.
.. ifconfig:: correction
**Correction** :
::
Variable N en Entier
Debut
N <- 0
Ecrire "Entrez un nombre entre 10 et 20"
TantQue N < 10 ou N > 20
Lire N
Si N < 10 Alors
Ecrire "Plus grand !"
SinonSi N > 20 Alors
Ecrire "Plus petit !"
FinSi
FinTantQue
Fin
Et les autres boucles : répéter... jusqu'à, etc...
.. raw:: latex
\begin{algorithm}
\caption{Exemple de boucle répéter}
\begin{algorithmic}[1]
\State $sum\gets 0$
\State $i\gets 1$
\Repeat
\State $sum\gets sum+i$
\State $i\gets i+1$
\Until{$i>n$}
\end{algorithmic}
\end{algorithm}