Binärbaum < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:58 So 08.05.2016 | | Autor: | Mina123 |
| Aufgabe | | Ich soll in Maple eine Prozedur schreiben, die rekursiv einen Binärbaum auswertet. Leider durchläuft die Prozedur nur den linken Teilbaum, wie komme ich an die rechte Seite? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Das ist mein Programmiercode bisher:
Prodtree := proc(f,u,k)
# Prozedur berechnet den Baum top-down, divide-and-conquer Algorithmus
# berechnet [mm] f(u_0),..., f(u_n-1) [/mm] = [mm] r_0(u_0),..., r_1(u_n-1)
[/mm]
# n ist der Grad von f
global M;
local r0;
local r1;
local n;
[mm] n:=2^k;
[/mm]
if n=1 then
return f;
else
r0:=rem(f,M[k-1,0],x); #berechnet den Rest für links
r1:=rem(f,M[k-1,1],x); #berechnet den Rest für rechts
Prodtree(r0,u[1..n/2],k-1); #linke Baumhälfte
Prodtree(r1,u[n/2+1..n],k-1); #rechte Baumhälfte
print(r0);
print(r1);
fi;
end:
Mit u[1..n/2] bzw. u[n/2+1..n] versuche ich die Rekursion auf eine Baumhälfte einzuschränken, das funktioniert aber leider nicht. M hole ich mir aus einer vorherigen Prozedur. Gerechnet wird nur die linke Baumhälfte, da die zweite Komponente von M mit 0 und 1 fix ist!?
Kann mir jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:28 Mo 09.05.2016 | | Autor: | felixf |
Moin!
> Ich soll in Maple eine Prozedur schreiben, die rekursiv
> einen Binärbaum auswertet. Leider durchläuft die Prozedur
> nur den linken Teilbaum, wie komme ich an die rechte
> Seite?
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Das ist mein Programmiercode bisher:
>
> Prodtree := proc(f,u,k)
> # Prozedur berechnet den Baum top-down, divide-and-conquer
> Algorithmus
> # berechnet [mm]f(u_0),..., f(u_n-1)[/mm] = [mm]r_0(u_0),..., r_1(u_n-1)[/mm]
>
> # n ist der Grad von f
> global M;
> local r0;
> local r1;
> local n;
>
> [mm]n:=2^k;[/mm]
>
> if n=1 then
> return f;
> else
>
> r0:=rem(f,M[k-1,0],x); #berechnet den Rest für links
> r1:=rem(f,M[k-1,1],x); #berechnet den Rest für rechts
>
> Prodtree(r0,u[1..n/2],k-1); #linke Baumhälfte
> Prodtree(r1,u[n/2+1..n],k-1); #rechte Baumhälfte
>
> print(r0);
> print(r1);
>
> fi;
> end:
>
> Mit u[1..n/2] bzw. u[n/2+1..n] versuche ich die Rekursion
> auf eine Baumhälfte einzuschränken, das funktioniert aber
> leider nicht. M hole ich mir aus einer vorherigen Prozedur.
> Gerechnet wird nur die linke Baumhälfte, da die zweite
> Komponente von M mit 0 und 1 fix ist!?
Du hast das Problem richtig erkannt. Deswegen brauchst du weitere Parameter für die Funktion, die dir sagen wie du die zweite Komponente von $M$ wählen musst.
> Kann mir jemand helfen?
Genauer helfen können wir dir nur, wenn wir mehr über $M$ wissen.
LG Felix
PS: Die Funktion gibt nur im Fall $n = 1$ etwas zurück. Du willst vermutlich eine Liste der ausgewerteten Punkte zurückgeben; dazu musst du die Ergebnisse vom rekursiven Prodtree-Aufruf speichern und kombinieren.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:54 Mi 11.05.2016 | | Autor: | Mina123 |
Hallo Felix;
Die M[i,j] sehen so aus, dass die Wurzel M[k,0] zugewiesen bekommt und dann binär aufgeteilt wird, dh. auf der zweiten Stufe habe ich M[k-1,0] und M[k-1,1], auf der dritten Stufe M[k-2,0], M[k-2,1], M[k-2,2] und M[k-2,3], etc. Dies habe ich mit folgender Prozedur berechnet:
Building:=proc(u,k)
#berechnet M[i,j]
global M;
local m;
local n;
local i;
local j;
[mm] n:=2^k;
[/mm]
m:=array(0..n-1);
M:=array(0..k,0..n-1);
for j from 0 to n-1 do
m[j]:=x-u[j+1];
M[0,j]:=m[j];
od;
for i from 1 to k do
for j from 0 to 2^(k-1)-1 do
M[i,j]:=expand(M[i-1,2*j]*M[i-1,2*j+1]);
od;
od;
return(M);
end:
z.B. für u=[1,2,3,4,5,6,7,8] und k=3 (also Building([1,2,3,4,5,6,7,8],3);) ergibt dies auch die richtigen Werte. Um die M's in der nächsten Prozedur Prodtree weiter verwenden zu können, habe ich sie global definiert.
Ich habe versucht, die M's in Prodtree entsprechend einzuschränken und ein zusätzliches j hinzugenommen. Für die Rekursion ergibt sich dann:
[mm] Prodtree(r0,M[k,0..2^j-1],u,k-1,j+1);
[/mm]
[mm] Protree(r1,M[k,2^j..2^{j+1}-1],u,k-1,j+1);
[/mm]
Leider gibt die Prozedur [mm] Prodtree(x^8-7*x+12,M,[1,2,3,4,5,6,7,8],3,1); [/mm] viele 0'en und dann nur für M[k-1,0] und M[k-1,1] die richtigen Werte aus. Wo liegt mein Fehler?
Vielen Dank für Deine Hilfe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:21 Sa 14.05.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:36 Di 17.05.2016 | | Autor: | Mina123 |
Ich bin weiterhin an einer Antwort interessiert.
|
|
|
|
