Erhalten Sie Zugang zu diesem und mehr als 300000 Büchern ab EUR 5,99 monatlich.
- Herausgeber: dpunkt.verlag
- Kategorie: Wissenschaft und neue Technologien
- Serie: Programmieren mit dpunkt
- Sprache: Deutsch
- Veröffentlichungsjahr: 2020
Ihr persönlicher Java-Coach !
- Ihr Java-Trainingsbuch mit Musterlösungen
- Lernen Sie Tipps und Kniffe vom Java-Experten kennen
- Erweitern Sie Ihr Java-Knowhow in praxisrelevanten Bereichen
Dieses Buch bietet Ihnen ein breit gefächertes Spektrum
von über 100 Übungsaufgaben und Programmierpuzzles
inklusive Lösungen zum Knobeln und Erweitern Ihrer
Kenntnisse zu unterschiedlichen praxisrelevanten
Themengebieten wie Arrays, Datenstrukturen, Rekursion,
Date and Time API usw.
Jedes Themengebiet wird in einem eigenen Kapitel behandelt, das zunächst mit einer Einführung in die Grundlagen beginnt. Danach finden sich zumeist
10 bis 15 Übungsaufgaben verschiedener Schwierigkeitsgrade, sodass von Anfänger bis Fortgeschrittenen immer etwas dabei ist und sich die Programmierkenntnisse effektiv verbessern lassen. Dabei helfen am Kapitelabschluss insbesondere
detaillierte Musterlösungen inklusive der genutzten
Algorithmen zu allen Aufgaben. Vielfach werden zudem alternative Lösungswege aufgezeigt, aber auch mögliche Fallstricke und typische Fehler thematisiert.
Abgerundet wird das Buch durch zwei Anhänge.
Einer gibt einen Überblick in wesentliche Neuerungen von Java 8. Der zweite beschäftigt sich mit der JShell, die zum Ausprobieren der Codeschnipsel
und Beispiele des Buchs oftmals hilfreich ist.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 698
Das E-Book (TTS) können Sie hören im Abo „Legimi Premium” in Legimi-Apps auf:
Ähnliche
Dipl.-Inform. Michael Inden ist Oracle-zertifizierter Java-Entwickler. Nach seinem Studium in Oldenburg hat er bei diversen internationalen Firmen in verschiedenen Rollen etwa als Softwareentwickler, -architekt, Consultant, Teamleiter sowie Trainer gearbeitet. Zurzeit ist er als CTO und Leiter Academy in Zürich tätig.
Michael Inden hat über zwanzig Jahre Berufserfahrung beim Entwurf komplexer Softwaresysteme gesammelt, an diversen Fortbildungen und mehreren Java-One-Konferenzen teilgenommen. Sein besonderes Interesse gilt dem Design qualitativ hochwertiger Applikationen mit ergonomischen GUIs sowie dem Coaching. Sein Wissen gibt er gerne als Trainer in internen und externen Schulungen und auf Konferenzen weiter, etwa bei der Java User Group Switzerland, bei der JAX/W-JAX, ch.open und den IT-Tagen.
Zu diesem Buch – sowie zu vielen weiteren dpunkt.büchern – können Sie auch das entsprechende E-Book im PDF-Format herunterladen. Werden Sie dazu einfach Mitglied bei dpunkt.plus+:
www.dpunkt.plus
Michael Inden
Java Challenge
Fit für das Job-Interview und die Praxis –mit mehr als 100 Aufgaben und Musterlösungen
Michael Inden
Lektorat: Michael Barabas
Copy-Editing: Ursula Zimpfer, Herrenberg
Satz: Michael Inden
Herstellung: Stefanie Weidner
Umschlaggestaltung: Helmut Kraus, www.exclam.de
Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
ISBN:
Print 978-3-86490-756-2
PDF 978-3-96910-028-8
ePub 978-3-96910-029-5
mobi 978-3-96910-030-1
1. Auflage 2020
Copyright © 2020 dpunkt.verlag GmbH
Wieblinger Weg 17
69123 Heidelberg
Hinweis:
Dieses Buch wurde auf PEFC-zertifiziertem Papier aus nachhaltiger Waldwirtschaft gedruckt. Der Umwelt zuliebe verzichten wir zusätzlich auf die Einschweißfolie.
Schreiben Sie uns:
Falls Sie Anregungen, Wünsche und Kommentare haben, lassen Sie es uns wissen: [email protected].
Die vorliegende Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten. Die Verwendung der Texte und Abbildungen, auch auszugsweise, ist ohne die schriftliche Zustimmung des Verlags urheberrechtswidrig und daher strafbar. Dies gilt insbesondere für die Vervielfältigung, Übersetzung oder die Verwendung in elektronischen Systemen.
Es wird darauf hingewiesen, dass die im Buch verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken- oder patentrechtlichem Schutz unterliegen.
Alle Angaben und Programme in diesem Buch wurden mit größter Sorgfalt kontrolliert. Weder Autor noch Verlag können jedoch für Schäden haftbar gemacht werden, die in Zusammenhang mit der Verwendung dieses Buches stehen.
5 4 3 2 1 0
Inhaltsverzeichnis
1Einleitung
1.1Aufbau der Kapitel
1.2Grundgerüst des Eclipse-Projekts
1.3Grundgerüst für die Unit Tests
1.4Anmerkung zum Programmierstil
1.5Ausprobieren der Beispiele und Lösungen
IGrundlagen
2Mathematische Aufgaben
2.1Einführung
2.1.1Römische Zahlen
2.1.2Zahlenspielereien
2.2Aufgaben
2.2.1Aufgabe 1: Grundrechenarten ()
2.2.2Aufgabe 2: Zahl als Text ()
2.2.3Aufgabe 3: Vollkommene Zahlen ()
2.2.4Aufgabe 4: Primzahlen ()
2.2.5Aufgabe 5: Primzahlpaare ()
2.2.6Aufgabe 6: Prüfsumme ()
2.2.7Aufgabe 7: Römische Zahlen ()
2.2.8Aufgabe 8: Kombinatorik ()
2.2.9Aufgabe 9: Armstrong-Zahlen ()
2.2.10Aufgabe 10: Max Change Calculator ()
2.2.11Aufgabe 11: Befreundete Zahlen ()
2.2.12Aufgabe 12: Primfaktorzerlegung ()
2.3Lösungen
2.3.1Lösung 1: Grundrechenarten ()
2.3.2Lösung 2: Zahl als Text ()
2.3.3Lösung 3: Vollkommene Zahlen ()
2.3.4Lösung 4: Primzahlen ()
2.3.5Lösung 5: Primzahlpaare ()
2.3.6Lösung 6: Prüfsumme ()
2.3.7Lösung 7: Römische Zahlen ()
2.3.8Lösung 8: Kombinatorik ()
2.3.9Lösung 9: Armstrong-Zahlen ()
2.3.10Lösung 10: Max Change Calculator ()
2.3.11Lösung 11: Befreundete Zahlen ()
2.3.12Lösung 12: Primfaktorzerlegung ()
3Rekursion
3.1Einführung
3.1.1Mathematische Beispiele
3.1.2Algorithmische Beispiele
3.1.3Ablauf beim Multiplizieren der Ziffern einer Zahl
3.1.4Typische Probleme
3.2Aufgaben
3.2.1Aufgabe 1: Fibonacci ()
3.2.2Aufgabe 2: Ziffern verarbeiten ()
3.2.3Aufgabe 3: ggT / GCD ()
3.2.4Aufgabe 4: Reverse String ()
3.2.5Aufgabe 5: Array Sum ()
3.2.6Aufgabe 6: Array Min ()
3.2.7Aufgabe 7: Konvertierungen ()
3.2.8Aufgabe 8: Exponentialfunktion ()
3.2.9Aufgabe 9: Pascal’sches Dreieck ()
3.2.10Aufgabe 10: Zahlenpalindrome ()
3.2.11Aufgabe 11: Permutationen ()
3.2.12Aufgabe 12: Count Substrings ()
3.2.13Aufgabe 13: Lineal ()
3.3Lösungen
3.3.1Lösung 1: Fibonacci ()
3.3.2Lösung 2: Ziffern verarbeiten ()
3.3.3Lösung 3: ggT / GCD ()
3.3.4Lösung 4: Reverse String ()
3.3.5Lösung 5: Array Sum ()
3.3.6Lösung 6: Array Min ()
3.3.7Lösung 7: Konvertierungen ()
3.3.8Lösung 8: Exponentialfunktion ()
3.3.9Lösung 9: Pascal’sches Dreieck ()
3.3.10Lösung 10: Zahlenpalindrome ()
3.3.11Lösung 11: Permutationen ()
3.3.12Lösung 12: Count Substrings ()
3.3.13Lösung 13: Lineal ()
4Strings
4.1Einführung
4.1.1Die Klasse String
4.1.2Die Klassen StringBuffer und StringBuilder
4.1.3Die Klasse Character
4.1.4Beispiele zu Character und String
4.2Aufgaben
4.2.1Aufgabe 1: Zahlenumwandlungen ()
4.2.2Aufgabe 2: Joiner ()
4.2.3Aufgabe 3: Reverse String ()
4.2.4Aufgabe 4: Palindrom ()
4.2.5Aufgabe 5: No Duplicate Chars ()
4.2.6Aufgabe 6: Doppelte Buchstaben entfernen ()
4.2.7Aufgabe 7: Capitalize ()
4.2.8Aufgabe 8: Rotation ()
4.2.9Aufgabe 9: Wohlgeformte Klammern ()
4.2.10Aufgabe 10: Anagramm ()
4.2.11Aufgabe 11: Morse Code ()
4.2.12Aufgabe 12: Pattern Checker ()
4.2.13Aufgabe 13: Tennis-Punktestand ()
4.2.14Aufgabe 14: Versionsnummern ()
4.2.15Aufgabe 15: Konvertierung strToLong ()
4.2.16Aufgabe 16: Print Tower ()
4.3Lösungen
4.3.1Lösung 1: Zahlenumwandlungen ()
4.3.2Lösung 2: Joiner ()
4.3.3Lösung 3: Reverse String ()
4.3.4Lösung 4: Palindrom ()
4.3.5Lösung 5: No Duplicate Chars ()
4.3.6Lösung 6: Doppelte Buchstaben entfernen ()
4.3.7Lösung 7: Capitalize ()
4.3.8Lösung 8: Rotation ()
4.3.9Lösung 9: Wohlgeformte Klammern ()
4.3.10Lösung 10: Anagramm ()
4.3.11Lösung 11: Morse Code ()
4.3.12Lösung 12: Pattern Checker ()
4.3.13Lösung 13: Tennis-Punktestand ()
4.3.14Lösung 14: Versionsnummern ()
4.3.15Lösung 15: Konvertierung strToLong ()
4.3.16Lösung 16: Print Tower ()
5Arrays
5.1Einführung
5.1.1Eindimensionale Arrays
5.1.2Mehrdimensionale Arrays
5.1.3Typische Fehler
5.2Aufgaben
5.2.1Aufgabe 1: Gerade vor ungeraden Zahlen ()
5.2.2Aufgabe 2: Flip ()
5.2.3Aufgabe 3: Palindrom ()
5.2.4Aufgabe 4: Inplace Rotate ()
5.2.5Aufgabe 5: Jewels Board Init ()
5.2.6Aufgabe 6: Jewels Board Erase Diamonds ()
5.2.7Aufgabe 7: Spiral-Traversal ()
5.2.8Aufgabe 8: Add One to Array As Number ()
5.2.9Aufgabe 9: Sudoku-Checker ()
5.2.10Aufgabe 10: Flood-Fill ()
5.2.11Aufgabe 11: Array Merge ()
5.2.12Aufgabe 12: Array Min und Max ()
5.2.13Aufgabe 13: Array Split ()
5.2.14Aufgabe 14: Minesweeper Board ()
5.3Lösungen
5.3.1Lösung 1: Gerade vor ungerade Zahlen ()
5.3.2Lösung 2: Flip ()
5.3.3Lösung 3: Palindrom ()
5.3.4Lösung 4: Inplace Rotate ()
5.3.5Lösung 5: Jewels Board Init ()
5.3.6Lösung 6: Jewels Board Erase Diamonds ()
5.3.7Lösung 7: Spiral-Traversal ()
5.3.8Lösung 8: Add One to Array As Number ()
5.3.9Lösung 9: Sudoku-Checker ()
5.3.10Lösung 10: Flood-Fill ()
5.3.11Lösung 11: Array Merge ()
5.3.12Lösung 12: Array Min und Max ()
5.3.13Lösung 13: Array Split ()
5.3.14Lösung 14: Minesweeper Board ()
6Datumsverarbeitung
6.1Einführung
6.1.1Die Aufzählungen DayOfWeek und Month
6.1.2Die Klassen LocalDate, LocalTime und LocalDateTime
6.1.3Die Klasse ZonedDateTime
6.1.4Die Klasse ZoneId
6.1.5Die Klasse Duration
6.1.6Die Klasse Period
6.1.7Datumsarithmetik
6.1.8Formatierung und Parsing
6.2Aufgaben
6.2.1Aufgabe 1: Schaltjahre ()
6.2.2Aufgabe 2: Basiswissen Date-API ()
6.2.3Aufgabe 3: Monatslänge ()
6.2.4Aufgabe 4: Zeitzonen ()
6.2.5Aufgabe 5: Zeitzonenberechnung ()
6.2.6Aufgabe 6: Berechnungen mit LocalDate ()
6.2.7Aufgabe 7: Kalenderausgabe ()
6.2.8Aufgabe 8: Wochentage ()
6.2.9Aufgabe 9: Sonntage und Schaltjahre ()
6.2.10Aufgabe 10: TemporalAdjuster ()
6.2.11Aufgabe 11: NthWeekdayAdjuster ()
6.2.12Aufgabe 12: Payday-TemporalAdjuster ()
6.2.13Aufgabe 13: Formatting and Parsing ()
6.2.14Aufgabe 14: Fault Tolerant Parsing ()
6.3Lösungen
6.3.1Lösung 1: Schaltjahre ()
6.3.2Lösung 2: Basiswissen Date-API ()
6.3.3Lösung 3: Monatslänge ()
6.3.4Lösung 4: Zeitzonenberechnung ()
6.3.5Lösung 5: Zeitzonen ()
6.3.6Lösung 6: Berechnungen mit LocalDate ()
6.3.7Lösung 7: Kalenderausgabe ()
6.3.8Lösung 8: Wochentage ()
6.3.9Lösung 9: Sonntage und Schaltjahre ()
6.3.10Lösung 10: TemporalAdjuster ()
6.3.11Lösung 11: NthWeekdayAdjuster ()
6.3.12Lösung 12: Payday-TemporalAdjuster ()
6.3.13Lösung 13: Formatting and Parsing ()
6.3.14Lösung 14: Fault Tolerant Parsing ()
7Basisdatenstrukturen: Listen, Sets und Maps
7.1Einführung
7.1.1Das Interface Collection
7.1.2Listen und das Interface List<E>
7.1.3Mengen und das Interface Set
7.1.4Schlüssel-Wert-Abbildungen und das Interface Map
7.1.5Der Stack als LIFO-Datenstruktur
7.1.6Die Queue als FIFO-Datenstruktur
7.2Aufgaben
7.2.1Aufgabe 1: Mengenoperationen ()
7.2.2Aufgabe 2: List Reverse ()
7.2.3Aufgabe 3: Duplikate entfernen ()
7.2.4Aufgabe 4: Maximaler Gewinn ()
7.2.5Aufgabe 5: Längstes Teilstück ()
7.2.6Aufgabe 6: Eigener Stack ()
7.2.7Aufgabe 7: Wohlgeformte Klammern ()
7.2.8Aufgabe 8: Check Magic Triangle ()
7.2.9Aufgabe 9: Pascal’sches Dreieck ()
7.2.10Aufgabe 10: Häufigste Elemente ()
7.2.11Aufgabe 11: Addition von Ziffern ()
7.2.12Aufgabe 12: Compound Key ()
7.2.13Aufgabe 13: List Merge ()
7.2.14Aufgabe 14: Excel Magic Select ()
7.3Lösungen
7.3.1Lösung 1: Mengenoperationen ()
7.3.2Lösung 2: List Reverse ()
7.3.3Lösung 3: Duplikate entfernen ()
7.3.4Lösung 4: Maximaler Gewinn ()
7.3.5Lösung 5: Längstes Teilstück ()
7.3.6Lösung 6: Eigener Stack ()
7.3.7Lösung 7: Wohlgeformte Klammern ()
7.3.8Lösung 8: Check Magic Triangle ()
7.3.9Lösung 9: Pascal’sches Dreieck ()
7.3.10Lösung 10: Häufigste Elemente ()
7.3.11Lösung 11: Addition von Ziffern ()
7.3.12Lösung 12: Compound Key ()
7.3.13Lösung 13: List Merge ()
7.3.14Lösung 14: Excel Magic Select ()
IIFortgeschrittenere und kniffligere Themen
8Rekursion Advanced
8.1Memoization
8.1.1Memoization für Fibonacci-Zahlen
8.1.2Memoization für Pascal’sches Dreieck
8.2Backtracking
8.2.1n-Damen-Problem
8.3Aufgaben
8.3.1Aufgabe 1: Türme von Hanoi ()
8.3.2Aufgabe 2: Edit Distance ()
8.3.3Aufgabe 3: Longest Common Subsequence ()
8.3.4Aufgabe 4: Weg aus Labyrinth ()
8.3.5Aufgabe 5: Sudoku-Solver ()
8.3.6Aufgabe 6: Math Operator Checker ()
8.3.7Aufgabe 7: Wassereimer-Problem ()
8.3.8Aufgabe 8: Alle Palindrom-Teilstrings ()
8.3.9Aufgabe 9: n-Damen-Problem ()
8.4Lösungen
8.4.1Lösung 1: Türme von Hanoi ()
8.4.2Lösung 2: Edit Distance ()
8.4.3Lösung 3: Longest Common Subsequence ()
8.4.4Lösung 4: Weg aus Labyrinth ()
8.4.5Lösung 5: Sudoku-Solver ()
8.4.6Lösung 6: Math Operator Checker ()
8.4.7Lösung 7: Wassereimer-Problem ()
8.4.8Lösung 8: Alle Palindrom-Teilstrings ()
8.4.9Lösung 9: n-Damen-Problem ()
9Binärbäume
9.1Einführung
9.1.1Aufbau, Begrifflichkeiten und Anwendungsbeispiele
9.1.2Binärbäume
9.1.3Binärbäume mit Ordnung: binäre Suchbäume
9.1.4Traversierungen
9.1.5Balancierte Bäume und weitere Eigenschaften
9.1.6Bäume für die Beispiele und Übungsaufgaben
9.2Aufgaben
9.2.1Aufgabe 1: Tree Traversal ()
9.2.2Aufgabe 2: In-, Pre- und Postorder iterativ ()
9.2.3Aufgabe 3: Tree-Höhe berechnen ()
9.2.4Aufgabe 4: Kleinster gemeinsamer Vorfahre ()
9.2.5Aufgabe 5: Breadth-First ()
9.2.6Aufgabe 6: Level Sum ()
9.2.7Aufgabe 7: Tree Rotate ()
9.2.8Aufgabe 8: Rekonstruktion ()
9.2.9Aufgabe 9: Math Evaluation ()
9.2.10Aufgabe 10: Symmetrie ()
9.2.11Aufgabe 11: Check Binary Search Tree ()
9.2.12Aufgabe 12: Vollständigkeit ()
9.2.13Aufgabe 13: Tree Printer ()
9.3Lösungen
9.3.1Lösung 1: Tree Traversal ()
9.3.2Lösung 2: In-, Pre- und Postorder iterativ ()
9.3.3Lösung 3: Tree-Höhe berechnen ()
9.3.4Lösung 4: Kleinster gemeinsamer Vorfahre ()
9.3.5Lösung 5: Breadth-First ()
9.3.6Lösung 6: Level Sum ()
9.3.7Lösung 7: Tree Rotate ()
9.3.8Lösung 8: Rekonstruktion ()
9.3.9Lösung 9: Math Evaluation ()
9.3.10Lösung 10: Symmetrie ()
9.3.11Lösung 11: Check Binary Search Tree ()
9.3.12Lösung 12: Vollständigkeit ()
9.3.13Lösung 13: Tree Printer ()
10Suchen und Sortieren
10.1Einführung Suchen
10.1.1Suchen in Collections und Arrays
10.1.2Binärsuche mit binarySearch()
10.2Einführung Sortieren
10.2.1Insertion Sort
10.2.2Selection Sort
10.2.3Merge Sort
10.2.4Quick Sort
10.2.5Bucket Sort
10.2.6Schlussgedanken
10.3Aufgaben
10.3.1Aufgabe 1: Contains All ()
10.3.2Aufgabe 2: Partitionierung ()
10.3.3Aufgabe 3: Binärsuche ()
10.3.4Aufgabe 4: Insertion Sort ()
10.3.5Aufgabe 5: Selection Sort ()
10.3.6Aufgabe 6: Quick Sort ()
10.3.7Aufgabe 7: Bucket Sort ()
10.3.8Aufgabe 8: Suche in rotierten Daten ()
10.4Lösungen
10.4.1Lösung 1: Contains All ()
10.4.2Lösung 2: Partitionierung ()
10.4.3Lösung 3: Binärsuche ()
10.4.4Lösung 4: Insertion Sort ()
10.4.5Lösung 5: Selection Sort ()
10.4.6Lösung 6: Quick Sort ()
10.4.7Lösung 7: Bucket Sort ()
10.4.8Lösung 8: Suche in rotierten Daten ()
11Schlusswort und ergänzende Literatur
11.1Schlusswort
11.1.1Gelerntes pro Kapitel
11.1.2Bedenkenswertes
11.2Knobelaufgaben
11.2.1Goldsäcke – Fälschung entdecken
11.2.2Pferderennen – schnellste drei Pferde ermitteln
11.3Ergänzende Literatur
IIIAnhang
ASchnelleinstieg JShell
A.1Java + REPL => jshell
BKurzeinführung JUnit 5
B.1Schreiben und Ausführen von Tests
B.1.1Beispiel: Ein erster Unit Test
B.1.2Grundlagen zum Schreiben und Ausführen von Tests
B.1.3Behandlung erwarteter Exceptions mit assertThrows()
B.2Parametrisierte Tests mit JUnit 5
CSchnelleinstieg O-Notation
C.1Abschätzungen mit der O-Notation
C.1.1Komplexitätsklassen
C.1.2Komplexität und Programmlaufzeit
Literaturverzeichnis
Index
Vorwort
Zunächst einmal bedanke ich mich bei Ihnen, dass Sie sich für dieses Buch entschieden haben. Hierin finden Sie eine Vielzahl an Übungsaufgaben zu den unterschiedlichsten Themengebieten, die kurzweilige Unterhaltung durch Lösen und Implementieren der Aufgaben bieten und Sie so entweder auf Bewerbungsgespräche einstimmen oder aber einfach Ihre Problemlösungsfähigkeiten verbessern.
Übung macht den Meister
Wir alle kennen das Sprichwort: »Übung macht den Meister.« Im Handwerk und in diversen Bereichen des realen Lebens wird viel geübt und der Ernstfall ist eher selten, etwa im Sport, bei Musikern und in anderen Bereichen. Merkwürdigerweise ist dies bei uns Softwareentwicklern oftmals deutlich anders. Wir entwickeln eigentlich fast die gesamte Zeit und widmen uns dem Üben und Lernen bzw. Einstudieren eher selten, teilweise gar nicht. Wie kommt das?
Vermutlich liegt das neben dem in der Regel vorherrschenden Zeitdruck auch daran, dass nicht so viel geeignetes Übungsmaterial zur Verfügung steht – es gibt zwar Lehrbücher zu Algorithmen sowie Bücher zu Coding, aber meistens sind diese entweder zu theoretisch oder zu Sourcecode-lastig und beinhalten zu wenig Erklärungen der Lösungswege. Das will dieses Buch ändern.
Wieso dieses Buch?
Wie kam ich dazu, dieses Buchprojekt in Angriff zu nehmen? Das hat mehrere Gründe. Zum einen wurde ich immer wieder per Mail oder persönlich von Teilnehmern meiner Workshops gefragt, ob es nicht ein Übungsbuch als Ergänzung zu meinem Buch »Der Weg zum Java-Profi« [2] geben würde. Dadurch kam die erste Idee auf.
Wirklich ausgelöst hat das Ganze, dass ein Recruiter von Google, mit einer Jobanfrage recht überraschend auf mich zukam. Als Vorbereitung für die dann bevorstehenden Jobinterviews und zur Auffrischung meiner Kenntnisse machte ich mich auf die Suche nach geeigneter Lektüre und entwickelte selbst schon einige Übungsaufgaben. Dabei entdeckte ich das großartige, aber auch teilweise recht anspruchsvolle Buch »Cracking the coding interview« von Gayle Laakmann McDowell [5], das mich weiter inspirierte, sodass ich ein paar der dort vorgestellten Ideen aufgreife.
An wen richtet sich dieses Buch?
Dieses Buch ist kein Buch für Programmierneulinge, sondern richtet sich an Leser, die bereits recht gutes Java-Know-how besitzen und dieses mithilfe von Übungen weiter vertiefen wollen. Anhand kleiner Programmieraufgaben erweitern Sie auf unterhaltsame Weise Ihr Wissen rund um Java, Algorithmen und gutes OO-Design.
Dieses Buch richtet sich im Speziellen an zwei Zielgruppen:
Zum einen sind dies engagierte Hobbyprogrammierer und Informatikstudierende, aber auch Berufseinsteiger, die Java als Sprache schon ganz gut beherrschen, und nun ihr Wissen anhand von Übungen vertiefen wollen.
Zum anderen ist das Buch für erfahrene Softwareentwickler und -architekten bestimmt, die ihr Wissen ergänzen oder auffrischen wollen, um einige althergebrachte Denkmuster aufzubrechen und neue Ideen zu entwickeln. Insbesondere zur Lösungsfindung und zu Algorithmen und Datenstrukturen sollte es das eine oder andere Aha-Erlebnis geben.
Generell verwende ich die maskuline Form, um den Text leichter lesbar zu halten. Natürlich beziehe ich damit alle weiblichen Leserinnen mit ein und freue mich über diese ganz besonders.
Was vermittelt dieses Buch?
Dieses Buch enthält einen bunten Mix an Übungsaufgaben zu verschiedenen Themengebieten. Mitunter gibt es auch einige Knobelaufgaben, die zwar nicht direkt für die Praxis wichtig sind, aber indirekt doch, weil Sie Ihre Fähigkeiten zur Kreativität und zur Lösungsfindung verbessern.
Neben Übungsaufgaben und dokumentierten Lösungen war es mir wichtig, dass jeder im Buch behandelte Themenbereich mit einer kurzen Einführung startet, damit auch diejenigen Leser abgeholt werden, die in einigen Gebieten vielleicht noch nicht so viel Know-how aufgebaut haben. Damit können Sie sich dann an die Aufgaben bis etwa zum mittleren Schwierigkeitsgrad wagen. In jedem Themengebiet finden sich immer auch einige leichtere Aufgaben zum Einstieg. Mit etwas Übung sollten Sie sich auch an etwas schwierigere Probleme wagen. Mitunter gibt es herausfordernde Knacknüsse, an denen sich dann Experten versuchen können oder solche, die es werden wollen.
Tipps und Hinweise aus der Praxis
Dieses Buch ist mit diversen Praxistipps gespickt. In diesen werden interessante Hintergrundinformationen präsentiert oder es wird auf Fallstricke hingewiesen.
Tipp: Praxistipp
In derart formatierten Kästen finden sich im späteren Verlauf des Buchs immer wieder einige wissenswerte Tipps und ergänzende Hinweise zum eigentlichen Text.
Schwierigkeitsgrad im Überblick
Für ein ausgewogenes, ansprechendes Übungsbuch bedarf es selbstverständlich einer Vielzahl an Aufgaben verschiedener Schwierigkeitsstufen, die Ihnen als Leser die Möglichkeit bieten, sich schrittweise zu steigern und Ihre Kenntnisse auszubauen. Dabei setze ich zwar ein gutes Java-Grundwissen voraus, allerdings erfordern die Lösungen niemals ganz tiefes Wissen über ein Themengebiet oder ganz besondere Sprachfeatures.
Damit der Schwierigkeitsgrad einfach und direkt ersichtlich ist, habe ich die von anderen Bereichen bekannte Sternekategorisierung genutzt, deren Bedeutung in diesem Kontext in nachfolgender Tabelle etwas genauer erläutert wird.
Sterne (Bedeutung)
Einschätzung
Zeitaufwand
(sehr leicht)
Die Aufgaben sollten ohne große Vorkenntnisse mit einfachem Java-Wissen in wenigen Minuten lösbar sein.
< 15 min
(leicht)
Die Aufgaben erfordern ein wenig Nachdenken, sind aber dann direkt zu lösen.
< 30 min
(mittel)
Die Aufgaben sind mit etwas Nachdenken, ein wenig Strategie und manchmal durch die Betrachtung verschiedener Rahmenbedingungen gut schaffbar.
~ 30 – 45 min
(schwierig)
Erprobte Problemlösungsstrategien, gutes Wissen zu Datenstrukturen und fundierte Java-Kenntnisse sind zur Lösung nötig.
~ 45 – 90 min
(sehr schwierig)
Die Aufgaben sind wirklich knifflig und schwierig zu lösen. Das sind erst dann Kandidaten, nachdem die anderen Aufgaben Ihnen keine größeren Schwierigkeiten mehr bereiten.
> 60 min
Dies sind jeweils nur Einschätzungen von meiner Seite und eher grobe Einordnungen. Bedenken Sie bitte, dass die von jedem Einzelnen wahrgenommene Schwierigkeit auch sehr von seinem Background und Wissensstand abhängt. Ich habe schon erlebt, dass sich Kollegen mit Aufgaben schwergetan haben, die ich als recht einfach empfand. Aber auch das Gegenteil kenne ich: Während andere eine Aufgabe anscheinend spielend lösen, ist man selbst am Verzweifeln, weil der Groschen einfach nicht fällt. Manchmal hilft dann eine Pause mit einem Kaffee oder ein kleiner Spaziergang. Lassen Sie sich auf keinen Fall demotivieren – jeder hat irgendwann mit irgendeiner Art von Aufgabe zu kämpfen.
Hinweis: Mögliche Alternativen zu den Musterlösungen
Beachten Sie bitte, dass es für Problemstellungen nahezu immer einige Varianten gibt, die für Sie vielleicht sogar eingängiger sind. Deswegen werde ich ab und an als Denkanstoß interessante Alternativen zur (Muster-)Lösung präsentieren.
Aufbau dieses Buchs
Nachdem Sie eine grobe Vorstellung über den Inhalt dieses Buchs haben, möchte ich die Themen der einzelnen Kapitel kurz vorstellen.
Wie bereits angedeutet, sind die Übungsaufgaben thematisch gruppiert. Dabei bilden die sechs Kapitel nach der Einleitung die Grundlage und die darauffolgenden drei Kapitel behandeln fortgeschrittenere Themengebiete.
Kapitel 1 – EinleitungDieses Kapitel beschreibt den grundsätzlichen Aufbau der folgenden Kapitel mit den Abschnitten Einführung, Aufgaben und Lösungen. Zudem wird ein Grundgerüst für die oftmals zur Prüfung der Lösungen genutzten Unit Tests vorgestellt. Abschließend gebe ich Hinweise zum Ausprobieren der Beispiele und Lösungen.
Kapitel 2 – Mathematische AufgabenDas zweite Kapitel widmet sich mathematischen Operationen sowie Aufgaben zu Primzahlen und dem römischen Zahlensystem. Darüber hinaus präsentiere ich ein paar Ideen zu Zahlenspielereien.
Kapitel 3 – RekursionRekursion ist ein wichtiger Basisbaustein bei der Formulierung von Algorithmen. Dieses Kapitel gibt einen kurzen Einstieg und die diversen Übungsaufgaben sollten dabei helfen, Rekursion zu verstehen.
Kapitel 4 – StringsStrings sind bekanntermaßen Zeichenketten, die eine Vielzahl an Methoden bieten. Ein solides Verständnis ist elementar wichtig, da nahezu kein Programm ohne Strings auskommt. Deswegen werden wir in diesem Kapitel die Verarbeitung von Zeichenketten anhand verschiedener Übungsaufgaben kennenlernen.
Kapitel 5 – ArraysNeben Strings sind Arrays ebenfalls Grundbausteine beim Programmieren. Arrays sind – wie Sie wissen – einfache Datenstrukturen zur Speicherung von Werten, allerdings ohne allzu viel Komfort. In der Praxis empfiehlt sich chrodeswegen oftmals, auf die Datenstrukturen des Collections-Frameworks zurückzugreifen. Diese behandelt dann Kapitel 7 eingehend.
Kapitel 6 – DatumsverarbeitungMit Java 8 wurde das JDK um einige Funktionalitäten zur Datumsverarbeitung erweitert. Diese sollte jeder Java-Entwickler kennen. Die Übungsaufgaben verschaffen Ihnen einen guten Einstieg in die Thematik, sodass der Transfer in die Praxis leichtfallen sollte.
Kapitel 7 – Basisdatenstrukturen: Listen, Sets und MapsIm Collections-Framework werden Listen, Mengen und Schlüssel-Wert-Abbildungen durch verschiedene Containerklassen realisiert. Für den Programmieralltag ist ein sicherer Einsatz von großem Vorteil, was durch die Übungsaufgaben trainiert wird.
Kapitel 8 – Rekursion AdvancedKapitel 3 hat das Thema Rekursion einleitend behandelt. In diesem Kapitel beschäftigen wir uns mit einigen fortgeschritteneren Aspekten rund um das Thema Rekursion. Wir starten mit der Optimierungstechnik namens Memoization. Im Anschluss schauen wir uns Backtracking als eine Problemlösungsstrategie an, die auf Versuch-und-Irrtum beruht und mögliche Lösungswege durchprobiert. Damit lassen sich diverse Algorithmen ziemlich verständlich und elegant halten.
Kapitel 9 – BäumeBaumstrukturen spielen in der Informatik sowohl in der Theorie als auch der Praxis eine wichtige Rolle. In vielen Anwendungskontexten lassen sich Bäume gewinnbringend einsetzen, etwa für die Verwaltung eines Dateisystems, die Darstellung eines Projekts mit Teilprojekten und Aufgabenpaketen oder eines Buchs mit Kapiteln, Unterkapiteln und Abschnitten.
Kapitel 10 – Suchen und SortierenSuchen und Sortieren sind zwei elementare Themen der Informatik im Bereich der Algorithmen und Datenstrukturen. Das Collections-Framework setzt beide um und nimmt einem dadurch viel Arbeit ab. Jedoch lohnt sich auch ein Blick hinter die Kulissen, etwa auf verschiedene Sortierverfahren und deren spezifische Stärken und Schwächen.
Kapitel 11 – Schlusswort und ergänzende LiteraturIn diesem Kapitel fasse ich das Buch zusammen und gebe vor allem einen Ausblick auf ergänzende Literatur. Um Ihr Können zu erweitern, ist neben dem Programmiertraining auch das Studium von weiteren Büchern empfehlenswert. Eine Auswahl an hilfreichen Titeln bildet den Abschluss des Hauptteils dieses Buchs.
Anhang A – Schnelleinstieg JShellIn diesem Buch werden diverse Beispiele direkt auf der Konsole ausprobiert. Der Grund ist vor allem, dass Java seit Version 9 die interaktive Kommandozeilenapplikation JShell als REPL (Read Evaluate Print Loop) bietet, die wir in diesem Anhang kurz kennenlernen wollen.
Anhang B – Schnelleinsteg JUnitZum Prüfen kleinerer Programmbausteine haben sich Unit Tests bewährt. Mit JUnit 5 ist das Ganze insbesondere beim Formulieren von Testfällen für mehrere Eingabekombinationen ziemlich komfortabel. Weil viele der hier im Buch erstellten Lösungen mit Unit Tests geprüft werden, gibt dieser Anhang einen Einstieg in die Thematik.
Anhang C – Schnelleinstieg O-NotationIn diesem Buch verwende ich manchmal zur Abschätzung des Laufzeitverhaltens und zur Einordnung der Komplexität von Algorithmen die sogenannte O-Notation. Dieser Anhang stellt Wesentliches dazu vor.
Konventionen und ausführbare Programme
Verwendete Zeichensätze
Im gesamten Text gelten folgende Konventionen bezüglich der Schriftart: Der normale Text erscheint in der vorliegenden Schriftart. Dabei werden wichtige Textpassagen kursiv oder kursiv und fett markiert. Englische Fachbegriffe werden eingedeutscht groß geschrieben. Zusammensetzungen aus englischen und deutschen (oder eingedeutschten) Begriffen werden mit Bindestrich verbunden, z. B. Plugin-Manager. Sourcecode-Listings sind in der Schrift courier gesetzt, um zu verdeutlichen, dass dieser Text einen Ausschnitt aus einem Java-Programm wiedergibt. Auch im normalen Text werden Klassen, Methoden, Konstanten und Übergabeparameter in dieser Schriftart dargestellt.
Verwendete Abkürzungen
Im Buch verwende ich die in der nachfolgenden Tabelle aufgelisteten Abkürzungen. Weitere Abkürzungen werden im laufenden Text in Klammern nach ihrer ersten Definition aufgeführt und anschließend bei Bedarf genutzt.
Abkürzung
Bedeutung
API
Application Programming Interface
ASCII
American Standard Code for Information Interchange
(G)UI
(Graphical) User Interface
IDE
Integrated Development Environment
JDK
Java Development Kit
JLS
Java Language Specification
JRE
Java Runtime Environment
JSR
Java Specification Request
JVM
Java Virtual Machine
Verwendete Java-Version(en)
Nahezu alle Programme nutzen Java 11 als Basis, da dies die letzte LTS-Version (Long Term Support) ist, die mittlerweile eine gute Verbreitung besitzt. Die neueren Java-Versionen bringen einige hilfreiche Syntaxänderungen und API-Erweiterungen, die jedoch zur Lösung der Aufgaben nicht von Bedeutung sind – außer für ganz spezielle Aufgaben zu switch mit Java 14.
Verwendete Klassen aus dem JDK
Werden Klassen des JDKs zum ersten Mal im Text erwähnt, so wird deren voll qualifizierter Name, d. h. inklusive der Package-Struktur, angegeben: Für die Klasse String würde dann etwa java.lang.String notiert. Dies erleichtert ein Auffinden im JDK. Im darauffolgenden Text wird zur besseren Lesbarkeit auf diese Angabe verzichtet und nur der Klassenname genannt. Zudem sind aus Platzgründen in den Listings nur selten import-Anweisungen abgebildet.
Im Text beschriebene Methodenaufrufe enthalten in der Regel die Typen der Übergabeparameter, etwa substring(int, int). Sind die Parameter in einem Kontext nicht entscheidend, wird auf deren Angabe aus Gründen der besseren Lesbarkeit verzichtet oder aber durch die Zeichenfolge … abgekürzt.
Download, Sourcecode und ausführbare Programme
Der Sourcecode der Beispiele steht auf der Webseite
www.dpunkt.de/java-challenge
zum Download bereit und ist in ein Eclipse-Projekt integriert. Weil dies ein Buch zum Mitmachen ist, sind einige der Programme mithilfe von Gradle-Tasks ausführbar. Deren Name wird in Kapitälchenschrift, etwa LOCALEEXAMPLE, angegeben – alternativ ist natürlich eine Ausführung in der IDE bzw. als Unit Test möglich.
Viele Codeschnipsel lassen sich aber auch hervorragend in der JShell ausprobieren. Um das zu gewährleisten, sind mitunter bereits entwickelte Methoden an geeigneter Stelle nochmals abgebildet.
Nacharbeiten nach Projekt-ImportNach dem erstmaligen Import müssen die Abhängigkeiten auf die externen Bibliotheken im Eclipse-Projekt mit dem Kommando gradle cleanEclipse eclipse neu initialisiert und auf Ihren Rechner aktualisiert werden.
Danksagung
Ein Fachbuch zu schreiben ist eine schöne, aber arbeitsreiche und langwierige Aufgabe. Alleine kann man dies kaum bewältigen. Daher möchte ich mich an dieser Stelle bei allen bedanken, die direkt oder indirekt zum Gelingen des Buchs beigetragen haben. Insbesondere konnte ich bei der Erstellung des Manuskripts auf ein starkes Team an Korrekturlesern zurückgreifen. Es ist hilfreich, von den unterschiedlichen Sichtweisen und Erfahrungen profitieren zu dürfen.
Zunächst einmal möchte ich mich bei Michael Kulla, der als Trainer für Java SE und Java EE bekannt ist, für sein mehrmaliges, gründliches Review vieler Kapitel, die fundierten Anmerkungen und den tollen Einsatz ganz herzlich bedanken. Ebenfalls bin ich Prof. Dr. Dominik Gruntz für eine Vielzahl an Verbesserungsvorschlägen sehr dankbar. Zudem erhielt ich die eine oder andere hilfreiche Anregung von Jean-Claude Brantschen, Prof. Dr. Carsten Kern und Christian Heitzmann. Wieder einmal hat auch Ralph Willenborg ganz genau gelesen und so diverse Tippfehler gefunden. Vielen Dank dafür!
Ebenso geht ein Dankeschön an das Team des dpunkt.verlags (Dr. Michael Barabas, Martin Wohlrab, Anja Weimer und Birgit Bäuerlein) für die tolle Zusammenarbeit. Außerdem möchte ich mich bei Torsten Horn für die fundierte fachliche Durchsicht sowie bei Ursula Zimpfer für ihre Adleraugen beim Copy-Editing bedanken.
Abschließend geht ein lieber Dank an meine Frau Lilija für ihr Verständnis und die Unterstützung, vor allem auch für etliche Stupser, um auf das Fahrrad zu steigen und eine Runde zu drehen, anstatt nur am Buch zu arbeiten.
Anregungen und Kritik
Trotz großer Sorgfalt und mehrfachen Korrekturlesens lassen sich missverständliche Formulierungen oder sogar Fehler leider nicht vollständig ausschließen. Falls Ihnen etwas Derartiges auffallen sollte, so zögern Sie bitte nicht, mir dies mitzuteilen. Gerne nehme ich auch Anregungen oder Verbesserungsvorschläge entgegen. Kontaktieren Sie mich bitte per Mail unter:
Zürich, im Juni 2020
Michael Inden
1Einleitung
Herzlich willkommen zu diesem Übungsbuch! Bevor Sie loslegen, möchte ich kurz darstellen, was Sie bei der Lektüre erwartet.
Dieses Buch behandelt verschiedene praxisrelevante Themengebiete und deckt diese durch Übungsaufgaben unterschiedlicher Schwierigkeitsstufen ab. Die Übungsaufgaben sind (größtenteils) voneinander unabhängig und können je nach Lust und Laune oder Interesse in beliebiger Reihenfolge gelöst werden.
Neben den Aufgaben finden sich die jeweiligen Lösungen inklusive einer kurzen Beschreibung des zur Lösung verwendeten Algorithmus sowie dem eigentlichen, an wesentlichen Stellen kommentierten Sourcecode.
1.1Aufbau der Kapitel
Jedes Kapitel ist strukturell gleich aufgebaut, sodass Sie sich schnell zurechtfinden werden.
Einführung
Ein Kapitel beginnt jeweils mit einer Einführung in die jeweilige Thematik, um auch diejenigen Leser abzuholen, die mit dem Themengebiet vielleicht noch nicht so vertraut sind, oder aber, um Sie auf die nachfolgenden Aufgaben entsprechend einzustimmen.
Aufgaben
Danach schließt sich ein Block mit Übungsaufgaben und folgender Struktur an:
AufgabenstellungJede einzelne Übungsaufgabe besitzt zunächst eine Aufgabenstellung. Dort werden in wenigen Sätzen die zu realisierenden Funktionalitäten beschrieben. Oftmals wird auch schon eine mögliche Methodensignatur als Anhaltspunkt zur Lösung angegeben.
BeispieleErgänzend finden sich fast immer Beispiele zur Verdeutlichung mit Eingaben und erwarteten Ergebnissen. Nur für einige recht einfache Aufgaben, die vor allem zum Kennenlernen eines APIs dienen, wird mitunter auf Beispiele verzichtet.
Oftmals werden in einer Tabelle verschiedene Wertebelegungen von Eingabeparameter(n) sowie das erwartete Ergebnis dargestellt, etwa wie folgt:
Eingabe A
Eingabe B
Ergebnis
[1, 2, 4, 7, 8]
[2, 3, 7, 9]
[2, 7]
Für die Angaben gelten folgende Notationsformen:
"AB" – steht für textuelle Angaben
true / false – repräsentieren boolesche Werte
123 – Zahlenangaben
[ value1, value2, …. ] – steht für Collections wie Sets oder Listen, aber auch Arrays
{ key1 : value1, key2 : value3, … } – beschreibt Maps
Lösungen
Auch der Teil der Lösungen besitzt die nachfolgend beschriebene Struktur.
Aufgabenstellung und BeispieleZunächst finden wir nochmals die Aufgabenstellung, sodass wir nicht ständig zwischen Aufgaben und Lösungen hin- und herblättern müssen, sondern das Ganze in sich abgeschlossen ist.
AlgorithmusDanach folgt eine Beschreibung des gewählten Algorithmus zur Lösung. Aus Gründen der Didaktik zeige ich bewusst auch einmal einen Irrweg oder eine nicht so optimale Lösung, um daran dann Fallstricke aufzudecken und iterativ zu einer Verbesserung zu kommen. Tatsächlich ist die eine oder andere Brute-Force-Lösung manchmal sogar schon brauchbar, bietet aber Optimierungspotenziale. Exemplarisch werde ich immer wieder entsprechende, mitunter verblüffend einfache, aber oft auch sehr wirksame Verbesserungen vorstellen.
PrüfungTeilweise sind die Aufgaben recht leicht oder dienen nur dem Kennenlernen von Syntax oder API-Funktionalität. Dafür scheint es mir oftmals ausreichend, ein paar Aufrufe direkt in der JShell auszuführen. Deshalb verzichte ich hierfür auf Unit Tests. Gleiches gilt auch, wenn wir bevorzugt eine grafische Aufbereitung einer Lösung, etwa die Darstellung eines Sudoku-Spielfelds zur Kontrolle nutzen und der korrespondierende Unit Test vermutlich schwieriger verständlich wäre.
Je komplizierter allerdings die Algorithmen werden, desto mehr lauern auch Fehlerquellen, wie falsche Indexwerte, eine versehentliche oder unterbliebene Negation oder ein übersehener Randfall. Deswegen bietet es sich an, Funktionalitäten mithilfe von Unit Tests zu überprüfen – in diesem Buch kann das aus Platzgründen natürlich nur exemplarisch für wichtige Eingaben geschehen. Insgesamt existieren jedoch über 90 Unit Tests mit rund 750 Testfällen. Ein ziemlich guter Anfang. Trotzdem sollte in der Praxis das Netz an Unit Tests und Testfällen wenn möglich noch umfangreicher sein.
1.2Grundgerüst des Eclipse-Projekts
Auch das mitgelieferte Eclipse-Projekt orientiert sich in seinem Aufbau an demjenigen des Buchs und bietet für die Kapitel mit Übungsaufgaben jeweils ein eigenes Package pro Kapitel, z. B. ch02_math oder ch08_recursion_advanced. Dabei weiche ich ausnahmsweise von der Namenskonvention für Packages ab, weil ich die Unterstriche in diesem Fall für eine lesbare Notation halte.
Einige der Sourcecode-Schnipsel aus den jeweiligen Einführungen finden sich in einem Subpackage intro. Die bereitgestellten (Muster-)Lösungen werden in jeweils eigenen Subpackages namens solutions gesammelt und die Klassen sind gemäß Aufgabenstellung wie folgt benannt: Ex<Nr>_<Aufgabenstellung>.
Das gesamte Projekt folgt dem Maven-Standardverzeichnisaufbau und somit finden siche die Sourcen unter src/main/java und die Tests unter src/test/java.
Sourcen – src/main/javaNachfolgend ist ein Ausschnitt für das Kapitel 2 gezeigt:
Test-Klassen – src/test/javaExemplarisch hier einige dazugehörige Tests:
Utility-KlassenAlle in den jeweiligen Kapiteln entwickelten nützlichen Utility-Methoden sind im bereitgestellten Eclipse-Projekt in Form von Utility-Klassen enthalten. Beispielsweise implementieren wir in Kapitel 5 einige hilfreiche Methoden, unter anderem swap() und find() (alle in Abschnitt 5.1.1). Diese kombinieren wir dann in einer Klasse ArrayUtils, die in einem eigenen Subpackage util liegt – für das Kapitel zu Arrays im Subpackage ch05_arrays.util. Gleiches gilt für die anderen Kapitel und Themengebiete.
1.3Grundgerüst für die Unit Tests
Um den Rahmen des Buchs nicht zu sprengen, zeigen die abgebildeten Unit Tests jeweils nur die Testmethoden, jedoch nicht die Testklasse und die Imports. Damit Sie ein Grundgerüst haben, in das Sie die Testmethoden einfügen können sowie als Ausgangspunkt für eigene Experimente, ist nachfolgend eine typische Testklasse gezeigt:
Neben den Imports und den ausgiebig genutzten parametrisierten Tests, die das Prüfen mehrerer Wertkombinationen auf einfache Weise erlauben, ist hier die Bereitstellung der Testeingaben über @CsvSource und @MethodSource in Kombination mit einem Stream<Arguments> gezeigt. Für Details schauen Sie bitte in Anhang B.
1.4Anmerkung zum Programmierstil
In diesem Abschnitt möchte ich noch vorab etwas zum Programmierstil sagen, weil in Diskussionen ab und an einmal die Frage aufkam, ob man gewisse Dinge nicht kompakter gestalten sollte.
Gedanken zur Sourcecode-Kompaktheit
In der Regel sind mir beim Programmieren und insbesondere für die Implementierungen in diesem Buch vor allem eine leichte Nachvollziehbarkeit sowie eine übersichtliche Strukturierung und damit später eine vereinfachte Wartbarkeit und Veränderbarkeit wichtig. Deshalb sind die gezeigten Implementierungen möglichst verständlich programmiert und vermeiden etwa den ?-Operator für komplexere Ausdrücke. Dadurch ist vielleicht nicht jedes Konstrukt maximal kompakt, dafür aber in der Regel gut verständlich. Diesem Aspekt möchte ich in diesem Buch den Vorrang geben. Auch in der Praxis kann man damit oftmals besser leben als mit einer schlechten Wartbarkeit, dafür aber einer kompakteren Programmierung.
Beispiel 1
Schauen wir uns zur Verdeutlichung ein kleines Beispiel an. Zunächst betrachten wir die lesbare, gut verständliche Variante zum Umdrehen des Inhalts eines Strings, die zudem sehr schön die beiden wichtigen Elemente des rekursiven Abbruchs und Abstiegs verdeutlicht:
Die folgende deutliche kompaktere Variante bietet diese Vorteile nicht:
static String reverseStringShort(final String input)
{
return input.length() <= 1 ? input :
reverseStringShort(input.substring(1)) + input.charAt(0);
}
Überlegen Sie kurz, in welcher der beiden Methoden Sie sich sicher fühlen, eine nachträgliche Änderung vorzunehmen. Und wie sieht es aus, wenn Sie noch Unit Tests ergänzen wollen: Wie finden Sie passende Wertebelegungen und Prüfungen?
Außerdem sollte man bedenken, dass die obere Variante entweder bereits während der Kompilierung (Umwandlung in den Bytecode) oder später während der Ausführung und Optimierung automatisch in etwas Ähnliches wie die untere Variante konvertiert wird – eben mit dem Vorteil der besseren Lesbarkeit beim Programmieren.
Beispiel 2
Lassen Sie mich noch ein weiteres Beispiel anbringen, um meine Aussage zu verdeutlichen. Nehmen wir folgende Methode countSubstrings(), die die Anzahl der Vorkommen eines Strings in einem anderen zählt und für die beiden Eingaben "halloha" und "ha" das Ergebnis 2 liefert.
Zunächst implementieren wir das einigermaßen geradeheraus wie folgt:
Schauen wir uns an, wie man dies kompakt zu realisieren versuchen könnte:
static int countSubstringsShort(final String input, final String valueToFind)
{
return input.length() < valueToFind.length() ? 0 :
(input.startsWith(valueToFind) ? 1 : 0) +
countSubstringsShort(input.substring(1), valueToFind);
}
Würden Sie lieber in dieser Methode oder der zuvor gezeigten ändern?
Übrigens: Die untere enthält noch eine subtile funktionale Abweichung! Bei den Eingaben von "XXXX" und "XX" »konsumiert« die erste Variante immer die Zeichen und findet zwei Vorkommen. Die untere bewegt sich aber jeweils nur um ein Zeichen weiter und findet somit drei Vorkommen.
Und weiter: Die Integration der oben realisierten Funktionalität des Weiterschiebens um den gesamten Suchstring in die zweite Variante wird zu immer undurchsichtigerem Sourcecode führen. Dagegen kann man oben das Weiterschieben um nur ein Zeichen einfach durch Anpassen des oberen substring(valueToFind.length())-Aufrufs umsetzen und diese Funktionalität dann sogar aus dem if herausziehen.
Gedanken zu final und var
Normalerweise bevorzuge ich, unveränderliche Variablen als final zu markieren. In diesem Buch verzichte ich mitunter darauf, vor allem in Unit Tests, um diese so kurz wie möglich zu halten. Ein weiterer Grund ist, dass die JShell das Schlüsselwort final nicht überall unterstützt, glücklicherweise aber an den wichtigen Stellen, nämlich für Parameter und lokale Variablen.
Local Variable Type Inference – varSeit Java 10 existiert die sogenannte Local Variable Type Inference, besser bekannt als var. Diese erlaubt es, auf die explizite Typangabe auf der linken Seite einer Variablendefinition zu verzichten, sofern sich der konkrete Typ für eine lokale Variable anhand der Definition auf der rechten Seite der Zuweisung vom Compiler ermitteln lässt:
Insbesondere im Zusammenhang mit generischen Containern spielt die Local Variable Type Inference ihre Vorteile aus:
Konvention: var falls lesbarerSofern die Verständlichkeit darunter nicht leidet, werde ich var an geeigneter Stelle verwenden, um den Sourcecode kürzer und klarer zu halten. Ist jedoch eine Typangabe für das Nachvollziehen von größerer Wichtigkeit, bevorzuge ich den konkreten Typ und vermeide var – die Grenzen sind aber fließend.
Konvention: final oder varEine weitere Anmerkung noch: Zwar kann man final und var kombinieren, ich finde dies jedoch stilistisch nicht schön und verwende entweder das eine oder das andere.
Anmerkungen zu Methodensichtbarkeiten
Vielleicht fragen Sie sich, wieso die vorgestellten Methoden nicht als public markiert sind. Die in diesem Buch vorgestellten Methoden sind oftmals ohne Sichtbarkeitsmodifier dargestellt, da sie vor allem in demjenigen Package und Kontext aufgerufen werden, wo sie definiert sind. Dadurch sind sie sowohl für die begleitenden Unit Tests als auch für Experimente in der JShell problemlos aufrufbar. Manchmal extrahiere ich aus der Implementierung der Übungsaufgabe zur besseren Strukturierung und Lesbarkeit einige Hilfsmethoden. Diese sind dann in der Regel private, um diesen Umstand entsprechend auszudrücken.
Tatsächlich fasse ich die wichtigsten Hilfsmethoden in speziellen Utility-Klassen zusammen, wo diese für andere Packages natürlich public und static sind, um den Zugriff zu ermöglichen.
Blockkommentare in Listings
Beachten Sie bitte, dass sich in den Listings diverse Blockkommentare finden, die der Orientierung und dem besseren Verständnis dienen. In der Praxis sollte man derartige Kommentierungen mit Bedacht einsetzen und lieber einzelne Sourcecode-Abschnitte in Methoden auslagern. Für die Beispiele des Buchs dienen diese Kommentare aber als Anhaltspunkte, weil die eingeführten oder dargestellten Sachverhalte für Sie als Leser vermutlich noch neu und ungewohnt sind.
Gedanken zur Formattierung
Die in den Listings genutzte Formatierung weicht leicht von den Coding Conventions von Oracle1 ab. Ich orientiere mich an denjenigen von Scott Ambler2, der insbesondere (öffnende) Klammern in jeweils eigenen Zeilen vorschlägt. Dazu habe ich ein spezielles Format namens Michaelis_CodeFormat erstellt. Dieses ist im Projekt-Download integriert.
1.5Ausprobieren der Beispiele und Lösungen
Grundsätzlich verwende ich möglichst nachvollziehbare Konstrukte und keine ganz besonders ausgefallenen Syntax- oder API-Features spezieller Java-Versionen. Sofern nicht explizit im Text erwähnt, sollten Sie die Beispiele und Lösungen daher mit der aktuellen LTS-Version Java 11 ausprobieren können. In wenigen Ausnahmen setze ich allerdings Syntaxerweiterungen aus Java 14 ein, weil diese das tägliche Programmiererleben deutlich einfacher und angenehmer gestalten.
Besonderheiten für Java-14-PreviewsDurch die mittlerweile kurzen Abstände von 6 Monaten zwischen den Java-Releases werden der Entwicklergemeinde einige Features als Previews vorgestellt. Möchte man diese nutzen, so sind in den IDEs und Build-Tools gewisse Parametrierungen sowohl beim Kompilieren als auch beim Ausführen nötig, etwa wie im folgenden Beispiel:
java --enable-preview -cp build/libs/Java14Examples.jar \
java14.RecordExamples
Weitere Details rund um Java 14 stelle ich in meinem Buch »Java – die Neuerungen in Version 9 bis 14: Modularisierung, Syntax- und API-Erweiterungen« [3] vor.
Ausprobieren mit JShell, Eclipse und als JUnit-TestVielfach können Sie die abgebildeten Sourcecode-Schnipsel einfach in die JShell kopieren und ausführen. Alternativ finden Sie alle relevanten Sourcen in dem zum Buch mitgelieferten Eclipse-Projekt. Dort lassen sich die Programme durch eine main()-Methode starten oder – sofern vorhanden – durch korrespondierende Unit Tests überprüfen.
Los geht’s: Entdeckungsreise Java Challenge
So, nun ist es genug der Vorrede und Sie sind bestimmt schon auf die ersten Herausforderungen durch die Übungsaufgaben gespannt. Deshalb wünsche ich Ihnen nun viel Freude mit diesem Buch sowie einige neue Erkenntnisse beim Lösen der Übungsaufgaben und beim Experimentieren mit den Algorithmen.
Wenn Sie zunächst eine Auffrischung Ihres Wissens zu JUnit, zur JShell oder der O-Notation benötigen, bietet sich ein Blick in die Anhänge an.
Teil I
Grundlagen
2Mathematische Aufgaben
In diesem Kapitel lernen wir zunächst Grundlegendes zu einigen mathematischen Operationen und zu Primzahlen, aber auch zum römischen Zahlensystem kennen. Darüber hinaus präsentiere ich ein paar Ideen zu Zahlenspielereien. Mit diesem Wissen sollten Sie für die Vielzahl an Übungsaufgaben gut gewappnet sein.
2.1Einführung
Kurzeinführung Division und Modulo
Neben Multiplikation und Division wird auch die Modulo-Operation (%) recht häufig verwendet. Sie dient dazu, den Rest einer Division zu ermitteln. Veranschaulichen wir uns dies wie folgt für Ganzzahlen, bei denen Divisionsreste unter den Tisch fallen:
Selbst mit diesen wenigen Operationen lassen sich diverse Aufgabenstellungen lösen. Wir rufen uns folgende Dinge für Aktionen auf Zahlen in Erinnerung:
n
% 10 – Ermittelt den Rest einer Division durch 10 und somit die letzte Ziffer.
n /
10 – Teilt offensichtlich durch den Wert 10 und erlaubt es dadurch, die letzte Ziffer abzuschneiden – auch hier wieder nur bei Ganzzahlen.
Extraktion von ZiffernZur Extraktion der Ziffern einer Zahl kombinieren wir Modulo und Division so lange, wie der verbleibende Wert größer als 0 ist:
Wir rufen diese Methode einmal auf, um deren Arbeitsweise zu verstehen – bitte beachten Sie, dass die Ziffern in umgekehrter Reihenfolge ausgegeben werden:
jshell> extractDigits(123)
3 2 1
Anzahl Ziffern ermittelnStatt einzelne Ziffern zu extrahieren, kann man mithilfe einer wiederholten Division auch die Anzahl der Ziffern einer Dezimalzahl ermitteln, indem man einfach so lange durch 10 teilt, bis kein Rest mehr übrigbleibt:
Kurzeinführung Teiler
Nachfolgend schauen wir uns an, wie man alle echten Teiler einer Zahl, also diejenigen ohne die Zahl selbst, ermitteln kann. Der Algorithmus ist recht einfach: Wir durchlaufen alle Zahlen bis zur Hälfte des Werts (alle höheren Werte können keine ganzzahligen Teiler sein, weil ja die 2 bereits ein Teiler ist) und prüfen, ob diese die gegebene Zahl ohne Rest teilen. Ist das der Fall, so ist diese Zahl ein Teiler und wird in eine Ergebnisliste aufgenommen. Das Ganze implementieren wir wie folgt:
Rufen wir diese Methode einmal auf, um deren Arbeitsweise zu verstehen und dies durch die erwartungskonforme Ausgabe zu bestätigen:
jshell> findProperDivisors(6);
...> findProperDivisors(24);
...> findProperDivisors(7);
$5 ==> [1, 2, 3]
$6 ==> [1, 2, 3, 4, 6, 8, 12]
$7 ==> [1]
Kurzeinführung Primzahlen
Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist. Es gibt zwei recht einfach zu verstehende Algorithmen, um zu prüfen, ob eine gegebene Zahl eine Primzahl ist, bzw. um Primzahlen bis zu einem vorgegebenen Maximalwert zu berechnen.
Brute-Force-Algorithmus für PrimzahlenOb eine Zahl eine Primzahl ist oder nicht, lässt sich wie folgt bestimmen: Man schaut für die zu prüfende Zahl ausgehend von der 2 bis maximal zur Hälfte der Zahl, ob die momentane Zahl ein Teiler der ursprünglichen Zahl ist.1 In dem Fall ist es keine Primzahl, ansonsten muss weiter geprüft werden. In Java lässt sich das folgendermaßen formulieren:
Zum Ausprobieren führen wir die Methode in einer Schleife aus und ermitteln alle Primzahlen bis zu 25 – die Programmausgaben zeigen uns, dass die Funktionalität korrekt arbeitet:
Optimierung: Sieb des EratosthenesDer Algorithmus zur Bestimmung der Primzahlen bis zu einem vorgegebenen Maximalwert nennt sich das Sieb des Eratosthenes und geht auf den gleichnamigen griechischen Mathematiker zurück.
Das Ganze funktioniert wie folgt: Initial werden alle Zahlen startend bei zwei bis zu dem vorgegebenen Maximalwert aufgeschrieben, etwa:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
Alle Zahlen gelten zunächst als potenzielle Kandidaten für Primzahlen. Nun werden schrittweise diejenigen Zahlen gestrichen, die keine Primzahlen sein können. Man nimmt die kleinste unmarkiert Zahl, hier zunächst die 2. Diese entspricht der ersten Primzahl. Nun streicht man alle Vielfachen davon, also im Beispiel 4, 6, 8, 10, 12, 14:
Weiter geht es mit der Zahl 3. Das ist die zweite Primzahl. Nun werden wieder die Vielfachen gestrichen, nachfolgend 6, 9, 12, 15:
Die nächste unmarkierte Zahl und somit eine Primzahl ist die 5. Das Verfahren wiederholt man so lange, wie es noch nicht durchgestrichene Zahlen nach der aktuellen Primzahl gibt:
Damit verbleibt dann als Ergebnis für alle Primzahlen kleiner 15:
2, 3, 5, 7, 11, 13
Prüfen Sie Ihren Algorithmus mit folgenden Werten:
Grenzwert
Resultat
15
[2, 3, 5, 7, 11, 13]
25
[2, 3, 5, 7, 11, 13, 17, 19, 23]
50
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
2.1.1Römische Zahlen
Das römische Zahlensystem arbeitet mit speziellen Buchstaben und Kombinationen daraus, um Zahlen zu repräsentieren. Dabei gilt folgende Grundabbildung:2
Der jeweilige Wert ergibt sich normalerweise aus der Addition der Werte der einzelnen Ziffern von links nach rechts, wobei normalerweise (siehe die nachfolgenden Regeln) links die größte und rechts die kleinste Zahl steht, beispielsweise XVI für den Wert 16.
Regeln
Die römischen Zahlen werden nach bestimmten Regeln zusammengesetzt:
Beispiele
Zum besseren Verständnis und zur Verdeutlichung der obigen Regeln schauen wir uns einige Notationen römischer Zahlen und die korrespondierenden Werte an:
Bemerkenswertes
Die bei uns heute verbreiteten arabischen Zahlen nutzen das Zehnersystem, bei dem die Position der Ziffern über deren Wert entscheidet: Somit kann die 7 einmal die Zahl selbst sein, aber auch für 70 oder 700 stehen. Im römischen Zahlensystem steht die V aber immer für eine 5, unabhängig von der Position.
Hinweis: Größere Zahlen
Für die Darstellung größerer römischer Zahlen (im Bereich von zehntausend und mehr) gibt es spezielle Schreibweisen, weil keine vier oder mehr M aufeinander folgen dürfen. Dies ist für die Aufgaben dieses Buchs nicht von Relevanz und kann vom Leser bei Interesse im Internet oder anderen Quellen nachgeschaut werden.
2.1.2Zahlenspielereien
Nachfolgend schauen wir uns ein paar spezielle Zahlenkonstellationen an:
Vollkommene oder perfekte Zahlen
Armstrong-Zahlen
Prüfsummen
Bei vielen der nachfolgend genutzten Algorithmen untergliedert man Zahlen in ihre Ziffern, um entsprechende Zahlenspielereien machen zu können.
Vollkommene oder perfekte Zahlen
Laut Definition wird eine Zahl als »vollkommene Zahl« oder auch »perfekte Zahl« bezeichnet, wenn ihr Wert gleich der Summe ihrer echten Teiler ist (also ohne sich selbst). Klingt etwas merkwürdig, ist aber ganz einfach. Betrachten wir als Beispiel die Zahl 6: Sie hat als echte Teiler die Zahlen 1, 2 und 3. Interessanterweise gilt nun:
Schauen wir uns noch ein Gegenspiel an: die Zahl 20. Diese besitzt die echten Teiler 1, 2, 4, 5 und 10, deren Summe ist jedoch 22 und nicht 20:
Armstrong-Zahlen
Im Folgenden betrachten wir sogenannte Armstrong-Zahlen: Das sind Zahlen, deren einzelne Ziffern zunächst mit der Anzahl der Ziffern in der Zahl potenziert und danach summiert werden. Wenn diese Summe dann mit dem Wert der ursprünglichen Zahl übereinstimmt, so spricht man von einer Armstrong-Zahl. Um das Ganze etwas einfacher zu halten, schauen wir uns den Spezialfall einer dreistelligen Zahl an. Als Armstrong-Zahl muss für diese Zahl folgende Gleichung erfüllt sein:
Dabei sind die Ziffern der Zahl als x, y und z modelliert und jeweils alle dem Wertebereich von 0 bis 9 entstammen.
Betrachten wir zwei Beispiele, für die diese Formel erfüllt ist:
AbwandlungAls Abwandlung ist es auch ganz interessant, für welche Ziffern bzw. Zahlen folgenden Gleichung erfüllt sind:
oder
Für die erste Gleichung gibt es folgende Lösungen:
[135, 175, 518, 598]
Für die zweite Gleichung existiert für x, y, z im Bereich bis 100 keine Lösung. Wenn Sie mögen, können Sie das beim Implementieren des Bonusteils von Aufgabe 9 selbst nachvollziehen – oder einfach in die Lösungen schauen.
Algorithmus für eine einfache Prüfsumme
In diverse Zahlen ist eine Prüfsumme hineincodiert, sodass die Validität ermittelt werden kann. Das gilt etwa für Kreditkartennummern und bei Datenübertragungen über spezielle Protokolle.
Nehmen wir an, es wäre eine Prüfsumme für eine Zahl mit vier Ziffern (nachfolgend als a bis d modelliert) zu berechnen. Dann könnte man positionsbasiert folgende Rechnung vornehmen:
abcd (a * 1 + b * 2 + c * 3 + d * 4) % 10
Auch hier möchte ich die Berechnung anhand von Beispielen verdeutlichen:
2.2Aufgaben
2.2.1Aufgabe 1: Grundrechenarten ()
Aufgabe 1a: Grundrechenarten ()
Schreiben Sie eine Methode int calc(int, int), die zwei Variablen m und n vom Typ int multipliziert, das Produkt dann halbiert und den Rest bezüglich der Division durch 7 ausgibt.
Beispiele
Als kleiner Hinweis zur Erinnerung hier nochmals: Bei einer Ganzzahldivision wird der Rest abgeschnitten, deswegen ergibt 25/2 als Ergebnis den Wert 12.
Aufgabe 1b: Statistik ()
Ermitteln Sie die Anzahl sowie die Summe der natürlichen Zahlen, die durch 2 oder 7 teilbar sind, bis zu einem gegebenen Maximalwert (exklusiv) und geben Sie diese auf der Konsole aus. Schreiben Sie eine Methode void calcSumAndCountAllNumbersDivBy_2_Or_7(int). Erweitern Sie das Ganze, sodass statt der Konsolenausgabe eine Rückgabe der beiden Werte erfolgt.
Beispiele
Aufgabe 1c: Gerade oder ungerade Zahl ()
Erstellen Sie die Methoden boolean isEven(int) und boolean isOdd(int), die prüfen, ob die übergebene Ganzzahl gerade bzw. ungerade ist.
2.2.2Aufgabe 2: Zahl als Text ()
Schreiben Sie eine Methode String numberAsText(int), die für eine gegebene positive Zahl die jeweiligen Ziffern in korrespondierenden Text umwandelt.
Starten Sie mit folgendem Fragment für die letzte Ziffer einer Zahl:
Beispiele
Eingabe
Resultat
7
"SEVEN"
42
"FOUR TWO"
24680
"TWO FOUR SIX EIGHT ZERO"
13579
"ONE THREE FIVE SEVEN NINE"
2.2.3Aufgabe 3: Vollkommene Zahlen ()
Laut Definition wird eine natürliche Zahl als »vollkommene / perfekte Zahl« bezeichnet, wenn ihr Wert gleich der Summe ihrer echten Teiler ist. Das gilt etwa für die 6 oder die 28:
1 + 2 + 3
6
1 + 2 + 4 + 7 + 14
28
Schreiben Sie eine Methode List<Integer> calcPerfectNumbers(int), die die perfekten Zahlen bis zu einem Maximalwert, z. B. 10.000, errechnet.
Beispiele
Eingabe
Resultat
1000
[6, 28, 496]
10000
[6, 28, 496, 8128]
2.2.4Aufgabe 4: Primzahlen ()
Schreiben Sie eine Methode List<Integer> calcPrimesUpTo(int) zur Berechnung aller Primzahlen bis zu einem vorgegebenen Wert. Zur Erinnerung: Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist. Zur Berechnung existiert das sogenannte Sieb des Eratosthenes, was zuvor schon beschrieben wurde.
BeispielePrüfen Sie Ihren Algorithmus mit folgenden Werten:
Eingabe
Resultat
15
[2, 3, 5, 7, 11, 13]
25
[2, 3, 5, 7, 11, 13, 17, 19, 23]
50
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
2.2.5Aufgabe 5: Primzahlpaare ()
Berechnen Sie alle Paare von Primzahlen mit einem Abstand von 2 (Zwilling), 4 (Cousin) und 6 (sexy) bis zu einer oberen Grenze für n. Für Zwillinge gilt dann:
isPrime (n) &&isPrime(n + 2)
BeispieleFolgende Ergebnisse werden für den Grenzwert 50 erwartet:
Art
Resultat
Zwilling
3=5, 5=7, 11=13, 17=19, 29=31, 41=43
Cousin
3=7, 7=11, 13=17, 19=23, 37=41, 43=47
Sexy
5=11, 7=13, 11=17, 13=19, 17=23, 23=29, 31=37, 37=43, 41=47, 47=53
2.2.6Aufgabe 6: Prüfsumme ()
Erstellen Sie eine Methode int calcChecksum(String), die zu einer beliebig langen als String vorliegenden Zahl für deren Prüfsumme positionsbasiert folgende Rechnung vornimmt, dabei seien die n Ziffern als z1 bis zn modelliert:
z1z2z3 … zn (1 * z1 + 2 * z2 + 3 * z3 + … + n * zn) % 10
Beispiele
2.2.7Aufgabe 7: Römische Zahlen ()
Aufgabe 7a: Römische Zahlen→Dezimalzahlen ()
Schreiben Sie eine Methode int fromRomanNumber(String), die aus einer textuell vorliegenden, gültigen römischen Zahl die korrespondierende Dezimalzahl errechnet.3
Aufgabe 7b: Dezimalzahlen→Römische Zahlen ()
Schreiben Sie eine Methode String toRomanNumber(int), die eine Dezimalzahl in eine (gültige) römische Zahl umwandelt.
Beispiele
Arabisch
Römisch
17
"XVII"
444
"CDXLIV"
1971
"MCMLXXI"
2020
"MMXX"
2.2.8Aufgabe 8: Kombinatorik ()
Berechnen Sie alle Kombinationen der Werte a, b und c (jeweils startend ab 1 und kleiner 100), für die folgende Formel gilt:
Bonus ()Reduzieren Sie die Laufzeit von O(n3) auf O(n2). Konsultieren Sie bei Bedarf den Anhang C für eine Einführung in die O-Notation.
Berechnen Sie alle Kombinationen der Werte a, b, c und d (jeweils startend ab 1 und kleiner 100), für die folgende Formel gilt:
Bonus ()Reduzieren Sie die Laufzeit von O(n4) auf O(n3).
2.2.9Aufgabe 9: Armstrong-Zahlen ()
Diese Übung behandelt dreistellige Armstrong-Zahlen. Per Definition versteht man darunter Zahlen, für deren Ziffern x, y und z von 1 bis 9 folgende Gleichung erfüllt ist:
Schreiben Sie eine Methode List<Integer> calcArmstrongNumbers() zur Berechnung aller Armstrong-Zahlen für x, y und z (jeweils < 10).
Beispiele
BonusFinden Sie eine generische Variante mit Lambdas und probieren Sie dann folgende drei Formeln aus:
2.2.10Aufgabe 10: Max Change Calculator ()
Nehmen wir an, wir hätten eine Sammlung von Münzen unterschiedlicher Werte. Schreiben Sie eine Methode calcMaxPossibleChange(values), die für positive Ganzzahlen ermittelt, welche Beträge damit ausgehend vom Wert 1 nahtlos erzeugt werden können. Als Ergebnis soll der Maximalwert zurückgeliefert werden.
Beispiele
Eingabe
Mögliche Werte
Maximum
1
1
1
1, 1
1, 2
2
1, 5
1
1
1, 2, 4
1, 2, 3, 4, 5, 6, 7
7
1, 2, 3, 7
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
13
1, 1, 1, 1, 5, 10, 20, 50
1, 2, 3, 4, 5, 6, …, 30, …, 39
39
2.2.11Aufgabe 11: Befreundete Zahlen ()
Zwei Zahlen n1 und n2 heißen befreundet, wenn die Summe ihrer Teiler der jeweils anderen Zahl entsprechen:
Schreiben Sie eine Methode Map<Integer, Integer> calcFriends(int) zur Berechnung aller befreundeten Zahlen bis zu einem übergebenen Maximalwert.
Beispiele
2.2.12Aufgabe 12: Primfaktorzerlegung ()
Jede natürliche Zahl größer 1 lässt sich als eine Multiplikation von Primzahlen darstellen – denken Sie daran, die 2 ist auch eine Primzahl. Schreiben Sie eine Methode List<Integer> calcPrimeFactors(int), die eine Liste mit Primzahlen liefert, deren Multiplikation die gegebene Zahl ergeben.
Beispiele
Eingabe
Primfaktoren
Resultat
8
2 * 2 * 2
[2, 2, 2]
14
2 * 7
[2, 7]
42
2 * 3 * 7
[2, 3, 7]
1155
3 * 5 * 7 * 11
[3, 5, 7, 11]
2222
2 * 11 * 101
[2, 11, 101]
