+1 Daumen
1,1k Aufrufe

Ich habe folgenden Algorithmus (Pythoncode):

def f(n):
    w = 0                        # Anfangswert 
    for i in range(n+1): # i=0,...,(n+1)-1
        w = w+i                # w um i erhöhen
    return w                  # Nach Beendigung der for-Schleife w zurückgeben.

Dieser Berechnet die Summe aller Zahlen 0,...,n .

Ich habe dazu folgende Schleifeninvariante aufgestellt:

$$ w'=\sum_{i=0}^n i-\sum_{k=i+1}^n k=\frac{n\cdot (n+1)+(i-n)\cdot (n+i+1)}{2} $$

Nur leider geht mein Induktionsbeweis nicht auf, verstehe aber nicht wiso.

Induktionsanfang. Für i=0 ist beim ersten Schleifendurchlauf $$ w'=\sum_{i=0}^n i-\sum_{k=0+1}^n k=\sum_{i=0}^n i-\sum_{k=1}^n k=0=\frac{n\cdot (n+1)+(0-n)\cdot (n+0+1)}{2}. $$

Induktionsvoraussetzung. Angenommen, die Schleifeninvariante gelte für den ersten Schleifendurchlauf.

Induktionsschritt. Dann gilt diese auch für den nachfolgenden, also für die (i+1)-te Iteration, also:

$$ w'=\sum_{i=0}^n i-\sum_{k=(i+1)+1}^n k=\frac{n\cdot (n+1)+((i+1)-n)\cdot (n+(i+1)+1)}{2}\\=\sum_{i=0}^n i-\sum_{k=i+2}^n k=\frac{n\cdot (n+1)+(i+1-n)\cdot (n+i+2)}{2}=\underline{\frac{i^2+3\cdot i+2}{2}}  $$ Dies zeigt man so:

$$ w'=w+i\stackrel{(IV)}{=} \Bigg(\sum_{i=0}^n i-\sum_{k=i+1}^n k\Bigg)+i=\frac{n\cdot (n+1)+(i-n)\cdot (n+i+1)}{2}+i\\=\underline{\frac{i^2+3\cdot i}{2}} $$

Was mache ich falsch?

von
folgende Schleifeninvariante aufgestellt:


Es fällt auf, dass du in der Summenschreibweise von w' i für zwei verschiedene Dinge (Summationsindex und -grenze) verwendest.

Ist das Absicht?

Ja, das ist so gewollt. Ich will in jeder i-ten Iteration die restliche Summe von der (i+1) - ten Iteration bis n abziehen, damit ich die aktuelle Summe von w' bekomme. Hier ein Beispiel:

$$ n=5\\i=0\quad w'=15-15=0\\i=1\quad w'=15-14=1\\i=2\quad w'=15-12=3\\i=3\quad w'=15-9=6\\i=4\quad w'=15-5=10\\i=5\quad w'=15-0=15 $$

Ich vermute mal, dass du meinen Einwand zum i nicht verstanden hast. Denn: Es gilt Punkt- vor Strichrechnung. D.h. du müsstest eigentlich Klammern setzen.

w' = Σ ( i - Σ k )

In dieser Interpretation wäre dann am Schluss gar kein i im Resultat.

Die Umformung scheint diese Klammer nicht zu berücksichtigen.

Zum Programmcode für die Schleife soll sich jemand in der Stacklounge äussern.

Nein ich meinte das hier:

$$ w'=\Bigg(\sum_{i=0}^n i\Bigg)-\Bigg(\sum_{k=i+1}^n k\Bigg)$$

Das sehe ich. Aber da machst du dir das Leben zu schwer mit den beiden verschiedenen i.

$$ w'=\Bigg(\sum_{k=0}^n k\Bigg)-\Bigg(\sum_{k=i+1}^n k\Bigg)$$

$$ w'=\Bigg(\sum_{k=0}^i k\Bigg)$$

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community