Sto~t man auf eine besonders elegante Formulierung eines Algorithmus, so fragt man sich meist, wie der Autor auf die entsprechende Programmieridee gekommen ist. Mustert man eine Vielzahl von Algorithmen genauer, so erkennt man, d~ es etwa ein Dutzend grund legender Programmiertechniken gibt. Im vorliegenden Band sollen daher einige solche Pro grammierprinzipien wie - Top-down-Prinzip - Rekursion - Iteration - Backtracking-Verfahren - Teile-und-Herrsche-Prinzip - Greedy-Algorithmen vorgestellt werden. Thre Realisierung wird an Hand von 25 vollstandigen BASIC-und Pascal-Programmen diskutiert. Diese Programme sind vielfaltigen Bereichen entnommen: Neben numerischen und unterhaltungs-mathematischen Problemen werden auch kombi natorische, Sortier-und Operations-Research-Fragen behandelt, z. B. - Permutationen - Springerzug - Labyrinth - Quicksort - Rucksackproblem - Travelling-Salesman. Viele Algorithmen sind durch Struktograrnme erkliirt und konnen damit gegebenenfalls in andere Programmiersprachen iibertragen werden. Anzing, Oktober 1983 Einfiihrung W? hrend in der FrUhzeit des Programmierens die Programmerstellun~ mehr oder weniger Sache des personlichen Geschmacks bzw. Geschicks war, hat sich mittlerweile das "Software-Engineering" entwickelt, das eine ganze Reihe von Anforderungen an Pro gramme erstellt. Ausgangspunkt war die Entwicklung des strukturierten Prograrnrnierens, die sich in dem Buch "Structured Prograrnrning" von Dijkstra, Hoare und Dahl (1972) niederschlug. Vorausgegangen war die beriihmte Kontroverse um Dijkstra 's "GOTO-considered harmful" (1968). ZieI des Strukturierens war, unter strikten Anwendung der Kontrollstrukturen - repetive Anweisung (FOR . . DO, REPEAT . . UNTIL, WHlLE . . DO) - alternative Anweisung (IF . . THEN . . ELSE, CASE . . OF) - Verbundanweisung (BEGIN . . ENO) und unter Vermeidung der Sprunganweisung (GOTO) den Programmablaufiiberschaubar und kontrollierbar zu machen.
Inhaltsverzeichnis
Einführung. - 1 Top-down-Methode. - 1. 1. Gauß-Elimination (Pascal). - 1. 2. Primzahlsieb (Pascal). - 2 Algebraische Umformungen. - 2. 1. Größter gemeinsamer Teiler (Pascal). - 2. 2. Elliptisches Integral 1. Art (BASIC). - 2. 3. Modulorest einer Potenz (BASIC). - 3 Rekursion. - 3. 1. Ackermann-Funktion (Pascal). - 3. 2. Permutationen (BASIC). - 3. 3. Partitionen (Pascal). - 4 Iteration. - 4. 1. Ackermann-Funktion (BASIC). - 4. 2. Binomialkoeffizienten (BASIC). - 4. 3. Gammafunktion (BASIC). - 5 Backtracking-Verfahren. - 5. 1. Springerzug (Pascal). - 5. 2. 0/1-Rucksackproblem (Pascal). - 5. 3. Labyrinth (Pascal). - 6 Teile-und-Herrsche-Prinzip. - 6. 1. Quicksort (Pascal). - 6. 2. Sortieren durch binäres Einfügen (Pascal). - 6. 3. Wägeproblem (Pascal). - 7 Heuristische Methoden. - 7. 1. Springerzug (BASIC). - 7. 2. Umfüllaufgabe (Pascal). - 8 Greedy-Methoden. - 8. 1. Rucksackproblem (BASIC). - 8. 2. Travelling-Salesman-Problem (BASIC). - 9 Riickwärtsrechnen. - 9. 1. Jeepproblem (Pascal). - 9. 2. Besselfunktion 1. Art (BASIC). - 10 Simulation. - 10. 1. Warten auf einen vollständigen Satz (BASIC). - 10. 2. Anzahlschätzung von Objekten (BASIC). - Sachwortverzeichnis.
