Python Challenge E-Book

Michael Inden

• Herausgeber: dpunkt.verlag
• Kategorie: Wissenschaft und neue Technologien
• Serie: Programmieren mit Python
• Sprache: Deutsch
• Veröffentlichungsjahr: 2021

Seitenzahl: 605

Beschreibung

Ihr persönlicher Python-Coach!

• Mehr als 100 Aufgaben und Lösungen
• für Einsteiger und Fortgeschrittene
• Vorbereitung füpr Jobinteriew und Prüfung

Mit 100 Übungsaufgaben und Programmierpuzzles inklusive Lösungen zum Knobeln und Erweitern Ihrer Kenntnisse bietet Ihnen die "Python Challenge" ein kurzweiliges Lernen, eine fundierte Vorbereitung auf die nächste Prüfung oder ein Jobinterview. Dabei werden viele praxisrelevante Themengebiete wie Strings, Datenstrukturen, Rekursion, Arrays usw. berücksichtigt.
Jedes Themengebiet wird in einem eigenen Kapitel behandelt, wobei zunächst kurz auf die Grundlagen eingegangen wird. Danach folgen rund 10 bis 15 Übungsaufgaben verschiedener Schwierigkeitsgrade.
So lassen sich die Programmierkenntnisse effektiv verbessern. Dabei helfen insbesondere detaillierte Musterlösungen inklusive der genutzten Algorithmen zu allen Aufgaben. Ebenso werden von Michael Inden
alternative Lösungswege beschrieben, aber auch mögliche Fallstricke und typische Fehler analysiert.
Abgerundet wird das Buch durch drei Anhänge. Einer beschäftigt sich mit dem Python-Kommandozeileninterpreter, der zum Ausprobieren der Codeschnipsel und Beispiele des Buchs oftmals hilfreich ist. Der zweite gibt einen Überblick über Pytest zum Unit Testen und Prüfen der Lösungen. Der dritte erläutert die O-Notation zur Abschätzung der Performance.

Leseprobe

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 Fort-bildungen 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

Python Challenge

Fit für Prüfung, Job-Interview und Praxis – mit 100 Aufgaben und Musterlösungen

Michael Inden

[email protected]

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-809-5

PDF     978-3-96910-140-7

ePub   978-3-96910-141-4

mobi   978-3-96910-142-1

1. Auflage 2021

Copyright © 2021 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

Für unsere bezaubernde Prinzessin Sophie Jelena

Inhaltsverzeichnis

1Einleitung

1.1Aufbau der Kapitel

1.2Grundgerüst des PyCharm-Projekts

1.3Grundgerüst für die Unit Tests mit PyTest

1.4Anmerkung zum Programmierstil

1.5Anmerkung zu den Aufgaben

1.6Ausprobieren 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.3Typische Probleme: Endlose Aufrufe und RecursionError

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.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 str_to_number ()

4.2.16Aufgabe 16: Print Tower ()

4.2.17Aufgabe 17: Gefüllter Rahmen ()

4.2.18Aufgabe 18: Vokale raten ()

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 str_to_number ()

4.3.16Lösung 16: Print Tower ()

4.3.17Lösung 17: Gefüllter Rahmen ()

4.3.18Lösung 18: Vokale raten ()

5Basisdatenstrukturen: Listen, Sets und Dictionaries

5.1Einführung

5.1.1Sequenzielle Datentypen

5.1.2Listen

5.1.3Mengen (Sets)

5.1.4Schlüssel-Wert-Abbildungen (Dictionaries)

5.1.5Der Stack als LIFO-Datenstruktur

5.1.6Die Queue als FIFO-Datenstruktur

5.2Aufgaben

5.2.1Aufgabe 1: Gemeinsame Elemente ()

5.2.2Aufgabe 2: Eigener Stack ()

5.2.3Aufgabe 3: List Reverse ()

5.2.4Aufgabe 4: Duplikate entfernen ()

5.2.5Aufgabe 5: Maximaler Gewinn ()

5.2.6Aufgabe 6: Längstes Teilstück ()

5.2.7Aufgabe 7: Wohlgeformte Klammern ()

5.2.8Aufgabe 8: Pascal’sches Dreieck ()

5.2.9Aufgabe 9: Check Magic Triangle ()

5.2.10Aufgabe 10: Häufigste Elemente ()

5.2.11Aufgabe 11: Addition von Ziffern ()

5.2.12Aufgabe 12: List Merge ()

5.2.13Aufgabe 13: Excel Magic Select ()

5.2.14Aufgabe 14: Stack Based Queue ()

5.3Lösungen

5.3.1Lösung 1: Gemeinsame Elemente ()

5.3.2Lösung 2: Eigener Stack ()

5.3.3Lösung 3: List Reverse ()

5.3.4Lösung 4: Duplikate entfernen ()

5.3.5Lösung 5: Maximaler Gewinn ()

5.3.6Lösung 6: Längstes Teilstück ()

5.3.7Lösung 7: Wohlgeformte Klammern ()

5.3.8Lösung 8: Pascal’sches Dreieck ()

5.3.9Lösung 9: Check Magic Triangle ()

5.3.10Lösung 10: Häufigste Elemente ()

5.3.11Lösung 11: Addition von Ziffern ()

5.3.12Lösung 12: List Merge ()

5.3.13Lösung 13: Excel Magic Select ()

5.3.14Lösung 14: Stack Based Queue ()

6Arrays

6.1Einführung

6.1.1Eindimensionale Arrays

6.1.2Mehrdimensionale Arrays

6.1.3Typische Fehler

6.1.4Besonderheiten

6.1.5Rekapitulation: NumPy

6.2Aufgaben

6.2.1Aufgabe 1: Gerade vor ungeraden Zahlen ()

6.2.2Aufgabe 2: Flip ()

6.2.3Aufgabe 3: Palindrom ()

6.2.4Aufgabe 4: Inplace Rotate ()

6.2.5Aufgabe 5: Jewels Board Init ()

6.2.6Aufgabe 6: Jewels Board Erase Diamonds ()

6.2.7Aufgabe 7: Spiral-Traversal ()

6.2.8Aufgabe 8: Add One to Array As Number ()

6.2.9Aufgabe 9: Sudoku-Checker ()

6.2.10Aufgabe 10: Flood-Fill ()

6.2.11Aufgabe 11: Array Min und Max ()

6.2.12Aufgabe 12: Array Split ()

6.2.13Aufgabe 13: Minesweeper Board ()

6.3Lösungen

6.3.1Lösung 1: Gerade vor ungeraden Zahlen ()

6.3.2Lösung 2: Flip ()

6.3.3Lösung 3: Palindrom ()

6.3.4Lösung 4: Inplace Rotate ()

6.3.5Lösung 5: Jewels Board Init ()

6.3.6Lösung 6: Jewels Board Erase Diamonds ()

6.3.7Lösung 7: Spiral-Traversal ()

6.3.8Lösung 8: Add One to Array As Number ()

6.3.9Lösung 9: Sudoku-Checker ()

6.3.10Lösung 10: Flood-Fill ()

6.3.11Lösung 11: Array Min und Max ()

6.3.12Lösung 12: Array Split ()

6.3.13Lösung 13: Minesweeper Board ()

IIFortgeschrittenere und kniffligere Themen

7Rekursion Advanced

7.1Memoization

7.1.1Memoization für Fibonacci-Zahlen

7.1.2Memoization für Pascal’sches Dreieck

7.1.3Memoization mit Python-Bordmitteln

7.2Backtracking

7.2.1n-Damen-Problem

7.3Aufgaben

7.3.1Aufgabe 1: Türme von Hanoi ()

7.3.2Aufgabe 2: Edit Distance ()

7.3.3Aufgabe 3: Longest Common Subsequence ()

7.3.4Aufgabe 4: Weg aus Labyrinth ()

7.3.5Aufgabe 5: Sudoku-Solver ()

7.3.6Aufgabe 6: Math Operator Checker ()

7.3.7Aufgabe 7: Wassereimer-Problem ()

7.3.8Aufgabe 8: Alle Palindrom-Teilstrings ()

7.3.9Aufgabe 9: n-Damen-Problem ()

7.4Lösungen

7.4.1Lösung 1: Türme von Hanoi ()

7.4.2Lösung 2: Edit Distance ()

7.4.3Lösung 3: Longest Common Subsequence ()

7.4.4Lösung 4: Weg aus Labyrinth ()

7.4.5Lösung 5: Sudoku-Solver ()

7.4.6Lösung 6: Math Operator Checker ()

7.4.7Lösung 7: Wassereimer-Problem ()

7.4.8Lösung 8: Alle Palindrom-Teilstrings ()

7.4.9Lösung 9: n-Damen-Problem ()

8Binärbäume

8.1Einführung

8.1.1Aufbau, Begrifflichkeiten und Anwendungsbeispiele

8.1.2Binärbäume

8.1.3Binärbäume mit Ordnung: binäre Suchbäume

8.1.4Traversierungen

8.1.5Balancierte Bäume und weitere Eigenschaften

8.1.6Bäume für die Beispiele und Übungsaufgaben

8.2Aufgaben

8.2.1Aufgabe 1: Tree Traversal ()

8.2.2Aufgabe 2: In-, Pre- und Postorder iterativ ()

8.2.3Aufgabe 3: Tree-Höhe berechnen ()

8.2.4Aufgabe 4: Kleinster gemeinsamer Vorfahre ()

8.2.5Aufgabe 5: Breadth-First ()

8.2.6Aufgabe 6: Level Sum ()

8.2.7Aufgabe 7: Tree Rotate ()

8.2.8Aufgabe 8: Rekonstruktion ()

8.2.9Aufgabe 9: Math Evaluation ()

8.2.10Aufgabe 10: Symmetrie ()

8.2.11Aufgabe 11: Check Binary Search Tree ()

8.2.12Aufgabe 12: Vollständigkeit ()

8.2.13Aufgabe 13: Tree Printer ()

8.3Lösungen

8.3.1Lösung 1: Tree Traversal ()

8.3.2Lösung 2: In-, Pre- und Postorder iterativ ()

8.3.3Lösung 3: Tree-Höhe berechnen ()

8.3.4Lösung 4: Kleinster gemeinsamer Vorfahre ()

8.3.5Lösung 5: Breadth-First ()

8.3.6Lösung 6: Level Sum ()

8.3.7Lösung 7: Tree Rotate ()

8.3.8Lösung 8: Rekonstruktion ()

8.3.9Lösung 9: Math Evaluation ()

8.3.10Lösung 10: Symmetrie ()

8.3.11Lösung 11: Check Binary Search Tree ()

8.3.12Lösung 12: Vollständigkeit ()

8.3.13Lösung 13: Tree Printer ()

9Suchen und Sortieren

9.1Einführung Suchen

9.1.1Binärsuche

9.2Einführung Sortieren

9.2.1Insertion Sort

9.2.2Selection Sort

9.2.3Merge Sort

9.2.4Quick Sort

9.2.5Bucket Sort

9.2.6Schlussgedanken

9.3Aufgaben

9.3.1Aufgabe 1: Contains All ()

9.3.2Aufgabe 2: Partitionierung ()

9.3.3Aufgabe 3: Binärsuche ()

9.3.4Aufgabe 4: Insertion Sort ()

9.3.5Aufgabe 5: Selection Sort ()

9.3.6Aufgabe 6: Quick Sort ()

9.3.7Aufgabe 7: Bucket Sort ()

9.3.8Aufgabe 8: Suche in rotierten Daten ()

9.4Lösungen

9.4.1Lösung 1: Contains All ()

9.4.2Lösung 2: Partitionierung ()

9.4.3Lösung 3: Binärsuche ()

9.4.4Lösung 4: Insertion Sort ()

9.4.5Lösung 5: Selection Sort ()

9.4.6Lösung 6: Quick Sort ()

9.4.7Lösung 7: Bucket Sort ()

9.4.8Lösung 8: Suche in rotierten Daten ()

10Schlusswort und ergänzende Literatur

10.1Schlusswort

10.1.1Gelerntes pro Kapitel

10.1.2Bedenkenswertes

10.2Knobelaufgaben

10.2.1Goldsäcke – Fälschung entdecken

10.2.2Pferderennen – schnellste drei Pferde ermitteln

10.3Ergänzende Literatur

IIIAnhang

AKurzeinführung Pytest

A.1Schreiben und Ausführen von Tests

A.1.1Installation von Pytest

A.1.2Beispiel: Ein erster Unit Test

A.1.3Ausführen von Tests

A.1.4Behandlung erwarteter Exceptions

A.1.5Parametrisierte Tests mit Pytest

A.2Weiterführende Literatur zu Pytest

BKurzeinführung Dekoratoren

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« [4] geben würde. Dadurch kam die erste Idee auf.

Doch wirklich ausgelöst hat das Ganze dann, dass ein Google-Recruiter 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 ein paar Übungsaufgaben. Dabei entdeckte ich das großartige, aber teilweise auch recht anspruchsvolle Buch »Cracking the coding interview« von Gayle Laakmann McDowell [6], das mich weiter inspirierte. Als Folge davon machte ich mich zunächst an ein auf Java ausgerichtetes Buchprojekt namens »Java Challenge«. Im Laufe der Zeit kam die Idee auf, etwas Entsprechendes auch für Python umzusetzen. Somit basiert diese Python-Ausgabe auf der Java-Version, allerdings wurde das gesamte Buch überarbeitet und pythonifiziert. Dazu habe ich an einigen Stellen Dinge ergänzt, leicht abgewandelt oder teilweise entfernt. Insbesondere zeige ich, da wo es sinnvoll ist, wie man mit Python-Besonderheiten wie List Comprehensions u. Ä. Lösungen prägnanter gestalten kann.

An wen richtet sich dieses Buch?

Dieses Buch ist kein Buch für Programmierneulinge, sondern richtet sich an Leser, die bereits etwas Python-Know-how besitzen und dieses mithilfe von Übungen vertiefen wollen. Anhand kleiner Programmieraufgaben erweitern Sie auf unterhaltsame Weise Ihr Wissen rund um Python, Algorithmen und gutes Design.

Dieses Buch richtet sich im Speziellen an folgende Zielgruppen:

Schüler und Studierende – Zunächst sind dies Schüler mit Interesse an Informatik sowie Informatikstudierende, die Python als Sprache schon ganz passabel beherrschen und nun ihr Wissen anhand von Übungen vertiefen wollen.

Lehrer und Dozierende – Selbstverständlich können auch Lehrer und Dozierende von diesem Buch und seiner Vielzahl unterschiedlich schwieriger Aufgaben profitieren, entweder als Anregung für den eigenen Unterricht oder als Vorlage für Übungen oder Prüfungen.

Hobbyprogrammierer und Berufseinsteiger – Außerdem richtet sich das Buch an engagierte Hobbyprogrammierer, aber auch Berufseinsteiger, die gerne mit Python programmieren und sich weiterentwickeln wollen. Das Lösen der Aufgaben hilft darüber hinaus, für potenzielle Fragen in Jobinterviews gut vorbereitet zu sein.

Erfahrene Softwareentwickler und -architekten – Schließlich ist das Buch für erfahrene Softwareentwickler und -architekten bestimmt, die ihr Wissen ergänzen oder auffrischen wollen, um ihre Junior-Kollegen besser unterstützen zu können, und dafür ein paar Anregungen und frische Ideen suchen. Zudem lassen sich diverse Aufgaben auch in Jobinterviews verwenden, mit dem Komfort, die Musterlösungen direkt zum Vergleich parat zu haben. Aber auch für die alten Hasen sollte es zur Lösungsfindung und zu Algorithmen und Datenstrukturen 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 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 dann an etwas schwierigere Probleme wagen. Mitunter gibt es herausfordernde Knacknüsse, an denen sich besser Experten versuchen 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:

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 Python-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 Python-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 Python-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 eine Kaffeepause 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 fünf Kapitel nach der Einleitung die Grundlage und die darauffolgenden drei Kapitel behandeln fortgeschrittenere Themengebiete.

Kapitel 1 – EinleitungDieses Kapitel beschreibt den 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 Funktionen 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 – Basisdatenstrukturen: Listen, Sets und Dictionaries Python bietet von Haus aus Listen, Mengen (Sets) und Schlüssel-Wert-Abbildungen (Dictionaries). Für den Programmieralltag ist ein sicherer Einsatz aller drei Container von großem Vorteil, was durch die Übungsaufgaben trainiert wird.

Kapitel 6 – ArraysArrays bilden in vielen Programmiersprachen Grundbausteine. In Python sind Listen gebräuchlicher. Bezüglich Performance und Speicherverbrauch besitzen Arrays aber deutliche Vorteile. Grund genug, sich das Ganze in diesem Kapitel genauer anzuschauen.

Kapitel 7 – Rekursion AdvancedKapitel 3 hat das Thema Rekursion einleitend behandelt. Dieses Kapitel thematisiert fortgeschrittenere Aspekte. 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 formulieren.

Kapitel 8 – BäumeBaumstrukturen spielen in der Informatik sowohl in der Theorie als auch in 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 9 – Suchen und SortierenSuchen und Sortieren sind zwei elementare Themen der Informatik. Die Python-Standardbibliothek setzt beide um und nimmt einem dadurch Arbeit ab. Jedoch lohnt sich auch ein Blick hinter die Kulissen, etwa auf verschiedene Sortierverfahren und deren spezifische Stärken und Schwächen.

Kapitel 10 – 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 – Kurzeinführung PytestZum Prüfen kleinerer Programmbausteine haben sich Unit Tests bewährt. Mit Pytest 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 B – Kurzeinführung DekoratorenIn diesem Anhang werden Dekoratoren beschrieben. Diese ermöglichen es, elegante Realisierungen von Querschnittsfunktionalitäten transparent vorzunehmen, also ohne Erweiterungen in der Implementierung einer Funktion selbst. Beispielsweise kann man sie für Parameterprüfungen verwenden, aber auch für Memoization, ein fortgeschrittenes Rekursionsthema.

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 Python-Programm wiedergibt. Auch im normalen Text werden Klassen, Methoden, Funktionen, 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

Verwendete Python-Version

Dieses Buch nutzt das aktuelle Python 3.8. Viele Lösungen müssten mit minimalen Anpassungen auch in Python 2.7 laufen. Das habe ich jedoch nur stichprobenartig geprüft. Generell ist es für neue Projekte sinnvoll, auf das modernere Python 3 zu setzen.

Download, Sourcecode und ausführbare Programme

Der Sourcecode der Beispiele steht auf der Webseite

www.dpunkt.de/python-challenge

zum Download bereit und ist in ein PyCharm-Projekt1 integriert. Weil dies ein Buch zum Mitmachen ist, sind viele der Programme ausführbar – natürlich ist eine Ausführung in der IDE bzw. als Unit Test möglich.

Viele Codeschnipsel lassen sich aber auch hervorragend im Python-Kommandozeileninterpreter ausprobieren. Um das zu gewährleisten, sind mitunter bereits entwickelte Funktionen an geeigneter Stelle nochmals abgebildet.

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.

Ein herzlicher Dank geht an Martin Stypinski für diverse nützliche Hinweise und Anregungen. Ebenfalls möchte ich Jean-Claude Brantschen für seine hilfreichen Vorschläge danken. Ihr habt mich noch stärker pythonifiziert :-) Auch verschiedene Kommentare von Rainer Grimm und Tobias Overkamp rund um Python und elegante Lösungen haben das Buch weiter verbessert. Schließlich hat Michael Kulla wie bei vielen meiner Bücher auch diese Python-Variante kritisch begutachtet. Vielen Dank an alle!

Da dieses Buch auf Basis der Java-Version entstanden ist, wird nachfolgend die Danksagung der Java Challenge wiederholt: 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 Tobias Overkamp 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 ihre 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:

[email protected]

Zürich, im Dezember 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 Signatur 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 Sets oder Listen

{ key1 : value1, key2 : value2, ... } – beschreibt Dictionaries

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, manchmal verblüffend einfache, aber oft auch sehr wirksame Verbesserungen vorstellen.

Python-ShortcutMitunter werden in der Aufgabenstellung gewisse Python-Standardfunktionalitäten explizit zur Realisierung der Lösung ausgeschlossen, um ein Problem algorithmisch zu durchdringen. In der Praxis sollten Sie aber die Standards nutzen. In diesem eigenen kurzen Abschnitt »Python-Shortcut« zeige ich, wie man damit die Lösung oftmals kürzer und prägnanter gestalten kann.

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 mit dem Python-Kommandozeileninterpreter 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 rund 80 Unit-Test-Module mit über 600 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 PyCharm-Projekts

Auch das mitgelieferte PyCharm-Projekt orientiert sich in seinem Aufbau an demjenigen des Buchs und bietet für die Kapitel mit Übungsaufgaben jeweils ein eigenes Verzeichnis pro Kapitel, z. B. ch02_math oder ch07_recursion_advanced.

Einige der Sourcecode-Schnipsel aus den jeweiligen Einführungen finden sich in einem Unterverzeichnis intro. Die bereitgestellten (Muster-)Lösungen werden in jeweils eigenen Unterverzeichnissen namens solutions gesammelt und die Module sind gemäß Aufgabenstellung wie folgt benannt: ex<Nr>_<Aufgabenstellung>.py.

SourcenNachfolgend ist ein Ausschnitt für das Kapitel 2 gezeigt:

Utility-KlassenAlle in den jeweiligen Kapiteln entwickelten nützlichen Utility-Funktionen sind im bereitgestellten PyCharm-Projekt in Form von Utility-Modulen enthalten. Diese kombinieren wir dann in einem Modul xyz_utils, das in einem eigenen Unterverzeichnis util liegt – für das Kapitel zu mathematische Aufgabenstellungen im Unterverzeichnis ch02_math.util. Gleiches gilt für die anderen Kapitel und Themengebiete.

Test-KlassenExemplarisch sind nachfolgend einige Tests zu Kapitel 2 gezeigt:

1.3Grundgerüst für die Unit Tests mit PyTest

Um den Rahmen des Buchs nicht zu sprengen, zeigen die abgebildeten Unit Tests jeweils nur die Testfunktionen, jedoch oftmals nicht die Imports. Damit Sie ein Grundgerüst haben, in das Sie die Testfunktionen einfügen können, sowie als Ausgangspunkt für eigene Experimente ist nachfolgend ein typisches Modul gezeigt:

Neben den Imports sehen wir die ausgiebig genutzten parametrisierten Tests, die das Prüfen mehrerer Wertkombinationen auf einfache Weise erlauben. Für Details und eine Kurzeinführung in Pytest schauen Sie bitte in Anhang A.

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 dadurch ist vielleicht nicht jedes Konstrukt maximal kompakt. Dem Aspekt der guten Verständlichkeit 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 deutlich kompaktere Variante bietet diese Vorteile nicht:

def reverse_string_short(input):

return input if len(input) <= 1 else \

reverse_string_short(input[1:]) + input[0]

Überlegen Sie kurz, in welcher der beiden Funktionen 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?

Beispiel 2

Lassen Sie mich noch ein weiteres Beispiel anbringen, um meine Aussage zu verdeutlichen. Nehmen wir folgende der Standardfunktion count() nachempfundene Funktion count_substrings(), 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:

def count_substrings_short(input, value_to_find):

return 0 if len(input) < len(value_to_find) else \

(1 if input.startswith(value_to_find) else 0) + \

count_substrings_short(input[1:], value_to_find)

Würden Sie lieber in dieser Funktion oder in 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 umsetzen und diese Funktionalität dann sogar aus dem if herausziehen.

Dekoratoren und Sanity Checks am Methodenanfang

Um für stabile Programme zu sorgen, ist es oftmals eine gute Idee, die Parameter einer Funktion auf Gültigkeit zu prüfen. Das kann man in Form einfacher if-Abfragen realisieren. In Python geht das aber eleganter mithilfe von Dekoratoren. Werfen Sie zum Einstieg doch bitte einen Blick in Anhang B.

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 Funktionen 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.

PEP 8 und Zen of Python

Neben meinen bereits präsentierten Gedanken zum Programmierstil möchte ich noch zwei Dinge explizit erwähnen:

PEP 8 – Coding-StandardDer offizielle Coding-Standard ist als PEP 8 unter https://www.python.org/dev/peps/pep-0008/ online verfügbar. Dieser soll dabei helfen, sauberen, einheitlichen und verständlichen Python-Code zu schreiben. Tendenziell legt man in der Python-Community mehr Wert auf schönen Sourcecode, als dies in anderen Sprachen der Fall ist. Generell ist aber »Hauptsache es funktioniert« keine nachhaltige Strategie, wie ich es auch bereits motiviert habe.

Allerdings gibt es ein paar wenige Dinge, über die man auch geteilter Meinung sein kann, etwa die Begrenzung der Zeilenlänge auf 79 Zeichen. Bei heutigen HiDPI-Monitoren und Auflösungen jenseits von Full-HD sind sicher auch längere Zeilen von rund 120 Zeichen möglich. Aber allzu lang sollte eine Zeile auch nicht werden – vor allem, wenn man einmal zwei Versionsstände einer Datei miteinander vergleichen möchte, kann dies sonst störend sein.

Zen of PythonInteressanterweise ist in den Kommandozeileninterpreter eine Ausgabe von Stilhinweisen, auch als Zen of Python bekannt, eingebaut. Diese erhält man durch einen Aufruf von:

>>> import this

Es kommt zu folgender Ausgabe:

The Zen of Python, by Tim Peters

Beautiful is better than ugly.

Explicit is better than implicit.

Simple is better than complex.

Complex is better than complicated.

Flat is better than nested.

Sparse is better than dense.

Readability counts.

Special cases aren't special enough to break the rules.

Although practicality beats purity.

Errors should never pass silently.

Unless explicitly silenced.

In the face of ambiguity, refuse the temptation to guess.

There should be one-- and preferably only one --obvious way to do it.

Although that way may not be obvious at first unless you're Dutch.

Now is better than never.

Although never is often better than *right* now.

If the implementation is hard to explain, it's a bad idea.

If the implementation is easy to explain, it may be a good idea.

Namespaces are one honking great idea -- let’s do more of those!

ToolingWie schon erwähnt, bietet sich PyCharm als IDE an und gibt direkt im Editor verschiedene Hinweise zum Stil und zu Verbesserungsmöglichkeiten. Eine Konfiguration kann man unter Preferences-> Editor-> Code Style -> Python sowie Preferences-> Editor-> Inspections-> Python vornehmen. Insbesondere gibt es bei letzterer die Möglichkeit, PEP8 coding style violation zu aktivieren.

Alternativ oder ergänzend können Sie das Tool flake8 wie folgt installieren:

pip3 install flake8

Dieses hilft dabei, verschiedene potenzielle Probleme und Verstöße gegen PEP 8 aufzudecken, wenn Sie es wie folgt aufrufen:

flake8 <mypythonmodule>.py mydirwithmodules ...

Es gibt noch weitere Tools. Empfehlenswert für größere Projekte, wenn auch etwas aufwendiger, ist es, eine statische Sourcecode-Analyse mittels Sonar auszuführen. Dazu ist allerdings Sonar und auch ein Sonar Runner zu installieren. Dafür erhält man dann aber eine schöne Übersicht sowie eine Historisierung, sodass man sowohl positive als auch negative Trends schnell erkennen und bei Bedarf gegensteuern kann.

Weitere InformationenWeitere Informationen, wie Sie sauberes Python schreiben, finden Sie in folgenden Büchern:

»Python-Tricks – Praktische Tipps für Fortgeschrittene« von Dan Bader

[2]

»Mastering Python« von Rick van Hattern

[14]

1.5Anmerkung zu den Aufgaben

Bei der Lösung der Aufgaben ist es das Ziel, sich mit den dazu notwendigen Algorithmen und Datenstrukturen zu befassen. Python bietet eine recht umfangreiche Sammlung an Funktionalitäten, etwa zur Ermittlung von Summen und Minimum von Listen oder gar komplexeren Dingen wie der Berechnung von Permutationen.

Einige der Aufgaben lassen sich mit den vorgefertigten Standardfunktionalitäten in wenigen Zeilen lösen. Das ist jedoch nicht das Ziel, denn die Übungsaufgaben dienen dem algorithmischen Verständnis und der Erweiterung Ihrer Problemlösungsstrategien. Wenn man dies selbst ergründet und löst, lernt man viel dabei. Dinge selbst zu entwickeln, ist nur für das Training gedacht, nicht für den Praxiseinsatz: Bedenken Sie bitte, dass in realen Projekten der Standardfunktionalität von Python immer der Vorzug gegeben werden sollte und Sie nicht im Traum daran denken sollten, etwas selbst zu erfinden, wofür es schon eine vorgefertigte Lösung gibt. Deswegen weise ich oftmals in einem eigenen kurzen Abschnitt »Python-Shortcut« auf eine Lösung hin, die Python-Standardfunktionalität verwendet.

1.6Ausprobieren der Beispiele und Lösungen

Grundsätzlich verwende ich möglichst nachvollziehbare Konstrukte und keine ganz besonders ausgefallenen Syntax- oder API-Features. Vielfach können Sie die abgebildeten Sourcecode-Schnipsel einfach in den Python-Kommandozeileninterpreter kopieren und ausführen. Alternativ finden Sie alle relevanten Sourcen in dem zum Buch mitgelieferten PyCharm-Projekt. Dort lassen sich die Programme durch eine main()-Funktion starten oder durch oftmals vorhandene korrespondierende Unit Tests überprüfen.

Los geht’s: Entdeckungsreise Python 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 Unit Tests, zum Python-Kommandozeileninterpreter oder der O-Notation benötigen, bietet sich ein Blick in die Anhänge an.

IGrundlagen

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 mit / beachtet werden und mit // 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 durch den Wert 10. Seit Python 3 liefert das eine Fließkommazahl als Ergebnis. Benötigt man eine Ganzzahl, so kann man eine Typumwandlung mit

int()

, etwa

int(value / 10)

, nutzen.

n //

10 – Teilt ebenfalls durch den Wert 10. Weil der Operator

//

eine Ganzzahldivision ohne Rest ausführt, ist es damit möglich, die letzte Ziffer abzuschneiden.

Extraktion von ZiffernZur Extraktion der Ziffern einer Zahl kombinieren wir Modulo und Division so lange, wie der verbleibende Wert größer als 0 ist:

In Python gibt es noch eine Besonderheit mit der Built-in-Funktion divmod(), die als Ergebnis sowohl den Teiler als auch den Rest liefert – als Abkürzung für die häufig in Kombination aufgerufenen Operatoren. Zudem nutzen wir das Tuple Unpacking nachfolgend aus, wodurch das Ergebnis der jeweiligen Variablen zugewiesen wird:

Wir rufen diese Funktion auf, um deren Arbeitsweise zu verstehen – bitte beachten Sie, dass die Ziffern in umgekehrter Reihenfolge ausgegeben werden und Leerzeilen bei der Verarbeitung im Python-Kommandozeileninterpreter mitunter Probleme machen: In IDEs wie PyCharm ist dies dagegen problemlos möglich – ich werde Leerzeilen für die Beispiele nutzen, sofern dies klareren Sourcecode gibt.

>>> extract_digits(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:

Noch eine kleine Anmerkung zur Namensgebung: Für Schleifenvariablen sind kurze Namen wie i gebräuchlich, aber current_number wäre auch eine lesbare Alternative. Mithilfe von List Comprehension1 schreiben wir die Berechnung kürzer:

Rufen wir diese Funktion einmal auf, um deren Arbeitsweise zu verstehen und durch die erwartungskonforme Ausgabe zu bestätigen:

>>> find_proper_divisors(6)

[1, 2, 3]

>>> find_proper_divisors(24)

[1, 2, 3, 4, 6, 8, 12]

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.2 In dem Fall ist es keine Primzahl, ansonsten muss weiter geprüft werden. In Python lässt sich das folgendermaßen formulieren:

Probieren wir die Berechnung einmal aus:

Mithilfe von List Comprehension schreiben wir dies kürzer:

In beiden Fällen erhalten wir dann als korrektes Ergebnis die Primzahlen kleiner 25:

[2, 3, 5, 7, 11, 13, 17, 19, 23]

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 unmarkierte 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

In Aufgabe 4 sollen Sie das Sieb des Eratosthenes selbst implementieren. Dann können Sie Ihren Algorithmus ergänzend zu den obigen mit folgenden Werten prüfen:

Grenzwert

Resultat

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:3

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.

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.

Regeln

Die römischen Zahlen werden nach bestimmten Regeln zusammengesetzt:

I steht nur vor V und X

X steht nur vor L und C

C steht nur vor D und M

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.

2.1.2Zahlenspielereien

Nachfolgend schauen wir uns ein paar spezielle Zahlenkonstellationen an:

Vollkommene oder perfekte Zahlen

Armstrong-Zahlen n 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 entnommen.

Die Formel 100 * x + 10 * y + z ergibt sich aus der Position der Ziffern und einer textuellen Darstellung von "xyz", also

Nach dieser Vorüberlegung betrachten wir zwei Beispiele, für die die obige Formel erfüllt ist:

AbwandlungAls Abwandlung ist es auch ganz interessant, für welche Ziffern bzw. Zahlen folgende Gleichungen 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 Funktion calc(m, n), die zwei Variablen vom Typ int multipliziert, das Produkt dann halbiert und den ganzzahligen 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 Summe sowie die Anzahl 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 Funktion calc_sum_and_count_all_-numbers_div_by_2_or_7(max_exclusive). 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 Funktionen is_even(n) und is_odd(n), die prüfen, ob die übergebene Ganzzahl gerade bzw. ungerade ist.

2.2.2Aufgabe 2: Zahl als Text ()

Schreiben Sie eine Funktion number_as_text(n), die für eine gegebene positive Zahl vom Typ int 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 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:

Schreiben Sie eine Funktion calc_perfect_numbers(max_exclusive), die die vollkommenen 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 Funktion calc_primes_up_to(max_value) zur Berechnung aller Primzahlen bis zu einem vorgegebenen Maximalwert. 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 Funktion calc_checksum(input), 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 Funktion from_roman_number(roman_number), die aus einer textuell vorliegenden, gültigen römischen Zahl die korrespondierende Dezimalzahl errechnet.4

Aufgabe 7b: Dezimalzahlen→Römische Zahlen ()

Schreiben Sie eine Funktion to_roman_number(value), die eine Dezimalzahl in eine (gültige) römische Zahl in textueller Form 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 Funktion calc_armstrong_numbers() zur Berechnung aller Armstrong-Zahlen für x, y und z (jeweils < 10).

Beispiele

BonusFinden Sie eine generische Variante mit Funktionen oder 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 bzw. Zahlen unterschiedlicher Werte. Schreiben Sie eine Funktion calc_max_possible_change(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 Funktion calc_friends(max_exclusive) 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 Funktion calc_prime_factors(value), die eine Liste mit Primzahlen liefert, deren Multiplikation die gewünschte 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]

2.3Lösungen

2.3.1Lösung 1: Grundrechenarten ()

Lösung 1a: Grundrechenarten ()

Schreiben Sie eine Funktion calc(m, n), die zwei Variablen vom Typ int multipliziert, das Produkt dann halbiert und den ganzzahligen 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.

AlgorithmusDie Implementierung folgt einfach der mathematischen Operationen:

def calc(m, n):

return m * n // 2 % 7

Statt des speziellen Operators // kann man auch eine Umwandlung des Ergebnisses der einfachen Division in eine Ganzzahl durch einen Aufruf von int() vornehmen:

def calc_v2(m, n):

return int(m * n / 2) % 7