Wie Rekursionsrelationen in Mathematica effizient berechnen?
-
10-10-2019 - |
Frage
Ich habe eine Rekursion zu lösen.
f(m,n)=Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]
f(0,n)=1, f(1,n)=n
Allerdings ist der folgende mma-Code ist sehr ineffizient
f[m_, n_] := Module[{},
If[m < 0, Return[0];];
If[m == 0, Return[1];];
If[m == 1, Return[n];];
Return[Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]];]
Es dauert unerträglich lange zu berechnen f [40,20]. Könnte jemand bitte vorschlagen dies eine effiziente Art und Weise zu tun? Vielen Dank!
Lösung
ist Standard-Trick Zwischenwerte zu speichern. Im Folgenden nimmt 0.000025 Sekunden
f[m_, n_] := 0 /; m < 0;
f[0, n_] := 1;
f[1, n_] := n;
f[m_, n_] := (f[m, n] =
Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2,
n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]);
AbsoluteTiming[f[40, 20]]
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow