Im letzten Kapitel haben wir uns mit Super- und Quanten-Computer befasst:
- Von Super-Computern wissen wir, dass diese sehr viel Parallelisieren. Können wir das auch auf unserem eigenen Computer? Bringt das etwas?
- Bei den Quantencomputern haben wir gesehen, dass diese eine Gefahr für die auf dem Faktorisierungs-Problem basierenden asymmetrischen Verschlüsselungen darstellen
Faktorisieren
Wir möchten eine Zahl faktorisieren. Wie können wir vorgehen? Wie können wir das Vorgehen optimieren?
Aufgabe
Schreibe eine Python-Funktion (ein Unterprogramm), das eine Zahl in ihre Primfaktoren zerlegt:
- Die Funktion erhält als Argument eine Zahl
- Die Zahl liefert die Primfaktoren als Liste zurück
Brute-Force
Wir testen alle möglichen Faktoren aus.
Lösung
def factorize(n):
zahl = n
factors = []
i = 2
while i <= n:
if zahl % i == 0:
factors.append(i)
zahl = zahl // i
else:
i = i + 1
return factors
Zusatzaufgabe
Programmiere eine Funktion, welche Primfaktorenzerlegungen überprüft:
- Die Funktion erhält eine Zahl und ihre Primfaktoren in Form einer Liste – also zwei Argumente
- Sie liefert
True
oderFalse
zurück, je nachdem ob die Zerlegung korrekt ist oder nicht.
Optimieren
- nur die 2 und ungerade Zahlen testen
- nur bis zur Hälfte der Zahl testen (aber Achtung Primzahl)
Aufgabe
Kopiere deine Funktion und benenne Sie neu. Optimiere nun die neue Funktion mit den oben beschriebenen Ideen (oder eigenen).
Du kannst nun die beiden Funktionen vergleichen. Verwende dazu die unten beschriebene Zeitmessung.
Lösung: optimiert
def factorize(n):
zahl = n
factors = []
i = 2
while zahl % i == 0:
factors.append(i)
zahl = zahl // i
i = 3
while i < n//2+1:
if zahl % i == 0:
factors.append(i)
zahl = zahl // i
else:
i = i + 2
if len(factors) == 0:
factors.append(zahl)
return factors
Lösung: rekursiv
def factorize(n):
if n == 1:
return []
for i in range(2,n+1):
if n%i == 0:
return [i] + factorize(n//i)
Zeit messen
Mit der Funktion time
aus dem gleichnamigen Modul, können wir die aktuelle Systemzeit in Sekunden abfragen. Wenn wir das 2x machen und die Differenz berechnen, dann haben wir die dazwischen verstrichene Zeit in Sekunden:
from time import time
start = time()
# mach etwas
end = time()
print(end - start)
OOP
Lies dich nochmals durch die Seite Grundprinzipien von OOP im Skript. Anschliessend kannst du die Aufgabe lösen:
Aufgabe
Erstelle eine Klasse Zeit
. Die Klasse soll eine Uhrzeit abspeichern und mit dieser arbeiten können. Du kannst die untenstehende Vorlage nehmen:
class Zeit:
def __init__(self, h, m):
self.h = h
self.m = m
def add(self, other):
pass
def __str__(self):
return str(self.h) + ":" + str(self.m)
mittag = Zeit(12,0)
morgen = Zeit(7,30)
mittag.add(morgen)
print(mittag)
Aufgabe: add
implementiere die Funktion add
: Passe aber auf wenn du über die Grenzen kommst (45 min + 45 min)
Aufgabe: sub
Baue auch die Subtraktion von Zeiten ein!
Aufgabe: print
Verschönere die Ausgabe von print
: Die Minuten-Angabe soll immer zweistellig – wenn nötig mit einer führenden Null – sein.
Zusatzaufgabe: Operatoren überladen
Mit Python kann man auch die Operatoren überladen. Das heisst, wir könnten Objekte unserer Zeit-Klasse mit einem +
zusammenzählen:
mittag = Zeit(12,0)
morgen = Zeit(7,30)
abend = mittag + morgen
print(abend)
Du kannst hier nachlesen wie das funktioniert, aber Achtung: es wird ein neues Objekt zurückgeliefert: c = a + b
https://www.geeksforgeeks.org/operator-overloading-in-python/
- Versuche deine Funktionen
add
undsub
entsprechend anzupassen. - implementiere Funktionen für Vergleiche (
< > <= >= == !=
) von Uhrzeiten.
Listen und Schleifen
Du kannst dich hier über Listen und Schleifen informieren:
Aufgaben
Versuche die folgenden Aufgaben zu lösen. Es handelt sich um eine Auswahl von der Seite
👉 https://www.w3resource.com/python-exercises/string/
Aufgabe 2
Write a Python program to count the number of characters (character frequency) in a string.
- Sample String
google.com
- Expected Result
{'g': 2, 'o': 3, 'l': 1, 'e': 1, '.': 1, 'c': 1, 'm': 1}
Tipp: Dictionary
Das erwartete Resultat ist ein sogenannter Dictionary. Dieser Dateityp ist ähnlich wie eine Liste, hat aber als Index einen String (und keine Zahl). Dadurch kann man keine Elemente anhängen (wie bei einer Liste) – jedes Element benötigt einen festen Index worüber der Zugriff geschieht:
meinDict = {}
meinDict["hello"] = 2
meinDict["goodbye"] = meinDict["hello"] * "Schüss"
print(meinDict)
liefert {'hello': 2, 'goodbye': 'SchüssSchüss'}
Lösung
def character_frequency(word):
count = {}
for character in word:
if character in count:
count[character] = count[character] + 1
else:
count[character] = 1
return count
print(character_frequency("google.com"))
Aufgabe 14
Write a Python program that accepts a comma-separated sequence of words as input and prints the distinct words in sorted form (alphanumerically).
- Sample Words
red, white, black, green, red
- Expected Result
black, green, red, white
Lösung
def distinct_sorted(inputStr):
result = []
for word in inputStr.split(","):
stripped_word = word.strip()
if stripped_word not in result:
result.append(stripped_word)
result.sort()
return result
print(distinct_sorted("red, white, black, green, red"))
Aufgabe 39
Write a Python program to reverse a string.
Lösung
def reverse(word):
result = ""
for character in word:
result = character + result
return result
print(reverse("sparmark"))
Aufgabe 40
Write a Python program to reverse words in a string.
Lösung
def reverseWords(sentence):
result = ""
for word in sentence.split():
result = word + " " + result
return result
print(reverseWords("Lieber nicht morgen"))
Aufgabe 42
Write a Python program to count repeated characters in a string.
- Sample string
thequickbrownfoxjumpsoverthelazydog
Expected output:
o 4
e 3
u 2
h 2
r 2
t 2
Lösung
def count_repeated(word):
count = {}
for character in word:
if character in count:
count[character] = count[character] + 1
else:
count[character] = 1
## unsorted
for key, value in count.items():
if value > 1:
print(key, value)
## sorted
for key in sorted(count, key=count.get, reverse=True):
value = count[key]
if value > 1:
print(key, value)
count_repeated("thequickbrownfoxjumpsoverthelazydog")
Aufgabe 45
Write a Python program to check whether a string contains all letters of the alphabet.
Lösung
def check_alphabet(sentence):
alphabet = "abcdefghijklmnopqrstuvwxyz"
for character in alphabet:
if character not in sentence:
return False
return True
print(check_alphabet("thequickbrownfoxjumpsoverthelazydog"))
print(check_alphabet("Matur"))
Aufgabe 87
Write a Python program to find the common values that appear in two given strings.
- Original strings
- Python3, Python2.7
- Expected output
- Python
Lösung
def common(string1, string2):
result = ""
length = min(len(string1), len(string2))
for i in range(length):
if string1[i] == string2[i]:
result = result + string1[i]
else:
break
return result
print(common("Python3", "Python2.7"))
Aufgabe 103
Write a Python program to replace each character of a word of length five and more with a hash character (#).
- Original string
Count the lowercase letters in the said list of words
- Expected output
##### the ######### ####### in the said list of ######
Lösung
def censor(sentence):
result = []
for word in sentence.split():
if len(word) >= 5:
result.append(len(word) * "#")
else:
result.append(word)
return " ".join(result)
print(censor("Count the lowercase letters in the said list of words"))
Aufgabe 106
Write a Python program to remove repeated consecutive characters and replace them with single letters and print a updated string.
Sample Data:
("Red Green White") -> "Red Gren White"
("aabbbcdeffff") -> "abcdef"
("Yellowwooddoor") -> "Yelowodor"
Lösung
def remove_repeated(sentence):
result = ""
last_character = ""
for character in sentence:
if not last_character == character:
result = result + character
last_character = character
return result
print(remove_repeated("Red Green White"))
print(remove_repeated("aabbbcdeffff"))
print(remove_repeated("Yellowwooddoor"))
Zusatzaufgabe
Aufgabe: Bigramme
Wie Aufgabe 2, aber es wird die Häufigkeit von Bigrammen – also zweier-Folgen von Buchstaben berechnet
Lösung
def bigramm(sentence):
count = {}
for word in sentence.lower().split():
for i in range(len(word)-1):
bi = word[i] + word[i+1]
if bi in count:
count[bi] = count[bi] + 1
else:
count[bi] = 1
## sorted
for key in sorted(count, key=count.get, reverse=True):
value = count[key]
if value > 2:
print(key, value)
bigramm("""Vor einem grossen Walde wohnte ein armer Holzhacker mit seiner Frau
und seinen zwei Kindern; das Bübchen hiess Hänsel und das Mädchen Gretel.
Er hatte wenig zu beissen und zu brechen, und einmal,
als grosse Teuerung ins Land kam, konnte er das tägliche Brot nicht mehr schaffen.
Wie er sich nun abends im Bette Gedanken machte und sich vor Sorgen herumwälzte,
seufzte er und sprach zu seiner Frau.""")