HOME


Algorithmen und Problemlösungen mit C++, Doina Logofatu


 





Copyright© 2007 by Doina Logofătu
Die Programme



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