Abstiegsfunktion < Softwaretechnik+Pro < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:58 Sa 31.01.2009 | | Autor: | farnold |
Hallo,
Vorbedinung: n>= 0, k >= 0
int binom (int n, int k) {
return (n < k) ? 0 :
(n==k) ? 1 :(binom(n-1,k)* n/(n-k));
}
diese Rekursive Funktion berechnet mir den Binominalkoeffizienten.
Wenn ich zeigen soll das diese Funktion partiell Korrekt ist, dann mach ich das mit der Schleifeninvariante und Induktion.
Habe ich dies gemacht weiß ich aber noch nicht ob diese Funktion terminiert. Um zu zeigen das die Funktion terminiert brauch ich eine "Abstiegsfunktion".
Frage: Wie finde ich eine Abstiegsfunktion?
Für diese Funktion wäre die Abstiegsfunktion ab(n,k) = n+k, aber keine Ahnung wie man da drauf kommt
int summe (int n) { assert (n>= 0);
return (n==0) ? 0 : n + summe(n-1);
}
hier wäre die Abstiegsfunktion ab(n) = n
Gibt es einen "einfachen" Weg an diese Abstiegsfunktion zu kommen ( ich seh hier gar keinen zusammenhang :()?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 02.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
