Bergervei/Python-Die Eulersche Zahl

Wiki-Quelltext dieser Seite.

<language>Python</language>
<code id="63ac13742e2bd" hidden>
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)
</code>

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

== Die Eulersche Zahl als Grenzwert einer Zahlenfolge ==

Die Zahlenfolge
<blockquote>$e_n=(1+\frac{1}{n})^n\hspace{0.3em},\hspace{0.3em}\mbox{für}\hspace{0.3em}n=1, 2, 3, ...$</blockquote>
hat als Grenzwert die Eulersche Zahl.
<blockquote>$e=\lim\limits_{n \to \infty}(1+\frac{1}{n})^n$</blockquote>

<code id="63cebc4fe0664">
def e_folgenglied(n):
  e = (1 + 1 / n) ** n
  return e
</code>

<run id="63cebc4fe06e6">
print(e_folgenglied(1000))
</run>

=== Konvergenz ===
<code id="63ac1fb152589">
def e_folge(n):
  folge = [1]
  for i in range(1, n + 1):
    folge.append(round((1 + 1 /  i) ** i, 4))
  return folge
</code>

<canvas w="400" h="300"></canvas>

<run id="63ac1fb152669">
c1 = canvas.new(1); c1.clear()
t1 = turtle.new(1); t1.hide()

folge1 =  e_folge(50)
balkendiagramm(t1, folge1)
print(folge1)
</run>

Diese Zahlenfolge konvergiert also sehr langsam.

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

<blockquote>$e=2+\dfrac{2}{2+\dfrac{3}{3+\dfrac{4}{4+\dfrac{5}{5+\dfrac{6}{...}}}}}$</blockquote>

=== Iterative Implementation ===
<code id="639da9b83896a">
def e_iterativ(n):
  e = 0
  for i in range(n, 1, -1):
    e = i / (e + i)
  return 2 + e
</code>

<run id="639da9b8389d5">
print(e_iterativ(10))
</run>

=== Rekursive Implementation ===
<code id="639dcde7f3bf6">
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)
</code>

<run id="639dcde7f3c69">
print(e_rekursiv(10))
</run>

=== Konvergenz ===
<code id="63ac1fb1525f5">
def e_folge_rekursiv(n):
  folge = []
  for i in range(1, n + 1):
    folge.append(round(e_rekursiv(i), 6))
  return folge
</code>

<canvas w="400" h="300"></canvas>

<run id="63ac1fb1526be">
c2 = canvas.new(2); c2.clear()
t2 = turtle.new(2); t2.hide()

folge2 =  e_folge_rekursiv(50)
balkendiagramm(t2, folge2)
print(folge2)
</run>

== Euler-Zufall 1 ==
Wie oft müssen Zufallszahlen aus dem Intervall [0, 1] gebildet werden, damit die Summe zum ersten Mal 1 überschreitet?
 
=== Simulation ===
<code id="639d9442a5eee">
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))
</code>

<run id="639d9442a5f88">
eulerzahl1(20000)
</run>

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

=== Simulation ===
<code id="639d9442a5f3d">
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))
</code>

<run id="639d97fe62936">
eulerzahl2(200000)
</run>

== Ein Rencontre-Problem (Fixpunktreie Permutationen) ==
Die Stapel zweier gleicher Kartenspiele werden jeweils gemischt und verdeckt nebeneinander gelegt.<br>
Fortlaufend werden die beiden oben liegenden Karten aufgedeckt und nebeneinander gelegt.<br>
Mit welcher Wahrscheinlichkeit kann ein gleiches Paar erwartet werden?

=== Simulation ===
<code id="639df1ca18887">
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)))
</code>

<run id="639df1ca188f1">
rencontre(10, 1000)
</run>

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

=== Simulation ===
<code id="639dfb6f8288e">
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)
</code>

<run id="639dfb6f82908">
rosinenproblem(1000)
</run>

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

=== Simulation ===
<code id="639d97fe628dc">
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)
</code>

<run id="639d97fe629c7">
muenzenproblem(50, 100)
</run>

== Das Sekretärinnenproblem ==
Für eine Sekretärinnenstelle gibt es $n$ Bewerberinnen.<br>
Die ersten $k$ Bewerberinnen werden zwar angehört, aber allesamt abgelehnt.<br>
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.<br>
Bei welcher Anzahl $k$ ist die Wahrscheinlichkeit am größten, die beste Bewerberin einzustellen?

=== Simulation ===
<code id="639da07322988">
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)
</code>

<run id="639da073229f9">
sekretaerinnenproblem(100, 37, 2500)
</run>

== 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.<br>

Löbau, den 17.12.2022<br>
Veit Berger