007_Itérations

Schéma fonctionnel


009_Récursivité
Page Suivante
Dans la méthode de construction des algorithmes, nous partons de l’objectif final, le plus souvent une valeur à calculer ; ainsi, nous faisons apparaître une variable pour laquelle il faut expliciter le mode de calcul. Ce calcul présuppose lui-même le calcul d’autres variables. On comprend intuitivement que la valeur finale est calculée en fonction des variables dont elle dépend. Chaque calcul peut faire l’objet d’un algorithme et on peut utiliser, dans une définition d’un algorithme, une valeur résultant de l’exécution d’un autre algorithme. Soit par exemple à fabriquer une série d’appareils dont chaque exemplaire sera équipé d’un quartz et de deux diviseurs de fréquence correspondant à la demande de chaque client. À la commande, le client précisera les 2 fréquences dont il a besoin. Nous allons écrire le programme qui détermine la valeur du quartz et les valeurs des deux diviseurs de fréquence, sachant que toutes ces valeurs sont des nombres entiers.

{\tt \begin{tabular}{|l|l|c|} \hline \multicolumn{3}{|l|}{FREQ : /* Calcul d'une fr\'equence et de deux diviseurs */}\\ \hline Lexique & Actions & ordre \\ \hline $Fq$ : Fr\'equence du quartz& AFFICHER$(Fq$, $div1$, $div2)$ ; & 5 \\ $F_{1}$ et $F_{2}$ : Fr\'equences client & $Fq =$ PPCM$(F_{1},F_{2})$ ; & 2 \\ $div1$ : diviseur pour $F_{1}$ & $div1 = \frac{Fq}{F_{1}}$ ; & 3 \\ & $div2 = \frac{Fq}{F_{2}}$ ; & 4 \\ $div2$ : diviseur pour $F_{2}$ & SAISIR$(F_{1},F_{2})$ ; & 1 \\ \hline \multicolumn{3}{c}{} \\ \multicolumn{3}{l}{La valeur $Fq$ sera renvoy\'ee par le calcul du {\sc ppcm} de $F_{1} \mbox{et} F_{2}$.}\\ \multicolumn{3}{c}{} \\ \hline \multicolumn{3}{|l|}{PPCM$(a, b)$ /* Calcul du Plus Petit Commun Multiple */ } \\ \hline & & \\ & PPCM $ = \frac{a\times b}{\mbox{PGCD}(a, b)}$ ; & \\ & & \\ \hline \multicolumn{3}{c}{} \\ \multicolumn{3}{l}{La valeur du {\sc ppcm} sera renvoy\'ee par le calcul du {\sc pgcd}\footnote{Le calcul du {\sc pgcd} peut \^etre fait de fa\c con r\'ecursive. Cf. page \pageref{Pgcd}} de $F_{1} \mbox{et} F_{2}$.}\\ \multicolumn{3}{c}{} \\ \hline \multicolumn{3}{|l|}{PGCD$(x, y)$ /* Calcul du Plus Grand Commun Diviseur */ } \\ \hline $m$ : variable temporaire & {\bf while (}$x != 0${\bf )} & \\ & \hspace{0mm}{\bf \{} & \\ & \hspace{5mm}$m = x$ ; & \\ & \hspace{5mm}$x = y$ ; & \\ & \hspace{5mm}$y = m$ modulo $y$ ; &\\ & \hspace{0mm}{\bf \}} & \\ & {\bf return } $y$ ; & \\ \hline \end{tabular} } \medskip

On voit donc que l’on est conduit à écrire 2 nouvelles fonctions (qui ne sont pas natives) le PPCM et le PGCD pour réaliser ce programme.

Relation de précédente

On définit une relation de précédente sur les variables d’un algorithme. Nous dirons que la variable x précède la variable y si x a au moins une occurrence dans la définition de y. À cause de cela, la valeur de y dépend de la valeur de x, et le calcul de y n’est possible que si x a déjà été calculé. La relation « x précède y » peut donc être lue comme « le calcul de x doit précéder le calcul de y ». Cette relation définit un ordre partiel sur les variables de l’algorithme. Un calendrier perpétuel

Définition du problème :

On se propose de déterminer le jour de la semaine d’une date donnée. Sachant que le 1^{er} janvier 1900 était un lundi ; on appellera décalage la position d’un jour dans la semaine \mid décalage \in [0-6], 0 \equiv dimanche. Pour cela, on va chercher le décalage entre le 1^{er} janvier de l’année 1900 et la date considérée. On se donne une table du nombre de jours écoulés depuis le début de l’année jusqu’au début du mois mois.

Rendered by QuickLaTeX.com

Graphe de dépendance des variables

On vérifie sur le graphe de dépendance des variables de la figure ci-dessus que l’objectif (Jour) présuppose le calcul des variables dont il dépend, et que chacune d’elles est explicitée, soit par un calcul simple, soit par l’appel d’une fonction, jusqu’à remonter aux valeurs fournies à l’algorithme.
007_Itérations
009_Récursivité
Page Suivante