Concevoir avec des fonctions

Raffinement successif

De l’énoncé à un main de quelques lignes

Les programmes de l’unité 4 ont été écrits entièrement à l’intérieur de main. Tant qu’ils tiennent sur un écran, on le tolère ; or un programme de deux cents lignes écrit ainsi exige de tout avoir en tête à la fois, et n’admet que le test de l’ensemble. Le raffinement successif, ou conception descendante, inverse l’ordre du travail : on écrit d’abord ce que fait le programme, dans le langage du problème, comme une suite d’appels à des fonctions qui n’existent pas encore ; on prend ensuite chacune de ces fonctions comme un problème nouveau, plus petit, et on répète la procédure jusqu’à arriver à des fonctions si simples que leur corps s’écrit sans rien décomposer.

Le problème suivant sert d’exemple. Un entier $n \geq 1$ est parfait si la somme de ses diviseurs propres (les diviseurs strictement positifs distincts de $n$) est égale à $n$, déficient si elle est strictement inférieure et abondant si elle est strictement supérieure : $28 = 1 + 2 + 4 + 7 + 14$ est parfait ; 8, avec $1 + 2 + 4 = 7$, est déficient ; 12, avec $1 + 2 + 3 + 4 + 6 = 16$, abondant. On veut un programme qui lise $n$ et écrive la somme de ses diviseurs propres et sa catégorie. Le premier niveau de la conception est main, et il s’écrit avant toute chose :

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Somme des diviseurs strictement positifs de n.// Précondition : n >= 1.// Postcondition : renvoie la somme de tous les diviseurs strictement positifs de n, n compris.std::int64_t divisorSum(int n);​// Catégorie de n selon la somme de ses diviseurs propres.// Précondition : n >= 1.// Postcondition : renvoie deficient, perfect ou abundant selon que la somme est inférieure, égale ou supérieure à n.Kind classify(int n);​// Nom d'une catégorie, pour l'écrire.// Précondition : aucune.// Postcondition : renvoie « déficient », « parfait » ou « abondant ».std::string kindName(Kind kind);​int main(){    int n{};    std::cin >> n;    std::println("Somme des diviseurs propres de {} : {}", n, divisorSum(n) - n);    std::println("{} est {}", n, kindName(classify(n)));}

/usr/bin/x86_64-linux-gnu-ld.bfd: main.o: in function `main':main.cpp:27:(.text+0x22a): undefined reference to `divisorSum(int)'/usr/bin/x86_64-linux-gnu-ld.bfd: main.cpp:28:(.text+0x3fd): undefined reference to `classify(int)'/usr/bin/x86_64-linux-gnu-ld.bfd: main.cpp:28:(.text+0x40d): undefined reference to `kindName[abi:cxx11](Kind)'collect2: error: ld returned 1 exit status

Le programme se compile sans aucun avertissement, parce que chaque appel concorde avec sa déclaration, qui est la seule chose que le compilateur vérifie, comme l’a enseigné la leçon Fonctions. Ce qui échoue, c’est l’édition de liens : l’éditeur de liens cherche les définitions et ne les trouve pas (« undefined reference », référence non définie ; l’ajout [abi:cxx11] est une marque interne de GCC pour les fonctions qui renvoient std::string). Cet état est exactement celui de la conception à ce stade : les interfaces sont décidées, les corps ne le sont pas. Si cela est ainsi, main se lit déjà comme la spécification du programme, et les trois déclarations sont les tâches en attente, chacune plus petite que le problème d’origine.

L’arbre de la décomposition

Le deuxième niveau descend dans chaque déclaration. kindName est une décision à trois cas. classify s’appuie sur divisorSum : un nombre est parfait quand la somme de tous ses diviseurs vaut $2n$. Et divisorSum est la boucle des diviseurs par paires $(d, n/d)$ de la leçon Algorithmes numériques, qui s’arrête à $\sqrt{n}$. Le résultat se dessine comme un arbre : la racine est le problème complet ; les enfants de chaque nœud, les sous-problèmes qui le résolvent ; les feuilles, des opérations que le langage offre déjà.

Une fois l’arbre complet, on écrit les définitions de bas en haut, de sorte que chaque fonction s’appuie sur d’autres déjà écrites :

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Somme des diviseurs strictement positifs de n.// Précondition : n >= 1.// Postcondition : renvoie la somme de tous les diviseurs strictement positifs de n, n compris.std::int64_t divisorSum(int n){    std::int64_t sum{0};    for (int d{1}; d <= n / d; ++d) {        if (n % d == 0) {            sum += d;            if (d != n / d) {                sum += n / d;            }        }    }    return sum;}​// Catégorie de n selon la somme de ses diviseurs propres.// Précondition : n >= 1.// Postcondition : renvoie deficient, perfect ou abundant selon que la somme est inférieure, égale ou supérieure à n.Kind classify(int n){    const std::int64_t proper{divisorSum(n) - n};    if (proper < n) {        return Kind::deficient;    }    if (proper == n) {        return Kind::perfect;    }    return Kind::abundant;}​// Nom d'une catégorie, pour l'écrire.// Précondition : aucune.// Postcondition : renvoie « déficient », « parfait » ou « abondant ».std::string kindName(Kind kind){    if (kind == Kind::deficient) {        return "déficient";    }    if (kind == Kind::perfect) {        return "parfait";    }    return "abondant";}​int main(){    int n{};    std::cin >> n;    std::println("Somme des diviseurs propres de {} : {}", n, divisorSum(n) - n);    std::println("{} est {}", n, kindName(classify(n)));}

28

Somme des diviseurs propres de 28 : 2828 est parfait

Trois traits du résultat sont dus à la méthode. D’abord, main n’a pas changé quand on a écrit ce qui se trouve en dessous. Ensuite, la somme est renvoyée comme std::int64_t (de <cstdint>, l’entier de 64 bits que la leçon Récursivité utilise aussi), parce que pour $n$ proche du maximum de int la somme de ses diviseurs peut le dépasser, et le décider dans l’interface protège tous ceux qui appellent. Enfin, chaque fonction se vérifie séparément : divisorSum(28) doit donner 56, divisorSum(1) doit donner 1 et divisorSum(36) doit donner 91, où la paire $(6, 6)$ ne compte qu’une fois ; la dernière partie de la leçon transforme ces vérifications en un programme.