Interpolação linear da sequência de Fibonacci

20

Sua tarefa é encontrar o n º número de Fibonacci, mas n não é necessariamente um número inteiro.

A sequência de Fibonacci, indexada em 0, é a seguinte:

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

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

No entanto, o que acontece se quisermos o número 2 .4 th ?

O 2,4º número é 0,4 vezes a diferença entre o e o número de Fibonacci mais o número de Fibonacci. Assim, o 2.4 th número de Fibonacci é 2 + 0.4 * (3 – 2) = 2.4.

Da mesma forma, a 6,35 th número de Fibonacci é 13 + 0.35 * (21 – 13) = 15.8.

Sua tarefa é encontrar o n º número de Fibonacci, de tal forma que n é maior ou igual a 0.

Você pode fazer isso com índice zero ou um, apenas diga qual você está usando.

Isso é , então o código mais curto em bytes vence!

Mais alguns exemplos:

0        1
4.5    6.5
0.7      1
7       21
Daniel
fonte
2
A operação que você está fazendo aqui é chamada "interpolação linear". (Você se importaria se eu mudasse o título da postagem para refletir isso?) Parece ter a propriedade Fibonacci que f (n-2) + f (n-1) = f (n), então acho que isso é uma generalização razoável da sequência de Fibonacci. (Não tenho certeza se há alguma generalização padrão.)
@ ais523, se você acha que isso melhoraria a pergunta, sim, você pode alterar o título da postagem.
Daniel
Acho que facilitará a busca de perguntas no futuro se alguém perguntar algo semelhante, além de esclarecer o que se trata, digamos, na lista "Relacionados". Portanto, isso melhorará a pergunta ajudando a colocar os respondentes no lugar certo.
2
@ais parece que há uma generalização da fórmula Binet: mathworld.wolfram.com/FibonacciNumber.html
Neil
1
Embora o código golf não precise justificar a solicitação (eu acho), isso parece uma operação estranha; de acordo com ele, já que F_0 = 0e F_2 = 1devemos ter F_1 = (1/2)(F_0 + F_2) = 1/2.
precisa saber é o seguinte

Respostas:

7

Gelatina , 5 bytes

_Ḟ1+¡

Esta é uma solução iterativa sem built-ins. Ele usa a mesma indexação que a especificação do desafio.

Experimente online!

fundo

Seja f a função definida na especificação de desafio e F a função Fibonacci definida como de costume (ou seja, com F (0) = 0 ). Para um número inteiro não negativo n , temos f (n) = F (n + 1) . Quando 0 ≤ x <1 , a especificação de desafio define f (n + x) como f (n) + (f (n + 1) - f (n)) x .

Claramente, esta apenas atinge os casos de base, mas não a fórmula recursiva, isto é, f (n) = f (n - 1) + f (n - 2) mantém como o faria para F . Isso significa que podemos simplificar a definição de argumentos não inteiros para facilitar f (n) = f (n) + f (n - 1) x .

Como outros observaram em suas respostas, o relacionamento recursivo também vale para argumentos não inteiros. Isso é facilmente verificável, pois

prova

Desde F (0) = F (1) = 1 , f em constante no intervalo [0, 1] e f (0 + x) = 1 para todos os x . Além disso, f (-1) = F (0) = 0 , então f (-1 + x) = f (-1) + (f (0) - f (-1)) x = 0 + 1x = x . Esses casos básicos cobrem em [-1, 1) ; portanto, juntamente com a fórmula recursiva, eles completam a definição de f .

Como funciona

Como antes, seja n + x o único argumento de nosso programa monádico.

¡é uma rápida , o que significa que ele consome alguns links para a sua esquerda e os transforma em um link rápido . ¡em particular, consome um ou dois links.

  • <F:monad|dyad><N:any>chama o link N , retornando r , e executa F um total de r vezes.

  • <nilad|missing><F:monad|dyad>define r para o último argumento da linha de comando (ou uma entrada de STDIN na ausência deles) e executa F um total de r vezes.

Como 1é um nilad (um link sem argumentos), o segundo caso se aplica e será executado + n vezes (um argumento não inteiro é arredondado para baixo). Após cada chamada para +, o argumento esquerdo do link rápido é substituído pelo valor retornado, e o argumento direito pelo valor anterior do argumento esquerdo.

Quanto ao programa inteiro, pisa a entrada, produzindo n ; então _subtrair o resultado a partir da entrada, dando origem a ** x, o que torna o valor de retorno.

1+¡então chama - como descrito anteriormente - com o argumento esquerdo 1 = f (0 + x) e o argumento direito x = f (-1 + x) , que calcula a saída desejada.

Dennis
fonte
Ah, quão útil é para os desafios de Fibonacci. Foi proposital ter um ¡trabalho como fibonacci com díades?
Erik the Outgolfer
Oooh - %1+¡: interpolação linear entre n × F (n) em n e n × F (n-1) + F (n) em n-ε e aumenta entre n-ε e n .
Jonathan Allan
@EriktheOutgolfer Bem, mais ou menos. Como o Jelly não tem variáveis, você perderia o acesso aos membros da sequência anterior, então fazia sentido implementá-lo dessa maneira.
Dennis
@ JonathanAllan Não sei se entendi. O que %1+¡deveria fazer?
Dennis
@ Dennis erm, significava , bem \ _O_ / ... mas isso é o que parece fazer com experimentação: D
Jonathan Allan
5

Mathematica, 32 bytes

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

Função pura, recebendo um número real não negativo como entrada e retornando um número real. Se 1~Max~#fosse substituído por 1, essa seria a definição recursiva padrão dos números de Fibonacci indexados em 0 para argumentos inteiros. Mas 1~Max~#é a função linear por partes correta para entradas reais entre 0 e 2, e a recursão cuida do resto. (Fato trivial: alterar isso para os números de Fibonacci indexados em 1 pode ser realizado simplesmente alterando o Maxpara a Min!)

O mais curto que pude obter com o built-in é o de 37 bytes (b=Fibonacci)[i=Floor@#](#-i)+b[i+1]&.

Greg Martin
fonte
3

JavaScript (ES6), 30 bytes

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>

Modificação trivial da definição de sequência de Fibonacci recursiva indexada a zero. Pode causar pequenos erros de arredondamento para algumas entradas.

ETHproductions
fonte
Isso é inteligente. Eu pensei que não funcionava.
Leaky Nun
1

Geléia , 17 12 bytes

’Ñ+Ñ
’»0‘ÇỊ?

Experimente online!

Solução não embutida.

Explicação

Função auxiliar 1Ŀ

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

Programa principal

’»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

Uma entrada no intervalo de 0 a 1, portanto, subtrai saturada para 0, portanto, adicionamos 1 para obter F (0) = F (1) = 1. Uma entrada no intervalo de 1 a 2 retornará automaticamente. Esses casos básicos são suficientes para fazer uma recursão típica de Fibonacci e calcular os outros valores a partir daí.


fonte
1

Excel, 137 124 119 113 102 97 Bytes

Abordagem não recursiva / iterativa. (Calcular diretamente os enésimos termos) Usa o método de um índice . Adicionando +1a =TRUNC(B1)altera para indexado a zero.

=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

O trecho de código deve ser colocado começando na célula A1 .

A célula de entrada é B1 . A célula de saída é A1 .

qoou
fonte
1

JavaScript (ES6), 67 64 bytes

Tem alguns problemas com o arredondamento

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

Tente

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

Shaggy
fonte
0

PHP, 90 bytes

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

Versão Online

Jörg Hülsermann
fonte
0

Geléia , 13 9 bytes

,‘ḞÆḞḅ%1$

Isso usa a mesma indexação que a especificação do desafio.

Experimente online!

fundo

Pela especificação, temos F (n + x) = F (n) + (F (n + 1) - F (n)) x , para n natural e 0 ≤ x <1 . Como F (n + 1) = F (n) + F (n - 1) , isso pode ser reescrito como F (n + x) = F (n) + F (n - 1) x .

Além disso, a indexação usada na especificação de desafio define uma função f (n) = F (n + 1) (onde F é a função Fibonacci usual, ou seja, F (0) = 0 ), então obtemos a fórmula f (n + x) = F (n + 1) + F (n) x .

Como funciona

,‘ḞÆḞḅ%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
fonte
0

Perl 6 ,  48  38 bytes

48.

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

Tente

38.

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

Tente

Expandido:

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
}

( $0e $1é a abreviação de $/[0]e $/[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
}

Isso foi inspirado em outras soluções Python e Javascript

Brad Gilbert b2gills
fonte