WHILE-Programm < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:40 Do 22.10.2009 | | Autor: | stefan00 |
| Aufgabe | Sei [mm] f:\IN \to \IN [/mm] mit [mm] f(x):=2^x.
[/mm]
Geben Sie ein WHILE-Programm P mit $AC [mm] \circ \tau(P) \circ EC^{(1)}$ [/mm] an. |
Hallo,
mein Problem ist, dass ich keine Idee habe, wie ich letztendlich die Exponentiation [mm] $2^x$ [/mm] in eine Addition überführe, weil ich ja in einem WHILE-Programm nur Register hoch- und runterzählen darf.
Danke für die Hilfe.
Gruß, Stefan.
|
|
| |
|
Hallo Stefan,
> [mm]AC \circ \tau(P) \circ EC^{(1)}[/mm]
Was bedeuten die einzelnen Funktionen der Komposition? (Wenn es denn eine Komposition ist.)
Gruß V.N.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:02 Fr 23.10.2009 | | Autor: | stefan00 |
Hallo,
> > [mm]AC \circ \tau(P) \circ EC^{(1)}[/mm]
>
> Was bedeuten die einzelnen Funktionen der Komposition?
> (Wenn es denn eine Komposition ist.)
ja es ist eine Komposition aus Eingabe (EC) mit einem Parameter x, WHILE-Programm [mm] ($\tau(p)$) [/mm] und Ausgabe (AC). Letztendlich ist das für die Lösung der Aufgabe ziemlich egal, ich habe es nur so formuliert, wie es in der Aufgabe steht. Mein Problem ist nur, dass ich halt die Exponentiation von [mm] $2^x$ [/mm] auf eine Addition zurückführen muss, weil ein WHILE-Programm eben nur Additionen, IF-Abfragen und WHILE-Statements zulässt. Und eben Register dür die Eingabe [mm] ($R_1$), [/mm] Ausgabe [mm] ($R_0$) [/mm] und Zwischenspeicherung [mm] ($R_n$ [/mm] mit $n>1$).
Mein Problem ist letztendlich "nur" wie ich mit diesen einfachen Mitteln die Berechnung von [mm] $2^x$ [/mm] hinbekomme.
Gruß, Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:35 Fr 23.10.2009 | | Autor: | cycore |
Hi,
also ich kann dir das auch nicht detailliert umsetzen - aber die semantik lässt es doch folgendes zu?:
[mm] x_i:=x_j+x_j
[/mm]
und wenn du das rekursiv x mal machst bekommst du [mm] 2^x
[/mm]
aber wie du das ganze beendest weiß ich auch nicht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:06 Fr 23.10.2009 | | Autor: | stefan00 |
Hallo,
> also ich kann dir das auch nicht detailliert umsetzen -
> aber die semantik lässt es doch folgendes zu?:
> [mm]x_i:=x_j+x_j[/mm]
> und wenn du das rekursiv x mal machst bekommst du [mm]2^x[/mm]
> aber wie du das ganze beendest weiß ich auch nicht
hm, ok, an eine Rekursion habe ich noch nicht gedacht, weil es ja um ein WHILE-Programm geht, da dachte ich an mehrfach ineinander geschachtelte WHILE-Schleifen, ob die Semantik eine Rekursion zulässt, weiß ich nicht, aber prinzipiell sollte das gehen, da hast du schon recht. Das Problem ist ja, dass ich nur Register [mm] $R_n$ [/mm] hoch- und runterzählen darf und nachher im Register [mm] $R_0$ [/mm] das Ergebnis steht. Aber da hakts bei mir noch.
Gruß, Stefan.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:19 Fr 23.10.2009 | | Autor: | stefan00 |
Folgende Lösung:
[mm] $(R_0=1;(\text{WHILE}~R_1 \neq 0~\text{DO}~((Q_1;Q_2);R_1-)))$\\
[/mm]
[mm] $Q_1:=(\text{WHILE}~R_0 \neq 0~\text{DO}~(R_0-;R_2+))$\\
[/mm]
[mm] $Q_2:=(\text{WHILE}~R_2 \neq 0~\text{DO}~(R_2-;R_0+;R_0+))$\\
[/mm]
Dies berechnet [mm] $2^x$.
[/mm]
Gruß, Stefan.
|
|
|
|
