steve-e - Fr 13.05.05 16:18
Titel: Entwurf iterativer Algorithmen.
Hi,
ich habe jetzt zum lernen schon mehrere Algorithmen gebildet, doch meists brauch ich sehr lange bis ich auf die Lösung komme. Hier ist wieder so ein Fall, wo ich auf keinen grünen Zweig komme.
Quelltext
1:
2:
3:
| f(n) = n falls n<3
und
f(n) = f(n-1) + 2f(n-2) + 3f(n-3) falls n>=3 |
Rekursive Möglichkeiten fallen mir meist recht schnell ins Auge, doch bei Iterativen hab ich so meine Probleme.
Wie müsste ein iterativer Algorithmus für eine solche Funktion aussehen? (Ich will kein Codebeispiel, nur die Impementierungsidee)
Was kann einem bei der Konstruktion eines iterativen Prozesses helfen? Gibts da irgendetwas was man beachten muss bzw. was einem helfen könnte auf die richtige Fährte zu kommen?
Danke für die Hilfe,
steve
alzaimar - Sa 14.05.05 10:47
Oder so:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| Function f(n : Integer) : Integer;
Var
_f : Array of Integer;
i : Integer;
Begin
if n<3 then
Result := n
else begin
setLength (_f, n);
_f[0] := 0; _f[1] := 1; _f[2] := 2;
For i:=3 to n do
_f[i] := _f[i-1] + 2*_f[i-2] + 3*_f[i-3];
Result := _f[n];
End
End; |
Einfach, benötigt aber Speicher.
Die Alternative verwendet einen Ringbuffer der Länge 4.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
| Function f(n : Integer) : Integer;
Var
_f : Array [0..3] of Integer;
i : Integer;
Begin
if n<3 then
Result := n
else begin
_f[0] := 0; _f[1] := 1; _f[2] := 2;
For i:=3 to n do
_f[i mod 4] := _f[(i+3) mod 4] + 2*_f[(i+2) mod 4] + 3*_f[(i+1) mod 4];
Result := _f[n mod 4];
End
End; |