Hinweis: Die gezeigten Beispiele sind mit Hinblick auf das Lernziel bewusst gestaltet. Sie nutzen mit Absicht möglichst wenige fertige Funktionen aus der Bibliothek von Python, selbst wenn diese schneller oder kürzer wären. Sie sollen hier üben, ein Problem durch eine Kontrollflussstruktur aus möglichst einfachen Anweisungen algorithmisch eigenständig zu lösen.
Aufgabe: Schreiben Sie ein Programm, das zwei Ganzzahlen multipliziert.¶
Nutzen Sie eine while-Schleife mit einer Abbruchbedingung, nicht den vorhandenen Operator *.
Aufgabe¶
faktor_1 = 5
faktor_2 = 7
ergebnis = 0
zaehler = 0
while # Bedingung :
# Anweisungen
print(ergebnis)
faktor_1 = 5
faktor_2 = 7
ergebnis = 0
zaehler = 0
while zaehler < faktor_2 :
ergebnis = ergebnis + faktor_1
zaehler = zaehler + 1
print(ergebnis)
Ohne Hilfsvariable (faktor_2 wird direkt vermindert)¶
faktor_1 = 5
faktor_2 = 7
ergebnis = 0
while faktor_2 > 0:
ergebnis = ergebnis + faktor_1
faktor_2 = faktor_2 - 1
print(ergebnis)
Aufgabe: Schreiben Sie ein Programm, das eine Ganzzahl durch eine andere Ganzzahl ganzzahlig dividiert.¶
Verwenden Sie dabei nicht die vorhandenen Operatoren // oder /, sondern nutzen Sie eine while-Schleife mit einer Abbruchbedingung.
Aufgabe¶
# Dividend : Divisor = Quotient
dividend = 57
divisor = 6
quotient = 0
rest = 0
while # Bedingung hier einfügen :
# Anweisungen hier einfügen
print(quotient, rest)
Musterlösung¶
Mit Hilfsvariable rest¶
# Dividend : Divisor = Quotient
dividend = 57
divisor = 6
quotient = 0
rest = dividend
while rest >= divisor:
quotient = quotient + 1
rest = rest - divisor
print(quotient, rest),
Ohne Hilfsvariable (dividend wird direkt vermindert)¶
# Variante ohne Hilfsvariable
# Dividend : Divisor = Quotient
dividend = 57
divisor = 6
quotient = 0
while dividend >= divisor:
quotient = quotient + 1
dividend = dividend - divisor
print(quotient, dividend)
Aufgabe: Berechnen Sie die Fakultät x!.¶
Die Fakultät $x!$ ist das Produkt aller ganzen Zahlen von $x >= zahl > 0$.
Beispiel:
3! = 3 * 2 * 1 = 6.
Aufgabe¶
x = 8
ergebnis = 1
while # Bedingung hier einfügen :
# Anweisungen hier einfügen
print(ergebnis)
Musterlösung¶
x = 8
ergebnis = 1
hilfsvariable = x
while hilfsvariable > 1:
ergebnis = ergebnis * hilfsvariable
hilfsvariable = hilfsvariable - 1
print('Die Fakultät von ', x, ' ist ', ergebnis)
Aufgabe: Wandeln Sie eine beliebige Binärzahl in eine Dezimalzahl um.¶
Verwenden Sie dabei keine von Python für diesen Zweck explizit vorhandenen Funktionen!
Aufgabe¶
binaerzahl = '01110101'
# Hier einfügen
Musterlösung¶
binaerzahl = '01110101'
dezimalzahl = 0
stellenwert = 1
# Wir müssen an der letzten Stelle anfangen
letzte_stelle = len(binaerzahl) - 1
for position in range(letzte_stelle, 0, -1):
if binaerzahl[position] == '1':
dezimalzahl = dezimalzahl + stellenwert
stellenwert = stellenwert * 2
print(binaerzahl, ' entspricht ', dezimalzahl)
print('Kontrolle: ', int(binaerzahl, 2))
Es wäre auch möglich
dezimalzahl = dezimalzahl + int(binaerzahl[position]) * stellenwert zu verwenden.
Tipp: Mit binaerzahl[::-1] oder reversed(binaerzahl) können Sie die Zeichenkette umdrehen. Dann läßt sich die Umwandlung eleganter formulieren:
binaerzahl = '01110101'
dezimalzahl = 0
stellenwert = 1
# Es ginge auch
# for digit in binaerzahl[::-1]:
for digit in reversed(binaerzahl):
dezimalzahl = dezimalzahl + int(digit) * stellenwert
stellenwert = stellenwert * 2
print(dezimalzahl)
Noch eleganter: Die Funktion enumerate() liefert bei jedem Durchgang den Index und den Wert zurück. Dies ist nicht klausurrelevant.
binaerzahl = '01110101'
dezimalzahl = 0
for position, zeichen in enumerate(reversed(binaerzahl)):
dezimalzahl += int(zeichen) * 2**position
print(dezimalzahl)
# Python-Profi
# int() erlaubt die Angabe der Basis als Parameter (2 für Binärzahlen)
print(int(binaerzahl, 2))
Aufgabe: Berechnen Sie die Quersumme einer beliebigen Ganzzahl.¶
Hinweis: Denken Sie daran, dass man eine Zahl mit str(<zahl>) in eine Zeichenkette umwandeln und mit int(<ziffer>) den Wert einer Zahl oder Ziffer aus einem String erhalten kann.
Aufgabe¶
zahl = 124723847273489
# Hier einfügen
Musterlösung¶
zahl = 124723847273489
zahl_als_zeichenkette = str(zahl)
quersumme = 0
for stelle in zahl_als_zeichenkette:
quersumme = quersumme + int(stelle)
print(quersumme)
Aufgabe: Suche in einer Liste¶
Aufgabe¶
Schreiben Sie ein Programm, das in einer Liste nach einem gegebenen Wert sucht. Wenn der Wert gefunden wird, soll seine Position in der Liste ausgegeben werden.
Nutzen Sie NICHT die von Python bereitgestellte Suchfunktion, sondern entwickeln Sie eine eigene Lösung auf Basis einer Schleife.
my_liste = ['Hepp', 'Meier', 'Mueller', 'Meier']
gesuchter_wert = 'Meier'
# Hier einfügen
Musterlösung¶
positionszaehler = 0
for element in my_liste:
if element == gesuchter_wert:
print(gesuchter_wert, 'gefunden an Position', positionszaehler)
positionszaehler = positionszaehler + 1
Aufgabe: Berechnen Sie die Prüfziffer für eine GTIN-13. (anspruchsvoll)¶
Die 13-stellige Ziffernfolge unter dem Barcode eines Konsumgüterproduktes besteht aus zwölf Nutzziffern und einer Prüfziffer, die Eingabe- und Lesefehler erkennen hilft.
Diese Prüfziffer wird aus den Nutzziffern wie folgt berechnet:
- Zunächst wird jede Stelle von links beginnend abwechselnd mit 1 und mit 3 multipliziert und zu einer Summe addiert.
- Dies nennt man eine gewichtete Quersumme, weil die Position einer Ziffer für die Quersumme relevant ist.
- Einfache Zahlendreher führen zu einer anderen Quersumme.
- Anschließend wird die Differenz zur nächstgrößeren durch zehn teilbaren Zahl ermittelt. Dies ergibt die Prüfziffer, die an 13ter Stelle eingefügt wird.
Beispiel:
$401500073853 => 1 * 4 + 3 * 0 + 1 * 1 + 3 * 5 + 1 * 0 + 3 * 0 + 1 * 0 + 3 * 7 + 1 * 3 + 3 * 8 + 1 * 5 + 3 * 3 = 82$
$ 90 - 82 = 8$
Die Prüfziffer ist also 8.
Aufgabe¶
gtin_13 = '401500073853'
# Hier einfügen
Musterlösung¶
checksum = 0
gewicht = 1
for ziffer in gtin_13:
checksum += int(ziffer) * gewicht
# Die Gewichtung könnte eleganter alterniert werden,
# aber das wäre unnötig verwirrend.
if gewicht == 1:
gewicht = 3
else:
gewicht = 1
naechstgroessere_zahl = (checksum // 10 + 1) * 10
checksum = naechstgroessere_zahl - checksum
# Eleganter, aber komplizierter:
# checksum = (10 - checksum % 10) % 10
print(checksum)
Aufgabe: Wandeln Sie eine Dezimalzahl in eine Binärzahl um.¶
Verwenden Sie dabei keine von Python für diesen Zweck explizit vorhandenen Funktionen!
Aufgabe¶
Gegeben sei eine Dezimalzahl zwischen 0 und 255. Sie soll in eine Binärzahl umgewandelt werden.
Tipp: Wir wissen, dass das höchste Bit einer achtstelligen Binärzahl die Wertigkeit 128 hat, das entspricht $2^7$. Wir können also nacheinander die Wertigkeiten aller Stellen von der größten zur kleinsten nehmen und prüfen, ob die Zahl größer oder gleich diesem Wert ist. In diesem Fall wird das Bit gesetzt und der Wert wird abgezogen.
dezimalzahl = int(154)
# Hier einfügen
Musterlösung¶
# Vereinfacht
eingabewert = dezimalzahl
ausgabewert = ''
wertigkeiten = [128, 64, 32, 16, 8, 4, 2, 1]
for bit_wert in wertigkeiten:
if eingabewert >= bit_wert:
ausgabewert = ausgabewert + "1"
eingabewert = eingabewert - bit_wert
else:
ausgabewert = ausgabewert + "0"
print('Die Dezimalzahl', dezimalzahl, 'entspricht der Binärzahl', ausgabewert)
Musterlösung, eleganter¶
Eleganter ist es, die Zweierpotenzen, beginnend mit der größten, die in Frage kommt, abzuarbeiten.
eingabewert = dezimalzahl
ausgabewert = ''
for bit in range(7, -1, -1): # 0 soll enthalten sein, daher nicht range(7, 0, -1)
if eingabewert >= 2**bit:
ausgabewert = ausgabewert + "1"
eingabewert = eingabewert - 2**bit
else:
ausgabewert = ausgabewert + "0"
print('Die Dezimalzahl', dezimalzahl, 'entspricht der Binärzahl', ausgabewert)
Aufgabe: Erzeugen Sie alle möglichen Passwortkombinationen.¶
Nehmen wir an, die meisten Nutzer verwenden eine Kombination aus dem Vornamen einer Person und einer Jahreszahl. Schreiben Sie ein Programm, dass alle möglichen Kombinationen aus den Namen
vornamen = ['Peter', 'Petra', 'Paul', 'Paula']und den Jahreszahlen von 2017 bis 2019 erzeugt.
Aufgabe¶
vornamen = ['Peter', 'Petra', 'Paul', 'Paula']
passwoerter = []
# Hier einfügen
Musterlösung¶
passwoerter = []
for name in vornamen:
for jahr in range(2017, 2020):
passwoerter.append(name + str(jahr))
print(passwoerter)
Aufgabe: Berechnen Sie die jährliche lineare Abschreibung und den jeweiligen Buchwert eines Investitionsgutes.¶
Aufgabe¶
Bei der linearen Abschreibung wird der Restwert am Ende jeder Periode um einen festen Prozentsatz der Anschaffungskosten vermindert.
abschreibungsdauer = 10 # Jahre
abschreibungssatz = 0.1 # 10 %
anschaffungskosten = 23450 # Euro
# Hier einfügen
Musterlösung¶
Hinweis: Zur lesbareren Formattierung nutzen wir hier f-Strings, die in Einheit 1 im Abschnitt 3.12.1.5 behandelt werden.
restwert = anschaffungskosten
abschreibung = anschaffungskosten * abschreibungssatz
for periode in range(1, abschreibungsdauer + 1):
restwert = restwert - abschreibung
print(f'Restwert am Ende der Periode {periode:2d}: {restwert:8.2f}')
Berechnen Sie die jährliche degressive Abschreibung und den jeweiligen Buchwert eines Investitionsgutes.¶
Aufgabe¶
Bei der degressiven Abschreibung wird der Restwert am Ende jeder Periode um einen festen Prozentsatz des Restwertes vermindert.
abschreibungsdauer = 10 # Jahre
abschreibungssatz = 0.20 # 20 %
anschaffungskosten = 23450 # Euro
# Hier einfügen
Musterlösung¶
restwert = anschaffungskosten
for periode in range(1, abschreibungsdauer + 1):
abschreibung = restwert * abschreibungssatz
restwert = restwert - abschreibung
print(f'Restwert am Ende der Periode {periode:2d}: {restwert:8.2f}')
Aufgabe: Wechselgeld¶
Schreiben Sie ein Python-Programm, das einen Rechnungsbetrag und einen Zahlbetrag vom Benutzer erfragt und berechnen Sie dann die kleinste Wechselgeldkombination (auf Basis der Stückelung im Euro-Raum: 1, 2, 5, 10, 20, 50 Cent, 1, 2, 5, 10, 20, 50, 100, 200 Euro).
Aufgabe¶
muenzen_und_scheine = [1, 2, 5, 10, 20, 50, 100, 200,
500, 1000, 2000, 5000, 10000, 20000]
# Wir benötigen die Werte der Zahlungsmittel in absteigender Reihenfolge
muenzen_und_scheine.sort(reverse=True)
rechnungsbetrag = float(input('Rechnungsbetrag in Euro? '))
zahlbetrag = float(input('Gezahlter Betrag? '))
# Hier einfügen
Musterlösung¶
wechselgeld_betrag = zahlbetrag - rechnungsbetrag
wechselgeld_betrag = wechselgeld_betrag * 100 # in Cent
for item in muenzen_und_scheine:
if wechselgeld_betrag >= item:
anzahl = int(wechselgeld_betrag // item)
print(anzahl, 'x', item)
wechselgeld_betrag = wechselgeld_betrag - item * anzahl
# Eleganter über Divisionsrest:
# wechselgeld_betrag = wechselgeld_betrag % item
else:
print('0 x', item)
Aufgabe: Wechselgeld mit Münzbestand¶
Erweitern Sie das Programm aus der vorherigen Aufgabe so, dass jeweils berücksichtigt wird, ob die benötigten Münzen und Scheine in der entsprechenden Menge vorhanden sind. Sonst müssen diese durch die nächstkleinere Größe ersetzt werden.
Aufgabe¶
muenzen_und_scheine = [1, 2, 5, 10, 20, 50, 100, 200,
500, 1000, 2000, 5000, 10000, 20000]
muenzen_und_scheine.sort(reverse=True)
bestand = {'1': 100, '2': 100, '5': 2, '10': 20, '20': 5, '50': 3,
'100': 10, '200': 2,
'500': 1, '1000': 5, '2000': 4, '5000': 2, '10000': 1, '20000': 0}
rechnungsbetrag = float(input('Rechnungsbetrag in Euro? '))
zahlbetrag = float(input('Gezahlter Betrag? '))
# Hier einfügen
Musterlösung¶
wechselgeld_betrag = zahlbetrag - rechnungsbetrag
wechselgeld_betrag = wechselgeld_betrag * 100 # in Cent
for item in muenzen_und_scheine:
if wechselgeld_betrag >= item:
anzahl = int(wechselgeld_betrag // item)
if bestand[str(item)] >= anzahl:
bestand[str(item)] = bestand[str(item)] - anzahl
else:
anzahl = bestand[str(item)]
bestand[str(item)] = 0
print(anzahl, 'x', item)
wechselgeld_betrag = wechselgeld_betrag - item * anzahl
else:
print('0 x', item)
Aufgabe: Taxikosten¶
Nehmen Sie an, der Preis für ein Taxi bestehe aus
- einem Grundpreis von 2,50 Euro und
- einem kilometerabhängigen Preis von 4 Euro pro Kilometer.
Schreiben Sie ein Python-Programm, das eine Preistabelle für alle Strecken zwischen 1 und 10 km ausgibt.
Aufgabe: Preistabelle¶
grundpreis = 2.50 # Euro
preis_pro_km = 4.0 # Euro
# Hier einfügen
Musterlösung¶
for strecke in range(1, 11):
print(strecke, 'km kosten', grundpreis + strecke * preis_pro_km, 'Euro.')
Aufgabe: Erweiterung: Rabatt ab 10 km¶
Erweitern Sie das Programm derart, dass der kilometerabhängige Preis ab dem fünften Kilometer auf 3 Euro pro Kilometer sinkt.
grundpreis = 2.50 # Euro
preis_pro_km = 4.0 # Euro
preis_pro_km_reduziert = 3.0 # Euro
# Hier einfügen
Musterlösung¶
for strecke in range(1, 11):
if strecke < 5:
print(strecke, 'km kosten', grundpreis + strecke * preis_pro_km, 'Euro.')
else:
print(strecke, 'km kosten',
grundpreis + preis_pro_km * 4 + (strecke - 4) * preis_pro_km_reduziert,
'Euro.')
Erweiterung: Benutzereingabe und Aufrunden auf Abrechnungseinheiten¶
Verändern Sie das Programm so, dass die Länge der Fahrt vom Programmbenutzer erfragt wird und der kilometerabhängige Preis nur in Einheiten von 500 m – mit Aufrunden – berechnet wird (Beispiel: Bei 3,25 km werden 3,5 km berechnet).
# Hier einfügen
Aufgabe: Telefongebühren¶
Schreiben Sie ein Programm, das aus folgenden Verbindungsdaten eine Telefonrechnung erstellt:
| Zielrufnummer | Verbindungsdauer (sec) |
|---|---|
| +49896004-0 | 30 |
| +4969123456 | 120 |
| +43152000 | 50 |
| +352989104-7 | 20 |
| +49896004-0 | 68 |
Alle Gespräche im Ortsbereich (beginnend mit "+4989") kosten 0,01 Euro pro Sekunde. Alle Gespräche innerhalb Deutschlands (beginnend mit "+49") kosten 0,04 Euro pro Sekunde. Alle übrigen Gespräche sind internationale Verbindungen und kosten 0,12 Euro pro Sekunde
Aufgabe¶
verbindungdaten = [('+49896004-0', 30),
('+4969123456', 120),
('+43152000', 50),
('+352989104-7', 20),
('+49896004-0', 68)]
preis_ort = 0.01 # Euro pro Sekunde
preis_inland = 0.04 # Euro pro Sekunde
preis_ausland = 0.12 # Euro pro Sekunde
# Hier einfügen
Musterlösung¶
rechnungssumme = 0
for item in verbindungdaten:
nummer, dauer = item
if nummer.startswith('+4989'):
betrag = dauer * preis_ort
elif nummer.startswith('+49'):
betrag = dauer * preis_inland
else:
betrag = dauer * preis_ausland
rechnungssumme = rechnungssumme + betrag
print('Rufnummer: ', nummer, ' Dauer:', dauer, 'Betrag:', betrag)
print('Gesamtbetrag:', rechnungssumme)
Aufgabe: Prüfen Sie, ob eine Zeichenkette ein Palindrom ist.¶
Ein Palindrom ist ein Wort, das vorwärts und rückwärts gelesen dieselbe Zeichenfolge hat.
Beispiele:
- ABBA ist ein Palindrom.
- OTTO ist ein Palindrom.
- LAGER ist kein Palindrom.
Aufgabe¶
Schreiben Sie ein Programm, das für eine gegebene Zeichenkette prüft, ob sie ein Palindrom ist.
text = 'FRANZ'
# Hier einfügen
Musterlösung¶
# Leichter verständliche Lösung
text_gespiegelt = ''
for char in text:
text_gespiegelt = char + text_gespiegelt
if text_gespiegelt == text:
print(f'{text} ist ein Palindrom.')
else:
print(f'{text} ist kein Palindrom, {text} != {text_gespiegelt}')
Elegantere Lösung:
text = 'ABBA'
# text[::-1] liefert eine Zeichenkette in umgekehrter Reihenfolge zurück
if text == text[::-1]:
print('Palindrom')
else:
print('Kein Palidrom')
Aufgabe: Einfache Verschlüsselung (Zeichensubstitution)¶
Schreiben Sie ein Programm, das eine beliebige Folge von Ziffern, die als Zeichenkette übergeben wird, in eine verschlüsselte Form übersetzt, indem jede Ziffer gemäß der folgenden Tabelle ersetzt wird:
| Ziffer | Verschlüsselte Ziffer |
|---|---|
| 0 | 4 |
| 1 | 9 |
| 2 | 1 |
| 3 | 0 |
| 4 | 7 |
| 5 | 8 |
| 6 | 2 |
| 7 | 5 |
| 8 | 6 |
| 9 | 3 |
Aufgabe¶
# schluessel ist zufällige Liste aller Ziffern
schluessel = [4, 9, 1, 0, 7, 8, 2, 5, 6, 3]
Musterlösung¶
# Verschlüsselung
meine_pin = '20191106'
chiffrat = ''
for ziffer in meine_pin:
neue_ziffer = schluessel[int(ziffer)]
chiffrat = chiffrat + str(neue_ziffer)
print('Verschlüsselte Form:', chiffrat)
Enschlüsselung:
zahl_dekodiert = ''
for ziffer in chiffrat:
urspruengliche_ziffer = schluessel.index(int(ziffer))
zahl_dekodiert = zahl_dekodiert + str(urspruengliche_ziffer)
print('Dekodiert:', zahl_dekodiert)
Aufgabe: Analyse der Buchstabenhäufigkeit¶
Zählen Sie die Häufigkeit der einzelnen Buchstaben im folgenden Text:
Im Bewußtsein seiner Verantwortung vor Gott und den Menschen, von dem Willen beseelt, als gleichberechtigtes Glied in einem vereinten Europa dem Frieden der Welt zu dienen, hat sich das Deutsche Volk kraft seiner verfassungsgebenden Gewalt dieses Grundgesetz gegeben. Die Deutschen in den Ländern Baden-Württemberg, Bayern, Berlin, Brandenburg, Bremen, Hamburg, Hessen, Mecklenburg-Vorpommern, Niedersachsen, Nordrhein-Westfalen, Rheinland-Pfalz, Saarland, Sachsen, Sachsen-Anhalt, Schleswig-Holstein und Thüringen haben in freier Selbstbestimmung die Einheit und Freiheit Deutschlands vollendet. Damit gilt dieses Grundgesetz für das gesamte Deutsche Volk.
Tipp: Nutzen Sie ein Dictionary, um die Buchstaben und ihre Häufigkeit zu speichern. Dabei sollte der Buchstabe der Schlüssel für einen Eintrag sein.
Aufgabe¶
text = """Im Bewußtsein seiner Verantwortung vor Gott und den Menschen,
von dem Willen beseelt, als gleichberechtigtes Glied in einem vereinten Europa
dem Frieden der Welt zu dienen, hat sich das Deutsche Volk kraft seiner
verfassungsgebenden Gewalt dieses Grundgesetz gegeben.
Die Deutschen in den Ländern Baden-Württemberg, Bayern, Berlin, Brandenburg,
Bremen, Hamburg, Hessen, Mecklenburg-Vorpommern, Niedersachsen, Nordrhein-Westfalen,
Rheinland-Pfalz, Saarland, Sachsen, Sachsen-Anhalt, Schleswig-Holstein und Thüringen
haben in freier Selbstbestimmung die Einheit und Freiheit Deutschlands vollendet.
Damit gilt dieses Grundgesetz für das gesamte Deutsche Volk."""
text = text.upper()
# Hier einfügen
Musterlösung¶
haeufigkeiten = {}
for char in text:
# Wir schließen Sonderzeichen und das Leerzeichen aus
# ord(<zeichen>) liefert den ASCII-Code eines Zeichens
# Das ist nur eine Verfeinerung
if ord(char) > 32:
haeufigkeiten[char] = haeufigkeiten.get(char, 0) + 1
print(haeufigkeiten)
Bonus: Visualisierung der Buchstabenhäufigkeit¶
Bitte ignorieren Sie den Programmcode, er ist für diese Vorlesung zu kompliziert.
import matplotlib.pylab as plt
data = sorted(haeufigkeiten.items(),
key=lambda freq: freq[1],
reverse=True)
x, y = zip(*data) # unpack list
plt.bar(x, y)
plt.show()
Aufgabe: Binäre Suche (anspruchsvoll)¶
Die binäre Suche ist ein sehr effizienter Algorithmus, um in einer sortierten Liste von Objekten zu suchen. Dabei wird zunächst in der Mitte der Liste geprüft, ob der gesuchte Eintrag genau dort, unterhalb oder oberhalb liegt.
Anschließend wird die Liste halbiert und nur noch in der relevanten Teilliste weiter gesucht. Dies wird wiederholt, bis das Element gefunden wurde oder die Liste erfolglos durchsucht wurde.
Für Details lesen bitte Sie den Wikipedia-Artikel zur binären Suche.
Aufgabe¶
daten = [39, 26, 78, 88, 49, 93, 23, 83, 12, 5, 34, 29, 44, 40, 77]
daten.sort()
# Wir müssen mit einer zweiten Variablen arbeiten, sonst werden die Eingangsdaten
# bei der Verarbeitung ggfls. verändert.
liste = daten
# Hier einfügen
Musterlösung¶
gesuchter_wert = 39
position = 0
while len(liste) > 0:
suchposition = len(liste) // 2
if liste[suchposition] == gesuchter_wert:
print('Wert gefunden, Position: ', position + suchposition)
break
elif liste[suchposition] < gesuchter_wert:
position += suchposition
liste = liste[suchposition:]
else:
liste = liste[:suchposition]
if len(liste) == 1 and liste[0] != gesuchter_wert:
print('Wert nicht gefunden.')
break
Aufgabe: Traveling Salesperson Problem (anspruchsvoll)¶
Das Problem des Handlungsreisenden ist eines bekanntesten Probleme der Logistik. Ziel ist es, aus einer Liste von Orten und einer Matrix der Entfernungen die kürzeste Route zu finden, die alle Orte genau einmal besucht und zum Ausgangsort zurückkehrt.
Die optimale Lösung ist nur mit hohem Rechenaufwand zu finden, wenn die Anzahl der Orte wächst. Siehe auch Peter Norvig: The Traveling Salesperson Problem.
In der Praxis greift man daher auf Heuristiken zu, wie z.B. den Nearest-Neighbor-Algorithmus. Hierbei wird einfach von einem Startknoten stets der am nächsten gelegene Ort angesteuert. Dies führt stets zu einer gültigen Lösung, die aber weit vom Optimum entfernt sein kann kann.
Gegeben sei folgende Entfernungsmatrix:
| Bielefeld | Frankfurt | München | Karlsruhe | |
|---|---|---|---|---|
| Bielefeld | 0 | 400 | 700 | 600 |
| Frankfurt | 400 | 0 | 400 | 300 |
| München | 700 | 400 | 0 | 350 |
| Karlsruhe | 600 | 400 | 350 | 0 |
Vollständige Lösung ("brute force")¶
Die Erzeugung aller möglichen Permutationen (Kombinationen) ist nicht ganz trivial, daher verzichten wir hier darauf. Es gibt aber in Python eine fertige Funktion, um alle Kombinationen aus einer Liste zu erzeugen:
staedte = ['Bielefeld', 'Frankfurt', 'München', 'Karlsruhe']
startort = staedte[0]
from itertools import permutations
routen = permutations(staedte[1:])
rundtouren = []
for route in routen:
rundtour = (startort,) + route + (startort,)
rundtouren.append(rundtour)
print(rundtouren)
Nun können Sie die Länge dieser Touren berechnen.
# Dictionaries mit Entfernungen
bielefeld = {'Bielefeld': 0, 'Frankfurt': 400, 'München': 700, 'Karlsruhe': 600}
frankfurt = {'Bielefeld': 400, 'Frankfurt': 0, 'München': 400, 'Karlsruhe': 300}
muenchen = {'Bielefeld': 700, 'Frankfurt': 400, 'München': 0, 'Karlsruhe': 350}
karlsruhe = {'Bielefeld': 600, 'Frankfurt': 400, 'München': 350, 'Karlsruhe': 0}
# Dictionary, das für einen Städtenamen das passende Dictionary speichert
entfernungen = {'Bielefeld': bielefeld,
'Frankfurt': frankfurt,
'München': muenchen,
'Karlsruhe': karlsruhe}
for route in rundtouren:
laenge = 0
restroute = route
while len(restroute) > 1:
# Wie weit ist es vom aktuellen Ort zum nächsten?
aktueller_ort = restroute[0]
naechster_ort = restroute[1]
laenge += entfernungen[aktueller_ort][naechster_ort]
restroute = restroute[1:]
print(route, "->", laenge)
Nearest-Neighbor-Verfahren¶
Beim Nearest-Neigbor-Algorithmus wird einfach von jedem Ort zum nächstgelegenen gefahren. Dies kann allerdings zu Routen führen, die weit entfernt vom Optimum liegen, weil die Strecke der letzten Rückfahrt nicht für die Entscheidung berücksichtigt wird.
startort = staedte[0]
tour = [startort]
ziele = staedte[1:]
while len(ziele) > 0:
aktueller_ort = tour[-1] # letztes Element
minimum = float('inf')
for ziel in ziele:
entfernung = entfernungen[aktueller_ort][ziel]
if entfernung < minimum:
nearest_neighbor = ziel
minimum = entfernung
# Am Ende enthält nearest_neighbor den nächsten Ort und
# das Minimum die Entfernung dorthin.
tour.append(nearest_neighbor)
ziele.remove(nearest_neighbor)
print(tour)
Vorbereitende Übung für Machine Learning (nicht klausurrelevant)¶
Die folgenden Aspekte sind wichtig, um die Idee maschineller Lernverfahren zu verstehen und anzuwenden. Dies ist nicht Gegenstand der Klausur, wird aber hier der Vollständigkeit halber beschrieben.
Für eine gute Einführung, siehe Wikipedia: Machine Learning (engl.).
Methode der kleinsten Quadrate¶
Wikipedia: Methode der kleinsten Quadrate Wikipedia: Lineare Einfachregression
import random
import matplotlib.pylab as plt
def funktion(wert):
ergebnis = 3 * wert**0.5 + 6
return ergebnis
def funktion_2(wert):
ergebnis = 2.4 * wert**0.75 + 7
return ergebnis
daten = [(i, round(funktion(i) + random.uniform(-2.0, 2.2), 2)) for i in range(10)]
funktion_plot = [(i, funktion(i)) for i in range(10)]
alternative = [(i, funktion_2(i)) for i in range(10)]
plt.plot(*zip(*daten), 'ro')
plt.plot(*zip(*funktion_plot), 'b')
plt.plot(*zip(*alternative), 'g--')
plt.show
summe = 0
summe_2 = 0
for value in daten:
x, y = value
prediction = funktion(x)
delta = prediction - y
fehlerquadrat = delta**2
summe += fehlerquadrat
prediction_2 = funktion_2(x)
delta_2 = prediction_2 - y
fehlerquadrat_2 = delta_2**2
summe_2 += fehlerquadrat_2
print(f'Wert: {value[1]} Vorhersage 1: {prediction:5.2f} [{delta:5.2f}], Vorhersage 2: {prediction_2:5.2f} [{delta_2:5.2f}]')
print(f'{summe:5.2f}, {summe_2:5.2f}')