Analyser un problème et construire une solution

Question : « combien de jours entre le 1^er et le 3 mars ? » Deux jours si l'on compte les sauts d'une date à l'autre, trois si l'on compte les deux dates, un seul si l'on ne garde que les jours strictement compris entre elles. La question semblait claire ; elle admet trois réponses justes. Définir l'objectif, c'est choisir l'une d'elles et l'écrire.

La fiche d'analyse ci-dessous se met à jour selon vos choix. Une précondition est une condition que doivent remplir les données pour que la solution s'applique ; il faut décider d'avance ce qu'on fait quand elle n'est pas remplie.

Question : comment savoir qu'une solution est juste ? On écrit, avant de la programmer, un tableau d'exemples dont on connaît la réponse : les résultats attendus. Exemple : une année est-elle bissextile (366 jours) ? La règle du calendrier grégorien (1582) dit : une année est bissextile si elle est divisible par 4, sauf les années divisibles par 100, à l'exception de celles divisibles par 400.

Quatre programmes candidats sont proposés. Choisissez-en un, puis le jeu de tests : les tests « ordinaires » se contentent d'années banales, les tests « avec cas particuliers » ajoutent les années séculaires.

Question : quel jour de la semaine tombait (ou tombera) une date donnée ? Le problème paraît d'un seul bloc ; on le découpe en sous-problèmes, chacun avec ses entrées et sa sortie, jusqu'à ce que chaque morceau soit évident. C'est l'analyse descendante, ou méthode des raffinements successifs.

Point de départ connu : le 1^er janvier 1600 était un samedi. On compte les jours écoulés depuis, et le reste de la division par 7 donne le décalage. Remarquez que la brique « bissextile ? » de la planche 2 est réutilisée telle quelle : un sous-problème résolu devient une pièce qu'on assemble.

Question : résoudre ax² + bx + c = 0. La formule apprise au lycée, x = (−b ± √Δ)/(2a) avec Δ = b² − 4ac, ne marche que dans le cas général. Que se passe-t-il si a = 0 ? si Δ est négatif ? si tous les coefficients sont nuls ? Chaque question ajoute une branche à l'organigramme.

Un dernier cas est plus sournois : quand b est très grand devant a et c, −b + √Δ soustrait deux nombres presque égaux, et l'ordinateur, qui ne garde qu'environ 16 chiffres significatifs, perd presque tout. On l'appelle l'annulation catastrophique. Le remède consiste à calculer d'abord la racine sans soustraction, puis l'autre par le produit des racines x₁x₂ = c/a.

Le banc d'essai des cas particuliers

Question : un point est-il à l'intérieur d'un polygone ? C'est ce que fait un logiciel de cartographie quand on clique sur une commune, ou un jeu vidéo quand il teste une collision. On applique les quatre étapes de la démarche.

Deux programmes appliquent la même idée. Le naïf compte un côté dès que le rayon le touche, extrémités comprises. Le robuste commence par l'étape ① et adopte une règle de demi-ouverture : un côté ne compte que si l'une de ses extrémités est strictement au-dessus du rayon et l'autre non — un sommet posé sur le rayon est traité comme s'il était juste en dessous. Une troisième méthode, indépendante, sert d'arbitre : la somme des angles sous lesquels P voit chaque côté vaut 360° à l'intérieur et 0° à l'extérieur.