Also habe ich versucht, die n- te Zahl in der Fibonacci-Folge so kompakt wie möglich zu schreiben :
public uint fibn ( uint N )
{
return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}
Aber ich frage mich, ob ich dies durch Ändern noch kompakter und effizienter machen kann
(N == 0 || N == 1)
in einen einzigen Vergleich. Gibt es eine ausgefallene Bitverschiebungsoperation, die dies kann?
c#
algorithm
optimization
arithmetic-expressions
user6048670
quelle
quelle
fibn(N-1) + fibn(N-2)
stattN * fibn(N-1)
?Antworten:
Dieser funktioniert auch
Die Quadratwurzel von 0 und 1 gibt 0 bzw. 1 zurück.
quelle
Math.Sqrt
ist eine komplizierte Gleitkommafunktion. Es läuft langsam im Vergleich zu den Nur-Ganzzahl-Alternativen !!Es gibt verschiedene Möglichkeiten, Ihren arithmetischen Test mit bitweiser Arithmetik zu implementieren. Dein Ausdruck:
x == 0 || x == 1
ist logisch äquivalent zu jedem dieser:
(x & 1) == x
(x & ~1) == 0
(x | 1) == 1
(~x | 1) == (uint)-1
x >> 1 == 0
Bonus:
x * x == x
(Der Beweis erfordert ein wenig Mühe)In der Praxis sind diese Formen jedoch am besten lesbar, und der winzige Leistungsunterschied ist es nicht wirklich wert, bitweise zu rechnen:
x == 0 || x == 1
x <= 1
(weilx
eine vorzeichenlose Ganzzahl ist)x < 2
(weilx
eine vorzeichenlose Ganzzahl ist)quelle
(x & ~1) == 0
x == 0 || x == 1
als für(x & ~1) == 0
oder(x | 1) == 1
. Für das erste ist es klug genug, es als gleichwertig zu erkennenx <= 1
und ein einfaches auszugebencmpl; setbe
. Die anderen verwirren es und lassen es schlechteren Code erzeugen.Da das Argument
uint
( ohne Vorzeichen ) ist, können Sie setzenWeniger lesbar (IMHO), aber wenn Sie jeden Charakter zählen ( Code Golf oder ähnlich)
Bearbeiten : für Ihre bearbeitete Frage :
Oder
quelle
return N<2?1:f(N-1)+f(n-2)
. : PSie können auch überprüfen, ob alle anderen Bits wie folgt 0 sind:
Der Vollständigkeit halber dank Matt die noch bessere Lösung:
In beiden Fällen müssen Sie sich um die Klammern kümmern, da bitweise Operatoren eine niedrigere Priorität als haben
==
.quelle
(N|1)==1
Wenn Sie die Funktion effizienter gestalten möchten, verwenden Sie eine Nachschlagetabelle. Die Nachschlagetabelle ist mit nur 47 Einträgen überraschend klein - der nächste Eintrag würde eine 32-Bit-Ganzzahl ohne Vorzeichen überlaufen. Es macht natürlich auch die Funktion trivial zu schreiben.
Sie können natürlich das Gleiche für Fakultäten tun.
quelle
Wie es mit Bitshift geht
Wenn Sie Bitshift verwenden und den Code etwas dunkel (aber kurz) machen möchten, können Sie Folgendes tun:
Bei einer vorzeichenlosen Ganzzahl
N
in der Sprache cN>>1
wird das Bit niedriger Ordnung weggeworfen. Wenn dieses Ergebnis ungleich Null ist, bedeutet dies, dass N größer als 1 ist.Hinweis: Dieser Algorithmus ist schrecklich ineffizient, da er Werte in der bereits berechneten Sequenz unnötig neu berechnet.
Etwas viel schneller
Berechnen Sie es in einem Durchgang, anstatt implizit einen Fibonaci (N) -großen Baum zu bauen:
Wie einige Leute bereits erwähnt haben, dauert es nicht lange, bis eine 64-Bit-Ganzzahl ohne Vorzeichen überläuft. Je nachdem, wie groß Sie werden möchten, müssen Sie Ganzzahlen mit beliebiger Genauigkeit verwenden.
quelle
uint
nicht implizit in C # umgewandelt werdenbool
kann und die Frage speziell als C # gekennzeichnet ist.--N != 0
stattdessen tun . Der Punkt ist, dass etwas O (n) O (fibn (n)) vorzuziehen ist.Wenn Sie eine Uint verwenden, die nicht negativ werden kann, können Sie überprüfen, ob
n < 2
BEARBEITEN
Oder für diesen speziellen Funktionsfall können Sie ihn wie folgt schreiben:
Dies führt natürlich zum gleichen Ergebnis auf Kosten eines zusätzlichen Rekursionsschritts.
quelle
1 * fibn(0) = 1 * 1 = 1
fibn
Überprüfen Sie einfach, ob
N
<= 1 ist, da Sie wissen, dass N ohne Vorzeichen ist. Es kann nur 2 Bedingungen geben,N <= 1
die zu folgenden Ergebnissen führenTRUE
: 0 und 1quelle
(N == 0 || N == 1)
. Sie wissen, dass es nicht kleiner als 0 sein wird (denn dann würde es signiert sein!), Und das Maximum könnte 1 sein.N <= 1
Vereinfacht es. Ich denke, der nicht signierte Typ ist nicht garantiert, aber das sollte woanders gehandhabt werden, würde ich sagen.int N
und Sie den ursprünglichen Zustand beibehalten würden, es unendlich wiederkehren würde, wenn N mit seinem ursprünglichen Zustand negativ ist. Da dies ein undefiniertes Verhalten ist, müssen wir uns darüber keine Sorgen machen. Wir können also davon ausgehen, dass N unabhängig von der Deklaration nicht negativ ist.Haftungsausschluss: Ich kenne C # nicht und habe diesen Code nicht getestet:
Keine Notwendigkeit für Bit-Shifting oder ähnliches, dies verwendet nur einen Vergleich und es sollte viel effizienter sein (O (n) gegen O (2 ^ n), denke ich?). Der Hauptteil der Funktion ist kompakter , endet jedoch mit der Deklaration etwas länger.
(Um Overhead von der Rekursion zu entfernen, gibt es die iterative Version, wie in Mathew Gunns Antwort )
PS: Dies ist ein gängiges Funktionsmuster für die Iteration mit Akkumulatoren. Wenn Sie ersetzen
N--
mitN-1
Sie keine Mutation effektiv verwenden, die sie verwendbar in einem reinen funktionalen Ansatz macht.quelle
Hier ist meine Lösung, es gibt nicht viel in der Optimierung dieser einfachen Funktion, andererseits biete ich hier Lesbarkeit als mathematische Definition der rekursiven Funktion an.
Die mathematische Definition der Fibonacci-Zahl in ähnlicher Weise.
Nehmen Sie es weiter, um das Switch-Gehäuse zum Erstellen einer Nachschlagetabelle zu zwingen.
quelle
switch
wenn Sie eine Reihe von Antworten haben können?für N ist uint, benutze einfach
quelle
Dmitrys Antwort ist am besten, aber wenn es sich um einen Int32-Rückgabetyp handelt und Sie einen größeren Satz von Ganzzahlen zur Auswahl haben, können Sie dies tun.
quelle
List.Contains
ist O (n), 3) einfach zwei Vergleiche durchzuführen (N > -3 && N < 3
) würde kürzeren und besser lesbaren Code ergeben.Die Fibonacci-Sequenz ist eine Reihe von Zahlen, bei denen eine Zahl gefunden wird, indem die beiden Zahlen davor addiert werden. Es gibt zwei Arten von Ausgangspunkten: ( 0,1 , 1,2, ..) und ( 1,1 , 2,3).
Die Position
N
beginnt in diesem Fall ab1
, sie ist kein0-based
Array-Index.Mit der C # 6-Expression-Body-Funktion und Dmitrys Vorschlag zum ternären Operator können wir eine einzeilige Funktion mit korrekter Berechnung für den Typ 1 schreiben:
und für den Typ 2:
quelle
Etwas spät zur Party, aber du könntest es auch tun
(x==!!x)
!!x
konvertiert den a-Wert in,1
wenn dies nicht der Fall ist0
, und belässt ihn bei,0
wenn dies der Fall ist.Ich benutze diese Art von Dingen oft in der C-Verschleierung.
Hinweis: Dies ist C, nicht sicher, ob es in C # funktioniert
quelle
uint n = 1; if (n == !!n) { }
gibtOperator '!' cannot be applied to operand of type 'uint'
auf den!n
# in C. Nur weil etwas in C funktioniert, heißt das nicht, dass es in C # funktioniert.#include <stdio.h>
funktioniert sogar nicht in C #, da C # nicht über die Präprozessor-Direktive "include" verfügt. Die Sprachen sind unterschiedlicher als C und C ++.Also habe ich eine
List
dieser speziellen Ganzzahlen erstellt und geprüft, obN
sie dazu gehört.Sie können auch eine Erweiterungsmethode für verschiedene Zwecke verwenden,
Contains
die nur einmal aufgerufen wird (z. B. wenn Ihre Anwendung gestartet wird und Daten lädt). Dies bietet einen klareren Stil und verdeutlicht die primäre Beziehung zu Ihrem Wert (N
):Wende es an:
Dies ist vielleicht nicht der schnellste Weg, aber für mich scheint es ein besserer Stil zu sein.
quelle