O Kalkül Zeitaufwand < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:26 Fr 07.01.2011 | | Autor: | anno |
| Aufgabe | Betrachten Sie folgende rekursiv definierte Funktion mit dem Namen pluto.
pluto(a, b) [mm] =\begin{cases} 0 & a > b \\ 1 & a = b \\ pluto(a, \bruch{a+b}{2}) + pluto(\bruch{a+b}{2}, b) & a < b \end{cases}
[/mm]
a und b sind ganze positive Zahlen.
Es sei n := b. Geben Sie den Wert von a im schlimmsten Fall f ̈r den Zeitaufwand T (n) der
u
Funktion an. |
Wie gebe ich denn hier den Wert für a an?
Könnte das hier richtig sein?
T(n) = T((a+n)/2) + T(n)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:32 Fr 07.01.2011 | | Autor: | felixf |
Moin!
> Betrachten Sie folgende rekursiv definierte Funktion mit
> dem Namen pluto.
>
> pluto(a, b) [mm]=\begin{cases} 0 & a > b \\ 1 & a = b \\ pluto(a, \bruch{a+b}{2}) + pluto(\bruch{a+b}{2}, b) & a < b \end{cases}[/mm]
Wird beim Berechnen von [mm] $\frac{a + b}{2}$ [/mm] irgendwie gerundet? Wenn nicht, dann ist die Funktion fuer $a < b$ gar nicht definiert.
> Es sei n := b. Geben Sie den Wert von a im schlimmsten Fall
> f ̈r den Zeitaufwand T (n) der
> u
> Funktion an.
Das liest sich recht holprig. Man soll also fuer festes $b$ einen Wert von $a$ angeben, so dass $pluto(a, b)$ maximal ist?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:50 Fr 07.01.2011 | | Autor: | anno |
Also, ich habe noch in der Aufgabe etwas ergänzt, was gefehlt hat. a und b sind ganze Zahlen.
Also mehr steht da jetzt auch nicht in der Aufgabe. Aber wenn man sich da mal einen Aufrufbaum der Funktion hin malt, dann bekommt man da einen einen endlosen Baum für pluto(1,4).
Vielleicht hat es ja was damit zu tun.
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:05 Fr 07.01.2011 | | Autor: | anno |
| Aufgabe | | Es sei n := b. Geben Sie die Rekurrenzgleichung für den Zeitwaufwand T(n) der Funktion im schlimmsten Fall an. (also der pluto Funktion) |
ok, dann vielleicht etwas anderes, genauer eine andere Aufgabe davon.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:24 So 09.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:51 Fr 07.01.2011 | | Autor: | felixf |
Moin!
> Also, ich habe noch in der Aufgabe etwas ergänzt, was
> gefehlt hat. a und b sind ganze Zahlen.
>
> Also mehr steht da jetzt auch nicht in der Aufgabe. Aber
> wenn man sich da mal einen Aufrufbaum der Funktion hin
> malt, dann bekommt man da einen einen endlosen Baum für
> pluto(1,4).
Genau, das ist das Problem. Man bekommt sogar einen endlosen Baum fuer alle $pluto(a, b)$ mit $a < b$.
Wenn jedoch [mm] $\frac{a + b}{2}$ [/mm] auf eine ganze Zahl gerundet wird (egal wie nun genau), dann wuerde das sehr wohl abbrechen und man koennte etwas darueber aussagen.
Vielleicht fehlt das einfach in der Aufgabenstellung? Eventuell kontaktiere mal den Uebungsleiter oder wer auch immer dafuer zustaendig ist 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:24 So 09.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
