Copyright© 2007 by Doina Logofătu
1 KOMPLEXE KODIERUNG 1
Programm code.in
2 VERSCHACHTELTE SCHACHTELN 15
Programm boxes.in
3 ZEICHENKETTEN 25
Problem 1. Sich wiederholende Zeichenketten 33
Programm woerter.in
Problem 2. Das Perlencollier 35
Programm collier.in
Problem 3. Parkinson 37
Programm parkinson.in
Problem 4. Rapunzel im Internet 40
Programm gitter.in
gitter.in
gitter.in
Problem 5. Bridge-Blatt 44
Programm bridge.in
Problem 6. Wo sind die Königinnen? 49
Programm queens.in
Problem 7. Vogelsprache 55
Programm vogel.in
vogel.in
4 MENGEN UND RELATIONEN 59
Problem 1. Cantor-Diagonalisierung 67
Programm cantor.in
Problem 2. Menge und Multimenge 72
Programm text.in
Problem 3. Relation und ihre Eigenschaften 75
Programm relation.in
relation.in
5 ARITHMETIK UND ALGEBRA 81
Problem 1. Primzahltest 93
Programm
Problem 2. Sieb des Eratosthenes 95
Programm C zahlen.in
Programm C++
Problem 3. Druck einer Broschüre 99
Programm broschuere.in
Problem 4. Primzahlen und Teiler 101
Programm n.in
Progr. Anzahl Ziffern
Problem 5. Der alte Gärtner 104
Programm gaertner.in
Progr. Anzahl Ziffern
Problem 6. Kätzchen in Hüten 108
Programm katzen.in
Problem 7. Hausnummer 113
Programm
Problem 8. Korrekte Nachrichten 115
Programm crc.in
Problem 9. Anzahl der Teiler 118
Programm teiler.in
Problem 10. Datumsverpackung 121
Programm datum.in
Problem 11. Die schöne Marie und der schöne Hans 122
Programm marie.in
Problem 12. Kubische Gleichung 125
Programm
Problem 13. Quadrat einer speziellen Zahl 126
Programm n2333.in
Problem 14. Umwandlung einer römischen Zahl in eine Dezimalzahl 128
Programm roman.in
Problem 15. Umwandlung einer Dezimalzahl in eine römische Zahl 130
Programm decRom.in
Problem 16. Hässliche Zahlen 132
Programm haesslich.in
haesslich.in
Problem 17. Vögel auf den Bäumen 134
Programm voegel.in
Problem 18. Wieviele sind es mindestens? (chinesischer Restsatz) 136
Programm baerchen.in
6 EBENE GEOMETRIE, TRIGONOMETRIE 139
Problem 1. Berechnung des Dreiecks (SSW) 142
Programm trigs.in
Problem 2. Der Kreisumfang 146
Programm circle.in
Problem 3. Kreise im gleichschenkligen Dreieck 150
Programm triangle.in
7 KOMBINATORIK 153
Problem 1. Alle Teilmengen einer Menge
in lexikographischer Reihenfolge 166
Programm
Problem 2. Der Gray-Code (minimale Änderungsreihenfolge) 170
Programm
Problem 3. Permutationen in lexikographischer Reihenfolge 173
Programm genperm.in
Problem 4. Ranking einer Permutation in lexikographischer Reihenfolge 175
Programm perm.in
perm.in
Problem 5. Unranking einer Permutation in lexikographischer Reihenfolge178
Programm rank.in
rank.in
Problem 6. Binomialkoeffizienten 180
Programm comb.in
Problem 7. Das kleinste Vielfache 186
Programm zahl.in
8 CATALAN-ZAHLEN 189
Algorithmen zur Berechnung der Catalan-Zahlen 200
Programm
Zweiter Algorithmus, eine weitere Rekursion 201
Programm
Dritter Algorithmus, der ohne Rekursion auskommt 202
Programm catalan.in
9 POTENZSUMMEN 207
Programm psum.in
10 ALGORITHMISCHE GEOMETRIE 219
Problem 1. Nächstes Paar 234
Programm punkte.in
Problem 2. Quadrätchen im Kreis 236
Programm quadrate.in
Problem 3. Wie sicher sind die Bürger? 241
Programm buerger.in
buerger.in
buerger.in
11 GRAPHEN 251
Problem 1. Breiten- und Tiefensuche (BFS und DFS) 264
Programm C graph.in
Problem 2. Die kürzesten Pfade 267
Programm graph.in
Problem 3. Das Alphabet der fremden Sprache 269
Programm index.in
index.in
Problem 4. Markus besucht seine Freunde 275
Programm tour.in
Problem 5. Das Haus des Nikolaus 280
Programm
12 GREEDY 283
Problem 1. Rucksackproblem 284
Programm C objects.in
Problem 2. Kartenfärbung 286
Programm map.in
Problem 3. Springer auf dem Schachbrett 287
Programm springer.in
13 REKURSION 291
Problem 1. Quersumme und Spiegelung einer natürlichen Zahl 298
Programm
Problem 2. Die Zahl 4 300
Programm nr4.in
Problem 3. Rest großer Potenzen 302
Programm bigmod.in
Problem 4. Die Torte (lineare Rekursion) 304
Programm 4.1. tart.in
Programm 4.2.
Problem 5. Die Ackermannfunktion
(verschachtelte Rekursion, "compound recursion") 306
Programm ack.in
Problem 6. Rekursive Zahlenumwandlung
(Dezimalsystem in System mit Basis P) 308
Programm baseP.in
Problem 7. Summe zweier Wurzeln (verzweigte Rekursion) 310
Programm equation.in
Problem 8. Collatz-Funktion (nicht-monotone Rekursion) 311
Programm numbers.in
Problem 9. Quadrate und Quadrätchen 313
Programm quadrate.in
Problem 10. Quadrate (direkte Rekursion) 316
stdafx.h
MainWindow.h
MainWindowImpl.cpp
main.cpp
Problem 11. Quadrate und Kreise (indirekte Rekursion) 325
stdafx.h
MainWindow.h
MainWindowImpl.cpp
main.cpp
Problem 12. Die Koch’sche Schneeflockenkurve 329
stdafx.h iteration.in
MainWindow.h
MainWindowImpl.cpp
main.cpp
14 TEILE UND HERRSCHE 337
Problem 1. Größter gemeinsamer Teiler mehrerer Zahlen 338
Programm numbers.in
Problem 2. Die Türme von Hanoi 340
Programm
Problem 3. Integral mit Trapezregel 342
Programm integral.in
Problem 4. Quicksort 344
Programm QSort.in
Problem 5. Mergesort (Sortieren durch Verschmelzen) 346
Programm MSort.in
Problem 6. Quad-Bäume 348
Programm quad.in
Problem 7. Diskrete Fourier-Transformation (DFT) 352
Programm fourier.in
15 BACKTRACKING 357
Problem 1. Das Problem der n Damen 357
Programm
Problem 2. Das Problem der n Türme 365
Programm
Problem 3. Das Problem der Türme auf den ersten m Reihen 367
Programm
Problem 4. Das Problem der aufsteigenden Türme
auf den ersten m Reihen 368
Programm 1. Variante
Programm 2. Variante
Problem 5. Die Freundschafts-Jugendherberge 369
Programm
Problem 6. Partitionen einer natürlichen Zahl 370
Programm n.in
Problem 7. Erdkunde-Referate 373
Programm
Problem 8. Alle Wege des Springers 375
Programm
Problem 9. Das Fotoproblem 378
Programm foto.in
Problem 10. Der ausbrechende Ball 379
Programm ball.in
Problem 11. Olivensport 382
Programm oliven.in
Problem 12. Testmusterkompaktierung 388
Programm tests.in
16 DYNAMISCHE PROGRAMIERUNG 403
Problem 1. Das Zählen der Kaninchen 408
Programm
Problem 2. Längste aufsteigende Teilfolge 411
Programm ascending.in
Problem 3. Zahlen-Dreieck 415
Programm dreieck.in
Problem 4. Domino 418
Programm domino.in
Problem 5. Verteilung der Geschenke 422
Programm geschenke.in
geschenke.in
Problem 6. Ähnliche Summe 425
Programm numbers.in
numbers.in
numbers.in
Problem 7. Schotten auf dem Oktoberfest 430
Programm 1
Programm 2
Programm 3 oktoberfest.in
Programm 4
Problem 8. Springer auf dem Schachbrett 437
Programm springer.in
Problem 9. Summen von Produkten 442
Programm prodsum.in
prodsum.in
Problem 10. Minimale Triangulierung eines konvexen Vielecks 445
Programm triang.in
Problem 11. Multiplikation einer Matrizenfolge 451
Programm matrix.in
Problem 12. Edit-Distanz 456
Programm edit.in