Σχεδίαση με συναρτήσεις

Σταδιακή εκλέπτυνση

Από την εκφώνηση σε μια main λίγων γραμμών

Τα προγράμματα της ενότητας 4 γράφτηκαν ολόκληρα μέσα στη main. Όσο χωρούν σε μία οθόνη, αυτό γίνεται ανεκτό· ωστόσο ένα πρόγραμμα διακοσίων γραμμών γραμμένο έτσι απαιτεί να τα έχει κανείς όλα στο μυαλό του ταυτόχρονα και δέχεται μόνο τη δοκιμή του συνόλου. Η σταδιακή εκλέπτυνση, ή καθοδικός σχεδιασμός, αντιστρέφει τη σειρά της δουλειάς: πρώτα γράφεται τι κάνει το πρόγραμμα, στη γλώσσα του προβλήματος, ως ακολουθία κλήσεων σε συναρτήσεις που δεν υπάρχουν ακόμη· έπειτα κάθε τέτοια συνάρτηση αντιμετωπίζεται ως νέο, μικρότερο πρόβλημα, και η διαδικασία επαναλαμβάνεται ώσπου να φτάσουμε σε συναρτήσεις τόσο απλές ώστε το σώμα τους να γράφεται χωρίς να αποσυνθέσουμε τίποτα.

Ως παράδειγμα χρησιμεύει το ακόλουθο πρόβλημα. Ένας ακέραιος $n \geq 1$ είναι τέλειος αν το άθροισμα των γνήσιων διαιρετών του (των θετικών που είναι διαφορετικοί από τον $n$) ισούται με $n$, ελλιπής αν είναι μικρότερο και υπερτέλειος αν είναι μεγαλύτερο: $28 = 1 + 2 + 4 + 7 + 14$ είναι τέλειος· ο 8, με $1 + 2 + 4 = 7$, είναι ελλιπής· ο 12, με $1 + 2 + 3 + 4 + 6 = 16$, υπερτέλειος. Ζητείται πρόγραμμα που διαβάζει τον $n$ και γράφει το άθροισμα των γνήσιων διαιρετών του και την κατηγορία του. Το πρώτο επίπεδο του σχεδιασμού είναι η main, και γράφεται πριν από οτιδήποτε άλλο:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Άθροισμα των θετικών διαιρετών του n.// Προσυνθήκη: n >= 1.// Μετασυνθήκη: επιστρέφει το άθροισμα όλων των θετικών διαιρετών του n, μαζί με τον n.std::int64_t divisorSum(int n);​// Κατηγορία του n με βάση το άθροισμα των γνήσιων διαιρετών του.// Προσυνθήκη: n >= 1.// Μετασυνθήκη: επιστρέφει deficient, perfect ή abundant αν το άθροισμα είναι μικρότερο, ίσο ή μεγαλύτερο από n.Kind classify(int n);​// Όνομα μιας κατηγορίας, για να γραφτεί.// Προσυνθήκη: καμία.// Μετασυνθήκη: επιστρέφει «ελλιπής», «τέλειος» ή «υπερτέλειος».std::string kindName(Kind kind);​int main(){    int n{};    std::cin >> n;    std::println("Γνήσιοι διαιρέτες του {}: άθροισμα {}", 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

Το πρόγραμμα μεταγλωττίζεται χωρίς καμία προειδοποίηση, γιατί κάθε κλήση συμφωνεί με τη δήλωσή της, που είναι το μόνο που ελέγχει ο μεταγλωττιστής, όπως δίδαξε το μάθημα Συναρτήσεις. Εκείνο που αποτυγχάνει είναι η σύνδεση: ο συνδέτης αναζητά τους ορισμούς και δεν τους βρίσκει («undefined reference», αναφορά χωρίς ορισμό· η προσθήκη [abi:cxx11] είναι εσωτερική σήμανση του GCC για τις συναρτήσεις που επιστρέφουν std::string). Αυτή η κατάσταση είναι ακριβώς η κατάσταση του σχεδιασμού σε αυτό το σημείο: οι διεπαφές έχουν αποφασιστεί, τα σώματα όχι. Αν αυτό ισχύει, η main διαβάζεται ήδη ως η προδιαγραφή του προγράμματος, και οι τρεις δηλώσεις είναι οι εκκρεμείς εργασίες, η καθεμία μικρότερη από το αρχικό πρόβλημα.

Το δέντρο της αποσύνθεσης

Το δεύτερο επίπεδο κατεβαίνει σε κάθε δήλωση. Η kindName είναι μια απόφαση τριών περιπτώσεων. Η classify στηρίζεται στη divisorSum: ένας αριθμός είναι τέλειος όταν το άθροισμα όλων των διαιρετών του είναι $2n$. Και η divisorSum είναι ο βρόχος των διαιρετών σε ζεύγη $(d, n/d)$ από το μάθημα Αριθμητικοί αλγόριθμοι, που σταματά στο $\sqrt{n}$. Το αποτέλεσμα σχεδιάζεται ως δέντρο: η ρίζα είναι το πλήρες πρόβλημα· τα παιδιά κάθε κόμβου, τα υποπροβλήματα που τον λύνουν· τα φύλλα, πράξεις που η γλώσσα ήδη προσφέρει.

Με το δέντρο πλήρες, οι ορισμοί γράφονται από κάτω προς τα πάνω, ώστε κάθε συνάρτηση να στηρίζεται σε άλλες ήδη γραμμένες:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Άθροισμα των θετικών διαιρετών του n.// Προσυνθήκη: n >= 1.// Μετασυνθήκη: επιστρέφει το άθροισμα όλων των θετικών διαιρετών του n, μαζί με τον 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;}​// Κατηγορία του n με βάση το άθροισμα των γνήσιων διαιρετών του.// Προσυνθήκη: n >= 1.// Μετασυνθήκη: επιστρέφει deficient, perfect ή abundant αν το άθροισμα είναι μικρότερο, ίσο ή μεγαλύτερο από 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;}​// Όνομα μιας κατηγορίας, για να γραφτεί.// Προσυνθήκη: καμία.// Μετασυνθήκη: επιστρέφει «ελλιπής», «τέλειος» ή «υπερτέλειος».std::string kindName(Kind kind){    if (kind == Kind::deficient) {        return "ελλιπής";    }    if (kind == Kind::perfect) {        return "τέλειος";    }    return "υπερτέλειος";}​int main(){    int n{};    std::cin >> n;    std::println("Γνήσιοι διαιρέτες του {}: άθροισμα {}", n, divisorSum(n) - n);    std::println("Ο {} είναι {}", n, kindName(classify(n)));}

28

Γνήσιοι διαιρέτες του 28: άθροισμα 28Ο 28 είναι τέλειος

Τρία γνωρίσματα του αποτελέσματος οφείλονται στη μέθοδο. Πρώτον, η main δεν άλλαξε όταν γράφτηκαν όσα βρίσκονται από κάτω. Δεύτερον, το άθροισμα επιστρέφεται ως std::int64_t (από τη <cstdint>, ο ακέραιος των 64 bit που χρησιμοποιεί και το μάθημα Αναδρομή), γιατί για $n$ κοντά στο μέγιστο του int το άθροισμα των διαιρετών του μπορεί να το υπερβεί, και η απόφαση μέσα στη διεπαφή προστατεύει όλους όσοι καλούν. Τρίτον, κάθε συνάρτηση ελέγχεται χωριστά: η divisorSum(28) πρέπει να δώσει 56, η divisorSum(1) πρέπει να δώσει 1 και η divisorSum(36) πρέπει να δώσει 91, όπου το ζεύγος $(6, 6)$ μετριέται μία μόνο φορά· η τελευταία παράγραφος του μαθήματος μετατρέπει αυτούς τους ελέγχους σε πρόγραμμα.