Bin ich eine Fibonacci-Nummer?

49

Deine Aufgabe:

Schreiben Sie ein Programm oder eine Funktion, um zu überprüfen, ob eine eingegebene Zahl eine Fibonacci-Zahl ist . Eine Fibonacci-Zahl ist eine Zahl, die in der Fibonacci-Folge enthalten ist.

Die Fibonacci-Sequenz ist definiert als: F(n) = F(n - 1) + F(n - 2)

Mit den Samen wird F(0) = 0und F(1) = 1.

Eingang:

Eine nicht negative ganze Zahl zwischen 0 und 1.000.000.000, die eine Fibonacci-Zahl sein kann oder nicht.

Ausgabe:

Ein wahrer / falscher Wert, der angibt, ob die Eingabe eine Fibonacci-Zahl ist oder nicht.

Beispiele:

0-->truthy
1-->truthy
2-->truthy
12-->falsy

Wertung:

Dies ist , die niedrigste Byte-Anzahl gewinnt.

Gryphon - Setzen Sie Monica wieder ein
quelle
2
Die von mir verwendete Programmiersprache unterstützt nur Zahlen bis 9999 (Geometry Dash). Ist es in Ordnung, wenn ich davon ausgehe, dass es theoretisch Nummern bis 1000000 unterstützt?
MilkyWay90

Antworten:

36

Neim , 2 Bytes

f𝕚

Erläuterung:

f       Push an infinite fibonacci list
 𝕚      Is the input in that list?

Funktioniert genauso wie meine Antwort auf " Es ist hip, quadratisch zu sein" , verwendet jedoch eine andere unendliche Liste f:, für Fibonacci.

Versuch es!

Okx
quelle
1
Beeindruckend! Beeindruckende Punktzahl.
Gryphon - Wiedereinsetzung von Monica am
2
Das ist toll, aber nicht 2 Bytes. In UTF-8 ist es als "66 F0 9D 95 9A" dargestellt
sm4rk0
10
@ sm4rk0 Das ist toll, aber du liegst falsch. Neim verwendet eine benutzerdefinierte Codepage , daher lautet die Byte-Darstellung hiervon66 D5
Okx
Ist diese Schleife nicht für immer, wenn die Eingabe nicht in der Liste enthalten ist? Wenn ja, zählt das als Falschgeld?
Enrico Borba
@EnricoBorba Neim weiß, dass das n-te Element in dieser unendlichen Liste immer gleich oder kleiner als das n + 1-te Element in der Liste ist. Daher kann es sich selbst fangen und es wird nicht für immer laufen. Hast du das Programm ausprobiert? : P
Okx
18

JavaScript (ES6), 34 Byte

f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

Generiert rekursiv die Fibonacci-Sequenz, bis ein Element gefunden wird, das größer oder gleich der Eingabe ist, und gibt dann die Eingabe item == zurück.

ETHproductions
quelle
NB: naive rekursive Berechnung der Fibonacci-Sequenz ist O (Fib (n)) - ungefähr O (1,6 ^ n)
Alnitak
f = n => n - n> 2 - f (n - 1) + f (n - 2): 1: 0 28 Bytes
jackkav
@jackkav Danke, aber die Herausforderung besteht darin , zu bestimmen , ob der Eingang ist eine Fibonacci - Zahl.
ETHproductions
12

Netzhaut , 23 Bytes

^$|^(^1|(?>\2?)(\1))*1$

Probieren Sie es online!

Eingabe in unary, Outputs 0oder 1.

Erläuterung

Die Fibonacci-Sequenz ist ein guter Kandidat für eine Lösung mit Vorwärtsreferenzen, dh einer "Rückreferenz", die sich entweder auf eine umgebende Gruppe oder auf eine Gruppe bezieht, die später im regulären Ausdruck erscheint (in diesem Fall verwenden wir tatsächlich beide). Wenn wir Zahlen wie diese abgleichen, müssen wir einen rekursiven Ausdruck für den Unterschied zwischen Sequenzelementen finden. Um beispielsweise Dreieckszahlen abzugleichen, stimmen wir normalerweise mit dem vorherigen Segment plus eins überein. Um quadratische Zahlen abzugleichen (deren Unterschiede ungerade sind), stimmen wir mit dem vorherigen Segment plus zwei überein.

Da wir die Fibonacci-Zahlen erhalten, indem wir das vorletzte Element zum letzten addieren, sind die Unterschiede zwischen ihnen auch nur die Fibonacci-Zahlen. Wir müssen also jedes Segment als die Summe der beiden vorherigen Segmente abgleichen. Der Kern des Regex ist:

(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

Nun werden die Fibonacci-Zahlen beginnend mit 1 , dh 1, 1, 2, 3, 5, ... addiert . Diejenigen Add bis zu 1, 2, 4, 7, 12, ... . Dh sie sind eins weniger als die Fibonacci-Zahlen, also fügen wir 1am Ende ein hinzu. Der einzige Fall, den dies nicht abdeckt, ist Null, daher haben wir ^$zu Beginn die Alternative, dies abzudecken.

Martin Ender
quelle
2
Sehr elegant! Ich möchte der Vollständigkeit halber darauf hinweisen, dass es in PCRE mit einem besitzergreifenden Quantifizierer auf 20 Bytes verkürzt werden kann:^$|^(^1|\2?+(\1))*1$
Deadcode
1
@Deadcode Ich vermisse die in .NET sehr;)
Martin Ender
Sparen Sie 1 Byte, indem Sie die unnötige Sekunde entfernen ^.
Neil
12

Regex (ECMAScript-Variante), 392 358 328 224 206 165 Bytes

Die Techniken, die erforderlich sind, um Fibonacci-Zahlen mit einem ECMAScript-Regex (in Unary) abzugleichen, sind weit davon entfernt, wie es in den meisten anderen Regex-Varianten am besten funktioniert. Das Fehlen von vorwärts / verschachtelten Rückverweisen oder Rekursionen bedeutet, dass es unmöglich ist, eine laufende Summe von irgendetwas direkt zu zählen oder zu behalten. Das Fehlen von Lookbehind macht es oft zu einer Herausforderung, auch genügend Platz zum Arbeiten zu haben.

Viele Probleme müssen aus einer ganz anderen Perspektive angegangen werden und scheinen unlösbar, bis einige wichtige Erkenntnisse vorliegen. Es zwingt Sie, ein viel breiteres Netz zu ziehen, um herauszufinden, welche mathematischen Eigenschaften der Zahlen, mit denen Sie arbeiten, verwendet werden können, um ein bestimmtes Problem lösbar zu machen.

Im März 2014 passierte dies für Fibonacci-Zahlen. Auf der Wikipedia-Seite konnte ich anfangs keinen Weg finden, obwohl eine bestimmte Eigenschaft verblüffend nahe lag. Dann skizzierte der Mathematiker Teukon eine Methode, die klar machte, dass es möglich wäre, diese Eigenschaft zusammen mit einer anderen zu verwenden. Er zögerte, den Regex tatsächlich zu konstruieren. Seine Reaktion, als ich weitermachte und es tat:

Du bist verrückt! ... Ich dachte, Sie könnten das tun.

Wie bei meinen anderen unären ECMAScript-Postings für mathematische Regex werde ich eine Warnung geben: Ich empfehle dringend, zu lernen, wie man unäre mathematische Probleme in ECMAScript-Regex löst. Es war eine faszinierende Reise für mich, und ich möchte sie keinem verderben, der sie möglicherweise selbst ausprobieren möchte, insbesondere nicht jenen, die sich für Zahlentheorie interessieren. In diesem Beitrag finden Sie eine Liste der nacheinander mit Spoiler-Tags gekennzeichneten empfohlenen Probleme, die Sie nacheinander lösen können.

So liest keine weiteren , wenn Sie nicht einig einstellige regex Magie für Sie verwöhnen wollen . Wenn Sie versuchen möchten, diese Magie selbst herauszufinden, empfehle ich dringend, zunächst einige Probleme in ECMAScript regex zu lösen, wie in dem oben verlinkten Beitrag beschrieben.

Die Herausforderung, vor der ich anfangs stand: Eine positive ganze Zahl x ist genau dann eine Fibonacci-Zahl, wenn 5x 2 + 4 und / oder 5x 2 - 4 ein perfektes Quadrat sind. Aber es gibt keinen Raum, um dies in einer Regex zu berechnen. Der einzige Raum, in dem wir arbeiten müssen, ist die Nummer selbst. Wir haben nicht einmal genug Platz, um mit 5 zu multiplizieren oder das Quadrat zu nehmen, geschweige denn mit beiden.

Teukon's Idee, wie man es löst ( ursprünglich hier gepostet ):

Der reguläre Ausdruck wird mit einer Zeichenfolge der Form dargestellt ^x*$, z sei seine Länge. Prüfen Sie, ob z eine der ersten Fibonacci-Zahlen ist (bis zu 21 sollten reichen). Wenn es das nicht ist:

  1. Lesen Sie ein paar Zahlen, a <b, so dass b nicht größer als 2a ist.
  2. Verwenden Sie die Vorausschau, um a 2 , ab und b 2 zu erstellen .
  3. Stellen Sie sicher, dass entweder 5a 2 + 4 oder 5a 2 - 4 ein perfektes Quadrat ist (also muss a für einige n F n-1 sein ).
  4. Stellen Sie sicher, dass entweder 5b 2 + 4 oder 5b 2 + 4 ein perfektes Quadrat ist (also muss b F n sein ).
  5. Überprüfen Sie, ob z = F 2n + 3 oder z = F 2n + 4 ist, indem Sie die zuvor erstellten a 2 , ab und b 2 und die Identitäten verwenden:
    • F 2n-1 = F n 2 + F n-1 2
    • F 2n = (2F n - 1 + F n ) F n
Kurz gesagt: Mit diesen Identitäten können wir das Problem der Überprüfung, ob eine bestimmte Zahl Fibonacci ist, auf die Überprüfung reduzieren, ob es sich bei einem Paar sehr viel kleinerer Zahlen um Fibonacci handelt. Eine kleine Algebra wird zeigen, dass für groß genug n (n = 3 sollte reichen) F 2n + 3 > F n + 5F n 2 + 4, so dass immer genügend Platz vorhanden sein sollte.

Und hier ist ein Modell des Algorithmus in C, das ich als Test geschrieben habe, bevor ich ihn in Regex implementiert habe.

Also ohne weiteres, hier ist der reguläre Ausdruck:

^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$

Probieren Sie es online!

Und die schön gedruckte, kommentierte Fassung:

^(
  (?=
    (x*)                   # \2+1 = potential number for which 5*(\2+1)^2 ± 4
                           # is a perfect square; this is true iff \2+1 is a Fibonacci
                           # number. Outside the surrounding lookahead block, \2+1 is
                           # guaranteed to be the largest number for which this is true
                           # such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
    .*
    (?=                    # tail = (\2+1) * (\2+1) * 5 + 4
      x{4}
      (                    # \3 = (\2+1) * 5
        x{5}
        (\2{5})            # \4 = \2 * 5
      )
      (?=\3*$)
      \4+$
    )
    (|x{4})                # \5 = parity - determined by whether the index of Fibonacci
                           #               number \2+1 is odd or even
    (?=xx (x*)(\6 x?))     # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
                           #      divided by 2
                           # \7 = the other half, including remainder
    \5
    # require that the current tail is a perfect square
    (x(x*))                # \8 = potential square root, which will be the square root
                           #      outside the surrounding lookahead; \9 = \8-1
    (?=(\8*)\9+$)          # \10 = must be zero for \8 to be a valid square root
    (?=\8*$\10)
    \8*
    (?=(x\2\9+$))          # \11 = result of multiplying \8 * (\2+1), where \8 is larger
    (x*)\12                # \12 = \11 / 2; the remainder will always be the same as it
                           #       is in \7, because \8 is odd iff \2+1 is odd
  )
  \7\11
  (
    \6\11
  |
    \12
  )
|
  x{0,3}|x{5}|x{8}|x{21}   # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

Der Multiplikationsalgorithmus wird in diesen Kommentaren nicht erläutert, sondern in einem Abschnitt meines Postens mit vielen regulären Zahlen kurz erläutert .

Ich habe sechs verschiedene Versionen des Fibonacci-Regex beibehalten: vier, die von der kürzesten Länge zur schnellsten Geschwindigkeit ratschen und den oben erläuterten Algorithmus verwenden, und zwei andere, die einen anderen, viel schnelleren, aber viel längeren Algorithmus verwenden, den ich tatsächlich zurückgeben kann Der Fibonacci-Index als Übereinstimmung (die Erklärung dieses Algorithmus hier würde den Rahmen dieses Beitrags sprengen, wird jedoch in der ursprünglichen Diskussion Gist erläutert ). Ich glaube nicht, dass ich so viele sehr ähnliche Versionen eines regulären Ausdrucks wieder beibehalten würde, weil ich zu der Zeit alle meine Tests in PCRE und Perl durchgeführt habe, aber meine reguläre Ausdrucksmaschine ist schnell genug, dass Geschwindigkeitsbedenken nicht mehr so ​​wichtig sind (und wenn ein bestimmtes Konstrukt einen Engpass verursacht, kann ich eine Optimierung hinzufügen) - obwohl ich wahrscheinlich wieder eine schnellste und eine kürzeste Version beibehalten würde, wenn der Unterschied wäre in der Geschwindigkeit waren groß genug.

Die Version "Gib den Fibonacci-Index minus 1 als Match zurück" (nicht stark golfen):

Probieren Sie es online!

Alle Versionen sind auf Github mit der vollständigen Commit-Historie der Golfoptimierungen:

regex zum Abgleichen Fibonacci - Zahlen - kurze, Geschwindigkeit 0.txt (kürzesten aber langsamste, wie in dieser Veröffentlichung)
regex zum Abgleichen Fibonacci - Zahlen - kurzen, Geschwindigkeit 1.txt
regex zum Abgleichen Fibonacci - Zahlen - kurze, Geschwindigkeit 2.txt
regex für passende Fibonacci-Zahlen - kurz, Geschwindigkeit 3.txt regulärer Ausdruck
für passende Fibonacci-Zahlen - schnellste.txt regulärer Ausdruck
für passende Fibonacci-Zahlen - Rückgabe index.txt

Deadcode
quelle
9

Python 3 , 48 Bytes

lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

Probieren Sie es online!

Dennis
quelle
1
Als Python sollte es bei ausreichenden Ressourcen nicht für beliebig große Eingaben funktionieren?
Jonathan Allan
2
Ich hatte immer den Eindruck, wir könnten jeden beliebigen Algorithmus verwenden, solange er in der Praxis funktioniert, wenn die Berechnungen in den Datentyp und theoretisch mit unendlicher Genauigkeit passen. Sicher, nur mit intwürde der Balken höher gesetzt (immer noch nicht beliebig groß), aber wir erzwingen auch nicht, dass C-Antworten 64-Bit-Ganzzahlen (oder 128-Bit mit gcc) verwenden. Jedenfalls erscheint es unsinnig, denselben Algorithmus in einer Sprache, aber nicht in einer anderen zu verwenden.
Dennis
Die algorithmische Sicht ist sinnvoll (ich hatte immer gedacht, dass es die Eingabedomäne ist, die die Kriterien für die Anpassung an den Datentyp vorgibt). Das einzige, worauf zu achten ist, ist die Grauzone zwischen der Idee des Algorithmus und seiner Implementierung. Hier könnte man überprüfen, ob eine der ganzen Zahlen quadratisch ist, ohne sie in Floats umzuwandeln. Ich denke, dass eine interne Besetzung als Nebeneffekt akzeptabel ist, solange sie Teil eines legitimen, funktionierenden Algorithmus ist (... und ich bin mir ziemlich sicher, dass ein Algorithmus, der sich auf die Besetzung stützt, nicht akzeptabel wäre).
Jonathan Allan
@ JonathanAllan Da der maximale Wert 1e9 ist, denke ich nicht, dass willkürlich große Eingaben ein Problem sein würden.
JAD
1
@ JarkoDubbeldam ja, dieses Detail wurde tatsächlich geändert, nachdem mein Kommentar abgegeben wurde.
Jonathan Allan
7

Python 2, 48 44 Bytes

f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

Probieren Sie es online aus

Vielen Dank an Jonathan Allan für das Speichern von 4 Bytes

mbomb007
quelle
Dies können 47 Bytes sein, wenn es sich um Wahrheitswerte Falseund falsche Werte handelt True: TIO!
Mr. Xcoder
Könnte auch n-aanstelle von n==aund -1 und 0 als Rückgabewerte verwenden.
Magic Octopus Urn
@carusocomputing Ich hatte das in meinem Bearbeitungsverlauf, aber es funktioniert nicht, weil Sie für größere Testwerte möglicherweise ein -101oder ein anderes Ergebnis anstelle von haben -1.
mbomb007
@ Mr.Xcoder glaubst du wirklich, dass das Speichern von 1 Byte jedermanns Verstand wert ist?
Frarugi87
1
@ frarugi87 Das Speichern eines Bytes lohnt sich immer
Mr. Xcoder
7

05AB1E , 8 7 Bytes

>ÅF¹å¹m

Erläuterung:

>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

Probieren Sie es online!

-1 Dank an Jonathan Allan für die Umgehung der 0-not-a-Fibonacci-Zahl.

Magische Kraken-Urne
quelle
Eigentlich wird nicht auf 6 Bytes aktualisiert. Ich kann nicht glauben, dass es KEINE Möglichkeit gibt, eine 0 an eine Liste mit weniger als 3 Bytes anzuhängen.
Magic Octopus Urn
@ JonathanAllan die "Fibbonacci-Funktion generieren" in 05AB1E enthält keine 0.
Magic Octopus Urn
@ JonathanAllan Ich verstehe jetzt, nette Idee. Ich brauchte eine Minute, um herauszufinden, was dort tatsächlich geschah.
Magic Octopus Urn
Reicht es nicht aus, bis zu n(ein Byte zu sparen) zu generieren, wie ÅFes inklusiv ist, und dies ¹åwürde in 0beiden Fällen dazu führen n=0?
Emigna
0AF = []. 1AF = [1,1]. Also anscheinend nicht.
Magic Octopus Urn
5

Perl 6 , 23 Bytes

{$_∈(0,1,*+*...*>$_)}
Sean
quelle
{(0,1,*+*...^*>$_).tail==$_}war das, was ich anfangs posten wollte. Vielleicht bin ich irgendwann zu Set-Operatoren gekommen .
Brad Gilbert b2gills
5

Im Ernst , 3 Bytes

,fu

Probieren Sie es online!

Gibt den Index +1 in der Liste der Fibonacci-Zahlen zurück, wenn wahr, andernfalls wird falsch zurückgegeben.

Erläuterung:

,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)
Genosse SparklePony
quelle
9
Ernsthaft unhöflich ^^
Jonathan Allan
5

Jelly ,  8 7  6 Bytes

-r‘ÆḞċ

Probieren Sie es online!

Wie?

-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

Anmerkungen:

  • der Zuwachs, wird, so dass diese Arbeiten benötigt für 2 und 3 , da sie das sind 3 rd und 4 th Fibonacci - Zahlen - über 3 alle Fibonacci - Zahlen sind größer als ihr Index.
  • die -benötigt wird , um ( und nicht nur ‘R) so Dies funktioniert für 0 , da 0 die 0 - te Fibonacci - Zahl;
Jonathan Allan
quelle
Ähm, das sieht zu sehr nach meiner Antwort aus ...
Erik the Outgolfer
Oh, ich habe meinen zu Ihren Gunsten gespielt, außer meiner arbeitet für 3:)
Jonathan Allan
Oh whoops ... Fibonacci ist komisch. (übrigens hat meine Antwort dann gelöscht, wenn du es sagst)
Erik the Outgolfer
Bist du dir bei der letzten Notiz sicher? Wenn ich das Fibonacci-Atom auf einer Liste ab 0 ausführe, ist 0 in der Ausgabe enthalten.
Scatter
1
Es scheint nicht relevant zu sein, basierend auf dem Wortlaut der Herausforderung, aber wenn Sie das Zählatom mit 1 als Argument in der Liste der Fibonacci-Zahlen verwenden, ist das Ergebnis 2 (nicht 1).
FryAmTheEggman
5

ZX81 BASIC 180 151 100 ~ 94 tokenisierte BASIC-Bytes

Dank Moggy in den SinclairZXWorld-Foren ist hier eine viel übersichtlichere Lösung, die mehr Bytes einspart.

 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

Dies gibt 1 aus, wenn eine Fibonacci-Zahl eingegeben wird, oder Null, wenn nicht. Das spart zwar Bytes, ist aber viel langsamer als die alten Lösungen unten. Entfernen Sie aus VALGründen der Geschwindigkeit (aber für mehr BASIC-Bytes) die Wrapper um die String-Literalzahlen. Hier sind die alten (er) Lösungen mit einigen Erklärungen:

 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

Die obigen Änderungen ersparen weitere BASIC-Bytes, um die IFAnweisungen in einer PRINTZeile 12 zusammenzufassen. Weitere Bytes wurden mit dem VALSchlüsselwort und mit gespeichert GOTO CODE "£", das im ZX81-Zeichensatz 12 lautet. Zeichenfolgen speichern mehr Bytes als Zahlen, da alle numerischen Werte als Gleitkommazahlen gespeichert werden. Nehmen Sie daher mehr Platz auf dem VAR-Stapel ein.

Bildbeschreibung hier eingeben

Shaun Bebbers
quelle
Tatsächlich könnte ich weitere 6 tokenisierte BASIC-Bytes sparen, indem ich Zeile 6 insgesamt entferne und Zeile 5 in 5 IF R<F THEN NEXT I- my bad ändere!
Shaun Bebbers
4

C #, 109 Bytes

bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

Könnte definitiv verbessert werden, aber ich hatte keine Zeit.

Kaito kid
quelle
Willkommen bei PPCG!
Martin Ender
1
Ich schrieb meine eigene Antwort, nur um zu erkennen, dass es das gleiche war wie bei Ihnen. Sie können Lambda-Ausdrücke und einfache Variablen verwenden, um Folgendes zu erhalten: n=>{int a=0,b=1,c=0;while(a<n&b<n)if(++c%2>0)a=a+b;else b=a+b;return a==n|b==n;}(nur 80 Byte). Probieren Sie es online!
Charlie
1
@CarlosAlejo Sparen Sie dazu weitere 2 Bytes mit a+=bstatt a=a+bund b+=astatt b=a+b.
TheLethalCoder
4

> <> , 21 19 + 3 = 24 22 Bytes

i1\{=n;
?!\:@+:{:}(

Es wird erwartet, dass die Eingabe beim Programmstart auf dem Stack ist, also +3 Bytes für das -vFlag.

Probieren Sie es online!

Dies funktioniert, indem Fibonacci-Zahlen generiert werden, bis sie größer oder gleich der eingegebenen Zahl sind, und dann die zuletzt generierte Zahl auf Gleichheit mit der Eingabe überprüft wird. Gibt aus, 1ob es eine Fibonacci-Zahl war,0 sonst aus, .

Um sicherzustellen, dass 0richtig gehandhabt wird, lautet der Startwert -1 1- die erste generierte Zahl ist 0eher als 1.

Vielen Dank an @cole für den Hinweis, dass mit STDIN auf den Stack geschoben werden ikann, -1wenn dieser leer ist. Sehr schlau!

Vorherige Version:

01-1\{=n;
}(?!\:@+:{:
Sok
quelle
Jetzt fühle ich mich dumm, Bytes zu verschwenden, die ständig jede generierte Zahl auf dem Weg überprüfen. Schön gemacht!
Emigna
1
22 Bytes verwenden istatt 01-.
Cole
@cole natürlich verwenden, ials -1wenn es keine Eingabe zu STDIN gibt, ich hätte das nicht berücksichtigt. Schön gemacht!
Sok
3

Mathematica, 37 Bytes

!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

-4 Bytes von @ngenisis

J42161217
quelle
Fibonacci[0]gibt 0, so können Sie 4Bytes sparen, indem Sie 0in den TableBereich aufnehmen. Sie können ein weiteres Byte mit der Infixnotation speichern für Table:!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&
ngenisis
3

MATL (16 Bytes)

2^5*4-t8+hX^tk=s

Probieren Sie es online!

Nicht die golferischste Lösung, aber ich wollte direkt prüfen, ob "5 * x ^ 2 +/- 4" ein perfektes Quadrat ist .

Erläuterung:

2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

Hinweis:

Im Fall "0" wird "2" zurückgegeben, da sowohl 4 als auch -4 perfekte Quadrate sind, die mit 1 identisch sind und "1 1" ergeben. Betrachten Sie jede Ausgabe ungleich Null als "wahr" und 0 als "falsch".

DrQuarius
quelle
3

PHP , 44 Bytes

for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

Probieren Sie es online!

PHP , 58 Bytes

for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

Probieren Sie es online!

Jörg Hülsermann
quelle
2
Golfed mehr: for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;.
user63956
@ user63956 Vielen Dank für den Lernaufwand bei der Zuweisung der Verkettungsvariablen
Jörg Hülsermann
3

Java, 72 69 68 63 59 55 50 49 Bytes

n->{int a=0,b=1;for(;a<n;a=b-a)b+=a;return a==n;}

Testen Sie es selbst!

Alternative (immer noch 49 Bytes)

n->{int a=0,b=1;for(;a<n;b=a+(a=b));return a==n;}

Nicht sehr originell: Es ist die einfache und grundlegende iterative Version.

Dies funktioniert für Zahlen bis zu 1.836.311.903 (47. Fibonacci-Zahl) enthalten. Darüber hinaus ist das Ergebnis undefiniert (einschließlich einer potenziellen Endlosschleife).

Danke an Kevin Cruijssen und David Conrad für die Hilfe beim Golfen :)

Olivier Grégoire
quelle
1
Netter Ansatz. Btw, können Sie Golf ein Byte durch eine Änderung n==0an n<1. In der Frage steht " Eine nicht negative ganze Zahl zwischen 0 und 1.000.000.000 ".
Kevin Cruijssen
1
@ KevinCruijssen Ich habe nicht 1, sondern 5 Bytes mit dieser Klausel gespielt! :-P Danke, ich hatte es nicht bemerkt.
Olivier Grégoire
2
Sie benötigen keine temporäre Variable für die Fibonacci-Sequenz. Sie können aufeinanderfolgende Paare mitb+=a;a=b-a;
David Conrad
1
Du machst schwarze Magie, @DavidConrad! Ich sage dir! Schwarze Magie! :)
Olivier Grégoire
3

C # (.NET Core) , 51 Byte

bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

Probieren Sie es online!

-6 Bytes dank @Oliver!

Diese Lösung verwendet eine ziemlich einfache rekursive Funktion.

  • Die Variable nist die zu testende Zahl.
  • Die Variablen aund bsind die 2 neuesten Zahlen in der Sequenz.
  • Prüft, ob die erste der letzten 2 Nummern kleiner als die eingegebene ist. Wenn dies der Fall ist, wird ein rekursiver Anruf zu den nächsten Nummern in der Reihe durchgeführt.
  • Überprüfen Sie andernfalls, ob die erste Zahl gleich der Eingabe ist, und geben Sie das Ergebnis zurück.

Die TIO-Verknüpfung zeigt, dass dies für 1134903170 funktioniert, was den für die Challenge erforderlichen Maximalwert überschreitet.

Dana
quelle
Es ist schön, in letzter Zeit C # -Lösungen zu sehen :) - Ich denke, Sie können einfach a<nnach 51 Bytes
Oliver
Vielen Dank! Und schöner Tipp :)
Dana
3

Alchemist , 205 134 Bytes

Ein großes Dankeschön an ASCII-only für das recht clevere Zusammenführen von Zuständen, wodurch 71 Bytes gespart werden !!

_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

Probieren Sie es online aus oder überprüfen Sie es im Batch!

Ungolfed

# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop
ბიმო
quelle
139 . Sie können einige 0Überprüfungen für weniger Bytes auf Kosten des Nichtdeterminismus entfernen
ASCII
129
Nur ASCII
@ Nur ASCII: Das ist ganz nett! Schlägt zwar für 0 bfehl , aber das Hinzufügen von -atom bei der Initialisierung behebt es (und speichert 2 Bytes): D Danke
ბიმო
2

Gelee , 5 Bytes

ȷḶÆḞi

Probieren Sie es online!

Gibt 0 für Nicht-Fibonacci-Zahlen und die 1-indizierte Position der Zahl in der Fibonacci-Sequenz für Fibonacci-Zahlen zurück.

Erläuterung:

ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found
streuen
quelle
Funktioniert nicht für 0.
Okx
@ComradeSparklePony Sind Sie sicher? Das ist für mich in Ordnung.
Scatter
1
Funktioniert nicht für 0 oder etwas größer als 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
Erik die Outgolfer
1
@ Mr.Xcoder Allgemeiner Konsens ist, dass Sie in der Lage sein müssen, mit den von Ihrem natürlichen Datentyp unterstützten Daten umzugehen, und dass Jelly Ganzzahlen mit willkürlicher Genauigkeit unterstützt.
Erik der Outgolfer
1
Noch funktioniert nicht für irgendetwas über 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626.
Erik die Outgolfer
2

R 43 40 Bytes

pryr::f(x%in%DescTools::Fibonacci(0:45))  

pryr::f erstellt eine Funktion:

function (x) 
x %in% DescTools::Fibonacci(0:45)

Dient DescTools::Fibonaccizum Erstellen der ersten x+1Fibonacci-Zahlen und zum Überprüfen der Aufnahme.x+1weil das dritte Fibnum 2 ist, und das würde nicht ausreichen, um die Einbeziehung von 3 zu überprüfen.

Zum Glück Desctools::Fibonacci(0)=0ist das also eine schöne Werbegeschenk.

-3 Bytes dank MickyT

JAD
quelle
-1:x+1Sie sparen ein Byte, aber 0:45Sie sparen drei und decken den erforderlichen Bereich ab
MickyT
@ MickyT Oh, ich muss die erforderliche Bereichsspezifikation übersehen haben. Vielen Dank :)
JAD
Ein alternativer Ansatz, nur 36 Bytes pryr::f(any(!(5*n^2+c(-4,4))^.5%%1)).
Turnbull
Ich habe es auf 32 Bytes reduziert, siehe hier .
Turnbull
Ich kenne mich nicht so gut mit Code-Golf-Regeln aus - macht es Sinn, Pakete zuzulassen, die keine Basispakete sind? Ich könnte beliebigen R-Code in ein Paket schreiben, es installieren und genauso ausführen, wie Sie die Funktion ausgeführt haben pryr.
mb7744
2

Haskell , 31 Bytes

f=0:scanl(+)1f
(`elem`take 45f)

Probieren Sie es online!Dies nutzt die Tatsache aus, dass die Eingabe im Bereich von 0 bis 1.000.000.000 liegt. Daher müssen nur die ersten 45 Fibonacci-Zahlen überprüft werden. f=0:scanl(+)1ferzeugt eine unendliche Liste von Fibonacci-Zahlen, take 45fist die Liste der ersten 45 Fibonacci-Zahlen und elemprüft, ob sich die Eingabe in dieser Liste befindet.


Uneingeschränkte Version: 36 Bytes

f=0:scanl(+)1f
g n=n`elem`take(n+3)f

Probieren Sie es online! Für jedenn , die die ersten n+3Fibonacci-Zahlen nehmen, wird garantiert, dass ndiese in dieser Liste stehen, wenn es sich um eine Fibonacci-Zahl handelt.

Beachten Sie, dass dieser Ansatz für hohe Zahlen, die keine Fibonacci-Zahlen sind, unglaublich ineffizient ist, da alle n+3Fibonacci-Zahlen berechnet werden müssen.

Laikoni
quelle
2

Javascript (ES6 ohne den Operator **), 44 Byte

f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

Beruht auf dem Verhältnis zwischen aufeinanderfolgenden Fibonacci-Zahlen, die sich dem Goldenen Schnitt nähern. Der Wert von c ist der Bruchteil der Eingabe geteilt durch den goldenen Schnitt. Wenn die Eingabe Fibonacci ist, liegt dieser Wert nahe bei 1 und der Wert von c-c² ist sehr klein.

Nicht so kurz wie einige der anderen JS-Antworten, läuft aber in O (1) -Zeit.

HP Williams
quelle
Bist du sicher, dass es genau ist?
user259412
Funktioniert nicht für die Fibonacchi-Nummer 16558014
Black Owl Kai
2

Julia 0,4 , 29 Bytes

!m=in(0,sqrt(5*m*m+[4,-4])%1)

Probieren Sie es online!


Wenn Sie Julia nicht so antworten, lassen Sie es mich wissen. Ich bin mir nicht sicher, wie die Eingabe bei TIO funktioniert.

Magische Kraken-Urne
quelle
1
Sie müssten es zu einer regulären Funktion (Zählen !m=) oder einem Lambda (Zählen m->) machen. Noch wichtiger ist, dass dies für 0 so wie es ist fehlschlägt .
Dennis
2

R 32 31 Bytes

Übernimmt Eingaben von stdin, kehrt zurück TRUEoder FALSEnach Bedarf.

any(!(5*scan()^2+-1:1*4)^.5%%1)
rturnbull
quelle
2

Common Lisp, 61 54 Bytes

(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

Probieren Sie es online!

Die Verkleinerung gegenüber der Vorgängerversion:

(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

Auslöser war die Idee, dass zur Erzeugung der Folge der Fibonacci-Zahlen nur zwei Variablen erforderlich sind, nicht drei.

Renzo
quelle
1

Mathematica, 33 Bytes

AtomQ@*InverseFunction[Fibonacci]
J42161217
quelle
Sie können mit ein paar Bytes speichern @*(und dann das Finale ablegen @#&)
Martin Ender
1

JS (ES6), 57 Bytes

n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))

Verwendet die Methode von carusocomputing . Viel Golfspieler als meine andere Antwort .

Ungolfed

n=>{
    y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
    return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}

quelle