Mit Funktionen entwerfen

Schrittweise Verfeinerung

Von der Aufgabenstellung zu einem main aus wenigen Zeilen

Die Programme der Einheit 4 wurden vollständig in main geschrieben. Solange sie auf einen Bildschirm passen, ist das hinnehmbar; ein Programm von zweihundert Zeilen, so geschrieben, verlangt jedoch, alles gleichzeitig im Kopf zu haben, und lässt nur den Test des Ganzen zu. Die schrittweise Verfeinerung, oder der absteigende Entwurf, kehrt die Reihenfolge der Arbeit um: Zuerst schreibt man, was das Programm tut, in der Sprache des Problems, als Folge von Aufrufen von Funktionen, die es noch nicht gibt; danach nimmt man jede dieser Funktionen als ein neues, kleineres Problem und wiederholt das Verfahren, bis man bei Funktionen ankommt, die so einfach sind, dass ihr Rumpf geschrieben wird, ohne etwas zu zerlegen.

Das folgende Problem dient als Beispiel. Eine ganze Zahl $n \geq 1$ heißt vollkommen, wenn die Summe ihrer echten Teiler (der positiven, die von $n$ verschieden sind) gleich $n$ ist, defizient, wenn sie kleiner ist, und abundant, wenn sie größer ist: $28 = 1 + 2 + 4 + 7 + 14$ ist vollkommen; 8 ist mit $1 + 2 + 4 = 7$ defizient; 12 mit $1 + 2 + 3 + 4 + 6 = 16$ abundant. Gesucht ist ein Programm, das $n$ einliest und die Summe seiner echten Teiler sowie seine Art ausgibt. Die erste Ebene des Entwurfs ist main, und sie wird vor allem anderen geschrieben:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Summe der positiven Teiler von n.// Vorbedingung: n >= 1.// Nachbedingung: gibt die Summe aller positiven Teiler von n zurück, n eingeschlossen.std::int64_t divisorSum(int n);​// Art von n nach der Summe seiner echten Teiler.// Vorbedingung: n >= 1.// Nachbedingung: gibt deficient, perfect oder abundant zurück, je nachdem, ob die Summe kleiner, gleich oder größer als n ist.Kind classify(int n);​// Name einer Art, um ihn auszugeben.// Vorbedingung: keine.// Nachbedingung: gibt „defizient“, „vollkommen“ oder „abundant“ zurück.std::string kindName(Kind kind);​int main(){    int n{};    std::cin >> n;    std::println("Summe der echten Teiler von {}: {}", n, divisorSum(n) - n);    std::println("{} ist {}", 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

Das Programm wird ohne jede Warnung kompiliert, weil jeder Aufruf mit seiner Deklaration übereinstimmt, und das ist das Einzige, was der Compiler prüft, wie die Lektion Funktionen gezeigt hat. Was scheitert, ist das Linken: Der Linker sucht die Definitionen und findet sie nicht („undefined reference“, undefinierte Referenz; der Zusatz [abi:cxx11] ist eine interne Markierung von GCC für Funktionen, die std::string zurückgeben). Dieser Zustand ist genau der des Entwurfs an diesem Punkt: Die Schnittstellen sind entschieden, die Rümpfe nicht. Wenn dem so ist, liest sich main bereits wie die Spezifikation des Programms, und die drei Deklarationen sind die offenen Aufgaben, jede kleiner als das ursprüngliche Problem.

Der Zerlegungsbaum

Die zweite Ebene steigt in jede Deklaration hinab. kindName ist eine Entscheidung mit drei Fällen. classify stützt sich auf divisorSum: Eine Zahl ist vollkommen, wenn die Summe aller ihrer Teiler $2n$ beträgt. Und divisorSum ist die Schleife über die Teiler in Paaren $(d, n/d)$ aus der Lektion Numerische Algorithmen, die bei $\sqrt{n}$ anhält. Das Ergebnis wird als Baum gezeichnet: Die Wurzel ist das vollständige Problem; die Kinder jedes Knotens sind die Teilprobleme, die ihn lösen; die Blätter sind Operationen, die die Sprache bereits bietet.

Ist der Baum vollständig, schreibt man die Definitionen von unten nach oben, sodass sich jede Funktion auf andere, bereits geschriebene stützt:

#include <cstdint>#include <iostream>#include <print>#include <string>​enum class Kind { deficient, perfect, abundant };​// Summe der positiven Teiler von n.// Vorbedingung: n >= 1.// Nachbedingung: gibt die Summe aller positiven Teiler von n zurück, n eingeschlossen.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;}​// Art von n nach der Summe seiner echten Teiler.// Vorbedingung: n >= 1.// Nachbedingung: gibt deficient, perfect oder abundant zurück, je nachdem, ob die Summe kleiner, gleich oder größer als n ist.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;}​// Name einer Art, um ihn auszugeben.// Vorbedingung: keine.// Nachbedingung: gibt „defizient“, „vollkommen“ oder „abundant“ zurück.std::string kindName(Kind kind){    if (kind == Kind::deficient) {        return "defizient";    }    if (kind == Kind::perfect) {        return "vollkommen";    }    return "abundant";}​int main(){    int n{};    std::cin >> n;    std::println("Summe der echten Teiler von {}: {}", n, divisorSum(n) - n);    std::println("{} ist {}", n, kindName(classify(n)));}

28

Summe der echten Teiler von 28: 2828 ist vollkommen

Drei Züge des Ergebnisses gehen auf die Methode zurück. Erstens hat sich main nicht geändert, als das Darunterliegende geschrieben wurde. Zweitens wird die Summe als std::int64_t zurückgegeben (aus <cstdint>, die 64-Bit-Ganzzahl, die auch die Lektion Rekursion verwendet), weil für $n$ nahe dem Maximum von int die Summe seiner Teiler dieses überschreiten kann, und die Entscheidung in der Schnittstelle schützt alle Aufrufer. Drittens wird jede Funktion einzeln geprüft: divisorSum(28) muss 56 ergeben, divisorSum(1) muss 1 ergeben und divisorSum(36) muss 91 ergeben, wobei das Paar $(6, 6)$ nur einmal gezählt wird; der letzte Teil der Lektion macht aus diesen Prüfungen ein Programm.