Pythonskripte Inf4St. Teil I

FizzBuzz: Einstieg in Python

for k in range (1,100,1):
    if k%3 == 0 or k%5 == 0:
        if k%5 !=0:
            print("fizz"" ", end="")
        if k%3 !=0:
            print("buzz"" ", end="")
        if k%3 == 0 and k%5 == 0:
            print("fizzbuzz"" ", end="")
    else:
        print (k," ", end="")

Linear Search: mit Zufallslisten-Generator und Zeitmessung für die Zeitkomplexität

import random
import time
meineliste=[]

for i in range(0,20):
    zufall = random.randint(1,100)
    meineliste.append(zufall)
print(meineliste)

startzeit = time.monotonic_ns()
maximum = meineliste[0]
for i in range(1, len(meineliste)):
    time.sleep(0.01)
    if maximum<meineliste[i]:
        maximum = meineliste[i]
        print("vorläufiges Maximum: ", maximum)
        time.sleep(0.01)
print("-------------------------------------------")
dauer = (time.monotonic_ns()-startzeit)/1000000
print("zeitdauer in milli-Sekunden: ", dauer)
print("endgültiges Maximum: ", maximum)

BubbleSort: mit Zufallslisten-Generator und Zeitmessung für die Zeitkomplexität

import random
import time

mliste = []
for k in range (0,20):
    mliste.append(random.randint(1,100))

print(mliste)

startzeit = time.monotonic_ns()
# bubblesort
for m in range(0,len(mliste)-1):
    time.sleep(0.01)
    for i in range(0,len(mliste)-1-m):
        time.sleep(0.01)
        if mliste[i]>mliste[i+1]:
            time.sleep(0.01)
            temp = mliste[i+1]
            mliste[i+1]= mliste[i]
            mliste[i]=temp
    print(mliste)
endzeit = time.monotonic_ns()
zeitdifferenz= (endzeit - startzeit)/1000000
print("vergangene Zeit: ", zeitdifferenz)

Quicksort-Simulation: Die Simulation aus dem Unterricht:
https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/visualize/

Prinzip von Funktionen: mit Parameterübergabe, Returnwert und globaler Variable für die Rückgabe

import random
import time

def macheZufallsliste(listenlaenge, obergrenze):
    print("übergebener Parameter: " + str(listenlaenge))
    meineListe = []
    for i in range(0,listenlaenge):
        meineListe.append(random.randint(1,obergrenze))
    print ("noch im Stack:           ", meineListe)
    return meineListe

auffangVariable= macheZufallsliste(10,10)

print("aufgefangen über Return: ", auffangVariable)
time.sleep(2)
print("aufgefangen über Return: ", auffangVariable)

Selection-Sort: mit Linear-Search-Funktion und Python „append()“ bzw. „insert()“

import random

def sucheLinear(testliste, modus):
    if modus=="max":
        maximum = testliste[0]
        for num in testliste:
            if num>maximum:
                maximum = num
        return maximum

    if modus=="min":
        minimum = testliste[0]
        for num in testliste:
            if num<minimum:
                minimum = num
        return minimum

mliste = []
for k in range (20):
    mliste.append(random.randint(1, 100))

for j in range (0, len(mliste)):
    groesstesElement = sucheLinear(mliste[0:len(mliste)-j], "max")
    print("aktuell grösstes Element:", groesstesElement)
    mliste.remove(groesstesElement)
    mliste.append(groesstesElement)
    print("Sortier-Schritt ",j+1, ": ", mliste)
print("endgültig sortierte Liste: ", mliste)

Stack-Simulation: Wie Funktionen im Speicher verwaltet werden, wichtig für Rekursion
https://visualgo.net/en/list

Rekursion: Skripte für das grundlegende Verständnis. Stack Auf- und Abbau.

def rek1(n):
    if n>1:
        print("lokales n: ", n)
        n-= 1
        rek1(n)
    else:
        print("lokales n: ", n, ", fertig: Basisfall, bzw. Abbruchbedingung")
        n-= 1
    print("lokales n: ", n)

rek1(4)
print("------------------------------------------------------")

summe=0
def rek2(n):
    global summe
    if n>1:
        summe=summe+n
        print("Hin ...     lokales n: ", n, "summe: ", summe)
        n-= 1
        rek2(n)
    else:
        summe=summe+n
        print("fertig.     lokales n: ", n, "summe: ", summe)
        n-= 1
    print("...& zurück lokales n: ", n, "summe: ", summe)

rek2(4)
print("------------------------------------------------------")

prod=1
def rek3(n):
    global prod
    if n>1:
        prod=prod*n
        print("Hin ...     lokales n: ", n, "prod: ", prod)
        n-=1
        rek3(n)
    else:
        prod = prod * n
        print("fertig.     lokales n: ", n, "prod: ", prod)
        n -= 1
    print("...& zurück lokales n: ", n, "prod: ", prod)

rek3(5)
print("------------------------------------------------------")

def rek4(n):
    if n>1:
        print("vorher, lokales n: ", n)
        prod = n * rek4(n-1)
        print("danach, lokales n: ", n, "zwischenergebnis: ", prod)
        return prod
    else:
        print("fertig. Lokales n: ", n)
        return 1
    print("...& zurück lokales n: ", n)

rek4(5)
print("------------------------------------------------------")

def rek5(n):
    if n>1:
        print("vorher, lokales n: ", n)
        knoten = rek5(n-1) + rek5(n-1)
        print("Ast.  Lokales n: ", n, "zwischenknoten: ", knoten)
        return knoten
    else:
        print("Blatt. Lokales n: ", n)
        return 1
    print("...& zurück lokales n: ", n)

rek5(3)
print("------------------------------------------------------")

Programm von F.S.: Quicksort-Implementierung

import random
laenge=10
list=[]

for i in range (0,laenge):
    list.append(random.randint(1,100))

print("Die zufällig ausgewählte Liste ist: ")
print(list)

def quicksort(list):
    rekursion(list,0,len(list)-1)

def rekursion (list,first,last):
    if first<last:                                 #Abbruchbedingung
        splitpoint=sortieren(list,first,last)
        rekursion(list,first,splitpoint-1)       #Rekursion für erste Listenhälfte!
        rekursion(list,splitpoint+1,last)        #Rekursionfür zweite Listenhälfte!

def sortieren(list,first,last):
    pivot=list[last]
    leftmark=first
    rightmark=last-1
    done=False
    while not done:
        while leftmark<=rightmark and list[leftmark]<= pivot:
            leftmark=leftmark+1

        while leftmark<=rightmark and list[rightmark]>= pivot:
            rightmark=rightmark-1

        if rightmark<leftmark:
            done=True
        else:
            temp=list[rightmark]
            list[rightmark]=list[leftmark]
            list[leftmark]=temp

    temp=list[leftmark]
    list[leftmark]=list[last]
    list[last]=temp

    return leftmark

quicksort(list)
print("--------------------------------------------------------------------------------------")
print("Die Liste ist nun sortiert.")
print(list)
print("--------------------------------------------------------------------------------------")

Programm von M.D.: Palindromprüfung

string_list = input()

def palyndrom2(stringarr_):
    if len(stringarr_) > 1:
            return stringarr_[0] == stringarr_[len(stringarr_)-1] and palyndrom2(stringarr_[1:len(stringarr_)-1])
    else:
        return True

x = palyndrom2(string_list)
print(x);

Binärer Baum: Turtle-Grafik „ohne Schnörkel“

import turtle

def binbaum(maxtiefe, tiefe):
    turtle.forward(100*pow(0.618,tiefe))

    if tiefe < maxtiefe:
        turtle.left(60)
        binbaum(maxtiefe, tiefe+1)
        turtle.right(120)
        binbaum(maxtiefe, tiefe+1)
        turtle.left(60)

    turtle.backward(100*pow(0.618,tiefe))

binbaum(6,0)

turtle.exitonclick()

Programm von M.M.: Binärer Baum mit Turtle-Grafik

import turtle
def tree(x_):
    if x_<=rek:
        turtle.down()
        turtle.forward(int(200/(x_*1.675)))
        leftfunk(x_)
        rightfunk(x_)
        turtle.up()
        turtle.backward(int(200/(x_*1.675)))

def leftfunk(x_):
    if x_ <=rek:
        turtle.left(winkel)
        tree(x_+1)
        turtle.right(winkel)

def rightfunk(x_):
    if x_ <=rek:
        turtle.right(winkel)
        tree(x_+1)
        turtle.left(winkel)

global rek
global winkel
winkel=30
rek=8
turtle.up()
turtle.goto(0,-200)
turtle.left(90)
turtle.down()
tree(1)
turtle.exitonclick()

Mini-Datenbank: für die Binäre Suche

dbListe = [["Staat", "Lebenserwartung", "MioEinwohner", "Fertilitaet"]
,["aegypten", 72.7, 97, 3.4]
,["aequatorialguinea", 64.2, 1.2, 4.9]
,["aethiopien", 62.2, 107.5, 4.4]
,["afghanistan", 51.3, 36.5, 4.8]
,["albanien", 78.3, 2.9, 1.7]
,["algerien", 76.8, 42.7, 3.1]
,["andorra", 82.8, 0.07, 1.3]
,["angola", 56.0, 25.8, 6.0]
,["antigua", 76.5, 0.09, 2.3]
,["argentinien", 77.1, 44.5, 2.3]
,["armenien", 74.6, 3, 1.6]
,["aserbaidschan", 72.5, 9.8, 2.1]
,["australien", 82.2, 24.3, 1.8]
,["bahamas", 72.4, 0.3, 2.0]
,["bahrain", 78.9, 1.3, 2.1]
,["bangladesch", 73.2, 166.4, 2.1]
,["barbados", 75.3, 0.2, 1.5]
,["belgien", 81, 11.3, 1.7]
,["belize", 68.7, 0.3, 2.5]
,["benin", 61.9, 11.1, 5.3]
,["bhutan", 70.1, 0.8, 2.1]
,["bolivien", 69.2, 10.8, 3]
,["bosnien", 76.7, 3.8, 1.3]
,["botswana", 54.5, 2.3, 2.8]
,["brasilien", 73.8, 209.4, 1.7]
,["brunei", 77.2, 0.4, 1.9]
,["bulgarien", 74.5, 7, 1.5]
,["burkinafaso", 55.5, 18.6, 5.7]
,["burundi", 60.5, 10.5, 6.1]
,["chile", 78.8, 18.1, 1.9]
,["china", 75.5, 1393.8, 1.8]
,["costarica", 78.6, 4.8, 1.8]
,["daenemark", 79.4, 5.6, 1.7]
,["deutschland", 80.7, 82.8, 1.6]
,["dominica", 77, 0.07, 3]
,["dominikanische", 78.1, 10.6, 2.4]
,["dschibuti", 63.2, 0.9, 3.2]
,["ecuador", 76.8, 16.3, 2.5]
,["elfenbeinkueste", 58.7, 23.2, 4.9]
,["elsalvador", 74.7, 6.1, 2]
,["emirate", 77.5, 9.2, 1.8]
,["eritrea", 64.9, 5.3, 4.2]
,["estland", 76.7, 1.3, 1.7]
,["fidschi", 72.7, 0.8, 2.7]
,["finnland", 80.9, 5.5, 1.6]
,["frankreich", 81.9, 65.1, 1.9]
,["gabun", 52.1, 2, 4.1]
,["gambia", 64.9, 2, 5.6]
,["georgien", 76.2, 3.9, 1.7]
,["ghana", 66.6, 28, 4.2]
,["grenada", 74.3, 0.1, 2.1]
,["grenadinen", 75.3, 0.1, 2]
,["griechenland", 80.5, 10.9, 1.3]
,["grossbritannien", 80.7, 66.4, 1.8]
,["guatemala", 72.3, 16.6, 3.1]
,["guinea", 60.6, 12.4, 5.1]
,["guineabissau", 50.6, 1.8, 5.6]
,["guyana", 68.4, 0.7, 2.3]
,["haiti", 63.8, 10.8, 3.2]
,["honduras", 71.1, 8.1, 2.5]
,["hongkong", 82.9, 7.3, 1.2]
,["indien", 68.5, 1371.3, 2.3]
,["indonesien", 72.7, 265.2, 2.4]
,["irak", 74.9, 40.2, 4.1]
,["iran", 71.4, 81.6, 2]
,["irland", 80.8, 4.7, 1.9]
,["island", 83, 0.3, 1.8]
,["israel", 82.4, 8.1, 3.1]
,["italien", 82.2, 60.6, 1.3]
,["jamaika", 73.6, 2.8, 2]
,["japan", 85, 126.5, 1.4]
,["jemen", 65.5, 27.4, 4.2]
,["jordanien", 74.6, 7.7, 3.5]
,["kambodscha", 64.5, 15.8, 2.6]
,["kamerun", 58.5, 23.9, 4.9]
,["kanada", 81.9, 37.2, 1.5]
,["kapverde", 72.1, 0.5, 2.3]
,["kasachstan", 70.8, 17.8, 2.6]
,["katar", 78.7, 2.2, 2]
,["kenia", 64, 51, 3.9]
,["kirgisistan", 70.7, 6, 2.5]
,["kiribati", 66.2, 0.1, 4.2]
,["kolumbien", 75.7, 49.8, 2]
,["komoren", 64.2, 0.8, 3.8]
,["kongo", 57.3, 84.3, 6.3]
,["kroatien", 75.9, 4.2, 1.5]
,["kuba", 78.7, 11.5, 1.5]
,["kuwait", 78, 4, 2.1]
,["laos", 64.3, 6.9, 3]
,["lesotho", 53, 2.1, 3.2]
,["lettland", 74.5, 1.9, 1.6]
,["libanon", 77.6, 6, 1.7]
,["liberia", 59, 4.6, 4.9]
,["libyen", 76.5, 6.3, 2.6]
,["liechtenstein", 81.9, 0.03, 1.4]
,["litauen", 74.9, 2.8, 1.6]
,["lucia", 77.8, 0.1, 1.7]
,["luxemburg", 82.3, 0.5, 1.7]
,["macau", 84.5, 0.5, 0.9]
,["madagaskar", 65.9, 24.9, 4.3]
,["malawi", 61.2, 17.7, 6.3]
,["malaysia", 75, 32.5, 1.9]
,["malediven", 75.6, 0.3, 2]
,["mali", 55.8, 18.1, 6]
,["malta", 80.4, 0.4, 1.3]
,["marokko", 76.9, 35.2, 2.2]
,["marshallinseln", 73.1, 0.05, 4.9]
,["mauretanien", 63, 4.1, 4.3]
,["mauritius", 75.6, 1.2, 1.4]
,["mazedonien", 76.2, 2, 1.5]
,["mexiko", 75.9, 130.8, 2.2]
,["mikronesien", 72.9, 0.5, 2.4]
,["moldau", 70.7, 4, 1.3]
,["mongolei", 69.6, 3, 3.1]
,["mosambik", 53.3, 28.7, 5.9]
,["myanmar", 66.6, 53.9, 2.3]
,["namibia", 63.6, 2.5, 3.6]
,["nauru", 67.1, 0.01, 3.4]
,["nepal", 70.7, 29.7, 2.3]
,["neuguinea", 67.2, 7.7, 4]
,["neuseeland", 81.2, 4.5, 2]
,["nevis", 75.7, 0.05, 2.3]
,["nicaragua", 73.2, 6.1, 2.4]
,["niederlande", 81.3, 16.9, 1.7]
,["niger", 55.5, 20.7, 7.6]
,["nigeria", 53.4, 195.9, 5.5]
,["nordkorea", 70.4, 25.2, 2.1]
,["norwegen", 81.8, 5.2, 1.7]
,["oesterreich", 81.5, 8.5, 1.5]
,["oman", 75.5, 4.6, 2.9]
,["osttimor", 68.1, 1.2, 5.7]
,["pakistan", 67.7, 200.6, 3.1]
,["palaestina", 73.9, 4.7, 4.1]
,["palau", 73.1, 0.02, 2.1]
,["panama", 78.6, 3.9, 2.5]
,["paraguay", 77.2, 6.7, 2.6]
,["peru", 73.7, 32.2, 2.4]
,["philippinen", 69.2, 107, 2.7]
,["polen", 77.6, 38.4, 1.4]
,["polynesien", 77.2, 0.2, 2.2]
,["portugal", 79.3, 10.3, 1.4]
,["principe", 64.9, 0.1, 4.4]
,["ruanda", 60.1, 11.9, 4.2]
,["rumaenien", 75.1, 19.3, 1.3]
,["russland", 70.3, 147.3, 1.6]
,["salomonen ", 75.3, 0.5, 3.7]
,["sambia", 52.5, 16.7, 5.3]
,["samoa", 73.7, 0.1, 3.8]
,["sanmarino", 83.3, 0.03, 1.2]
,["saudiarabien", 75.3, 33.4, 2.4]
,["schweden", 82.1, 9.8, 1.8]
,["schweiz", 82.6, 8.3, 1.5]
,["senegal", 61.7, 15.5, 5]
,["serbien", 75.5, 8.8, 1.6]
,["seychellen", 74.7, 0.09, 2.1]
,["sierraleone", 58.2, 7.4, 5.1]
,["simbabwe", 58, 15.9, 4]
,["singapur", 85, 5.6, 1.2]
,["slowakei", 77.1, 5.4, 1.4]
,["slowenien", 78.1, 2, 1.6]
,["somalia", 52.4, 14.3, 6.4]
,["spanien", 81.7, 46.7, 1.3]
,["srilanka", 76.8, 20.8, 2.1]
,["sudan", 64.1, 41.7, 4.7]
,["suedafrika", 63.1, 57.7, 2.4]
,["suedkorea", 82.4, 51.8, 1.1]
,["suriname", 72.2, 0.5, 2.4]
,["swasiland", 51.6, 1.3, 3.3]
,["syrien", 68.4, 18.5, 2.7]
,["tadschikistan", 67.7, 8.6, 3.3]
,["taiwan", 80.1, 23.3, 1.1]
,["tansania", 62.2, 59.1, 5.2]
,["thailand", 74.7, 66.2, 1.5]
,["togo", 65, 7.4, 4.1]
,["tonga", 76.2, 0.1, 3.6]
,["trinidad", 72.9, 1.3, 1.7]
,["tschad", 50.2, 14.4, 6.4]
,["tschechien", 78.6, 10.5, 1.6]
,["tuerkei", 74.8, 81.3, 2.1]
,["tunesien", 76.1, 11.3, 2]
,["turkmenistan", 70.1, 5.4, 2.4]
,["tuvalu", 66.5, 0.01, 3.7]
,["uganda", 55.4, 44.1, 5.4]
,["ukraine", 71.8, 42.3, 1.3]
,["ungarn", 75.9, 9.8, 1.4]
,["uruguay", 77.2, 3.4, 1.9]
,["usa", 79.8, 328, 1.8]
,["usbekistan", 73.8, 32.9, 2.5]
,["vanuatu", 73.4, 0.2, 3.8]
,["venezuela", 75.8, 31.8, 2.4]
,["vietnam", 73.4, 94.7, 2.1]
,["weissrussland", 72.7, 9.4, 1.8]
,["westsahara", 63, 0.5, 2.9]
,["zentralafrika", 52.3, 4.9, 4.4]
,["zypern", 78.7, 1.1, 1.5]]

Binary Search auf der MiniDB:

import MiniDB
cL = MiniDB.dbListe

suchstring = "ruanda"

startindex = 0
endindex = len(cL)-1

while startindex < endindex:
    mitte_index = round((endindex+startindex)/2)

    if cL[mitte_index][0] < suchstring:
        startindex = mitte_index

    if cL[mitte_index][0] > suchstring:
        endindex = mitte_index

    if cL[mitte_index][0] == suchstring:
        print(mitte_index)
        break

Binary-Tree Klasse:

import turtle

class Node:
    def __init__(self, data, tiefe, xwert, parent):
        self.links = None
        self.rechts = None
        self.wert = data
        self.tiefe = tiefe
        self.xwert = xwert
        self.parent = parent

# ------------------------------------------------------
    def printNode(self):
        print(self.wert)
        print(self.tiefe)
        print(self.xwert)

# ------------------------------------------------------
    def printBaum(self):
        if self.links:
            self.links.printBaum()
        print("wert: ", self.wert, "tiefe: ", self.tiefe, "xwert: ", self.xwert )
        turtle.penup()
        turtle.setpos(self.xwert*900/pow(2,self.tiefe), -200 + self.tiefe*50)
        if self.parent is not None:
            turtle.pendown()
            turtle.goto(self.parent.xwert*900/pow(2,self.parent.tiefe), -200 + self.parent.tiefe*50)
        turtle.setpos(self.xwert * 900 / pow(2, self.tiefe), -200 + self.tiefe * 50)
        turtle.dot(24, (0,255,0))
        turtle.setpos(self.xwert * 900 / pow(2, self.tiefe), -208 + self.tiefe * 50)
        turtle.write(str(self.wert), False, align="center")
        turtle.penup()
        if self.rechts:
            self.rechts.printBaum()

# ------------------------------------------------------
    def insert(self, einfuegewert):
        if self.wert is not None:
            if einfuegewert<self.wert :
                if self.links is None:
                    self.links = Node(einfuegewert, self.tiefe + 1, 2*self.xwert-1, self)
                else:
                    self.links.insert(einfuegewert)

            if einfuegewert>=self.wert:
                if self.rechts is None:
                    self.rechts = Node(einfuegewert, self.tiefe + 1, 2*self.xwert+1, self)
                else:
                    self.rechts.insert(einfuegewert)

        if self.wert is None:
            self.wert = einfuegewert

# ------------------------------------------------------
def findeWert(self, suchwert):
    if suchwert < self.wert:
        if self.links is None:
            print("hier is nix")
        return self.links.findeWert(suchwert)

    if suchwert > self.wert:
        if self.rechts is None:
            print("hier is nix")
        return self.links.findeWert(suchwert)

    if suchwert == self.wert:
        print("gefunden! ", self.wert)

# ------------------------------------------------------

import random
root = Node(random.randint(1,100),1, 0, None)

templist = []
for i in range(0,21):
    templist.append(i)

for i in range(20):
    tempindex = random.randint(0,len(templist)-1)
    root.insert(templist[tempindex])
    del(templist[tempindex])

turtle.setup(1000,500)
turtle.colormode(255)
turtle.speed(100)
turtle.hideturtle()
root.printBaum()
turtle.exitonclick()