Wyzwanie

Musisz napisać program, który pobiera dodatnią liczbę całkowitą njako dane wejściowe i wyprowadza nth liczbę Fibonacciego (skróconą przez cały Fib #), która zawiera nth Fib # jako podtekst. Na potrzeby tego wyzwania sekwencja Fibonacciego zaczyna się od 1.

Oto kilka przykładów, które można wykorzystać jako przypadki testowe lub jako przykłady wyjaśniające wyzwanie (w przypadku tych ostatnich zostaw komentarz poniżej wyjaśniający, co uważasz za niejasne).

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

Jak zawsze, jest to gra w golfa kodowego , więc wybierz najniższą możliwą liczbę bajtów.

Jeśli coś jest mylące / niejasne, zostaw komentarz.

(To wyzwanie jest oparte na innym wyzwaniu, które opublikowałem: Wydrukuj n-tą liczbę pierwszą zawierającą n )

Haskell , 85 84 bajtów

EDYTOWAĆ:

• -1 bajt: Laikoni skrócił się l.
• Literówka ( x>=sdla x<=s) w objaśnieniu.

fbierze Inti zwraca a 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

Wypróbuj online!

Jak to działa

• lto nieskończona lista liczb Fibonacciego, zdefiniowana rekurencyjnie jako częściowe sumy 0:1:l. Zaczyna się od, 0ponieważ listy są indeksowane 0. mto ta sama lista przekonwertowana na ciągi.
• W f:
  • njest liczbą wejściową i xjest (ciągiem) nliczby Fibonacciego.
  • W rozumieniu listy zewnętrznej yjest liczbą Fibonacciego sprawdzoną pod kątem tego, czy zawiera xjako podłańcuch. Przekazywanie ys są gromadzone na liście i indeksowane z końcowym, !!naby dać wynik. Do xtestów dołączana jest dodatkowa , aby zaoszczędzić dwa bajty !!(n-1)na końcu.
  • Aby uniknąć liczenia ys kilka razy, testy każdego z nich ysą zawinięte ori kolejne zrozumienie listy.
  • W wewnętrznym zrozumieniu listy, siteruje się poprzez przyrostki y.
  • Aby sprawdzić, czy xjest prefiksem s, sprawdzamy, czy x<=si x++":">s. ( ":"jest nieco arbitralny, ale musi być większy niż dowolna liczba).

Galaretka , 15 14 bajtów

1 bajt dzięki Jonathanowi Allanowi.

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

Wypróbuj online!

Python 2 , 99 86 bajtów

• Ørjan Johansen Zapisano 7 bajtów: zaczynając od b=i=x=-1 a=1i upuszczającx and
• Ørjan Johansen ponownie zapisał 3 bajty: f and n==2dof*(n>2)
• Felipe Nardi Batista zapisał 9 bajtów: ekonomiczna zamiana a,b=a+b,astenografii f-=str(x)in str(a), ściśnięta(n<2)*f
• ovs zapisał 13 bajtów: przejście z Pythona 3 do Pythona 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

Wypróbuj online!

Wyjaśnienie:

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 bajtów

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)

Wypróbuj online!

Java, 118 111 bajtów

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;}

Nadal uważam, że nie powinno się powielać bitu Fibonacciego, ale wszystkie moje wysiłki w jakiś sposób skutkują większą liczbą bajtów.

Dzięki Kevinowi za ulepszenia ... zgaduję, że to była moja pierwsza próba gry w golfa :)

Perl 6 , 45 bajtów

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

$_jest argumentem funkcji; @fjest sekwencją Fibonacciego, generowaną leniwie.

JavaScript (ES6), 96 93 92 90 86 bajtów

Indeksowane 0, przy czym numerem 0 w sekwencji jest 1. Bzdury na 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)))

• 2 6 bajtów zapisanych dzięki Arnauldowi

Spróbuj

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>

Wyjaśnienie

Zaktualizowana wersja do naśladowania, kiedy dostanę minutę.

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

Węgiel drzewny , 65 bajtów

ＡＩθνＡνφＡ±¹βＡβιＡβξＡ¹αＷ∧›ν²φ«Ａ⁺ι¹ιＡ⁺αβχＡαβＡχαＡ⎇⁼ιναξξＡ⁻φ›№ＩαＩξ⁰φ»Ｉα

Wypróbuj online! Link do pełnego kodu wyjaśniającego.

PHP , 96 bajtów

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

Wypróbuj online!

Mathematica, 85 bajtów

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

wkład

[10]

-4 bajty od @JungHwan Min

wydajność

4660046610375530309

R 77 77 bajtów

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

To wykorzystuje gmpbibliotekę dla liczby Fibonacciego. Dość prosta realizacja pytania.

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

Niektóre testy

> 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

Clojure, 99 bajtów

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

Podstawowe rozwiązanie wykorzystuje nieskończoną sekwencję liczb Fibonacciego s.

C #, 35 bajtów

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

Spróbuj

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";}

NewStack , 14 bajtów

N∞ ḟᵢfi 'fif Ṗf⁻

Podział:

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

W języku angielskim: (z przykładem 3)

N∞: Zrób listę liczb naturalnych [1,2,3,4,5,6...]

ḟᵢ: Zapisz dane wejściowe w zmiennej f [1,2,3,4,5,6...]

fi: Konwertuj listę na liczby Fibonacciego [1,1,2,3,5,8...]

'fif: Zachowaj wszystkie elementy, które zawierają fth liczbę Fibonacciego[2,21,233...]

Ṗf⁻: Wydrukuj f-1element th (-1 z powodu indeksowania 0)233

Japt , 16 15 bajtów

_søNg)«´U}a@MgX

Spróbuj