Progettare con le funzioni

Raffinamento successivo

Dall’enunciato a un main di poche righe

I programmi dell’unità 4 sono stati scritti interamente dentro main. Finché stanno in uno schermo, lo si tollera; tuttavia, un programma di duecento righe scritto così esige di tenere tutto in testa nello stesso momento, e ammette soltanto il test dell’insieme. Il raffinamento successivo, o progettazione discendente, inverte l’ordine del lavoro: prima si scrive ciò che il programma fa, nel linguaggio del problema, come una sequenza di chiamate a funzioni che ancora non esistono; poi si prende ciascuna di quelle funzioni come un problema nuovo, più piccolo, e si ripete il procedimento fino ad arrivare a funzioni così semplici che il loro corpo si scrive senza scomporre nulla.

Il problema seguente serve da esempio. Un intero $n \geq 1$ è perfetto se la somma dei suoi divisori propri (quelli positivi diversi da $n$) è uguale a $n$, difettivo se è minore e abbondante se è maggiore: $28 = 1 + 2 + 4 + 7 + 14$ è perfetto; l’8, con $1 + 2 + 4 = 7$, è difettivo; il 12, con $1 + 2 + 3 + 4 + 6 = 16$, abbondante. Si vuole un programma che legga $n$ e scriva la somma dei suoi divisori propri e la sua categoria. Il primo livello del progetto è main, e si scrive prima di tutto:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Somma dei divisori positivi di n.// Precondizione: n >= 1.// Postcondizione: restituisce la somma di tutti i divisori positivi di n, compreso n.std::int64_t divisorSum(int n);​// Categoria di n secondo la somma dei suoi divisori propri.// Precondizione: n >= 1.// Postcondizione: restituisce deficient, perfect o abundant a seconda che la somma sia minore, uguale o maggiore di n.Kind classify(int n);​// Nome di una categoria, per scriverlo.// Precondizione: nessuna.// Postcondizione: restituisce «difettivo», «perfetto» o «abbondante».std::string kindName(Kind kind);​int main(){    int n{};    std::cin >> n;    std::println("Somma dei divisori propri di {}: {}", n, divisorSum(n) - n);    std::println("{} è {}", 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

Il programma si compila senza alcun avviso, perché ogni chiamata concorda con la sua dichiarazione, che è l’unica cosa che il compilatore verifica, come ha insegnato la lezione Funzioni. Ciò che fallisce è il collegamento: il linker cerca le definizioni e non le trova («undefined reference», riferimento non definito; l’aggiunta [abi:cxx11] è un marchio interno di GCC per le funzioni che restituiscono std::string). Questo stato è esattamente quello del progetto a questo punto: le interfacce sono decise, i corpi no. Se le cose stanno così, main si legge già come la specifica del programma, e le tre dichiarazioni sono i compiti in sospeso, ciascuno più piccolo del problema originale.

L’albero della scomposizione

Il secondo livello scende in ogni dichiarazione. kindName è una decisione a tre casi. classify si appoggia a divisorSum: un numero è perfetto quando la somma di tutti i suoi divisori è $2n$. E divisorSum è il ciclo dei divisori a coppie $(d, n/d)$ della lezione Algoritmi numerici, che si ferma a $\sqrt{n}$. Il risultato si disegna come un albero: la radice è il problema completo; i figli di ogni nodo, i sottoproblemi che lo risolvono; le foglie, operazioni che il linguaggio offre già.

Con l’albero completo, si scrivono le definizioni dal basso verso l’alto, in modo che ogni funzione si appoggi ad altre già scritte:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Somma dei divisori positivi di n.// Precondizione: n >= 1.// Postcondizione: restituisce la somma di tutti i divisori positivi di n, compreso n.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;}​// Categoria di n secondo la somma dei suoi divisori propri.// Precondizione: n >= 1.// Postcondizione: restituisce deficient, perfect o abundant a seconda che la somma sia minore, uguale o maggiore di 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;}​// Nome di una categoria, per scriverlo.// Precondizione: nessuna.// Postcondizione: restituisce «difettivo», «perfetto» o «abbondante».std::string kindName(Kind kind){    if (kind == Kind::deficient) {        return "difettivo";    }    if (kind == Kind::perfect) {        return "perfetto";    }    return "abbondante";}​int main(){    int n{};    std::cin >> n;    std::println("Somma dei divisori propri di {}: {}", n, divisorSum(n) - n);    std::println("{} è {}", n, kindName(classify(n)));}

28

Somma dei divisori propri di 28: 2828 è perfetto

Tre tratti del risultato si devono al metodo. Primo, main non è cambiato quando si è scritto ciò che sta sotto. Secondo, la somma si restituisce come std::int64_t (da <cstdint>, l’intero a 64 bit che usa anche la lezione Ricorsione), perché per $n$ vicino al massimo di int la somma dei suoi divisori può superarlo, e deciderlo nell’interfaccia protegge tutti quelli che chiamano. Terzo, ogni funzione si verifica separatamente: divisorSum(28) deve dare 56, divisorSum(1) deve dare 1 e divisorSum(36) deve dare 91, dove la coppia $(6, 6)$ si conta una sola volta; l’ultima parte della lezione trasforma queste verifiche in un programma.