Español
English
Português
中文 (中国)
العربية
हिन्दी
Русский
Français
Ελληνικά
Italiano
日本語
한국어
LatineZusammenfassung
Diese Lektion eröffnet die sechste Einheit des Kurses, die den zusammengesetzten Daten gewidmet ist. Sie erklärt, wozu die Einheit dient: zu lehren, wie man Sammlungen von Daten darstellt (Folgen fester und variabler Größe, Tabellen und Datensätze) und wie man sie mit den grundlegenden Algorithmen verarbeitet, von Hand geschrieben und der Bibliothek entnommen, und dabei abschätzt, was sie kosten; sie stellt ihre sechs Lektionen vor und den Faden, der sie verbindet; sie erinnert daran, was die Einheit voraussetzt, vor allem die Schleifen mit Invariante und die Übergabe per konstanter Referenz; sie formuliert das Problem, das die Einheit löst, das eines Programms, das Daten speichern muss, deren Anzahl es nicht kennt, und das, mit einzelnen Variablen geschrieben, die überzähligen stillschweigend übergeht; sie nimmt die Kosten als zweites Maß eines Algorithmus neben seiner Korrektheit vorweg; und sie zeigt, wohin sie führt, in den folgenden Einheiten und im Kurs Programmieren in C++ II.
Lernziele
- Die Abfolge der Inhalte der Einheit beschreiben und erklären, was jede Lektion zur nächsten beiträgt.
- Die Schleifen, ihre Invarianten und die Parameterübergabe (per Wert, per Referenz und per konstanter Referenz) in Erinnerung rufen und sie bei Bedarf wiederholen.
- An einem Beispiel die Kosten eines Algorithmus als zweites Maß seiner Qualität neben seiner Korrektheit vorwegnehmen.
- Erkennen, was man am Ende der Einheit können soll, und es von dem unterscheiden, was man in den folgenden Einheiten lernen wird.
Eingangstest
Bevor man die Einheit durcharbeitet, lohnt es sich, den Ausgangspunkt zu bestimmen. Dieser Test ist eine Selbstüberprüfung: Er wird nicht benotet, und sein einziger Zweck ist es, das Lernen zu leiten. Die ersten vier Fragen prüfen, was die Einheit voraussetzt: die Invariante der Schleife, die ein Maximum sucht, die Art der Übergabe eines großen Parameters, die Anzahl der Durchläufe zweier verschachtelter Schleifen und die vorzeichenlose Arithmetik. Die sechs folgenden behandeln in der Reihenfolge der Lektionen die zentralen Ideen der Einheit: die gültigen Indizes einer Folge, das Erzeugen eines Vektors, wie oft sich eine Größe halbieren lässt, die Suche in sortierten Daten, den doppelten Index einer Tabelle und die Gefahr, die Daten ein und derselben Entität in getrennten Sammlungen zu speichern. Niemand muss sie schon richtig beantworten, und bei einigen von ihnen ist „Das weiß ich noch nicht“ eine ehrliche Antwort: Jede Antwort, ob richtig oder nicht, erklärt den Punkt und nennt die Lektion, die ihn behandelt. Dieselben Fertigkeiten werden am Ende erneut gemessen, in der Synthese-Lektion.
Miss vor Beginn der Einheit deinen Ausgangspunkt. Es ist eine kurze Selbsteinschätzung: Sie wird nicht benotet, und das Ergebnis wird nur in deinem Browser gespeichert.
Frage 1Aus früheren EinheitenDas Fragment
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }soll inlargestdie höchste der eingelesenen Temperaturen hinterlassen. Bei welcher Eingabe versagt es?Der erste Durchlauf vergleicht den Wert mit 0 und behält ihn, wenn er positiv ist: Mit einem einzigen positiven Wert ist das Ergebnis korrekt. Es lohnt sich, den Ablauf zu verfolgen, bevor man antwortet.Mit>ersetzt ein Wert, der dem Maximum gleicht, dieses nicht, aber das Maximum ist dieselbe Zahl: Die Wiederholung ändert das Ergebnis nicht.Verrät, dass die Initialisierung nicht an der Invariante geprüft wurde: Eine korrekte Schleife verlangt, dass die Invariante vor dem ersten Durchlauf gilt.Die gewünschte Invariante, „largestist das Maximum des bisher Eingelesenen“, gilt am Anfang nicht, denn bevor etwas eingelesen ist, gibt es kein Maximum, und die anfängliche 0 schlägt jeden negativen Wert. Man korrigiert es, indem man mit dem ersten Wert initialisiert, nachdem man geprüft hat, dass er existiert. Die Lektion Vektoren tut dasselbe auf einer gespeicherten Folge, und die Bibliothek drückt es mitstd::ranges::maxaus, dessen Vorbedingung lautet, dass die Folge nicht leer ist.Wiederholen: Korrekte Schleifen entwerfen
Frage 2Aus früheren EinheitenEine Funktion berechnet, wie viele Vokale ein Text von einer Million Zeichen enthält, der in einem
std::stringgespeichert ist, und verändert ihn nicht. Wie deklariert man ihren Parameter am besten?Die Wertübergabe kopiert die Million Zeichen bei jedem Aufruf: Sie ist korrekt, zahlt aber Kosten, die nichts bringen.Diese Deklaration kopiert nicht, erlaubt aber, den Text ohne Not zu verändern, und nimmt weder ein Literal noch ein temporäres Objekt an: Die Antwort verwechselt „nicht kopieren“ mit „verändern erlauben“.Die Art der Übergabe gehört zur Schnittstelle: Die Wertübergabe verspricht der Funktion eine eigene Kopie, und das Programm muss sie anfertigen.Die konstante Referenz liest den Text, ohne ihn zu kopieren und ohne die Erlaubnis, ihn zu verändern, und nimmt außerdem ein temporäres Objekt an. In Einheit 6 wird diese Wahl zur Regel: Eine Funktion, die einen Vektor von einer Million Elementen liest, erhält ihn alsconst std::vector<int>&, und die unnötige Kopie wird zum häufigsten Kostenfehler.Wiederholen: Parameter und Gültigkeitsbereich
Frage 3Aus früheren EinheitenWie oft wird
++countinfor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }ausgeführt?Richtige Antwort:
Die innere Schleife macht 0 Durchläufe bei , einen bei und so fort bis 5 bei : insgesamt , also . Die Lektion Die Kosten eines Algorithmus verallgemeinert die Rechnung: Zwei Schleifen, die alle Paare von Elementen durchgehen, machen Durchläufe, und diese Zahl entscheidet, ob ein Algorithmus für eine Million Elemente taugt.Wiederholen: Schleifen
Frage 4Aus früheren EinheitenWas schreibt
std::println("{}", 0u - 1);auf einem System, in demunsigned int32 Bit hat?Glaubt, ein vorzeichenloser Typ lasse negative Werte zu.Glaubt, die Subtraktion bleibe beim kleinsten Wert des Typs stehen; die vorzeichenlose Arithmetik überschlägt sich, sie sättigt nicht.Verwechselt eine mögliche Warnung mit einem Fehler: Der Ausdruck ist gültig, und sein Wert ist definiert.Die vorzeichenlose Arithmetik ist modular: 1 von 0 abzuziehen überschlägt sich zum größten Wert des Typs, . Einheit 6 misst Größen mitstd::size_t, das ebenfalls vorzeichenlos ist, sodassv.size() - 1bei einem leeren Vektor nicht ergibt, sondern eine riesige Zahl; die Lektion Arrays warnt vor dieser Subtraktion, und die Lektion Vektoren zeigt die Schleife, die ihretwegen die Grenzen verlässt.Wiederholen: Ganze Zahlen und ihre Darstellung
Frage 5In einer Folge von Elementen, die wie in C++ nummeriert sind: Welche Indizes bezeichnen ein Element?
Nummeriert von eins an, wie in der Alltagssprache; in C++ liegta[n]bereits außerhalb der Folge.Das ist der häufigste Off-by-one-Fehler: Er zählt Indizes für Elemente.Das ist eine ehrliche Antwort: Lektion 6.1 erklärt es, mit dem Grund, weshalb man von null an zählt.Der Index von C++ zählt von null an, weil er der Versatz vom ersten Element aus ist: Das erste ista[0]und das letztea[n - 1]. Mit[]auf einen Index außerhalb dieses Intervalls zuzugreifen, ist undefiniertes Verhalten, und die Lektion Arrays lehrt, mit der Schleifeninvariante zu beweisen, dass jeder Zugriff gültig ist.Wiederholen: Arrays
Frage 6Was enthält
vnachstd::vector<int> v(3, 7);?Liest die runden Klammern, als wären es geschweifte.Vertauscht die Rollen der beiden Zahlen.Das ist eine ehrliche Antwort: Lektion 6.2 stellt den Vektor und die Arten vor, ihn zu erzeugen.Mit runden Klammern ist die erste Zahl die Anzahl und die zweite der Wert jedes Elements; mit geschweiften Klammern iststd::vector<int> v{3, 7};die Liste der Elemente, die 3 und die 7. Der Vektor ist der erste Typ des Kurses, bei dem geschweifte und runde Klammern Verschiedenes besagen, und die Lektion Vektoren zeigt es mit einem Programm.Wiederholen: Vektoren
Frage 7Wie viele Durchläufe macht
for (int m{1024}; m > 1; m /= 2) { ... }?Richtige Antwort:
Die Werte vonmzu Beginn jedes Durchlaufs sind 1024, 512, 256, 128, 64, 32, 16, 8, 4 und 2: zehn Durchläufe, weil gilt, und zehn ist . Ein Algorithmus, der sein Problem bei jedem Schritt halbiert, braucht größenordnungsmäßig Schritte, und die Lektion Die Kosten eines Algorithmus nennt ihn logarithmisch: Bei einer Milliarde Elementen genügen ihm etwa dreißig.Wiederholen: Die Kosten eines Algorithmus
Frage 8Ein Telefonbuch enthält eine Million Namen in alphabetischer Reihenfolge. Um einen zu finden, schlägt man es in der Mitte auf, verwirft die Hälfte, in der der Name nicht stehen kann, und wiederholt das mit der anderen. Wie oft muss man es höchstens aufschlagen?
Das ist die Rechnung der Suche, die die Namen einen nach dem anderen prüft: Ohne die Ordnung auszunutzen, durchläuft man im Mittel die Hälfte des Telefonbuchs.Das ist die Quadratwurzel aus einer Million: Verwechselt das Halbieren des Teilstücks mit dem Aufteilen in Blöcke.Verwendet den dekadischen Logarithmus: Jedes Aufschlagen verwirft die Hälfte, nicht neun Zehntel.Jedes Aufschlagen halbiert das Teilstück, in dem der Name stehen kann, und übersteigt eine Million: Nach zwanzig Halbierungen bleibt ein einziger Name übrig. Das ist die binäre Suche der Lektion Suchen und Sortieren, die nur funktioniert, wenn die Daten sortiert sind, und die sich mit einer Invariante begründen lässt.Wiederholen: Suchen und Sortieren
Frage 9Bei
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};: Welche Werte habent[1][0]undt.size()?Liest den ersten Index als Spalte und zählt die Spalten statt der Zeilen.Glaubt,size()zähle alle Zellen der Tabelle.Das ist eine ehrliche Antwort: Lektion 6.5 stellt die Tabellen als Vektoren von Vektoren vor.Frage 10Ein Programm speichert die Namen einer Gruppe in einem Vektor und ihre Noten in einem anderen, sodass die Note
grades[i]die vonnames[i]ist. Was geschieht, wenn es nur den Vektor der Noten sortiert?Für den Compiler sind die beiden Vektoren unabhängig: Die Beziehung existiert nur im Kopf dessen, der das Programm geschrieben hat.Der Algorithmus erhält einen einzigen Vektor und weiß nichts von der Existenz des anderen.Jeder Zugriff ist gültig und jedes Ergebnis definiert: Der Mangel ist ein logischer, und deshalb meldet ihn keiner der beiden Sanitizer des Kurses (der für Speicherfehler, AddressSanitizer, und der für undefiniertes Verhalten, UndefinedBehaviorSanitizer).Die Zuordnung zwischen den beiden Vektoren ist eine Vereinbarung, die in keinem Typ geschrieben steht, und nur einen davon zu sortieren, zerstört sie stillschweigend. Die Lektion Datensätze fasst den Namen und die Note jeder Person in einem einzigen Wert zusammen, sodass sie sich beim Sortieren gemeinsam bewegen.Wiederholen: Datensätze
Inhalt wird geladen…
Abgeschlossen
Melde dich an, um deinen Fortschritt zu speichern