Keine Ahnung, wie zu lösen SICP übung 1.11
https://stackoverflow.com/questions/2365993
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Eine Funktion
fist definiert durch die Regel, dassf(n) = nwennn < 3undf(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)wennn > 3.Schreiben Sie eine Prozedur berechnet, dassfmittels einer rekursiven Prozess.Schreiben Sie eine Prozedur berechnet, dassfdurch einen iterativen Prozess.
Durchführung von it-rekursiv ist einfach genug.Aber ich konnte nicht herausfinden, wie es zu tun iterativ.Ich habe versucht, den Vergleich mit dem Fibonacci-Beispiel, aber ich nicht wissen, wie zu verwenden Sie es als eine Analogie.So gab ich (Schande über mich) und Gegoogelt für eine Erklärung, und ich fand das:
(define (f n)
(if (< n 3)
n
(f-iter 2 1 0 n)))
(define (f-iter a b c count)
(if (< count 3)
a
(f-iter (+ a (* 2 b) (* 3 c))
a
b
(- count 1))))
Nach dem Lesen, ich verstehe den code und wie es funktioniert.Aber was ich nicht verstehe, ist der Prozess musste aus der rekursiven definition der Funktion dieser.Ich weiss nicht, wie der code könnte sich gebildet haben, in jemandes Kopf.
Könnten Sie erklären die Gedanken-Prozess benötigt, um auf die Lösung kommst?
Lösung
Sie müssen den Zustand, in einigen Akkumulatoren erfassen und den Zustand bei jeder Iteration zu aktualisieren.
Wenn Sie Erfahrung in einer imperativen Sprache haben, stellen Sie sich eine while-Schleife zu schreiben und während jeder Iteration der Schleife in Variablen-Tracking-Informationen. Welche Variablen würden Sie brauchen? Wie würden Sie sie aktualisieren? Das ist genau das, was man eine iterative (Schwanz-rekursiv) Gruppe von Anrufen in Schema zu tun hat, zu machen.
Mit anderen Worten, könnte es helfen, denkt dies als eine while-Schleife zu starten, anstatt eine rekursiven Definition. Irgendwann werden Sie fließend genug, um mit rekursiv sein. -> iterative Transformationen, dass Sie nicht auf zusätzliche Hilfe benötigen, um loszulegen
Für dieses spezielle Beispiel, müssen Sie an den drei Funktionsaufrufen genau hinsehen, denn es ist nicht sofort klar ist, wie sie zu vertreten. Aber hier ist der wahrscheinlich Denkprozess: (in Python Pseudo-Code den Imperativ zu betonen)
Jeder rekursive Schritt verfolgt drei Dinge:
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)
Also brauche ich drei Stücke Zustand den Strom zu verfolgen, die letzte und die vorletzte Werte von f. (Das heißt, f(n-1), f(n-2) and f(n-3).) Nennen sie a, b, c. Ich muss diese Stücke in jeder Schleife aktualisieren:
for _ in 2..n:
a = NEWVALUE
b = a
c = b
return a
Also, was ist NEWVALUE? Nun, da wir Darstellungen von f(n-1), f(n-2) and f(n-3) haben, es ist nur die rekursive Gleichung:
for _ in 2..n:
a = a + 2 * b + 3 * c
b = a
c = b
return a
Jetzt alles, was übrig bleibt, ist die Anfangswerte von a, b and c herauszufinden. Aber das ist einfach, da wir diese f(n) = n if n < 3 kennen.
if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
a = a + 2 * b + 3 * c
b = a
c = b
return a
Das ist immer noch ein wenig anders aus dem Schema iterativen Version, aber ich hoffe, dass Sie jetzt den Denkprozess sehen.
Andere Tipps
Ich denke, Sie Fragen sich, wie man vielleicht entdecken Sie den Algorithmus natürlich außerhalb der "design pattern".
War es hilfreich für mich zu sehen der Ausweitung der f(n) zu jedem n-Wert:
f(0) = 0 |
f(1) = 1 | all known values
f(2) = 2 |
f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)
Suchen Sie näher an f(3), sehen wir, dass wir es sofort berechnen kann aus den bekannten Werten.Was müssen wir tun, um berechnen Sie f(4)?
Wir müssen mindestens berechnen Sie f(3) + [rest].Aber wie berechnen wir f(3), berechnen wir f(2) und f(1), als auch, was wir gerade brauchen für die Berechnung von [den rest] f(4).
f(3) = f(2) + 2f(1) + 3f(0)
↘ ↘
f(4) = f(3) + 2f(2) + 3f(1)
So, für jede Zahl n, kann ich beginnen mit der Berechnung von f(3), und verwenden Sie die Werte aus, die ich verwenden, um zu berechnen, f(3) zu berechnen, f(4)...und das Muster geht weiter...
f(3) = f(2) + 2f(1) + 3f(0)
↘ ↘
f(4) = f(3) + 2f(2) + 3f(1)
↘ ↘
f(5) = f(4) + 2f(3) + 3f(2)
Da werden wir, um Sie wiederzuverwenden, können geben Sie einen Namen ein, b, c.gelesen werden Sie mit dem Schritt, den wir auf, und gehen Sie durch eine Berechnung von f(5):
Step 1: f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a1 + 2b1 +3c1
wo
ein1 = f(2) = 2,
b1 = f(1) = 1,
c1 = 0
da f(n) = n für n n n n < 3.
Also:
f(3) = a1 + 2b1 + 3c1 = 4
Step 2: f(4) = f(3) + 2a1 + 3b1
Also:
ein2 = f(3) = 4 (oben berechnet in Schritt 1),
b2 = a1 = f(2) = 2,
c2 = b1 = f(1) = 1
Also:
f(4) = 4 + 2*2 + 3*1 = 11
Step 3: f(5) = f(4) + 2a2 + 3b2
Also:
ein3 = f(4) = 11 (berechnet in Schritt 2 weiter oben),
b3 = a2 = f(3) = 4,
c3 = b2 = f(2) = 2
Also:
f(5) = 11 + 2*4 + 3*2 = 25
Während des oben beschriebenen Berechnung, die wir erfassen Zustand im vorherigen Berechnung und übergeben Sie es an den nächsten Schritt, insbesondere:
einSchritt = Ergebnis von Schritt 1
bSchritt = aSchritt 1
cSchritt = bSchritt 1
Sobald ich das sah, dann die iterative version war unproblematisch.
Da der Beitrag, den Sie in Verbindung mit viel über die Lösung beschreibt, ich werde versuchen, nur ergänzende Informationen zu geben.
Sie versuchen, eine Schwanz-rekursive Funktion in Schema definieren hier, da ein (nicht-tail) rekursive Definition.
Basisfall der Rekursion (f (n) = n, wenn n <3) durch beiden Funktionen behandelt. Ich bin nicht wirklich sicher, warum der Autor dies tut; die erste Funktion könnte einfach sein:
(define (f n)
(f-iter 2 1 0 n))
Die allgemeine Form wäre:
(define (f-iter ... n)
(if (base-case? n)
base-result
(f-iter ...)))
Hinweis: Ich habe füllen nicht in Parameter für die f-iter noch, da müssen Sie zuerst verstehen, was den Bedarf des Staates von einer Iteration zur nächsten weitergegeben werden.
Lassen Sie uns nun einen Blick auf die Abhängigkeiten der rekursiven Form von f (n). Es Referenzen f (n - 1), f (n - 2), und f (n - 3), so dass wir diese Werte zu halten, um brauchen. Und natürlich müssen wir den Wert von n selbst, so dass wir Iterieren über sie stoppen kann.
Das ist also, wie Sie mit dem Schwanz-rekursive Aufruf kommen: Wir berechnen f (n) als f zu verwenden (n - 1), drehen sie f (n - 1) bis f (n - 2) und f (n - 2) bis f (n -. 3) und Dekrement Zahl
Wenn dies immer noch nicht hilft, versuchen Sie eine spezifischere Fragen an -. Es ist wirklich schwer zu beantworten, wenn Sie schreiben: „Ich verstehe nicht,“ schon eine relativ ausführliche Erklärung gegeben
Ich werde auf diesem in einem etwas anderen Ansatz zu den anderen Antworten, hierher kommen, darauf konzentriert, wie Stil Codierung den Denkprozess hinter einem Algorithmus wie dies leichter verständlich machen.
Das Problem mit Bills Ansatz , in Ihrer Frage zitiert , ist, dass es nicht sofort klar, was Sinn durch die Zustandsvariablen gefördert wird, a, b und c. Ihre Namen vermitteln keine Information, und Bills Beitrag beschreibt keine unveränderliche oder andere Regel, dass sie gehorchen. Ich finde es einfacher zu formulieren und iterative Algorithmen zu verstehen, wenn die Zustandsvariablen einige dokumentierte Regeln, die beschreiben ihre Beziehungen zueinander zu gehorchen.
In diesem Sinne, sollten Sie diese alternative Formulierung des gleichen Algorithmus, der sich von Bills nur mit sinnvoller Variablennamen für a, b und c und ein Erhöhen Zählervariable anstelle eines Erniedrigen ein:
(define (f n)
(if (< n 3)
n
(f-iter n 2 0 1 2)))
(define (f-iter n
i
f-of-i-minus-2
f-of-i-minus-1
f-of-i)
(if (= i n)
f-of-i
(f-iter n
(+ i 1)
f-of-i-minus-1
f-of-i
(+ f-of-i
(* 2 f-of-i-minus-1)
(* 3 f-of-i-minus-2)))))
Auf einmal die Richtigkeit der Algorithmus - und der Denkprozess hinter seiner Schöpfung - ist einfach zu sehen und zu beschreiben. Zur Berechnung f(n):
- Wir haben eine Zählvariable
idass beginnt bei 2 und steigt aufn, bei jedem Aufruf vonf-iterum 1 erhöht wird. - Bei jedem Schritt auf dem Weg, verfolgen wir
f(i),f(i-1)undf(i-2), die ausreichend ist, unsf(i+1)zu berechnen können. - Sobald
i=n, sind wir fertig.
Eine Funktion
fwird von der Regel, dassf(n) = n, if n<3undf(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3definiert. Schreibe eine Prozedur, die berechnet mittels eines rekursiven Prozessf.
Es is bereits geschrieben:
f(n) = n, (* if *) n < 3
= f(n - 1) + 2f(n - 2) + 3f(n - 3), (* if *) n > 3
Ob Sie es glauben oder nicht, war es einmal eine solche Sprache . Um diese nach unten in einer anderen Sprache zu schreiben, ist nur eine Frage der Syntax. Und übrigens, die Definition, wie Sie (mis) zitiert sie einen Fehler hat, die nun sehr deutlich und klar ist.
Schreiben ein Verfahren, das berechnet mit Hilfe eines iterativen Prozesses
f.
gehen vorwärts ( es gibt Ihre Erklärung) in Bezug auf die Rekursion Gegensatz los zurück zuerst:
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)
= a + 2b + 3c
f(n+1) = f(n ) + 2f(n - 1) + 3f(n - 2)
= a' + 2b' + 3c' a' = a+2b+3c, b' = a, c' = b
......
Dies beschreibt somit die Zustandsübergänge des Problems als
(n, a, b, c) -> (n+1, a+2*b+3*c, a, b)
Wir könnten es codieren als
g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)
, aber natürlich wäre es nicht immer zu stoppen. So müssen wir stattdessen
habenf n = g (2, 2, 1, 0)
where
g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b), (* if *) k < n
g (k, a, b, c) = a, otherwise
und das ist schon genau, wie der Code, den Sie gefragt, bis zu Syntax.
Zählen bis zu n ist hier natürlich, nach unserem Paradigma der „going forward“, sondern das Zählen bis zu 0 wie der Code, den Sie tut zitieren ist natürlich völlig äquivalent.
Die Ecke Fälle und mögliche Off-by-one Fehler ausgelassen wie Bewegung nicht interessant technisch.
