Conception d'algorithmes et résolution de problèmes

Le cycle de vie du développement de programme est l'ensemble des étapes utilisées pour créer un programme. Il comprend quatre étapes.

Analyse

En analyse, vous comprenez le problème. Deux compétences clés aident :

• l'abstraction — conserver uniquement les détails importants et ignorer le reste;
• la décomposition — diviser un grand problème en petites parties plus faciles à gérer.

Conception

Lors de la conception, vous planifiez la solution, souvent en utilisant la décomposition. Vous pouvez représenter les parties comme des sous-systèmes dans un diagramme de structure (un schéma qui divise un système en petites boîtes).

Exemple corrigé. Un parking possède une borne de paiement. Le conducteur saisit la plaque d’immatriculation de la voiture, la borne calcule la durée du stationnement et le montant à payer, le conducteur paie en espèces ou par carte, puis un reçu est imprimé. Dessinez un diagramme de structure.

Le système entier figure dans la case supérieure. Chaque case du niveau suivant correspond à une tâche du système, et une case peut être divisée à son tour (le paiement se divise en espèces et carte). Lisez chaque niveau de gauche à droite dans l’ordre où les tâches se déroulent. Un diagramme de structure montre les parties, et non l’ordre des décisions ou des boucles : c’est le rôle d’un organigramme ou du pseudocode.

Codage et test

Lors du codage, vous écrivez le code du programme. Vous utilisez un test itératif — tester de petits segments encore et encore au fur et à mesure de leur construction. Lors du test, vous exécutez l'intégralité du programme avec des données de test pour vérifier son bon fonctionnement.

Vous pouvez planifier une solution de trois manières principales.

• un diagramme structurel — montre les parties d'un système et comment elles s'emboîtent ;
• un organigramme — un diagramme utilisant des boîtes et des flèches pour montrer les étapes dans l'ordre ;
• pseudocode — étapes écrites en anglais simple, semblable à du code (pas une vraie langue).

Un algorithme est un ensemble d'étapes, dans le bon ordre, qui résout un problème. Tout algorithme peut être divisé en trois parties :

• données d'entrée — les données qui entrent ;
• traitement — le travail effectué sur les données ;
• résultat — la sortie qui en résulte.

C’est ce qu’on appelle la décomposition en entrées, traitements et sorties. Par exemple, pour « trouver la moyenne de trois notes » : les entrées sont les trois notes ; le traitement consiste à les additionner et à diviser le résultat par 3 ; la sortie est la moyenne.

Lorsqu'une donnée est saisie, vous la vérifiez pour réduire les erreurs.

La validation vérifie que les données sont cohérentes et respectent les règles. Elle ne peut pas vérifier si les données sont vraies, seulement si elles sont autorisées.

La vérification vérifie que les données ont été copiées ou saisies correctement (sans erreurs de frappe). Deux méthodes :

• contrôle visuel — une personne compare les données tapées avec l'original ;
• double saisie — les données sont saisies deux fois et les deux copies sont comparées.

Écrire une routine de validation

Un examen demande souvent d’écrire le code d’un contrôle. Utilisez une boucle qui redemande la saisie jusqu’à ce que la valeur soit acceptable et affichez un message à l’utilisateur lorsqu’elle ne l’est pas.

Exemple corrigé. Écrivez un pseudocode permettant de saisir une note de test, qui doit être un nombre entier compris entre 0 et 100 (contrôle de plage), et de redemander la saisie jusqu’à ce qu’une note valide soit entrée.

DECLARE Mark : INTEGER
REPEAT
    OUTPUT "Enter a mark from 0 to 100"
    INPUT Mark
    IF Mark < 0 OR Mark > 100
      THEN
        OUTPUT "Invalid: the mark must be from 0 to 100"
    ENDIF
UNTIL Mark >= 0 AND Mark <= 100

La condition UNTIL correspond à la plage acceptée, et la condition IF est son contraire. Remarquez OR dans IF : une note ne peut pas être inférieure à 0 et supérieure à 100 en même temps, donc AND à cet endroit ne serait jamais vrai.

Les autres contrôles suivent le même modèle, avec une condition différente :

Un contrôle de type est généralement effectué par le langage lui-même, par exemple lorsqu’une saisie est stockée dans une variable de type INTEGER.

Un tableau de traçage enregistre la valeur de chaque variable au fur et à mesure qu'un algorithme s'exécute, étape par étape. Il vous aide à :

• vérifier qu'un algorithme fonctionne correctement ;
• déterminer ce que fait un algorithme en le suivant avec des données données.

Exemple : tracez cet algorithme avec l'entrée 5.

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

Le tableau de traçage montre que l'algorithme additionne 1 à n. Avec l'entrée 5, la sortie est 15.

Worked example. Tracez cet algorithme et donnez la sortie.

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV ne donne que la partie entière d'une division. Prenez une ligne par passage : x devient 10 (count 1), puis 5 (count 2), puis 2 (count 3), puis 1 (count 4). Maintenant x > 1 est faux, donc la boucle s'arrête et la sortie est 4. Deux habitudes protègent ces points : testez la condition avant chaque passage plutôt qu'après, et écrivez une nouvelle ligne pour chaque passage — essayer de garder les valeurs en tête est ce qui fait échouer les traces.

Trouver et corriger les erreurs

Une question courante présente un algorithme contenant des erreurs et vous demande de les trouver et de les corriger. Lisez-le ligne par ligne et demandez-vous : chaque variable reçoit-elle une valeur initiale ? Chaque boucle a-t-elle la bonne longueur ? Chaque comparaison est-elle dans le bon sens ? La sortie est-elle au bon endroit ?

Exemple corrigé. Cet algorithme doit saisir 10 nombres et afficher le plus grand. Trouvez les trois erreurs et corrigez-les.

Largest ← 1000
FOR Count ← 1 TO 9
    INPUT Number
    IF Number < Largest
      THEN
        Largest ← Number
    ENDIF
    OUTPUT Largest
NEXT Count

• Ligne 1 : la valeur initiale de Largest ← 1000 est trop élevée, donc aucun nombre ne la remplacerait. Correction : Largest ← -1000 (ou saisir le premier nombre et l’utiliser comme valeur initiale).
• Ligne 2 : la boucle ne s’exécute que 9 fois. Correction : FOR Count ← 1 TO 10.
• Ligne 4 : < trouve le plus petit nombre. Correction : IF Number > Largest.

Il y a aussi un problème avec OUTPUT : à l’intérieur de la boucle, cette instruction affiche le plus grand nombre trouvé jusque-là après chaque saisie. La déplacer après NEXT Count permet d’afficher uniquement la réponse finale. Pour chaque erreur, indiquez la ligne, expliquez ce qui ne va pas et écrivez la ligne corrigée en entier.

Test data est les données que vous utilisez pour tester un programme. Il existe quatre types que vous devez connaître.

Exemple corrigé. Un programme accepte le nombre de personnes réservant une table, de 1 à 12. Donnez des données de test de chaque type, avec le résultat attendu.

Donnez toujours le résultat attendu avec les données : un test n’est utile que si vous savez ce qui doit se produire. Une donnée extrême est la valeur limite elle-même ; les données limites forment une paire, avec une valeur de chaque côté de la limite.

Vous devez connaître ces algorithmes courants.

Recherche linéaire

Une recherche linéaire compare chaque élément avec la valeur cible, en commençant au début. Arrêter lorsque la valeur est trouvée ou que la liste se termine. La liste n'a pas besoin d'être triée. L'exemple suivant utilise les positions 1 à 4.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
    I ← I + 1
ENDWHILE
OUTPUT Found

Comparaison illustrée. La recherche de 5 compare 8, 3 puis 5 : trois comparaisons, avec Found devenant TRUE. Le quatrième élément n'est pas vérifié. La recherche de 9 compare les quatre valeurs ; Found reste FALSE. S'arrêter avant d'essayer de lire la position 5, qui est hors de cet tableau.

Tri à bulles

Un tri à bulles ordonne une liste. Comparer des valeurs adjacentes et les échanger si la valeur de gauche est supérieure. Une seule passe ne suffit généralement pas. Cette version complète répète les passes jusqu'à ce qu'une passe entière ne provoque aucun échange.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
    Swapped ← FALSE
    FOR I ← 1 TO 3
        IF List[I] > List[I + 1]
          THEN
            Temp ← List[I]
            List[I] ← List[I + 1]
            List[I + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]

Passes illustrées. Commencer avec 8, 3, 5, 1. Lors de la première passe, la liste devient 3, 8, 5, 1, puis 3, 5, 8, 1, puis 3, 5, 1, 8. Cela place la plus grande valeur à la fin mais laisse le reste non trié. La deuxième passe s'arrête à 3, 1, 5, 8 ; la troisième à 1, 3, 5, 8. La quatrième ne fait aucun échange et confirme que cette version peut s'arrêter. Réinitialiser Swapped à FALSE au début de chaque passe ; l'augmenter de TRUE à chaque échange.

Totalling and counting

Somme cumulée ajoute chaque valeur requise à un total courant : Total ← Total + Value. Comptage ajoute 1 pour chaque élément requis : Count ← Count + 1. Initialiser les deux à zéro avant de traiter les valeurs.

Exemple illustré. Quatre tentatives d'entrée sont −20, 4, 50 et 6. Accepter une valeur uniquement si elle est supérieure à −20 et inférieure à 50. Cet exemple traite quatre tentatives, pas quatre valeurs acceptées.

DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
    INPUT Value
    IF Value > -20 AND Value < 50
      THEN
        Total ← Total + Value
        Count ← Count + 1
    ENDIF
NEXT I
IF Count > 0
  THEN
    OUTPUT Total, ", ", Count, ", ", Total / Count
  ELSE
    OUTPUT "No accepted values"
ENDIF

Les limites strictes rejettent −20 et 50. Les deux mises à jour appartiennent à l'intérieur du test d'acceptation, donc les tentatives rejetées ne changent ni le total ni le compteur. La moyenne des valeurs acceptées est :

Ne pas diviser par quatre : seulement deux valeurs ont été ajoutées. Si aucune valeur n'est acceptée, le compteur est zéro et une moyenne ne peut être calculée ; afficher un message au lieu de diviser par zéro.

Transfert vers un nombre fixe de valeurs acceptées. Si une tâche demande 50 valeurs acceptées, plutôt que quatre tentatives, remplacer la boucle fixée FOR par WHILE Count < 50 et la fermer avec ENDWHILE. Conserver la même entrée et le même test d'acceptation à l'intérieur. Les entrées rejetées laissent Count inchangé, donc une nouvelle entrée est demandée. À la fin, Count est 50, bien que le nombre de tentatives puisse être supérieur. Afficher le total et calculer la moyenne comme Total / Count.

Maximum, minimum and average

Le maximum est la plus grande valeur et le minimum est la plus petite. La moyenne est la somme divisée par le nombre de valeurs. Pour une liste non vide, initialiser les deux à partir de son premier élément. Pour chaque élément restant, remplacer le maximum si la nouvelle valeur est plus grande, et remplacer le minimum si elle est plus petite.

Exemple illustré. La liste est −8, −3, −12, −5. Commencer le maximum à zéro échouerait : aucun élément de la liste n'est supérieur à zéro, donc l'algorithme afficherait un nombre qui n'est pas dans la liste. Commencer à −8 fonctionne sans supposer que les données sont positives.

DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
    IF List[I] > Maximum
      THEN
        Maximum ← List[I]
    ENDIF
    IF List[I] < Minimum
      THEN
        Minimum ← List[I]
    ENDIF
    Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4

Le maximum est −3 et le minimum est −12. La moyenne utilise les quatre valeurs :

La moyenne se situe entre le minimum et le maximum ; c'est une vérification utile, mais pas une preuve que le calcul est correct. L'initialisation à partir du premier élément nécessite une liste non vide. Gérer une liste vide séparément avant de tenter de lire cet élément.

• Les quatre étapes du cycle de vie : analyse → conception → codage → test. L'abstraction conserve uniquement l'essentiel ; la décomposition divise un problème en parties.
• Validation vérifie que les données sont cohérentes (vérifications de plage, longueur, type, présence, format) ; verification vérifie qu'elles ont été correctement copiées (visual check ou double entry).
• Apprenez les quatre types de données de test : normales (acceptées), anormales (rejetées), extrêmes (les plus grandes/plus petites encore autorisées), frontières (de part et d'autre d'une limite).
• Un tableau de trace (valeur de chaque variable à chaque étape) montre ce que fait un algorithme.
• Pour écrire une routine de validation, placez la saisie dans une boucle REPEAT … UNTIL dont la condition UNTIL correspond aux données valides.
• Lorsque vous corrigez une erreur, citez la ligne et écrivez toute la ligne corrigée.
• Connaissez les algorithmes standards : linear search (vérifier chaque élément tour à tour) et bubble sort (échanger les paires côte à côte jusqu'à ce qu'aucun échange ne soit nécessaire).