Think Like a Programmer

Typische Programmieraufgaben kreativ lösen am Beispiel von C++

• Von der Aufgabe zur Lösung - so gehen Sie vor
• Probleme analysieren und schrittweise bearbeiten
• Systematisches Vorgehen lernen und anwenden

Aus dem Inhalt:

• Strategien zur Problemlösung
• Eingabeverarbeitung
• Statusverfolgung
• Arrays
• Zeiger und dynamische Speicherverwaltung
• Klassen
• Rekursion
• Wiederverwendung von Code
• Rekursive und iterative Programmierung
• Denken wie ein Programmierer

Die Herausforderung beim Programmieren besteht nicht im Erlernen der Syntax einer bestimmten Sprache, sondern in der Fähigkeit, auf kreative Art Probleme zu lösen. In diesem einzigartigen Buch widmet sich der Autor V. Anton Spraul genau jenen Fähigkeiten, die in normalen Lehrbüchern eher nicht behandelt werden: die Fähigkeit, wie ein Programmierer zu denken und Aufgaben zu lösen. In den einzelnen Kapiteln behandelt er jeweils verschiedene Programmierkonzepte wie beispielsweise Klassen, Zeiger und Rekursion, und fordert den Leser mit erweiterbaren Übungen zur praktischen Anwendung des Gelernten auf. Sie lernen unter anderem:

• Probleme in diskrete Einzelteile zerlegen, die sich leichter lösen lassen
• Funktionen, Klassen und Bibliotheken möglichst effizient nutzen und wiederholt verwenden
• die perfekte Datenstruktur für eine Aufgabenstellung auswählen
• anspruchsvollere Programmiertechniken wie Rekursion und dynamischen Speicher einsetzen
• Ihre Gendanken ordnen und Strategien entwickeln, um bestimmte Problemkategorien in Angriff zu nehmen

Die Beispiele im Buch werden mit C++ gelöst, die dargestellten kreativen Problemlösungskonzepte gehen aber weit über die einzelnen Programmiersprachen und oft sogar über den Bereich der Informatik hinaus. Denn wie die fähigsten Programmierer wissen, handelt es sich beim Schreiben herausragender Quelltexte um kreative Kunst und der erste Schritt auf dem Weg zum eigenen Meisterwerk besteht darin, wie ein Programmierer zu denken. Über den Autor: V. Anton Spraul hat über 15 Jahre lang Vorlesungen über die Grundlagen der Programmierung und Informatik gehalten. In diesem Buch fasst er die von ihm dabei perfektionierten Verfahren zusammen. Er ist auch Autor von »Computer Science Made Simple«. V. Anton Spraul gibt seit mehr als 15 Jahren Kurse zur Einführung in die Programmierung und Computerwissenschaften. In diesem Buch vereint er die Techniken, mit denen er in zahlreichen Einzelstunden Programmierschülern geholfen hat.

1;Cover;1 2;Titel;3 3;Impressum;4 4;Inhaltsverzeichnis;5 5;Danksagungen;11 6;Einführung;13 6.1;Über dieses Buch;15 6.1.1;Voraussetzungen;16 6.1.2;Ausgewählte Themen;16 6.1.3;Programmierstil;16 6.1.4;Übungen;17 6.1.5;Warum C++?;17 7;Strategien zur Problemlösung;19 7.1;1.1 Klassische Rätsel;20 7.1.1;1.1.1 Fuchs, Gans und Getreidesack;21 7.1.1.1;Aufgabe: Wie kann der Fluss überquert werden?;21 7.1.2;1.1.2 Schiebepuzzles;25 7.1.2.1;Aufgabe: Verschieben der 8;26 7.1.2.2;Aufgabe: Verschieben der 5;27 7.1.3;1.1.3 Sudoku;30 7.1.3.1;Aufgabe: Vervollständigen eines Sudoku-Quadrats;31 7.1.4;1.1.4 Das Quarrasi-Schloss;33 7.1.4.1;Aufgabe: Öffnen des außerirdischen Schlosses;33 7.2;1.2 Gängige Verfahren zur Problemlösung;36 7.2.1;1.2.1 Niemals ohne Plan;37 7.2.2;1.2.2 Umformulieren der Aufgabenstellung;38 7.2.3;1.2.3 Zerlegung in Teilaufgaben;39 7.2.4;1.2.4 Mit Bekanntem anfangen;40 7.2.5;1.2.5 Reduktion der Problemstellung;41 7.2.6;1.2.6 Analogien suchen;42 7.2.7;1.2.7 Experimentieren;43 7.2.8;1.2.8 Nicht entmutigen lassen;44 7.3;1.3 Übungen;45 8;Wahre Rätsel;47 8.1;2.1 Verwendete C++-Syntax;47 8.2;2.2 Ausgabe von Mustern;48 8.2.1;Aufgabe: Halbiertes Quadrat;48 8.2.2;Aufgabe: Quadrat (Halbiertes Quadrat, Reduktion);48 8.2.3;Aufgabe: Zeile (Halbiertes Quadrat, weitere Reduktion);49 8.2.4;Aufgabe: Herunterzählen durch Hochzählen;50 8.2.5;Aufgabe: Hochkant stehendes Dreieck;51 8.3;2.3 Eingabeverarbeitung;54 8.3.1;Aufgabe: Test einer Luhn-Prüfsumme;54 8.3.2;2.3.1 Zerlegung der Aufgabenstellung;56 8.3.2.1;Aufgabe: Ziffer in Ganzzahl konvertieren;58 8.3.2.2;Aufgabe: Test einer Luhn-Prüfsumme fester Länge;60 8.3.2.3;Aufgabe: Test einer einfachen Prüfsumme fester Länge;60 8.3.2.4;Aufgabe: Positiv oder negativ;63 8.3.3;2.3.2 Zusammenstellen der Teillösungen;64 8.4;2.4 Statusverfolgung;66 8.4.1;Aufgabe: Entschlüsseln einer Botschaft;66 8.4.2;Aufgabe: Einlesen einer Zahl mit drei oder vier Ziffern;71 8.4.3;Aufgabe: Einlesen einer Zahl mit drei oder vier Ziffern, weiter vereinfacht;72 8.5;2
.5 Fazit;81 8.6;2.6 Übungen;81 9;Arrays;85 9.1;3.1 Array-Grundlagen;86 9.1.1;3.1.1 Speichern;86 9.1.2;3.1.2 Kopieren;87 9.1.3;3.1.3 Zugriff und Suche;88 9.1.4;3.1.4 Sortieren;89 9.1.5;3.1.5 Statistische Werte;92 9.2;3.2 Aufgabenstellungen mit Arrays;93 9.2.1;Aufgabe: Modalwert berechnen;93 9.2.2;3.2.1 Refactoring;97 9.3;3.3 Arrays mit fest vorgegebenen Daten;100 9.4;3.4 Nicht-skalare Arrays;102 9.5;3.5 Mehrdimensionale Arrays;104 9.6;3.6 Wann werden Arrays verwendet?;108 9.7;3.7 Übungen;113 10;Zeiger und dynamische Speicherverwaltung;115 10.1;4.1 Zeiger-Grundlagen;115 10.2;4.2 Vorteile von Zeigern;117 10.2.1;4.2.1 Festlegung der Größe von Datenstrukturen zur Laufzeit;117 10.2.2;4.2.2 Größenänderung von Datenstrukturen;117 10.2.3;4.2.3 Gemeinsame Speichernutzung;118 10.3;4.3 Wann werden Zeiger verwendet?;119 10.4;4.4 Speicherverwaltung;120 10.4.1;4.4.1 Stack und Heap;120 10.4.2;4.4.2 Arbeitsspeicher;124 10.4.3;4.4.3 Lebensdauer;125 10.5;4.5 Aufgabenstellungen mit Zeigern;126 10.5.1;4.5.1 Zeichenketten variabler Länge;127 10.5.1.1;Aufgabe: Bearbeitung von Zeichenketten variabler Länge;127 10.5.2;4.5.2 Verkettete Listen;139 10.5.2.1;Aufgabe: Nachverfolgen einer unbekannten Zahl von Schülerdatensätzen;139 10.6;4.6 Fazit und Ausblick;148 10.7;4.7 Übungen;149 11;Klassen;151 11.1;5.1 Klassen-Grundlagen;151 11.2;5.2 Ziele bei der Verwendung von Klassen;153 11.2.1;5.2.1 Verkapselung;154 11.2.2;5.2.2 Wiederverwendung von Code;155 11.2.3;5.2.3 Zerlegung in Teilaufgaben;155 11.2.4;5.2.4 Information Hiding;156 11.2.5;5.2.5 Verständlichkeit;158 11.2.6;5.2.6 Ausdrucksfähigkeit;159 11.3;5.3 Eine einfache Klasse;159 11.3.1;Aufgabe: Notenliste;160 11.3.2;5.3.1 Grundgerüst einer Klasse;160 11.3.3;5.3.2 Unterstützende Methoden;165 11.4;5.4 Klassen mit dynamischen Daten;169 11.4.1;Aufgabe: Nachverfolgen einer unbekannten Zahl von Schülerdatensätzen;169 11.4.2;5.4.1 Hinzufügen eines Knotens;172 11.4.3;5.4.2 Umorganisieren einer Liste;175 11.4.4;5.4.3 Destruktor;179 11.4.5;5.4.4 Tiefe Kop
ien (Deep Copy);180 11.4.6;5.4.5 Klassen mit dynamischen Daten im Überblick;185 11.5;5.5 Fehlervermeidung;186 11.5.1;5.5.1 Fingierte Klassen;187 11.5.2;5.5.2 Monotalente;188 11.6;5.6 Übungen;188 12;Rekursion;191 12.1;6.1 Grundlagen der Rekursion;191 12.2;6.2 Start- und Endrekursion;192 12.2.1;Aufgabe: Wie viele Papageien?;192 12.2.2;6.2.1 Lösungsweg 1;193 12.2.3;6.2.2 Lösungsweg 2;194 12.2.3.1;Aufgabe: Wer ist unser bester Kunde?;196 12.2.4;6.2.3 Lösungsweg 1;198 12.2.5;6.2.4 Lösungsweg 2;199 12.3;6.3 Das Hauptkonzept der Rekursion;201 12.3.1;Aufgabe: Berechnung der Summe eines Arrays von Ganzzahlen;202 12.4;6.4 Häufige Fehler;204 12.4.1;6.4.1 Zu viele Parameter;205 12.4.2;6.4.2 Globale Variablen;206 12.5;6.5 Rekursion bei dynamischen Datenstrukturen;208 12.5.1;6.5.1 Rekursion und verkettete Listen;208 12.5.1.1;Aufgabe: Negative Zahlen in einer einfach verketteten Liste zählen;210 12.5.2;6.5.2 Rekursion und Binärbäume;211 12.5.2.1;Aufgabe: Suche nach dem größten Wert in einem Binärbaum;213 12.6;6.6 Wrapper-Funktionen;214 12.6.1;Aufgabe: Anzahl der Blätter eines Binärbaums;214 12.7;6.7 Wann wird Rekursion verwendet?;217 12.7.1;6.7.1 Rekursion: Gegenargumente;218 12.7.1.1;Aufgabe: Ausgabe einer verketteten Liste;220 12.7.1.2;Aufgabe: Ausgabe einer verketteten Liste in umgekehrter Reihenfolge;220 12.8;6.8 Übungen;222 13;Wiederverwendung von Code;225 13.1;7.1 Sinnvolle und nicht sinnvolle Wiederverwendung von Code;225 13.2;7.2 Komponenten;227 13.2.1;7.2.1 Code-Blöcke;227 13.2.2;7.2.2 Algorithmen;227 13.2.3;7.2.3 Entwurfsmuster;228 13.2.4;7.2.4 Abstrakte Datentypen;229 13.2.5;7.2.5 Bibliotheken;230 13.3;7.3 Kenntnisse über Komponenten erweitern;230 13.3.1;7.3.1 Forschendes Lernen;231 13.3.1.1;Aufgabe: Klassenvorsteher;232 13.3.2;7.3.2 Lernen bei Bedarf;235 13.3.2.1;Aufgabe: Effizientes Durchlaufen einer Liste;236 13.4;7.4 Auswahl eines Komponententyps;244 13.4.1;7.4.1 Komponentenwahl in der Praxis;246 13.4.1.1;Aufgabe: Teilweise Sortierung;246 13.4.2;7.4.2 Vergleich der
Ergebnisse;251 13.5;7.5 Übungen;251 14;Denken wie ein Programmierer;253 14.1;8.1 Das Gesamtkonzept;253 14.1.1;8.1.1 Stärken ausschöpfen, Schwächen lindern;254 14.1.2;8.1.2 Aufbau des Gesamtkonzepts;261 14.2;8.2 Beliebige Aufgabenstellungen in Angriff nehmen;262 14.2.1;Aufgabe: Schummeln beim Galgenmännchen;264 14.2.2;8.2.1 Wie man schummelt;265 14.2.3;8.2.2 Erforderliche Operationen zum Schummeln beim Galgenmännchen;267 14.2.4;8.2.3 Der erste Entwurf;269 14.2.5;8.2.4 Der erste Code;270 14.2.6;8.2.5 Analyse der ersten Ergebnisse;281 14.2.7;8.2.6 Die Kunst des Problemlösens;282 14.3;8.3 Programmierkenntnisse weiterentwickeln;283 14.3.1;8.3.1 Neue Programmiersprachen;284 14.3.2;8.3.2 Kenntnisse in bekannten Programmiersprachen erweitern;287 14.3.3;8.3.3 Zusätzliche Bibliotheken;288 14.3.4;8.3.4 Besuchen Sie einen Kurs;289 14.4;8.4 Fazit;289 14.5;8.5 Übungen;291 15;Stichwortverzeichnis;293