Beweis Rekursion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:58 Do 19.01.2006 | | Autor: | kuminitu |
| Aufgabe | Es sei bei Aufruf b eine positive Zahl. Was berechnet die folgende Methode (mit Beweis)?
public static int wasTueIch ( int a, int b )
{
return ( b == 1 ? a : a + wasTueIch( a, b - 1 ) ) ;
} |
Hallo,
also, habe rausgefunden, dass diese Methode einfach
a * b zurückgibt, aber wie beweise ich sowas???
Bin über jede Hilfe erfreut.
MFG
Kuminitu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:43 Do 19.01.2006 | | Autor: | piet.t |
Hallo,
"Rekursion" und"(vollständige) Induktion" sind zwei Begriffe, die eigentlich meistens Hand in Hand gehen.
In diesem Fall würde ich also behaupten, dass die Funktion a*b liefert und das ganze dann durch vollständige Induktion über b beweisen, sollte keine große Sache sein.
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:03 Fr 20.01.2006 | | Autor: | kuminitu |
Hallo,
eigentlich ist es normalerweise kein problem,
aber ich weis nur nicht wie ich die methode
genau in formeln fassen kann, dass heisst
ich komme ich nicht mal auf Ind. Anf...
bzw auf eine idee beim induktionsschluss
|
|
|
| |
|
Hallo kuminitu,
> aber ich weis nur nicht wie ich die methode
> genau in formeln fassen kann
Schauen wir uns nochmal deinen Quelltext an:
> public static int wasTueIch ( int a, int b )
> {
> return ( b == 1 ? a : a + wasTueIch( a, b - 1 ) ) ;
> }
Deinen Java-Code können wir auch "mathematischer" aufschreiben:
[mm]\mathrm{wasTueIch}\,(a,b) := \begin{cases}b=1,&a\\b>1,&a + \mathrm{wasTueIch}\,(a, b - 1)\end{cases}[/mm]
Zuerst machen wir ein Beispiel. Sei dazu [mm]b = 3[/mm]. Was ich jetzt tue ist lediglich die wiederholte Anwendung der Definition von [mm]\mathrm{wasTueIch}[/mm]:
[mm]\mathrm{wasTueIch}\,(a,3) \mathop =^{b=3>1} a+\mathrm{wasTueIch}\,(a,2) \mathop =^{b=2>1} a+a+\mathrm{wasTueIch}\,(a,1) \mathop =^{b=1} a+a+a = 3a[/mm]
Du siehst also, daß hier tatsächlich [mm]a[/mm] mit [mm]b[/mm] multipliziert wird, wie schon piet.t gesagt hat.
Jetzt müssen wir das Ganze noch beweisen, und Induktion über [mm]b[/mm] ist wirklich eine gute Idee hier. Jede Induktion benötigt einen Induktionsanfang. Und dieser springt einem für [mm]b = 1[/mm] praktisch schon ins Auge.  (Wenn nicht, so schau nochmal auf die Definition.) Wir beginnen also mit dem ...
[mm]\underline{\texttt{Induktionsanfang }(b=1):}[/mm]
[mm]\mathrm{wasTueIch}\,(a,1) \mathop =^{\text{Definition}} a = 1\cdot{a}\;\Diamond[/mm]
[mm]\underline{\texttt{Induktionsannahme:}}[/mm]
Angenommen es gilt [mm]\forall b \in \mathbb{N}_{\ge 1}:\mathrm{wasTueIch}\,(a,b) = ba[/mm].
[mm]\underline{\texttt{Induktionsschritt }(b \leadsto b+1):}[/mm]
[mm]\mathrm{wasTueIch}\,(a,b+1) \mathop =^{\text{Definition}} a+\mathrm{wasTueIch}\,(a,b) \mathop =^{\text{Induktionsannahme}}a+ba \mathop =^{\begin{subarray}{l}
\text{Distributiv-- \&}\\
\text{Kommutativgesetz :-)}
\end{subarray}}(b+1)a\;\Box[/mm]
Ähnliche Aufgaben solltest Du jetzt dann selber versuchen können. Wenn dir noch etwas unklar sein sollte, so frag' einfach nach.
Viele Grüße
Karl
|
|
|
|
