Rekursionsgleichung

08.11.2010, 10:26	fanta90	Auf diesen Beitrag antworten »
Rekursionsgleichung Für natürliche Zahlen x; y wollen wir x^y berechnen, und betrachten folgende Rekursionsgleichung: P(x; y) = { x falls y=1 P(x,y/2)² falls y>=2, y grade x*P(x,y-1) falls y>=2; y ungrade } 1. Zeigen Sie, dass für alle x; y [Element] N gilt x^y = P(x; y). 2. Bestimmen Sie eine möglichst kleine obere Schranke für die Rekursionstiefe in Abhängigkeit von x; y. (D.h. die Anzahl der rekursiven Aufrufe ausgehend vom Startaufruf P(x; y), bis der Rekursionsanfang P(x; 1) erreicht wird.) So ist die Aufgabenstellung (zum Themengebiet der Theoretischen Informatik). Das die Rekursionsgleichung stimmt, sehe ich ja, aber wie "zeige" ich das? Ich bin glücklich über jede Hilfe. Vielen Dank. MfG fanta90
08.11.2010, 11:17	René Gruber	Auf diesen Beitrag antworten »
Vollständige Induktion über $\begin{eqnarray} y \end{eqnarray}$ im "erweiterten" Sinne (d.h. Induktionsschritt $\begin{eqnarray} (<y)\to y \end{eqnarray}$ statt wie üblich nur $\begin{eqnarray} (y-1)\to y \end{eqnarray}$ ). Falls dir das nicht behagt, kannst du (in inhaltlich äquivalenter Weise) auch indirekt vorgehen: Nimm an, dass es $\begin{eqnarray} x,y \end{eqnarray}$ gibt mit $\begin{eqnarray} P(x;y) \neq x^y \end{eqnarray}$ , dann gibt es unter diesen Gegenbeispielen auch solche mit minimalem $\begin{eqnarray} y \end{eqnarray}$ ... Das kann man dann zum Widerspruch führen.
08.11.2010, 11:36	fanta90	Auf diesen Beitrag antworten »
RE: Rekursionsgleichung Danke für deine Antwort. die Induktionsannahme steht ja in der Aufgabenstellung x^y = P(x; y) das hieße: P(x,1)=x P(x,2)= P(x, 2/2) ^2 = P(x,1) ^2 P(x,3)= x * P(x, 3-1) = x * P(x,2) = x * P(x,1)^2 soweit so gut nur wie komme ich nun auf eine algemeine Rekursionsgleichung ich hab ja immernoch diese zwei fälle (y grade oder ungrade) sry ich kapier das nicht...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »