Wie funktioniert diese Schleifen-Aufgabe? Schreiben Sie mithilfe einer while-Schleife...

Question

a) Schreiben Sie mit Hilfe einer while-Schleife einen Pseudo-Code, welcher für eine gegebene natürliche

Zahl n ihre Fakultät n! berechnet. (Hinweis: Es gilt die Konvention 0! = 1. Sie benötigen eine Laufvariable

k und eine Ergebnisvariable f.)

b) Begründen Sie, warum die Schleife terminiert.

c) Bestimmen Sie eine sinnvolle Eigenschaft der Schleife und zeigen Sie durch vollständige Induktion, dass

sie eine Schleifeninvariante ist.

Zeigen Sie, dass der Code total korrekt ist. (Hinweis: Zeigen Sie, dass aus der abweisenden Schleifenbedingung

und der Schleifeninvariante folgt f = n!.)

Comments

Leider kann ich dir nur mit  "Wolfgang-Pseudocode" für a) dienen, deshalb ein Kommentar und keine Antwort. Aber vielleicht hilft es ja ein wenig :-)

Input(n∈ℕ₀)

wenn (n=0 oder n=1)  dann [ Output("n! = 1") ;  Programmende ]

sonst

        f := 1

        while  n > 1 do

              begin

                   f := f * n

                   n := n -1

              end

Ende von sonst

Output("n! = ", f)

Programmende

-----------------------

Zu b) noch ein Vorschlag:

"n erreicht in jedem Fall den Wert 1, weil Wolfgang das behauptet hat"    :-)

Answer 1

Für die zu fuehrenden Beweise ist folgender Code recht geschickt:

f = 1;
k = 0;

while (k < n) {
    k = k + 1;
    f = f * k;
}

Teil b) überlasse ich Dir und für Teil c) habe ich den Tipp, dass die Invariante \(k\le n\wedge f=k!\) lautet.