eines Kettenbruch ist eine Reihe von Unterteilungen dieser Art zu berechnen:optimaler Algorithmus das Ergebnis einer forte Fraktion
depth 1 1+1/s
depth 2 1+1/(1+1/s)
depth 3 1+1/(1+1/(1+1/s))
. . .
. . .
. . .
Die Tiefe ist eine ganze Zahl, aber s ist eine Gleitkommazahl.
Was wäre ein optimaler Algorithmus (leistungsmäßig), um das Ergebnis für einen solchen Bruch mit großer Tiefe zu berechnen?
Hinweis: entrollen jeder dieser Formeln Grund Algebra. Sie werden sehen, dass ein Muster entsteht.
Ich werde Ihnen die ersten Schritte zeigen, so wird es offensichtlich:
f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1)/(s + 1)
/* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2)/(2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3)/(3*s + 2)
...
Hint2: Wenn Sie sehen das offensichtliche Muster Schwellen Form nicht die oben, die optimalste Der Algorithmus würde die Berechnung von Fibonacci-Zahlen beinhalten (Sie müssten also nach dem optimalen Fibonacci # -Generator suchen).
HINWEIS: Ich habe keine grundlegenden Algebra in Englisch gelernt, ich hoffe, ich habe "Nenner" und "Nominator" nicht in den obigen Kommentar gemischt - hoffe, die Formeln sind offensichtlich genug für sich selbst, auch wenn ich die Terminologie verwechselt habe. – DVK
Nein, ich glaube, Sie haben es richtig. Der Zähler ist die Nummer auf "oben" der Division, und der Nenner ist auf der "Unterseite". IE, 2/3 -> Zähler = 2; Nenner = 3 – Daenyth
@Daenyth - Thx! – DVK
Riecht wie Tail-Rekursion (Rekursion (Rekursion (...))).
(Mit anderen Worten - Schleife it)
Im Allgemeinen unterstützt C keine Tail-Rekursion. –
@James Black Aber jeder rekursive Algorithmus kann entrollt werden :-) Er ändert nicht die Laufzeitkomplexität. (Ich argumentiere nicht, dass dies eine gute Antwort für den "optimalen" Algorithmus ist.) –
@James Black: Wie @pst erwähnt, befürworte ich die Umwandlung des tailrekursiven Problems (auf konzeptioneller Ebene) in eine Schleife (auf der Codeebene), was beweisbar ein eher trivialer Prozess ist. Da kommt mein "loop it" -Kommentar rein, obwohl ich denke, dass es klarer hätte sein können. –
würde ich mit der Berechnung 1/s, beginnt die wir a nennen.
Verwenden Sie dann eine for-Schleife, da bei der Verwendung von Rekursion in C möglicherweise ein Stapelüberlauf auftritt.
Da dies Hausaufgaben ist, werde ich nicht viel Code geben, aber, wenn Sie mit einer einfachen Schleife von 1 beginnen, dann erhöhen Sie es, bis Sie zu 4 kommen, dann können Sie einfach zu n-mal gehen.
Da Sie immer teilen werden 1/s und Abteilung ist teuer, nur tun es einmal wird mit der Leistung helfen.
Ich erwarte, dass wenn Sie es herausfinden, Sie tatsächlich ein Muster finden können, das Ihnen helfen wird, weiter zu optimieren.
Sie können einen Artikel wie diesen finden: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/, um hilfreich zu sein.
Ich nehme an performanceweise meinen Sie, dass Sie wollen, dass es schnell ist, unabhängig vom verwendeten Speicher, übrigens.
Sie können feststellen, dass Sie die von Ihnen berechneten Werte bei jedem Schritt zwischenspeichern, sodass Sie sie wiederverwenden können, anstatt eine teure Berechnung zu wiederholen.
Ich würde persönlich 4-5 Schritte von Hand machen, die Gleichungen und Ergebnisse jedes Schrittes ausschreiben und sehen, ob irgendein Muster auftaucht.
Update:
GCC hinzugefügt Endrekursion, und ich habe nie bemerkt es, weil ich versuche, aus Gewohnheit Rekursion stark in C, zu begrenzen. Aber diese Antwort hat eine schöne schnelle Erklärung der verschiedenen Optimierungen, die gcc basierend auf dem Optimierungslevel gemacht hat.
http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s
Ihre Algorithmen sind entschieden nicht optimal, obwohl es die optimale Implementierung dieses speziellen Algorithmus ist. – DVK
@DVK - Ich versuche nicht, den optimalsten Algorithmus zu geben, da es als Hausaufgabe aufgeführt wurde, sondern um einen Weg zu finden, vielleicht einen besseren Algorithmus zu finden, weshalb ich vorgeschlagen habe, mehrere Schritte von Hand zu machen, um ein Muster zu finden , so dass eine Lösung gefunden werden kann, die besser ist als das, was ich vorgeschlagen habe. –
Ich möchte ein wenig auf DVK's excellent answer erarbeiten. Ich bleibe bei seiner Notation f(d,s), um den gesuchten Wert für die Tiefe d zu bezeichnen.
Wenn Sie den Wert f(d,s) für große d berechnen, werden Sie feststellen, dass die Werte konvergieren, wie d erhöht.
Lassen Sie φ = f (∞, s). Das heißt, φ ist das Limit, da d Unendlichkeit nähert, und ist der fortgesetzte Teil vollständig erweitert. Beachten Sie, dass φ eine Kopie von sich selbst enthält, so dass wir φ = 1 + 1/φ schreiben können. Multipliziert man beide Seiten durch φ und Neuordnen, erhalten wir die quadratische Gleichung
φ - φ - 1 = 0
die
erhalten gelöst werden könnenφ = (1 + √ 5)/2.
Dies ist die famous golden ratio.
Sie werden feststellen, dass f(d,s) ist sehr nah an φ als d wird groß.
Aber warte. Es gibt mehr!
Wie DVK darauf hingewiesen hat, beinhaltet die Formel für f(d,s) Begriffe aus der Fibonacci-Sequenz. Insbesondere beinhaltet es Verhältnisse aufeinanderfolgender Terme der Fibonacci-Sequenz. Es gibt eine closed form expression for the nth term of the sequence, nämlich
(φ n - (1- φ) n)/√ 5.
Da 1- φ kleiner als eins ist, (1- φ) n wird klein, da n wird groß, so eine gute Näherung für die n-te Fibonacci ist φ n/√ 5. Und zurück zur DVK Formel, wird das Verhältnis der aufeinander folgenden Begriffe in der Fibonacci-Folge zuneigenn + 1/φ n = φ.
Das ist ein zweiter Weg, um zu der Tatsache zu kommen, dass der fortgesetzte Bruch in dieser Frage φ ergibt.
dies ist keine Hausaufgaben, weil meine Schule letzten Juli geschlossen ist, jetzt sitze ich in meinem Haus und ich versuche nur ein Problem zu lösen –
Da wirst du höchstwahrscheinlich selbst das lösen wollen, für den besten Lerneffekt, denke ich Es ist gut, diese Frage so zu behandeln, als wären es Hausaufgaben. – Svante