Interpolacja liniowa sekwencji Fibonacciego

20

Twoim zadaniem jest znalezienie n- tej liczby Fibonacciego, ale n niekoniecznie jest liczbą całkowitą.

Sekwencja Fibonacciego, indeksowana 0, wygląda następująco:

0, 1, 2, 3, 4, 5,  6,  7, ...

1, 1, 2, 3, 5, 8, 13, 21, ...

Co się jednak stanie, jeśli chcemy 2, 4- liczbę?

2,4 p liczba jest 0,4 razy większa różnica między 3 rd i 2 nd Fibonacciego plus 2 ND liczby Fibonacciego. Tak więc 2,4- ta liczba Fibonacciego to 2 + 0.4 * (3 – 2) = 2.4.

Podobnie 6,35 th liczba Fibonacciego jest 13 + 0.35 * (21 – 13) = 15.8.

Twoim zadaniem jest znalezienie n- tej liczby Fibonacciego, aby n było większe lub równe 0.

Możesz zrobić to zero lub z jednym indeksowaniem, po prostu powiedz, którego używasz.

To jest , więc wygrywa najkrótszy kod w bajtach!

Kilka innych przykładów:

0        1
4.5    6.5
0.7      1
7       21
Daniel
źródło
2
Operacja, którą tutaj wykonujesz, nazywa się „interpolacją liniową”. (Czy miałbyś coś przeciwko, jeśli zmieniłem tytuł postu, aby to odzwierciedlić?) Wydaje się, że ma właściwość Fibonacciego, że f (n-2) + f (n-1) = f (n), więc myślę, że to jest rozsądne uogólnienie sekwencji Fibonacciego. (Nie jestem pewien, czy istnieje jakieś standardowe uogólnienie.)
@ ais523, jeśli uważasz, że poprawiłoby to pytanie, to tak, możesz zmienić tytuł wpisu.
Daniel
Myślę, że łatwiej będzie znaleźć pytanie w przyszłości, jeśli ktoś zapyta o coś podobnego, a także wyjaśni, o co chodzi, powiedzmy, na liście „Pokrewnych”. To poprawi pytanie, pomagając odpowiedzieć użytkownikom we właściwym miejscu.
2
@ais Wygląda na to, że istnieje generalizacja formuły Bineta: mathworld.wolfram.com/FibonacciNumber.html
Neil
1
Chociaż Code Golf nie musi uzasadniać żądania (tak sądzę), wydaje się to dziwną operacją; zgodnie z nim, ponieważ F_0 = 0i F_2 = 1powinniśmy mieć F_1 = (1/2)(F_0 + F_2) = 1/2.
LSpice

Odpowiedzi:

7

Galaretka , 5 bajtów

_Ḟ1+¡

Jest to iteracyjne rozwiązanie bez wbudowanych elementów. Używa tego samego indeksowania co specyfikacja wyzwania.

Wypróbuj online!

tło

Niech f będzie funkcją zdefiniowaną w specyfikacji wyzwania, a F funkcją Fibonacciego zdefiniowaną jak zwykle (tj. Z F (0) = 0 ). Dla nieujemnej liczby całkowitej n mamy f (n) = F (n + 1) . Gdy 0 ≤ x <1 , specyfikacja wyzwania definiuje f (n + x) jako f (n) + (f (n + 1) - f (n)) x .

Oczywiście, dotyczy to tylko przypadki bazowe, ale nie rekurencyjne o wzorze, to znaczy M (n) = r (n - 1) + F (n - 2) posiada, jak to będzie w F . Oznacza to, że możemy uprościć definicję argumentów niecałkowitych do łatwiejszego f (n) = f (n) + f (n - 1) x .

Jak zauważyli inni w swoich odpowiedziach, relacja rekurencyjna dotyczy również argumentów niecałkowitych. Jest to łatwe do zweryfikowania, jak

proof

Od Rf (0) = f (1) = 1 , M w stałych w przedziale [0, 1], i f (0 + x) = 1 dla wszystkich x . Ponadto, f (-1) = F (0) = 0 , więc f (-1 + x) = f (-1) + (f (0) - f (-1)) x = 0 + 1x = x . Te przypadki podstawowe obejmują [-1, 1) , więc wraz ze wzorem rekurencyjnym uzupełniają definicję f .

Jak to działa

Tak jak poprzednio, niech n + x będzie jedynym argumentem naszego programu monadycznego.

¡jest szybki , co oznacza, że ​​zużywa niektóre linki po lewej stronie i zamienia je w szybkie łącze . ¡w szczególności zużywa jedno lub dwa łącza.

  • <F:monad|dyad><N:any>wywołuje łącze N , zwracając r , i wykonuje F łącznie r razy.

  • <nilad|missing><F:monad|dyad>ustawia r na ostatni argument wiersza poleceń (lub dane wejściowe z STDIN w przypadku ich braku) i wykonuje F łącznie r razy.

Ponieważ 1jest to nilad (link bez argumentów), obowiązuje drugi przypadek i zostanie wykonany + n razy (argument nie będący liczbą całkowitą jest zaokrąglany w dół). Po każdym wywołaniu do +lewy argument szybkiego łącza jest zastępowany wartością zwracaną, a prawy poprzednią wartością lewego argumentu.

Jeśli chodzi o cały program, wprowadza dane wejściowe na podłogę, dając n ; następnie _odejmij wynik od danych wejściowych, uzyskując ** x, który staje się wartością zwracaną.

1+¡następnie wywołuje - jak opisano wcześniej - z lewym argumentem 1 = f (0 + x) i prawym argumentem x = f (-1 + x) , co oblicza pożądany wynik.

Dennis
źródło
Ach, jak przydatne są wyzwania Fibonacciego. Czy celowe było mieć ¡pracę jak fibonacci z diadami?
Erik the Outgolfer
Oooh - %1+¡: interpolacja liniowa między n × F (n) przy n oraz n × F (n-1) + F (n) przy n-ε , i zwiększenie między n-ε i n .
Jonathan Allan
@EriktheOutgolfer Cóż, mniej więcej. Ponieważ Jelly nie ma zmiennych, w przeciwnym razie utracisz dostęp do poprzednich elementów sekwencji, więc sensowne było zaimplementowanie go w ten sposób.
Dennis
@JonathanAllan Nie jestem pewien, czy rozumiem. Co jest%1+¡ ma robić?
Dennis
@Dennis erm, miał na myśli , no \ _o_ / ... ale to właśnie wydaje się mieć związek z eksperymentami: D
Jonathan Allan
5

Mathematica, 32 bajty

If[#<2,1~Max~#,#0[#-1]+#0[#-2]]&

Czysta funkcja przyjmująca nieujemną liczbę rzeczywistą jako dane wejściowe i zwracająca liczbę rzeczywistą. Gdyby 1~Max~#zostały zastąpione przez 1, byłaby to standardowa rekurencyjna definicja liczb Fibonacciego o indeksie 0 dla argumentów liczb całkowitych. Ale 1~Max~#jest to poprawna cząstkowa funkcja liniowa dla rzeczywistych danych wejściowych od 0 do 2, a rekurencja zajmuje się resztą. (Ciekawostki: zmiana tego na 1-indeksowane liczby Fibonacciego można osiągnąć po prostu poprzez zmianę na Maxa Min!)

Najkrótszy, jaki mogłem uzyskać dzięki wbudowanemu, to 37-bajtowy (b=Fibonacci)[i=Floor@#](#-i)+b[i+1]&.

Greg Martin
źródło
3

JavaScript (ES6), 30 bajtów

f=x=>x<1?1:x<2?x:f(x-1)+f(x-2)
<input type=number value=2.4 oninput="O.value=f(value)"> <input id=O value=2.4 disabled>

Trywialna modyfikacja rekurencyjnej definicji sekwencji Fibonacciego o indeksie zerowym. Może powodować niewielkie błędy zaokrąglania dla niektórych danych wejściowych.

ETHprodukcje
źródło
To jest sprytne. Myślałem, że to nie działa.
Leaky Nun
1

Galaretka , 17 12 bajtów

’Ñ+Ñ
’»0‘ÇỊ?

Wypróbuj online!

Niezintegrowane rozwiązanie.

Wyjaśnienie

Funkcja pomocnika 1Ŀ

’Ñ+Ñ
 Ñ    Call the main program on
’       {the input} - 1;
   Ñ  Call the main program on {the input};
  +   Add those results{and return the result}

Główny program

’»0‘ÇỊ?
’        Subtract 1
 »0      but replace negative results with 0
     Ị?  If the result is less than or equal to 1
   ‘     Return the result plus 1
    Ç    else return the result

Dane wejściowe z zakresu od 0 do 1 będą zatem nasycone - odejmą do zera, dlatego dodajemy 1, aby otrzymać F (0) = F (1) = 1. Dane wejściowe z zakresu od 1 do 2 powrócą. Te podstawowe przypadki są wystarczające, aby wykonać typową rekurencję Fibonacciego i obliczyć z niej inne wartości.


źródło
1

Excel, 137 124 119 113 102 97 bajtów

Podejście nierekurencyjne / iteracyjne. (Bezpośrednio obliczyć n-ty termin). Wykorzystuje metodę z jednym indeksowaniem . Dodanie +1do =TRUNC(B1)zmienia go do zindeksowanego zera.

=A7+(A8-A7)*MOD(B1,1)
=5^.5
=(1+A2)/2
=TRUNC(B1)
=A4+1
=-1/A3
=(A3^A4-A6^A4)/A2
=(A3^A5-A6^A5)/A2

Fragment kodu jest przeznaczony do umieszczenia w komórce A1 .

Komórka wejściowa to B1 . Komórka wyjściowa to A1 .

qoou
źródło
1

JavaScript (ES6), 67 64 bajtów

Ma kilka problemów z zaokrąglaniem

n=>(i=(g=(z,x=1,y=0)=>z?g(--z,x+y,x):y)(++n|0))+n%1*(g(++n|0)-i)

Spróbuj

f=
n=>(i=(g=(z,x=1,y=0)=>z?g(--z,x+y,x):y)(++n|0))+n%1*(g(++n|0)-i)
console.log(f(2.4))
console.log(f(6.35))
console.log(f(42.42))

Kudłaty
źródło
0

PHP, 90 bajtów

for($f=[1,1];$i<$a=$argn;)$f[]=$f[+$i]+$f[++$i];echo$f[$b=$a^0]+($a-$b)*($f[$b+1]-$f[$b]);

Wersja online

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

Galaretka , 13 9 bajtów

,‘ḞÆḞḅ%1$

Używa tego samego indeksowania co specyfikacja wyzwania.

Wypróbuj online!

tło

Zgodnie ze specyfikacją mamy F (n + x) = F (n) + (F (n + 1) - F (n)) x , dla naturalnego n i 0 ≤ x <1 . Ponieważ F (n + 1) = F (n) + F (n - 1) , można to przepisać jako F (n + x) = F (n) + F (n - 1) x .

Ponadto indeksowanie zastosowane w specyfikacji wyzwania definiuje funkcję f (n) = F (n + 1) (gdzie F jest zwykłą funkcją Fibonacciego, tj. F (0) = 0 ), więc otrzymujemy wzór f (n + x) = F (n + 1) + F (n) x .

Jak to działa

,‘ḞÆḞḅ%1$  Main link. Argument: n + x

 ‘         Increment; yield n + 1 + x.
,          Pair; yield [n + x, n + 1 + x].
  Ḟ        Floor; yield [n, n + 1].
   ÆḞ      Fibonacci; yield [F(n), F(n + 1)].
      %1$  Modulus 1; yield (n + x) % 1 = x.
     ḅ     Unbase; yield F(n)x + F(n + 1).
Dennis
źródło
0

Perl 6 ,  48  38 bajtów

48

{$/=(1,1,*+*...*)[$_,$_+1];$0+($_-.Int)*($1-$0)}

Spróbuj

38

sub f(\n){3>n??max 1,n!!f(n-1)+f(n-2)}

Spróbuj

Rozszerzony:

48

{
  $/ =          # store here so we can use $0 and $1
  (
    1,1,*+*...* # Fibonacci sequence
  )[
    $_,         # get the value by using floor of the input
    $_ + 1      # and get the next value
  ];

    $0            # the first value from above
  +
    ( $_ - .Int ) # the fractional part of the input
  *
    ( $1 - $0 )   # the difference between the two values in the sequence
}

( $0i $1jest skrótem od $/[0]i $/[1])

38

sub f (\n) {
    3 > n           # if n is below 3
  ??
    max 1, n        # return it if it is above 1, or return 1
                    # if it was below 1, the answer would be 1
                    # the result for numbers between 1 and 3
                    # would be the same as the input anyway
  !!
    f(n-1) + f(n-2) # the recursive way to get a fibonacci number
}

To był inspirowany przez inne Python i Javascript rozwiązania

Brad Gilbert b2gills
źródło