Python-Die Eulersche Zahl

Aus ProgrammingWiki

canvas = window.Canvas turtle = window.Turtle rand = 50 maxbreite = 400 - 2 * rand maxhoehe = 300 - 2 * rand def minmax(ls): erg = [0, 0] for i in range(len(ls)): if erg[0] > ls[i]: erg[0] = ls[i] if erg[1] < ls[i]: erg[1] = ls[i] return erg def balken(turtle, hoehe, breite): turtle.forward(breite); turtle.left(90) turtle.forward(hoehe); turtle.left(90) turtle.forward(breite); turtle.left(90) turtle.forward(hoehe); turtle.left(90) turtle.forward(breite) def balkendiagramm(turtle, ls): breite = maxbreite / len(ls) extrem = minmax(ls) minwert = extrem[0]; maxwert = extrem[1] turtle.penUp() turtle.right(90) turtle.move(rand, rand + maxwert / (maxwert - minwert) * maxhoehe) turtle.penDown() for i in range(len(ls)): balken(turtle, ls[i] / (maxwert - minwert) * maxhoehe, breite)

Es gilt: $e = 2,718~281~828~459~045~235~360~287~471~352~...$

Inhaltsverzeichnis 1 Die Eulersche Zahl als Grenzwert einer Zahlenfolge 1.1 Konvergenz 2 Die Eulersche Zahl als Kettenbruch 2.1 Iterative Implementation 2.2 Rekursive Implementation 2.3 Konvergenz 3 Euler-Zufall 1 3.1 Simulation 4 Euler-Zufall 2 4.1 Simulation 5 Ein Rencontre-Problem (Fixpunktreie Permutationen) 5.1 Simulation 6 Das Rosinenproblem 6.1 Simulation 7 Das Münzenproblem 7.1 Simulation 8 Das Sekretärinnenproblem 8.1 Simulation 9 Anmerkung

Die Eulersche Zahl als Grenzwert einer Zahlenfolge

Die Zahlenfolge

$e_n=(1+\frac{1}{n})^n\hspace{0.3em},\hspace{0.3em}\mbox{für}\hspace{0.3em}n=1, 2, 3, ...$

hat als Grenzwert die Eulersche Zahl.

$e=\lim\limits_{n \to \infty}(1+\frac{1}{n})^n$

def e_folgenglied(n): e = (1 + 1 / n) ** n return e

print(e_folgenglied(1000))

ausführen

Konvergenz

def e_folge(n): folge = [1] for i in range(1, n + 1): folge.append(round((1 + 1 / i) ** i, 4)) return folge

c1 = canvas.new(1); c1.clear() t1 = turtle.new(1); t1.hide() folge1 = e_folge(50) balkendiagramm(t1, folge1) print(folge1)

ausführen

Diese Zahlenfolge konvergiert also sehr langsam.

Die Eulersche Zahl als Kettenbruch

Die Eulersche Zahl lässt sich deutlich schneller mit einem Kettenbruch annähern.

$e=2+\dfrac{2}{2+\dfrac{3}{3+\dfrac{4}{4+\dfrac{5}{5+\dfrac{6}{...}}}}}$

Iterative Implementation

def e_iterativ(n): e = 0 for i in range(n, 1, -1): e = i / (e + i) return 2 + e

print(e_iterativ(10))

ausführen

Rekursive Implementation

def e_rekursiv(n): def e_tail(i, n): if i > n: return 0 else: return i / (i + e_tail(i + 1, n)) return 2 + e_tail(2, n)

print(e_rekursiv(10))

ausführen

Konvergenz

def e_folge_rekursiv(n): folge = [] for i in range(1, n + 1): folge.append(round(e_rekursiv(i), 6)) return folge

c2 = canvas.new(2); c2.clear() t2 = turtle.new(2); t2.hide() folge2 = e_folge_rekursiv(50) balkendiagramm(t2, folge2) print(folge2)

ausführen

Euler-Zufall 1

Wie oft müssen Zufallszahlen aus dem Intervall [0, 1] gebildet werden, damit die Summe zum ersten Mal 1 überschreitet?

Simulation

from random import * from math import exp def eulerzufall1(n): m = 0 for i in range(n): z = 0; j = 0 while z < 1: z += random() j += 1 m += j return m / n def eulerzahl1(n): print("Eulerzahl: %1.8f" % eulerzufall1(n)) print("Zum Vergleich: e = %1.8f" % exp(1))

eulerzahl1(20000)

ausführen

Euler-Zufall 2

Eine Folge von Zahlen wird zufällig aus dem Intervall [0, 1] erzeugt.
Der Prozess wird so lange fortgesetzt, wie die Folge monoton steigend ist.
Welche Länge der monotonen Folge wird erwartet?

Simulation

from random import * from math import exp def eulerzufall2(n): m = 0 for i in range(n): z0 = 0; z = random() j = 1 while z0 < z: z0 = z z = random() j += 1 m += j return m / n def eulerzahl2(n): print("Eulerzahl: %1.8f" % eulerzufall2(n)) print("Zum Vergleich: e = %1.8f" % exp(1))

eulerzahl2(200000)

ausführen

Ein Rencontre-Problem (Fixpunktreie Permutationen)

Die Stapel zweier gleicher Kartenspiele werden jeweils gemischt und verdeckt nebeneinander gelegt.
Fortlaufend werden die beiden oben liegenden Karten aufgedeckt und nebeneinander gelegt.
Mit welcher Wahrscheinlichkeit kann ein gleiches Paar erwartet werden?

Simulation

from random import * from math import exp def perm(n): p = [] while len(p) < n: a =randint(1, n) if not(a in p): p.append(a) return(p) def permdiff(n): p1 = perm(n); p2 = perm(n) diff =[] for i in range(n): diff.append(p1[i] - p2[i]) return diff def ergebnis(n, anz): ges = 0 for j in range(anz): diff = permdiff(n) c = 0 for i in range(n): if diff[i] == 0: c = 1; break ges += c return ges / anz def rencontre(n, anz): print("Relative Häufigkeit: %1.8f" % ergebnis(n, anz)) print("Zum Vergleich: 1 - 1 / e = %1.8f" % (1 - 1 / exp(1)))

rencontre(10, 1000)

ausführen

Das Rosinenproblem

In den Teig für 100 Brötchen werden zufällig 100 Rosinen hinengeknetet.
Wie viele Brötchen enthalten mindestens eine Rosine?

Simulation

from random import * from math import exp def rosinen(n): r = [randint(0, n - 1) for i in range(n)] z = 0 for j in range(n): k = 0 for i in range(n): if r[i] == j: k = 1; break z += k return z / n def rosinenproblem(anz): z = 0 for i in range(anz): z += rosinen(100) mw = z / anz print("Relative Häufigkeit: %1.8f" % mw) ew = 1 - 1 / exp(1) print("Zum Vergleich: 1 - 1/e = %1.8f" % ew)

rosinenproblem(1000)

ausführen

Das Münzenproblem

Eine Fastfood-Kette verschenkt bei jedem Einkauf eine Münze eines 50-teiligen Satzes von Sondermünzen.
Ziel ist es, den gesamten Münzsatz zu sammeln.
Welchen Bruchteil des kompletten Münzsatzes würde man nach 50 Einkäufen erwarten?

Simulation

from random import * from math import exp def auswahl(n): muenzen = [i for i in range(n)] pos = randint(0, n - 1) return muenzen[pos] def muenzenproblem(n, anz): sum = 0 for j in range(anz): set = [] for i in range(n): muenze = auswahl(n) if not (muenze in set): set.append(muenze) sum += len(set) / n h = sum / anz print("Relative Häufigkeit: %1.8f" % h) vw = 1 - 1 / exp(1) print("Zum Vergleich: 1 - 1 / e = %1.8f" % vw)

muenzenproblem(50, 100)

ausführen

Das Sekretärinnenproblem

Für eine Sekretärinnenstelle gibt es $n$ Bewerberinnen.
Die ersten $k$ Bewerberinnen werden zwar angehört, aber allesamt abgelehnt.
Die Gespräche werden fortgeführt und die Kandidatin eingestellt, die besser als alle Vorgängerinnen ist. Solle es keine bessere geben, muss die letzte Bewerberin eingestellt werden.
Bei welcher Anzahl $k$ ist die Wahrscheinlichkeit am größten, die beste Bewerberin einzustellen?

Simulation

from random import * from math import exp def auswahl(n, k): bewliste = [random() for i in range(n)] bewteilliste = [] for i in range(k): bewteilliste.append(bewliste[i]) maxwert = max(bewliste) bestwert = max(bewteilliste) kandidat = 0 while kandidat < bestwert and k < n: kandidat = bewliste[k] k += 1 if kandidat == maxwert: return 1 else: return 0 def sekretaerinnenproblem(n, k, anz): z = 0 for i in range(anz): z += auswahl(n, k) h = z / anz print("Relative Häufigkeit: %1.8f" % h) vw = 1 / exp(1) print("Zum Vergleich: 1/e = %1.8f" % vw)

sekretaerinnenproblem(100, 37, 2500)

ausführen

Anmerkung

Diese Algorithmen wurden anlässlich des 315. Geburtstages Leonhard Eulers gemeinsam mit Dr. Hubert Langlotz (Thüringen) in einem webbasierten Seminar am 06.12.2022 vorgestellt.

Löbau, den 17.12.2022
Veit Berger