Lösungen

Lösungen

Hausaufgabe: Array-Funktionen

def sum(nums):
  sum = 0
  for i in range(0, len(nums)):
    sum = sum + nums[i]
  return sum
def from_to(lower,upper):
  nums = [None] * (upper-lower+1)
  for i in range(lower,upper+1):
    nums[i-lower] = i
  return nums

Bonusaufgabe: Programmierung mit Arrays

def is_valid_walk(walk):
  if len(walk) != 10:
    return False
  x = 0
  y = 0
  for i in range(0, len(walk)):
    step = walk[i]
    if step == "n":
      y = y + 1
    if step == "s":
      y = y - 1
    if step == "o":
      x = x + 1
    if step == "w":
      x = x - 1
  return x == 0 and y == 0

Hausaufgabe: Suche in sortierten Arrays

Das folgende Programm sucht ein gegebenes element x in einem sortierten Feld a und bricht die Suche ab, sobald die restlichen Elemente größer sind als das gesuchte.

def is_in_sorted(a,x):
  found = False                                  #1
  i = 0                                          #2
  while not found and i < len(a) and a[i] <= x:  #3
    found = (a[i] == x)                          #4
    i = i + 1                                    #5
  return found                                   #6

Die folgende Programmtabelle:kumentiert die Ausführung der Funktion für die Argumente a = [2,4,6,8,10] und x = 5.

PPfoundi!foundi < a.sizea[i] <= xRückgabewert
#1False
#20
#3TrueTrueTrue
#4False
#51
#3TrueTrueTrue
#4False
#52
#3TrueTrueFalse
#6False

Aufgabe: Array von Fibonacci-Zahlen

Das folgende python-Programm berechnet ein Array aus Fibonaci-Zahlen, indem es in einer Schleife basierend auf den beiden vorherigen Einträgen vergrößert wird.

n = 10
fibs = [None] * (n+1)
fibs[0] = 0
fibs[1] = 1
for i in range(2, n+1):
  fibs[i] = fibs[i-1] + fibs[i-2]
print(fibs)

Es gibt das Array [0,1,1,2,3,5,8,13,21,34,55] aus.

Aufgabe: Binäre Suche in Arrays

Die folgende Funktion sucht mit sogenannter binärer Suche.

def bin_search(a,x):
  # Die Grenzen left und right definieren,
  # in welchem Bereich noch gesucht werden muss.
  # Dieser Bereich wird in jedem Schritt halbiert.
  left  = 0
  right = len(a)
  # right ist der erste Index, der nicht mehr betrachtet werden muss.
  found = False
  while not found and left < right:
    i = (left + right) // 2
    if a[i] < x:
      left = i + 1
      # left = i wäre hier falsch, 
      # da dann z.B. der Aufruf bin_search([0],1) nicht terminiert.
    if a[i] > x:
      right = i
      # right = i - 1 wäre hier falsch,
      # da dann z.B. bin_search([0,1],0) False zurück liefern würde.
    found = a[i] == x
  return found

In jedem Schritt wird der zu durchsuchende Bereich halbiert. Dazu wird zunächst das mittlere Element getestet und dann rechts oder links davon weiter gesucht, falls es nicht das gesuchte Element ist.

Wir können die Laufzeiten von is_in_sorted() und bin_search() mit dem folgenden Programm vergleichen.

from datetime import datetime
from is_in_sorted import is_in_sorted

n = 200_000_000
big = [None] * n

for i in range(0,n):
  big[i] = i + 1
print(datetime.now())
print(is_in_sorted(big,n))
print(datetime.now())
print(bin_search(big,n))
print(datetime.now())

Die Funktion is_in_sorted() braucht fast eine halbe Minute, um ein Feld mit 200 Millionen Elementen zu durchsuchen, bin_search() schafft das gleiche in unter einer Sekunde:

2022-03-08 14:49:15.087615
True
2022-03-08 14:49:41.921407
True
2022-03-08 14:49:41.921445

Bonusaufgabe: Was berechnet dieses Programm?

Das gezeigte Programm gibt alle Primzahlen aus, die kleiner sind als 100. Dazu streicht es gemäß des Siebs des Eratosthenes Vielfache von gefundenen Primzahlen, so dass am Ende nur noch Primzahlen übrig bleiben.