Il est souvent difficile d'écrire la version définitive du premier coup, on risque en effet de se perdre dans des détails et de ne pas voir l'essentiel.
Pour éviter cet écueil, on procède par étapes en définissant des actions très générales (qui ne sont pas des actions élémentaires de la machine).
Pour passer d'une étape (version) à l'étape suivante , on détaille un peu plus les actions générales, mais pour ne pas perdre l'évolution de ce processus, on place l'action générale en commentaire, et on la détaille un peu plus à la suite de ce commentaire.
A la fin on doit obtenir une version qui ne contient plus que des actions exécutables par l'opérateur.
Cette méthode est appelée méthode par "raffinages successifs".
Cette méthode donne de bons résultats, mais elle ne garantit pas qu'on obtiendra bien le résultat (parfois il faut revenir en arrière).
Un programme est un enchaînement de différentes opérations et calculs plus ou moins complexes. La difficulté pour élaborer un tel programme est généralement proportionnelle à la taille du problème.
On part d'une description de la résolution du problème, très abstraite et à chaque étape, on la raffine en utilisant :
les structures de contrôle pour décrire les choix et les répétitions.
les structures de composition pour élaborer un calcul complexe à partir de calculs plus élémentaires (composition fonctionnelle et séquentielle)jusqu'à obtenir quelque chose écrit dans un langage proche de celui de la machine.
Il ne restera alors qu'à traduire dans le langage de programmation utilisé.
Le raffinage consiste en ces trois étapes où se mêlent rigueur et savoir-faire :
Diviser le problème à résoudre en sous-problèmes. C'est une partie importante qui conditionne le reste et qui, malheureusement, n'est basée que sur l'expérience.
Résoudre chacun des sous-problèmes soit en appliquant à nouveau la première étape, soit en résolvant directement le sous-problème qui est un problème simple et connu.
Combiner les résultats des sous-problèmes. C'est la partie la plus rigoureuse dans laquelle on doit faire attention à ce que donnent les sous-résultats et à ce qu'il est nécessaire de faire pour obtenir le résultat final
Objectif : Permuter 2 variables (A et B )
Niveau 1 : Idée Générale
debut /* niveau 1 */
Recopier A dans C;
Recopier B dans A;
Recopier C dans B;
fin
Remarque : on passe par une recopie dans une autre variable C pour conserver la valeur de A avant de faire la copie de B.
Niveau 2 : On détaille un peu plus les actions qui devront être décomposées vue le peu d'opérations élémentaires au niveau de l'affectation
debut /* niveau 2 */
/* Recopier A dans C; */
Mise à zéro de C;
Tant que A > 0 Faire
Debut
Incrémenter C de 1;
Décrémenter A de 1;
fin /*du Tant que */
Et ...
/* Recopier B dans A; */
Tant que B > 0 Faire
Debut
Incrémenter A de 1;
Décrémenter B de 1;
fin /* du Tant que */
/* Recopier C dans B; */
...
Niveau 3 : il n'y a plus d'opérations complexes, on traduit toutes les opérations avec les opérations de base et on combine les 2 parties.
Debut /* niveau 3 */
/* Recopier A dans C; */
C<-0;
Tant que A > 0 Faire
Debut
C<-C+1;
A<-A-1;
fin /*du Tant que */
/* Recopier B dans A; */
Tant que B > 0 Faire
Debut
A<-A+1;
B<-B-1;
fin /* du Tant que */
/* Recopier C dans B; */
...
Fin
Objectif : Écrire un programme qui lit un certain nombre d'entiers et détermine si chacun d'eux est pair, et qui, dans le cas contraire, détermine si l'entier est premier. (L'utilisateur rentrera les nombres un à un et tapera 0 pour terminer sa saisie.)
Niveau 0
Debut /* niveau 0 */
Lire et étudier une liste d'entiers
Fin
Pour passer au niveau 1 :
Je reprends l'action et je raffine.
Tout en raffinant, je fais des choix de conception de l'algorithme : Mémorise-t-on toutes les valeurs ou les traite-t-on au fur et à mesure ? Est-on limité en taille mémoire ? Comment se fait la saisie ? (0 = arrêt ou nombre d'entiers connu ?)
Niveau 1
Début /* niveau 1 */
/* Programme qui lit et étudie une liste d'entiers */
Lire un entier ; /* (a) */
Tant que cet entier est différent de 0 Faire /* (b) */
Début
Calculer s'il est pair et éventuellement s'il est premier ; /* (c) */
Lire l'entier suivant /* (d) */
fin
Fin
Ici, les actions a, b et d sont suffisamment simple pour qu'on puisse les traiter à chaque niveau dans son intégralité, mais l'action c nécessite un nouveau niveau. Chaque opération ou calcul d'un niveau est indépendamment des autres. Il faut simplement s'assurer que l'état initial et l'état final de l'opération raffinée sont bien ceux attendus.
Début /* niveau 2 */
/* Programme qui lit et étudie une liste d'entiers */
/* Lire un entier */
Lire (N);
Tant que /* cet entier est différent de 0 */ N ≠ 0 Faire
Début
/*Calculer s'il est pair et éventuellement s'il est premier*/
S'il est pair alors
Début
Afficher un message 1;
Sinon
Afficher un message 2;
Calculer s'il est premier ;
Afficher un message selon qu'il soit premier ou non
fin ;
/*Lire l'entier suivant*/
Lire (N)
fin
Fin.
Niveau 3
Début /* niveau 3 */
/* Programme qui lit et étudie une liste d'entiers */
/* Lire un entier */
Lire (N);
Tant que /* cet entier est différent de 0 */ N ≠ 0 Faire
Début
/* Calculer s'il est pair et éventuellement s'il est premier */
Si /*il est pair*/ (N mod 2) = 0 alors
début
/* Afficher un message */
Afficher (N, '' est pair'');
Sinon
/* Afficher un message */
Afficher (N, '‘ n'est pas pair'');
/* Calculer s'il est premier */
Diviseur <- 2;
Tant que ((N mod Diviseur) ≠ 0) et (Diviseur * Diviseur ≤ N) Faire
début
Incrémenter le Diviseur ;
/* Afficher un message selon qu'il soit premier ou non */
Si {s'il est premier} N mod Diviseur ≠ 0 alors
début
Afficher un message
Sinon
Afficher un message
fin ;
/* Lire l'entier suivant */
fin
fin
Lire (N)
fin
Fin.
Niveau 4
Début /* niveau 4 */
/* Programme qui lit et étudie une liste d'entiers */
/* Lire un entier */
Lire (N);
Tant que /* cet entier est différent de 0 */ N ≠ 0 Faire
début
/* Calculer s'il est pair et éventuellement s'il est premier*/
Si {il est pair} (N mod 2) = 0 alors
début
/*Afficher un message*/
Afficher (N, "est pair")
Sinon
/*Afficher un message*/
Afficher (N, '' n'est pas pair'');
/*Calculer s'il est premier*/
Diviseur <- 2;
Tant que ((N mod Diviseur) ≠ 0) et (Diviseur * Diviseur ≤ N) Faire
début
/*Incrémenter le Diviseur*/
Diviseur <- Diviseur + 1;
/*Afficher un message selon qu'il soit premier ou non*/
Si {s'il est premier} N mod Diviseur ≠ 0 alors
début
/*Afficher un message*/
Afficher (N, '' est premier'')
fin
Sinon
début
/*Afficher un message*/
Afficher (N, '' n'est pas premier'')
fin
fin
fin
/*Lire l'entier suivant*/
Lire (N)
fin
Fin.
La conception d'un algorithme par raffinage ne garantit pas qu'il n'y a pas d'erreurs
Pensez à vérifier :
Que des variables utilisées dans la condition d'une sélection ont bien été associées à une valeur avant l'évaluation de la condition.
Que l'expression évaluée dans la condition d'une répétition évolue bien et va converger vers un arrêt.
Que vous avez bien traité toutes les opérations du niveau précédent.