Wydrukuj n-ty numer Fibonacciego zawierający n-ty numer Fibonacciego!

22

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 , 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 )

ericw31415
źródło
3
Polecam n=5dołączyć skrzynkę testową, ponieważ właśnie popełniłem głupi błąd, gdy napisałem czek, który policzył liczbę kilka razy, jeśli miał podłańcuch więcej niż jeden raz. n=5złapałbym to z powodu 55.
Ørjan Johansen
2
@officialaimm Nie sądzę, że rozsądnie jest oczekiwać bardzo dużej liczby. Moje rozwiązanie działa na TIO do n=25(wyjście ma 1186 cyfr), po czym zostaje zabite n=26(3085 cyfr skompilowanych na moim laptopie). Wydaje się, że pojawia się trudność, gdy fib(n)dostaje się jeszcze jedną cyfrę (jak można się spodziewać). Następny skok, 31, ma 12990 cyfr w końcowym wyniku.
Ørjan Johansen
1
Tak. Lol! moje rozwiązanie python utknęło dla n> 6, ponieważ istnieje funkcja rekurencyjna, która jest wywoływana wiele razy w pętli. : D
oficjalny
1
@officialaimm No tak, wykładniczy wybuch jest problemem przy definiowaniu Fibonacciego bezpośrednio za pomocą rekurencji. Nawet bez tego możesz wkrótce przekroczyć limit rekurencji w Pythonie.
Ørjan Johansen
1
@Shaggy: To właśnie miałem na myśli przez konsekwentne: gdy 0 jest 0 liczbą Fibonacciego, wtedy 1 jest pierwszą („1”?) Liczbą Fibonacciego.
ShreevatsaR

Odpowiedzi:

12

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).
Ørjan Johansen
źródło
1
l=0:scanl(+)1lzapisuje bajt.
Laikoni,
10

Galaretka , 15 14 bajtów

1 bajt dzięki Jonathanowi Allanowi.

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

Wypróbuj online!

Leaky Nun
źródło
4

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!

Officialaimm
źródło
1
Możesz pozbyć się 7 dodatkowych bajtów, zaczynając od b=i=x=-1 a=1i upuszczając x and . (Zasadniczo rozpoczynając 3 kroki wcześniej w dwustronnej sekwencji Fibonacciego -1, 1, 0, 1, 1, 2, ....)
Ørjan Johansen
1
Zostawiłeś spację na końcu -1: P
Ørjan Johansen
1
Erm rumieniec . Ponadto chcę się pozbyć `n> 2`, ale wydaje się, że n==2naprawdę wymaga specjalnego traktowania. Ale można go skrócić *(n>2).
Ørjan Johansen
1
grał w golfa do 88 bajtów , niektóre zmiany dotyczą wyłącznie Pythona 2, ale reszta będzie działać również w Pythonie 3
Felipe Nardi Batista
1
dla Pythona 3 nadal możesz grać w golfa 9 bajtów: tutaj
Felipe Nardi Batista
4

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 :)

laszlok
źródło
2
Fragmenty nie są dozwolone. Powinieneś zamienić to w lambda tak: 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;}(118 bajtów)
Okx
1
Witamy w PPCG! Po zmianie na lambda, jak zauważył @Okx, muszę powiedzieć, że to imponująca odpowiedź. Próbowałem wykonać to wyzwanie około godzinę temu tuż przed lunchem i poddałem się. Więc +1 ode mnie. Kilka małych rzeczy do gry w golfa: while(--n>0){q=p;p=c;c+=q;}może być for(;--n>0;p=c,c+=q)q=p;i n=c;while(i>0){if((""+c).contains(""+n))--i;q=p;p=c;c+=q;}może być for(n=c;i>0;q=p,p=c,c+=q)if((""+c).contains(""+n))--i;. (W sumie: 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 bajtów )
Kevin Cruijssen
2

Perl 6 , 45 bajtów

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

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

Sean
źródło
2

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

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
Kudłaty
źródło
Twoja odpowiedź wydaje się dostarczać inny wynik niż w przykładach.
ericw31415
@ ericw31415, ponieważ jest indeksowany na 0.
Shaggy
Napisałem jednak specjalnie: „Na potrzeby tego wyzwania sekwencja Fibonacciego zaczyna się od 1.”
ericw31415
@ ericw31415: A moja sekwencja zaczyna się od 1, jest po prostu indeksowana 0; cyfry 0 i 1 w sekwencji to 1, 2 to 2, 3 to 3, 4 to 5, 5 to 8 itd. i tak dalej.
Shaggy
2

Węgiel drzewny , 65 bajtów

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

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

Tylko ASCII
źródło
1

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!

Jörg Hülsermann
źródło
1

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

J42161217
źródło
2
Wygląda dziwnie, ale f@i@n++jest całkowicie poprawny, zmniejszając 1 bajt. Użycie Forzamiast Whilezmniejsza 3 bajty. 85 bajtów:(i=ToString;f=Fibonacci;For[n=t=0,t<#,If[i@f@n++~StringContainsQ~i@f@#,t++]];f[n-1])&
JungHwan Min
Po prostu pojedynku, zadeklarowanie osobno zmiennych globalnych jest całkowicie w porządku . Mój błąd.
JungHwan Min
1

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
MickyT
źródło
0

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.

NikoNyrh
źródło
0

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";}
Erlantz Calvo
źródło
1
Witamy w Programowaniu Puzzle i Code-Golf. Odpowiedzi muszą być pełnym programem lub funkcją, podczas gdy podałeś tylko fragment kodu. W szczególności zakładasz, że wejście jest w, ni po prostu wkładasz wyjście b(myślę). Możesz napisać to njako argumenty i zwroty b... Jestem też pewien, że nie obliczasz tego, o co prosi wyzwanie. Właściwie nie mam pojęcia, co robisz. Czy możesz podać użycie kodu, który możemy uruchomić, aby zweryfikować twoje rozwiązanie? (twojego „Try it” nie można uruchomić tak, jak jest ...)
Dada
0

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...]

: 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

Grawiton
źródło
GitHub wydaje się zawierać tylko readme i samouczek. Implementacja jest przywoływana, ale nie jest powiązana. Chociaż PPCG pozwala teraz na języki nowsze niż wyzwanie, uważam, że wciąż potrzebujemy publicznie dostępnej implementacji.
Ørjan Johansen
@ ØrjanJohansen, Ahah dzięki za przypomnienie. Zapomniałem przesłać to! Będzie za minutę.
Graviton
Twoja implementacja wydaje się używać UTF-8, w którym to przypadku jest to 28 bajtów (nie przejmuj się ustawieniem Haskell, używam TIO tylko do liczenia bajtów). Z tego powodu języki takie jak Jelly itp. Mają własne strony kodowe.
Ørjan Johansen
@ ØrjanJohansen Touché, jestem w trakcie dystrybucji tabeli do jej własnego kodowania, gdy mówimy.
Graviton
0

Japt , 16 15 bajtów

_søNg)«´U}a@MgX

Spróbuj

Kudłaty
źródło