Tantangan

Anda harus menulis sebuah program yang mengambil bilangan bulat positif nsebagai input, dan mengeluarkan angka nFibonacci th (disingkat Fib # seluruh) yang berisi nFib # sebagai subtring. Untuk tujuan tantangan ini, urutan Fibonacci dimulai dengan a 1.

Berikut adalah beberapa contoh yang dapat Anda gunakan sebagai kasus uji, atau sebagai contoh untuk mengklarifikasi tantangan (untuk yang terakhir, silakan tinggalkan komentar di bawah ini untuk menjelaskan apa yang Anda temukan tidak jelas).

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

Seperti biasa, ini adalah kode-golf , jadi lakukan penghitungan byte terendah yang dimungkinkan.

Jika ada sesuatu yang membingungkan / tidak jelas, silakan tinggalkan komentar.

(Tantangan ini didasarkan pada tantangan lain yang saya posting: Cetak nth prime yang berisi n )

Haskell , 85 84 byte

EDIT:

• -1 byte: Laikoni disingkat l.
• Typo ( x>=sfor x<=s) dalam penjelasan.

fmengambil Intdan mengembalikan 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

Cobalah online!

Bagaimana itu bekerja

• ladalah daftar angka Fibonacci yang tidak terbatas, didefinisikan secara rekursif sebagai jumlah parsial dari 0:1:l. Dimulai dengan 0karena daftar diindeks 0. madalah daftar yang sama dikonversi ke string.
• Dalam f:
  • nadalah nomor input, dan xmerupakan (string dari) nnomor Fibonacci.
  • Dalam pemahaman daftar luar, yadalah angka Fibonacci yang diuji apakah mengandung xsebagai substring. Passing ydikumpulkan dalam daftar dan diindeks dengan final !!nuntuk memberikan output. Ekstra xditambahkan ke tes untuk menghemat dua byte dari penggunaan !!(n-1)di akhir.
  • Untuk menghindari penghitungan ybeberapa kali, tes masing y- masing dibungkus ordan pemahaman daftar lainnya.
  • Dalam pemahaman daftar dalam, siterates melalui akhiran y.
  • Untuk menguji apakah xmerupakan awalan dari s, kami memeriksa apakah x<=sdan x++":">s. ( ":"Agak sewenang-wenang tetapi harus lebih besar dari angka apa pun.)

Jelly , 15 14 byte

Terima kasih 1 byte untuk Jonathan Allan.

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

Cobalah online!

Python 2 , 99 86 byte

• Ørjan Johansen Disimpan 7 byte: dimulai dengan b=i=x=-1 a=1dan menjatuhkanx and
• Ørjan Johansen lagi menyimpan 3 byte: f and n==2kef*(n>2)
• Felipe Nardi Batista menyimpan 9 byte: a,b=a+b,asingkatan swap ekonomi f-=str(x)in str(a), diperas(n<2)*f
• Ovs disimpan 13 byte: transisi dari python 3 ke 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

Cobalah online!

Penjelasan:

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 byte

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)

Cobalah online!

Java, 118 111 byte

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

Saya terus berpikir seharusnya tidak boleh menggandakan bit Fibonacci, tetapi semua usaha saya entah bagaimana menghasilkan lebih banyak byte.

Terima kasih kepada Kevin untuk peningkatan ... tebak ini menunjukkan ini adalah usaha pertama saya bermain golf :)

Perl 6 , 45 byte

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

$_adalah argumen untuk fungsi; @fadalah deret Fibonacci, yang dihasilkan dengan malas.

JavaScript (ES6), 96 93 92 90 86 byte

Diindeks 0, dengan nomor 0 dalam urutan sedang 1. Omong kosong di 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 byte disimpan berkat Arnauld

Cobalah

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>

Penjelasan

Versi terbaru untuk diikuti, ketika saya mendapatkan satu menit.

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

Arang , 65 byte

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

Cobalah online! Tautan ke kode verbose untuk penjelasan.

PHP , 96 byte

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

Cobalah online!

Mathematica, 85 byte

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

memasukkan

[10]

-4 byte dari @JungHwan Min

keluaran

4660046610375530309

R, 77 72 byte

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

Ini memanfaatkan gmpperpustakaan untuk angka Fibonacci. Implementasi pertanyaan foward cukup lurus.

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

Beberapa tes

> 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 byte

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

Solusi dasar, menggunakan urutan angka Fibonacci yang tak terbatas s.

C #, 35 byte

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

Cobalah

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 byte

N∞ ḟᵢfi 'fif Ṗf⁻

Rinciannya:

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

Dalam bahasa Inggris: (dengan contoh input 3)

N∞: Buat daftar bilangan asli [1,2,3,4,5,6...]

ḟᵢ: Simpan input dalam variabel f [1,2,3,4,5,6...]

fi: Konversikan daftar ke angka Fibonacci [1,1,2,3,5,8...]

'fif: Simpan semua elemen yang mengandung fangka Fibonacci[2,21,233...]

Ṗf⁻: Cetak f-1elemen ke-1 (-1 karena pengindeksan berbasis 0)233

Japt , 16 15 byte

_søNg)«´U}a@MgX

Cobalah