Entwurf iterativer Algorithmen.

steve-e · Hält's aus hier Beiträge: 4

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.

markieren

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

Gausi · Verfasst: Fr 13.05.05 16:29

eine Möglichkeit, bei diesem Beispiel:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

nehme ein Array der Länge 4
berechne f(1) auf platz 1
berechne f(2) auf platz 2
berechne f(3) auf platz 3
berechne f(4) auf platz 4

solange "nicht bei n" mache:
    Schiebe alle Ergebnisse im Array eins nach hinten
    Berechne f(nächstes i) auf Platz 4

_________________
We are, we were and will not be.

alzaimar · Verfasst: Sa 14.05.05 10:47

Oder so:

markieren

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.

markieren

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;

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme