Drucken Sie die n-te Fibonacci-Zahl aus, die die n-te Fibonacci-Zahl enthält!

22

Herausforderung

Sie müssen ein Programm schreiben, das eine positive Ganzzahl nals Eingabe verwendet und die nth-Fibonacci-Zahl (durchgehend als Fib # abgekürzt) ausgibt , die die nth-Fib # als Unterzeichenfolge enthält. Für diese Herausforderung beginnt die Fibonacci-Sequenz mit a 1.

Hier sind einige Beispiele, die Sie als Testfälle oder als Beispiele zur Verdeutlichung der Herausforderung verwenden können (für letztere hinterlassen Sie bitte einen Kommentar, der erklärt, was Sie für unklar halten).

n=1
Fib#s: 1
       ^1 1st Fib# that contains a 1 (1st Fib#)
Output: 1

n=2
Fib#s: 1, 1
       ^1 ^2 2nd Fib# that contains a 1 (2nd Fib#)
Output: 1

n=3
Fib#s: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
             ^1              ^2                   ^3 3rd Fib# that contains a 2 (3rd Fib#)
Output: 233

n=4
Output: 233

n=5
Output: 6765

n=6
Output: 28657

n=7
Output: 1304969544928657

n=8
Output: 14472334024676221

n=9
Output: 23416728348467685

n=10
Fib#s: 1, ..., 34, 55, 89, ..., 63245986, 102334155, 165580141, ..., 2880067194370816120, 4660046610375530309
                   ^1                     ^2         ^3                                   ^10 10th Fib# that contains a 55 (10th Fib#)
Output: 4660046610375530309

Wie immer ist dies , also versuchen Sie die niedrigste mögliche Bytezahl.

Wenn etwas verwirrend / unklar ist, hinterlassen Sie bitte einen Kommentar.

(Diese Herausforderung basiert auf einer anderen Herausforderung, die ich veröffentlicht habe: Gib die n-te Primzahl aus, die n enthält. )

ericw31415
quelle
3
Ich empfehle, den n=5Testfall einzuschließen, weil ich gerade einen dummen Fehler gemacht habe, bei dem ich einen Scheck geschrieben habe, der eine Zahl mehrmals gezählt hat, wenn er den Teilstring mehr als einmal hatte. n=5würde das wegen der fangen 55.
Ørjan Johansen
2
@officialaimm Ich halte es nicht für vernünftig, sehr hohe Zahlen zu erwarten. Meine Lösung funktioniert mit TIO bis zu n=25(die Ausgabe hat 1186 Stellen) und wird dann für n=26(3085 Stellen, die auf meinem eigenen Laptop kompiliert wurden) getötet. Es scheint einen Sprung in den Schwierigkeitsgrad zu geben, wenn fib(n)eine weitere Ziffer erreicht wird (wie zu erwarten). Der nächste Sprung, 31, hat 12990 Stellen in der endgültigen Ausgabe.
Ørjan Johansen
1
Ja. Lol! Meine Python-Lösung bleibt für n> 6 hängen, weil es eine rekursive Funktion gibt, die in einer Schleife oft aufgerufen wird. : D
officialaimm
1
@officialaimm Oh, richtig, exponentielles Aufblasen ist ein Problem, wenn Fibonacci direkt mit Rekursion definiert wird. Auch ohne das könnten Sie ziemlich bald Pythons Rekursionslimit erreichen.
Ørjan Johansen
1
@ Shaggy: Das habe ich mit konsistent gemeint: Wenn 0 die 0. Fibonacci-Zahl ist, dann ist 1 die erste ("1."?) Fibonacci-Zahl.
ShreevatsaR

Antworten:

12

Haskell , 85 84 Bytes

BEARBEITEN:

  • -1 Byte: Laikoni verkürzt l.
  • Tippfehler ( x>=sfür x<=s) in Erklärung.

fnimmt ein Intund gibt ein zurück String.

l=0:scanl(+)1l
m=show<$>l
f n|x<-m!!n=[y|y<-x:m,or[x<=s|s<-scanr(:)""y,x++":">s]]!!n

Probieren Sie es online!

Wie es funktioniert

  • list die unendliche Liste von Fibonacci-Zahlen, rekursiv definiert als die Teilsummen von 0:1:l. Es beginnt damit, 0dass Listen mit 0-Index versehen sind. mist die gleiche Liste in Zeichenfolgen konvertiert.
  • In f:
    • nist die eingegebene Zahl und xist die (Zeichenfolge der) nth Fibonacci-Zahl.
    • Im äußeren Listenverständnis ywird eine Fibonacci-Zahl daraufhin geprüft, ob sie xeine Teilzeichenfolge enthält . Die übergebenen ys werden in der Liste gesammelt und mit dem Finale indiziert !!n, um die Ausgabe zu erhalten. xDen Tests wird ein Extra vorangestellt, um !!(n-1)am Ende zwei Bytes zu sparen .
    • Um zu vermeiden , das Zählen ys mehrmals, die Tests jedes yin gewickelt orund eine andere Liste Verständnis.
    • Im inneren Listenverständnis wird sdurch die Suffixe von iteriert y.
    • Um zu testen, ob xein Präfix von ist s, prüfen wir, ob x<=sund x++":">s. ( ":"ist etwas willkürlich, muss aber größer sein als jede Zahl.)
Ørjan Johansen
quelle
1
l=0:scanl(+)1lSpeichert ein Byte.
Laikoni
10

Jelly , 15 bis 14 Bytes

1 Byte danke an Jonathan Allan.

0µ³,ÆḞẇ/µ³#ÆḞṪ

Probieren Sie es online!

Undichte Nonne
quelle
4

Python 2 , 99 86 Bytes

  • Ørjan Johansen 7 Bytes gespeichert: Beginnen mit b=i=x=-1 a=1und Löschen derx and
  • Ørjan Johansen sparte erneut 3 Bytes: f and n==2bisf*(n>2)
  • Felipe Nardi Batista sparte 9 Bytes: Wirtschafts-Swap- a,b=a+b,aKürzel f-=str(x)in str(a), gequetscht(n<2)*f
  • ovs sparte 13 Bytes: Übergang von Python 3 zu Python 2.
f=n=input()
b=i=x=-1
a=1
while(n>2)*f:i+=1;a,b=a+b,a;x=[x,a][i==n];f-=`x`in`a`
print a

Probieren Sie es online!

Erläuterung:

f=n=int(input())                 # f is number of required numbers

b=i=x=-1                         # i is index(counter) set at -1
                                 # In Two-sided fibonacci, fib(-1) is 1 
                                 # and b(fib before it) i.e. fib(-2) is -1
                                 # Taking advantage of all -1 values, x is 
                                 # also set to -1 so that the `if str(...`
                                 # portion does not execute until x is set a 
                                 # value(i.e. the nth fibonacci) since there 
                                 # is no way -1 will be found in the number 
                                 # (ALL HAIL to Orjan's Genius Idea of using 
                                 # two-sided fibonacci)      

a=1                              # fib(-1) is 1


while(n>2)*f:                    # no need to perform this loop for n=1 and 
                                 # n=2 and must stop when f is 0

 i+=1                            # increment counter

 b,a=a,a+b                       # this might be very familiar (fibonacci 
                                 # thing ;))                         

 x=[x,a][i==n]                   # If we have found (`i==n`) the nth 
                                 # fibonacci set x to it

 f-=`x`in`a`                     # the number with required substring is 
                                 # found, decrease value of f

print a                          # print required value

Python 3 , 126 120 113 112 110 101 99 Bytes

f=n=int(input())
b=i=x=-1
a=1
while(n>2)*f:i+=1;a,b=a+b,a;x=[x,a][i==n];f-=str(x)in str(a)
print(a)

Probieren Sie es online!

officialaimm
quelle
1
Sie können 7 weitere Bytes loswerden, indem Sie mit dem beginnen b=i=x=-1 a=1und es fallen lassen x and . (Beginnen Sie im Wesentlichen 3 Schritte früher in der zweiseitigen Fibonacci-Sequenz -1, 1, 0, 1, 1, 2, ....)
Ørjan Johansen
1
Sie haben am Ende von -1: P
Ørjan Johansen
1
Ähm erröten . Außerdem möchte ich `und n> 2` loswerden, aber es scheint n==2wirklich eine besondere Behandlung zu erfordern. Es kann aber auch auf gekürzt werden *(n>2).
Ørjan Johansen
1
Auf 88 Bytes reduziert , sind einige Änderungen exklusiv für Python 2. Der Rest funktioniert jedoch auch in Python 3
Felipe Nardi Batista,
1
Für Python 3 können Sie noch 9 Bytes Golf spielen: hier
Felipe Nardi Batista
4

Java, 118 111 Bytes

i->{long n=i,p=0,q,c=1;for(;--n>0;p=c,c+=q)q=p;for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;return p;}

Ich denke immer wieder, dass es möglich sein sollte, das Fibonacci-Bit nicht zu duplizieren, aber alle meine Bemühungen führen irgendwie zu mehr Bytes.

Vielen Dank an Kevin für die Verbesserungen ... schätze, es zeigt, dass dies mein erster Versuch war, Golf zu spielen :)

laszlok
quelle
2
Schnipsel sind nicht erlaubt. Sie sollten dies in ein Lambda wie i->{long n=i,p=0,q,c=1;while(--n>0){q=p;p=c;c+=q;}n=c;while(i>0){if((""+c).contains(""+n))--i;q=p;p=c;c+=q;}return p;}
folgt umwandeln
1
Willkommen bei PPCG! Nachdem Sie es in ein Lambda geändert haben, wie @Okx betont hat, muss ich sagen, dass es eine beeindruckende Antwort ist. Ich habe vor ungefähr einer Stunde kurz vor dem Mittagessen versucht, diese Herausforderung anzunehmen, und habe aufgegeben. Also +1 von mir. Einige Kleinigkeiten zum Golfen: while(--n>0){q=p;p=c;c+=q;}Kann sein for(;--n>0;p=c,c+=q)q=p;und n=c;while(i>0){if((""+c).contains(""+n))--i;q=p;p=c;c+=q;}kann sein for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;. (Insgesamt: i->{long n=i,p=0,q,c=1;for(;--n>0;p=c,c+=q)q=p;for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;return p;}( 111 Bytes )
Kevin Cruijssen
2

Perl 6 , 45 Bytes

{my@f=0,1,*+*...*;@f.grep(/$(@f[$_])/)[$_-1]}

$_ist das Argument für die Funktion; @fist die Fibonacci-Sequenz, die träge erzeugt wird.

Sean
quelle
2

JavaScript (ES6), 96 93 92 90 86 Bytes

0-indiziert, wobei die 0. Ziffer in der Sequenz ist 1. Scheißt um 14.

f=(n,x=1,y=1)=>n?f(n-1,y,x+y):x+""
g=(n,x=y=0)=>x>n?f(y-1):g(n,x+!!f(y++).match(f(n)))

Versuch es

f=(n,x=1,y=1)=>n?f(n-1,y,x+y):x+""
g=(n,x=y=0)=>x>n?f(y-1):g(n,x+!!f(y++).match(f(n)))
oninput=_=>o.innerText=(v=+i.value)<14?`f(${v}) = ${f(v)}\ng(${v}) = `+g(v):"Does not compute!"
o.innerText=`f(0) = ${f(i.value=0)}\ng(0) = `+g(0)
<input id=i min=0 type=number><pre id=o>


Erläuterung

Aktualisierte Version folgt, wenn ich eine Minute Zeit habe.

f=...                   :Just the standard, recursive JS function for generating the nth Fibonacci number
g=(...)=>               :Recursive function with the following parameters.
n                       :  The input integer.
x=0                     :  Used to count the number of matches we've found.
y=0                     :  Incremented on each pass and used to generate the yth Fibonacci number.
x>n?                    :If the count of matches is greater than the input then
f(y-1)                  :    Output the y-1th Fibonacci number.
:                       :Else
g(...)                  :    Call the function again, with the following arguments.
n                       :      The input integer.
x+                      :      The total number of matches so far incremented by the result of...
RegExp(f(n)).test(f(y)) :        A RegEx test checking if the yth Fibonacci number, cast to a string, contains the nth Fibonacci number.
                        :        (returns true or false which are cast to 1 and 0 by the addition operator)
y+1                     :      The loop counter incremented by 1
Zottelig
quelle
Ihre Antwort scheint eine andere Ausgabe als die Beispiele zu liefern.
ericw31415
@ ericw31415, das liegt daran, dass es 0-indiziert ist.
Shaggy
Ich schrieb speziell schrieb dies jedoch: "Für die Zwecke dieser Herausforderung beginnt die Fibonacci-Sequenz mit einer 1."
ericw31415
@ ericw31415: Und meine Sequenz beginnt mit 1, sie ist nur 0-indiziert. Die 0. und 1. Ziffer in der Sequenz ist 1, die 2. ist 2, die 3. ist 3, die 4. ist 5, die 5. ist 8 und so weiter und so fort.
Shaggy
2

Kohle , 65 Bytes

AIθνAνφA±¹βAβιAβξA¹αW∧›ν²φ«A⁺ι¹ιA⁺αβχAαβAχαA⎇⁼ιναξξA⁻φ›№IαIξ⁰φ»Iα

Probieren Sie es online! Link zum ausführlichen Code zur Erklärung.

Nur ASCII
quelle
1

PHP , 96 Bytes

for($f=[0,1];$s<$a=$argn;$s+=$f[$a]&&strstr($f[$i],"$f[$a]")?:0)$f[]=$f[$i]+$f[++$i];echo$f[$i];

Probieren Sie es online!

Jörg Hülsermann
quelle
1

Mathematica, 85 Bytes

(i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])&

Eingang

[10]

-4 Bytes von @JungHwan min

Ausgabe

4660046610375530309

J42161217
quelle
2
Sieht komisch aus, f@i@n++ist aber völlig gültig und verringert 1 Byte. Verwenden Forstatt Whilereduziert 3 Bytes. 85 Bytes:(i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])&
JungHwan Min
Nur ein Köpfchen, die Deklaration globaler Variablen ist völlig in Ordnung . Mein Fehler.
JungHwan Min
1

R 77 72 Bytes

F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)

Dies nutzt die gmpBibliothek für die Fibonacci-Nummer. Ziemlich geradeaus Umsetzung der Frage.

F=gmp::fibnum;          # Alias Fibonacci function to F
i=0;                    # intitalise counter
d=n=scan();             # get n assign to d as well
while(n)               # loop while n
  if(grepl(F(d),F(i<-i+1)))  # use grepl to determine if Fib of input is in Fib# and increment i
     n=n-1;             # decrement n
F(i)                  # output result

Einige Tests

> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 2
2: 
Read 1 item
Big Integer ('bigz') :
[1] 1
> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 3
2: 
Read 1 item
Big Integer ('bigz') :
[1] 233
> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 10
2: 
Read 1 item
Big Integer ('bigz') :
[1] 4660046610375530309
> F=gmp::fibnum;i=0;d=n=scan();while(n)if(grepl(F(d),F(i<-i+1)))n=n-1;F(i)
1: 15
2: 
Read 1 item
Big Integer ('bigz') :
[1] 1387277127804783827114186103186246392258450358171783690079918032136025225954602593712568353
MickyT
quelle
0

Clojure, 99 Bytes

(def s(lazy-cat[0 1](map +(rest s)s)))#(nth(filter(fn[i](.contains(str i)(str(nth s %))))s)(dec %))

Eine grundlegende Lösung verwendet eine unendliche Folge von Fibonacci-Zahlen s.

NikoNyrh
quelle
0

C #, 35 Bytes

int u=1,b=1;for(;b<n;){b+=u;u=b-u;}

Versuch es

int n=int.Parse(t2.Text);int u=1,b=1;for(;b<n;){b+=u;u=b-u;t.Text+=b.ToString()+" ";}if(b==n){t.Text+="true";}
Erlantz Calvo
quelle
1
Willkommen beim Programmieren von Puzzle und Code-Golf. Die Antworten müssen entweder ein vollständiges Programm oder eine Funktion sein, während Sie nur einen Ausschnitt bereitgestellt haben. Insbesondere nehmen Sie an, dass die Eingabe in nund Sie setzen nur die Ausgabe in b(ich denke). Sie könnten das nals Argumente nehmen und zurückgeben b... Außerdem bin ich mir ziemlich sicher, dass Sie nicht berechnen, was die Herausforderungen verlangen. Eigentlich habe ich keine Ahnung, was Sie berechnen. Können Sie uns bitte einen Code zur Verfügung stellen, mit dem wir Ihre Lösung überprüfen können? (Ihr "Try it" kann nicht ausgeführt werden, wie es ist ..)
Dada
0

NewStack , 14 Bytes

N∞ ḟᵢfi 'fif Ṗf⁻

Die Panne:

N∞              Add all natural numbers to the stack
   ḟᵢ           Define new function will value of input
     fi          Get the n'th Fibonacci number for ever element n
       'fif      Remove all elements that don't contain the (input)'th Fibonacci number 
           Ṗf⁻  Print the (input-1)'th element

Auf Englisch: (am Beispiel einer Eingabe von 3)

N∞: Machen Sie eine Liste der natürlichen Zahlen [1,2,3,4,5,6...]

ḟᵢ: Speichern Sie die Eingabe in der Variablen f [1,2,3,4,5,6...]

: Konvertiert die Liste in Fibonacci-Zahlen [1,1,2,3,5,8...]

'fif: Behalte alle Elemente, die die fFibonacci-Zahl enthalten[2,21,233...]

Ṗf⁻: Gibt das f-1th-Element aus (-1 aufgrund der 0-basierten Indizierung)233

Graviton
quelle
Der GitHub scheint nur eine Readme und ein Tutorial zu enthalten. Auf eine Implementierung wird verwiesen, sie ist jedoch nicht verknüpft. Obwohl PPCG jetzt Sprachen erlaubt, die neuer sind als die Herausforderung, glaube ich, dass wir immer noch eine öffentlich verfügbare Implementierung benötigen.
Ørjan Johansen
@ ØrjanJohansen, Ahah, danke, dass du mich daran erinnert hast. Ich habe vergessen, das hochzuladen! Es wird in einer Minute auf sein.
Graviton
Ihre Implementierung verwendet anscheinend UTF-8. In diesem Fall sind das tatsächlich 28 Byte (die Haskell-Einstellung macht nichts, ich verwende nur TIO, um Bytes zu zählen). Sprachen wie Jelly usw. haben aus diesem Grund ihre eigenen Codepages.
Ørjan Johansen
@ ØrjanJohansen Touché, ich bin gerade dabei, eine Tabelle für die eigene Codierung zu verteilen, während wir sprechen.
Graviton
0

Japt , 16 15 Bytes

_søNg)«´U}a@MgX

Versuch es

Zottelig
quelle