AUFGABE 1 (Programmm + Laufzeitbestimmung)
1.1 Programm für zweitgrößte Zahl
def secondLargest(A):
max1 = A[0]
max2 = A[1]
if max2 > max1:
max1, max2 = max2, max1
for i in range(2, len(A)):
if A[i] > max2:
if A[i] > max1:
max2 = max1
max1 = A[i]
max2 = A[i]
return max2
1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen
TODO
1.3 Funktion zur Berechnung von F_n in Zeit O(n)
def fastFibonacci(n):
fibs = [1] * n
for i in range(2, n):
fibs[i] = fibs[i - 1] + fibs[i - 2]
return fibs[n-1]
AUFGABE 2 (Felder + Hashing)
2.1 Suchen und Löschen eines Elementes aus einem Feld
def removeFromArray(A, x):
i = 0
while i < len(A) and A[i] != x:
i = i + 1
if i < len(A):
A[i], A[-1] = A[-1], A[i]
A.pop()
2.2 Löschen eines Elementes aus einer Hashtabelle
def removeFromHashTable(T, h, x):
removeFromArray(T[h(x)], x)
AUFGABE 3 (Binäre Heaps)
3.2 Funktion zur Überprüfung der Heapeigenschaft
def checkHeapProperty(heap):
for i in range(2, len(heap)):
child_value = heap(i)
parent_value = heap(i/2)
if child_value < parent_value:
return False
return True
AUFGABE 4 (Graphen)
4.2 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzlisten
# graph is represented as an array of n adjacency lists, where n = #nodes.
def numEdges(graph):
count = 0
for i in range(0, len(graph)):
count += len(graph[i])
return count
4.3 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzmatrix
# graph is represented as an array of n array, each of size n, where n = #nodes.
def numEdges(graph):
count = 0
n = len(graph)
for i in range(0, n):
for j in range(0, n):
if graph[i][j] > 0:
count += 1
return count