Eine Funktion f fi durch die Regel definiert, dassIteraction for-Schleife
eine Funktion f Schreiben (n) die
Ich schrieb dieses f durch einen iterativen Prozess berechnet. und immer noch nicht richtig. Bitte geben Sie an, wie Sie es beheben können.
def f(n):
if (n<3):
return n
else:
for x in range (n):
a = f(n-1) + 2*f(n-2) + 3*f(n-3)
return (a)
einfach eine Speicher-Cache verwenden:
def f(n):
if n < 3:
return n
a,b,c = 0,1,2
for i in range(n-2):
a,b,c = b,c,c+2*b+3*a
return c
In dieser Funktion wir a verwenden f bezeichnen (n-3), bf (n-2) und c zu bezeichnen, für f (n-1), berechnen wir bei jedem iterativen Schritt f (n) und somit verschieben wir: a wird b, b wird c und c erhält den neuen Wert. Wir tun dies, bis wir die gewünschte n erreicht haben.
Also zunächst berechnen wir f (3). In diesem Fall af (0) = 0 ist, b ist f (1) = 1 und c ist f (2) = 2. Nun nach dieser Iteration a nimmt f (1) = 1, b nimmt f (2) = 2 und c nimmt f (3) = f (2) + 2 × f (1) + 3 × f (0) = 5, und Sie tun das weiter, bis c das Recht n hat.
in der rekursiven Variante Diese da schneller arbeiten, rufen Sie für f(n-2) und f(n-1), aber f(n-1) wird auf seinem Weg Ruf nach f(n-2) somit doppelte Arbeit einzuführen.
Wenn Sie die Funktion wollen erste n Elemente zurückzukehren, können Sie einfach die dynamische Programmierung mit memoization mit O(n) Raum und Zeit verwenden:
def F(n):
f = [0]*n
f[:4] = range(4)
for i in range(4, n):
f[i] = f[i-1] + f[i-2] + f[i-3]
return f
print F(20)
# [0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, 4841, 8904, 16377, 30122, 55403]
heraus Nehmen Sie sich für die Schleife entfernen, x nicht – depperm
Was genau verwendet wird, ist falsch damit? Das 'for x in range' macht nichts; Sie können diese Zeile entfernen. Aber was stimmt nicht mit den Antworten, die dir die Funktion gibt? – TheDrooper
@TheDrooper: Ich denke, es ist aufgebläht: Sie werden eine ganze Call-Struktur mit vielen doppelten Arbeit erstellen. Die zeitliche Komplexität ist exponentiell (auch ohne das 'for'), während iterativ * O (n) * ist. –