Skip to content

Programmieren

Repetition

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

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

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

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

python
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/

  1. Versuche deine Funktionen add und sub entsprechend anzupassen.
  2. implementiere Funktionen für Vergleiche (< > <= >= == !=) von Uhrzeiten.

Listen und Schleifen

Du kannst dich hier über Listen und Schleifen informieren:

👉 Skript Programmieren

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:

python
meinDict = {}
meinDict["hello"] = 2
meinDict["goodbye"] = meinDict["hello"] * "Schüss"
print(meinDict)

liefert {'hello': 2, 'goodbye': 'SchüssSchüss'}

Lösung
python
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
python
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
python
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
python
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
python
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
python
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
python
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
python
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
python
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
python
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.""")

Zusatzaufgabe

Weitere Aufgaben findet man hier:

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

Gymnasium Kirchenfeld, fts & lem