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

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 oder False zurück, je nachdem ob die Zerlegung korrekt ist oder nicht.

Brute-Force

Wir testen alle möglichen Faktoren aus.

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)

Listen

Du kannst dich hier über Listen und Schleifen informieren:

👉 Skript Programmieren

Aufgaben

Versuche die folgenden Aufgaben zu lösen. Es handelt sich um eine 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}

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

Expected Result

black, green, red, white

Aufgabe 39

Write a Python program to reverse a string.

Aufgabe 40

Write a Python program to reverse words in a string.

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

Aufgabe 45

Write a Python program to check whether a string contains all letters of the alphabet.

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

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

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"

Zusatzaufgabe

Aufgabe: Bigramme

Wie Aufgabe 2, aber es wird die Häufigkeit von Bigrammen – also zweier-Folgen von Buchstaben berechnet

Zusatzaufgabe

Weitere Aufgaben findet man hier:

👉 https://www.w3resource.com/python-exercises/string/