Implementar a sequência aleatória de Fibonacci

Question

A sequência aleatória de Fibonacci é definida da seguinte forma:

$$ f_n = \begin{cases} f_{n-1}+f_{n-2} \text{ with probability } 1/2 \\ f_{n-1}-f_{n-2} \text{ with probability } 1/2 \\ \end{cases} $$ $$ f_1 = f_2 = 1 $$

ou seja, se o próximo termo é a soma ou diferença dos dois anteriores é escolhido aleatoriamente, independentemente dos termos anteriores. Sua tarefa é implementar esta sequência.

Cada realização aleatória da sequência deve usar valores consistentes. Por exemplo, se \$f_3 = 2\$, \$f_4\$então deve ser \$2+1 = 3\$ou \$2-1 = 1\$. Isso pode ser pensado como a sequência "lembrando" dos valores anteriores. Isso significa que este programa de exemplo é inválido, pois os valores anteriores na sequência não são mantidos por valores posteriores. Além disso, você deve explicar como seu programa atende a \$1/2\$ exigência de probabilidade.

Como é padrão para desafios de sequência , você pode realizar uma das três tarefas:

• Pegue um número inteiro positivo \$n\$como entrada e saída \$f_n\$
• Pegue um número inteiro positivo \$n\$como entrada e saída \$f_1, f_2, ..., f_n\$
• Produza a sequência indefinidamente sem fim

Novamente, como é padrão, você pode usar \$0\$ou \$1\$indexação, mas os dois valores iniciais \$f_1 = f_2 = 1\$ deve ser usado.

Este é o código-golfe , então o código mais curto, em bytes, vence.

Exemplos

n -> possible values of f_n | probabilities of values
1 -> 1                      | 1
2 -> 1                      | 1
3 -> 2, 0                   | 1/2, 1/2
4 -> 3, 1, -1               | 1/4, 1/2, 1/4
5 -> 5, 3, 1, -1            | 1/8, 1/8, 3/8, 3/8
6 -> 8, 4, 2, 0, -2         | 1/16, 1/8, 1/4, 5/16, 1/4

Answer 1

05AB1E , 8 7 bytes

λ₂D(‚Ω+

-1 byte graças a @ovs .

Imprime a seqüência infinita.

Experimente online.

Explicação:

λ        # Create a recursive environment to output the infinite sequence,
         # implicitly starting at a(0)=1
         #  (push a(n-1) implicitly)
 ₂       #  Push a(n-2) (NOTE: all negative a(n) are 0, so a(-1)=0)
  D      #  Duplicate a(n-2)
   (     #  Negate the copy: -a(n-2)
    ‚    #  Pair them together: [a(n-2), -a(n-2)]
     Ω   #  Pop and push a random item
      +  #  And add it to the a(n-1)
         # (after which the infinite list is output implicitly)

Answer 2

APL (Dyalog Unicode) , 20 bytes

{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1

Experimente online!

Pega n de stdin e imprime os primeiros n termos.

{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1  ⍝ Full program. Input: n
{              }/⎕⍴1  ⍝ Reduce a vector of n ones...
           ¯2↑⍵  ⍝ Last two items ([0 1] for the first iteration)
   (¯1*?2)       ⍝ 1 or -1
          ⊥      ⍝ Base convert (or polynomial evaluate),
                 ⍝ giving f(x-2)+f(x-1) or -f(x-2)+f(x-1) with 50% chance each
 ⍵,              ⍝ Append to the previous iteration

Answer 3

Japt , 14 13 11 bytes

Produz o nº termo, indexado em 1. Usa JavaScript Math.random()como visto aqui .

@Zä+iÍö)Ì}g

Experimente , verifique os primeiros ntermos ou veja as distribuições em 10.000 corridas

@Zä+iÍö)Ì}g     :Implicit input of integer U
@               :Function taking an array as argument via parameter Z
 Zä             :  Consecutive pairs of Z reduced by
   +            :    Literal "+"
    i           :    Insert
     Í          :      "n" at index 2 with wrapping, resulting in "n+"
                :      (Hooray for shortcut abuse!)
      ö         :    Random character from that string, where XnY=Y-X
       )        :  End reduction
        Ì       :  Get last element
         }      :End function
          g     :Starting with [0,1], repeatedly run it through that function,
                : pushing the result back to it each time
                :Implicit output of Uth element, 0-indexed

Para explicar como o abuso de atalho funciona aqui: Íé o atalho do Japt n2<space>que se destina principalmente a ser usado para converter strings binárias em inteiros (por exemplo, "1000"Í="1000"n2 =8). No entanto, quando você passa um atalho de 2 caracteres + espaço como esse para outro método - neste caso i- o espaço é usado para fechar esse método e os 2 caracteres são divididos e passados ​​para esse método como argumentos separados. O que é útil aqui, pois o imétodo para strings espera que um argumento contendo a string seja inserido e outro argumento inteiro opcional para o índice em que ela será inserida.

Answer 4

Gelatina , 10 bytes

^{Tenho certeza de que 10 é tão bom quanto caberia no Jelly; Tive algumas soluções muito mais longas ao longo do caminho.}

1ṫ-ḅØ-XṭƲ¡

Um Link monádico que aceita um número inteiro, que produz todos os valores até e incluindo esse índice indexado 0
(ou seja, \$n \to [f_0, f_1,\cdots, f_n]\ |\ f_0=f_1=1 : f_n = f_{n-1} \pm f{n-2} \$)

Experimente online!

Quão?

1ṫ-ḅØ-XṭƲ¡ - Link: integer, n
1          - set the left argument to 1
         ¡ - repeat this n times:
        Ʋ  -   last four links as a monad f(left):  e.g. left = [1,1,2,3,5,8]
 ṫ-        -     tail from 1-based, modular index -1            [5,8]
                 (tailing 1 from index -1 yields [1])
    Ø-     -     signs (a nilad)                                [-1,1]
   ḅ       -     convert from base (vectorises)                 [3,13]
                                        (i.e. [5×-1¹+8×-1°, 5×1¹+8×1°])
      X    -     random choice                                  3?
       ṭ   -     tack                                           [1,1,2,3,5,8,3]

Answer 5

perl -061 -M5.010, 46 43 bytes

say$,while($,,$/)=($/,$/+$,-2*$,*(.5<rand))

Experimente online!

Isso imprime a série infinita.

Salvou três bytes usando uma sugestão de Nahuel Fouilleul.

Como funciona?

O primeiro truque é a troca de linha de comando -061. Isso define o registro de entrada para 1(já que o valor ASCII de 1é 49, também conhecido como 61 em octal). O separador de registro de entrada é $/.

Em seguida, usamos duas variáveis ​​para manter o estado, $,que inicialmente é a string vazia, mas Perl tratará isso como se fosse 0um número. $/é definido 1como, conforme discutido acima. Em um loop infinito, definimos $,para $/, e $/para $, + $/, e então, com probabilidade 0,5, subtraímos 2 * $,do último. Em seguida, imprimimos $,.

Answer 6

Linguagem Wolfram (Mathematica) , 45 bytes

Gera f (n) usando RandomInteger 0 ou 1

#&@@Nest[+##|(-1)^Random@0[[0]]#&@@#&,0|1,#]&

Experimente online!

-6 bytes de @att

Eu também tentei isso 46 bytes

If[#>1,#0[#-1]+(-1)^RandomInteger[]#0[#-2],#]&     

mas a sequência não conseguiu "lembrar" os valores anteriores

Answer 7

Python 2, 66 64 bytes

Produz a sequência infinitamente.

from random import*
a=b=1
while 1:print a;a,b=b,b+choice([-a,a])

Experimente online!

Python 2, 73 bytes

Produz o enésimo termo da sequência.

from random import*
a,b=0,1
exec"a,b=b,b+choice([-a,a]);"*input()
print a

Experimente online!

Answer 8

J , ²⁸ 22 bytes

-6 graças ao Bubbler!

0{1&({,]#.~_1^?@2)&1 1

Experimente online!

0{1&({,]#.~_1^?@2)&1 1
  1&      …       &1 1 a verb that will apply 1&… on 1 1 y (the input) times 
              ?@2        0 or  1
           _1^           1 or _1
       ]#.~              to base, e.g. 3 5:
                           (3* 1^1)+(5* 1^0) = 8 or
                           (3*_1^1)+(5*_1^0) = 2
     {,                  prepend tail of list, i.e. 5 8 or 5 2
0{                     take first element

Answer 9

JavaScript (ES6),  68 67 66 53  52 bytes

2 bytes economizados graças a @Shaggy

Retorna o n -ésimo termo, 0-indexados.

f=(n,p=1,q=0)=>n?f(n-1,Math.random()<.5?p+q:p-q,p):p

Experimente online!

Comentou

f = (                // f is a recursive function taking:
  n,                 //   n = 0-indexed input
  p = 1,             //   p = previous value
  q = 0              //   q = penultimate value
) =>                 //
  n ?                // if n is not equal to 0:
    f(               //   do a recursive call:
      n - 1,         //     decrement n
      Math.random()  //     set p to either:
      < 0.5 ? p + q  //       p + q
            : p - q, //       or p - q
      p              //     copy the previous value in q
    )                //   end of recursive call
  :                  // else:
    p                //   return the last value

Answer 10

> <> , 22 bytes

1|.00<-x+40.08&:{&:}n:

Experimente online!

Geralmente é uma linguagem terrível para desafios envolvendo aleatoriedade, uma vez que a única fonte de aleatoriedade em> <> é x.

Mas neste caso as coisas funcionam bem. xenvia o ponteiro de instrução em uma direção aleatória, de modo que ele se enrola na direção y ou atinge a +ou -com igual probabilidade.

Answer 11

C (gcc) , 58 57 47 bytes

a,b;f(x){a=--x?f(b=x),b+=rand(x=b)%2?a:-a,x:1;}

Experimente online!

• Salvo 1 graças a @ceilingcat
• Salvo 10 graças a @Dominic van Essen

Solução recursiva que inicia todas as chamadas necessárias antes de executá-las, a última chamada inicializa os valores.

a, b; - variáveis ​​aux
f (x) {- função aderindo a um inteiro n e
               retornando n º termo 1 indexado.

a = - retorno através do registro eax
--x? f (b = x) - chama recursivamente antes de fazer o trabalho
x = b - local x usado como temp
, b + = rand ()% 2? a: -a - rnd fib step
, x - atribuir temp (x) a um
: 1;} - interrompe a recursão e inicializa a para 1

Answer 12

R , 69 ... 55 bytes

-1 byte graças a Giuseppe (que levou a mais -4 bytes), e -1 byte graças a Dominic van Essen (que levou a mais -1 byte)

F=0:1;repeat cat(" ",{F=F[2]+F[1]*(0:-1)^sample(2)}[1])

Experimente online!

Imprime a sequência indefinidamente, separada por espaços.

Fé inicializado como o vetor [1 1].

Em cada etapa, desenhe uma permutação aleatória do vetor [1 2]com sample(2). Isso significa que (0:-1)^sample(2)é [0^1 (-1)^2]=[0 1]ou [0^2 (-1)^1]=[0 -1](com probabilidade 1/2 cada). Em ambos os casos, F[1]assume o valor anterior de F[2]e, dependendo do sorteio aleatório, F[2]torna-se F[2]+F[1]ou F[2]-F[1]. Conclua a etapa imprimindo o primeiro valor de F.

Observe que posso diminuir esses 2 bytes usando um delimitador estúpido entre os valores de sequência: Experimente online uma versão de 53 bytes que usa a string TRUE como delimitador.

Answer 13

Raku , 26 bytes

{1,1,*+* *(-1,1).pick...*}

Experimente online!

Produz uma lista infinita preguiçosa. Isso é praticamente idêntico ao programa fibonacci normal, mas com *(-1,1).pickanexado para inverter aleatoriamente o sinal do segundo parâmetro.

Answer 14

Python 3 , 77 bytes

from random import*
f=lambda n,t=0,o=1:o if n<2else f(n-1,o,o+choice((-t,t)))

Uma função recursiva que aceita \$n\$e produz um possível \$f_n\$.

Experimente online! Ou veja os primeiros como distribuições 10K de amostra .

Answer 15

Vermelho , 75 bytes

func[n][a: b: 1 loop n - 1[set[a b]reduce[b b +(a * pick[1 -1]random 2)]]a]

Experimente online!

Retorna o nº termo.

Answer 16

Wolfram Language (Mathematica) , 38 bytes

Imprime a sequência indefinidamente. Adaptado da resposta de J42161217 .

#0[Echo@+##,RandomChoice@{#,-#}]&[0,1]

Experimente online!

Ungolfed:

f[a_, b_] := ( Echo[a+b]; f[a+b, RandomChoice[{a,-a}]] );
f[0, 1]

Answer 17

R , 55 54 53 52 51 49 48 47 bytes

Edit: -1 byte, e novamente -1 byte graças a Giuseppe, -1 byte graças ao AZTECCO

cat(1);repeat cat(" ",T<-sign(rt(1,1))*F+(F=T))

Experimente online! ou verifique a distribuição n = 6 .

Programa completo sem entrada. Retorna a sequência completa de Fibonacci aleatória.

O programa para retornar o nelemento usando a mesma abordagem tem 48 bytes .

Comentado:

cat(1);             # First, print the first element (1) 
                    # (T is initialized to 1 by default,
                    # and F is initialized to 0).
repeat              # Now, repeat indefinitely:
 cat(" ",           # output " ", followed by...
  T<-               #   T, updated to equal...
     sign(rt(1,1))  #   the sign of 1 randomization of 
                    #     the t-distribution with 1 degree-of-freedom
                    #     (distribution is centred around zero,
                    #     so sign is [+1,-1] with probability [.5,.5])...
     *F             #   times F (second-last value)...
       +(F=T))      #   plus T (last value)...
                    #   while updating F to equal T.

Answer 18

Dotty, 75 bytes

val| :Stream[Int]=1#::1#::(|zip|.tail map(_*((math.random*2).toInt*2-1)+_))

Experimente online

O mesmo que abaixo.

Scala, 91 87 85 84 bytes

4 bytes salvos graças ao corvus_192

val| :Stream[Int]=1#::1#::(|zip|.tail map{t=>t._2+t._1*((math.random*2).toInt*2-1)})

Experimente online

|é um Streampara que os elementos anteriores sejam lembrados. Para obter o enésimo elemento, você pode usar |(n-1)(é indexado em 0). Para obter os primeiros n elementos, use |.take(n)( l.take(n).toListpara forçá-lo).

Answer 19

Carvão , 28 bytes

≔⁰θ≔¹ηＦＮ«≔⁺η×θ⊖⊗‽²ι≔ηθ≔ιη»Ｉθ

Experimente online! O link é para a versão detalhada do código. Produz o nésimo número. Explicação:

≔⁰θ≔¹η

Comece com 0 como o iº número e 1como o i+1º número.

ＦＮ«

nTempos de loop .

≔⁺η×θ⊖⊗‽²ι

Calcule o próximo número.

≔ηθ≔ιη

Misture os valores ao redor.

»Ｉθ

Produza o nésimo número.

29 bytes para produzir os primeiros nnúmeros:

Ｆ²⊞υ¹ＦＮ⊞υ⁺§υ±¹×§υ±²⊖⊗‽²Ｉ✂υ⁰±²

Experimente online! O link é para a versão detalhada do código. Explicação:

Ｆ²⊞υ¹

Comece com 1o primeiro e o segundo números.

ＦＮ

nTempos de loop .

⊞υ⁺§υ±¹×§υ±²⊖⊗‽²

Calcule o próximo número.

Ｉ✂υ⁰±²

Produza todos, exceto dois dos números.

Answer 20

Ícone , 70 bytes

procedure n()
f:=[1,1]
while write(f[2])&push(f,f[1]+?[1,-1]*f[2])
end

Experimente online!

Imprime a sequência indefinidamente.

Answer 21

código de máquina x86, 21 bytes

A versão rdtsc tem o mesmo tamanho para o código de máquina x86-64.

rdrand reg(3 bytes) nos dá um número verdadeiramente aleatório. Ramificar em seu bit de sinal é barato. Testando apenas 1 bit, a probabilidade de 50/50 é obviamente satisfeita exatamente com o viés zero.

rdtsc(2 bytes) nos dá um timestamp "ciclo de referência" cujos bits de baixo são um tanto aleatório (que leva pelo menos 25 ciclos para executar back-to-back instruções RDTSC, mas o contador não está em execução que muito mais rápido do que estamos amostragem isto). Testar um bit com test al, 1leva a uma correlação significativa entre decisões consecutivas, mas test al,al/ jnp(ramificação no sinalizador de paridade, xor horizontal dos 8 bits baixos) dá resultados surpreendentemente bons e pode ser usado em máquinas pré-IvyBridge que faltam rdrand. Ambos jogam com o mesmo tamanho geral no modo de 32 bits.

Experimente online! Listagem NASM para rdrandversão EAX rfib(ECX):, chamável de C com MS__fastcall

21                         rfib:          ;;; 0-indexed.  ecx=5 gives the n=6 test case results.
22 00000020 31C0               xor eax, eax
23 00000022 99                 cdq                         ; EDX = fib[-1] = 0
24 00000023 40                 inc eax                     ; fib[0] = 1
25 00000024 E30E               jecxz   .done               ; ecx=0 : return 1 without looping

27                         .loop:
28 00000026 0FC7F7             rdrand  edi
29 00000029 85FF               test    edi, edi        ; 1 byte shorter than sar reg, imm / xor / sub 2's complement bithack
30 0000002B 7902               jns    .no_negate       ; the top bit is fully random
31 0000002D F7DA               neg    edx
32                         .no_negate:
33 0000002F 0FC1D0             xadd    eax, edx        ; like xchg + add, and same size
34 00000032 E2F2               loop   .loop
35                         .done:
36 00000034 C3                 ret
 size = 0x35 - 0x20 = 0x15 = 21 bytes

Observe que xadd, na verdade, não economiza bytes em comparação com xchg eax, edx/ add eax, edx. É muito divertido. E são "apenas" 3 uops, em vez de 4 no total, no Intel Skylake com operandos registradores. (Normalmente a instrução só é usada com o lockprefixo e um destino de memória, mas funciona totalmente com registradores).

Caso de teste:

  bash loop to test the ECX=5 case
$ asm-link -m32 -dn random-fib.asm && { declare -A counts; counts=(); for i in {1..10000}; do ./random-fib; ((counts[$?]++));done; 
  for i in "${!counts[@]}"; do echo "result: $(( i > 128 ? i-256 : i )):   
${counts[$i]} times";done }

result: 8:   617 times
result: 4:   1290 times
result: 2:   2464 times
result: 0:   3095 times
result: -2:   2534 times

---

NASM lista de rdtscversão : EBX rfib2(ECX). Essa versão teria o mesmo tamanho no modo de 64 bits; não precisa de 1 byte inc. O RDTSC grava EAX e EDX, portanto, não podemos tirar proveito do cdqinit.

 2                         rfib2:            ; 0-index count in ECX, returns in EBX
 3 00000000 31F6               xor  esi, esi
 4 00000002 8D5E01             lea  ebx, [esi+1]           ; fib[0] = 1, fib[-1] = 0
 5 00000005 E30D               jecxz .done
 6                         .loop:
 7 00000007 0F31               rdtsc                       ; EDX:EAX = TimeStamp Counter
 8                         
 9 00000009 84C0               test    al, al               ; low bits are essentially random; high bits not so much
10 0000000B 7B02               jnp    .no_negate
11 0000000D F7DE               neg     esi
12                         .no_negate:
13 0000000F 0FC1F3             xadd    ebx, esi
14 00000012 E2F3               loop   .loop
15                         .done:
16                             ; returns in EBX
17 00000014 C3                 ret
 size = 0x15 = 21 bytes

Resultados do teste para ECX = 5:

result: 8:   668 times         (ideal: 625)
result: 4:   1217 times        (ideal: 1250)
result: 2:   2514 times        (ideal: 2500)
result: 0:   3135 times        (ideal: 3125)
result: -2:   2466 times       (ideal: 2500)

vs. com test al, 1/ jnzpara usar apenas o bit inferior do TSC como o valor aleatório:

  # test al,1  / jnz   version: correlation between successive results.
result: 8:   115 times
result: 4:   79 times
result: 2:   831 times
result: 0:   3070 times
result: -2:   5905 times

test al,4funciona razoavelmente bem para execuções longas em minha CPU Skylake (i7-6700k) que aumenta até 3,9 GHz na energy_performance_preference = balance_performance que estou usando, em comparação com uma frequência de referência (TSC) de 4008 MHz ( mais informações sobre a constante x86 -TSC stuff ). Eu imagino que haja alguma alquimia estranha de previsão de ramificação, e rdtscela mesma tendo uma taxa de transferência de ~ 25 ciclos (relógios centrais) no Skylake (https://uops.info)

Os resultados são geralmente melhor distribuídos com test al,al/ jnpembora, então prefira que obtenha a entropia de todos os 8 bits baixos. Quando a frequência da CPU é baixa (ociosa), de modo que o TSC não está perto da mesma frequência que o núcleo, obter entropia de um único bit pode funcionar ainda melhor, embora a paridade dos 8 bits baixos provavelmente ainda seja melhor.

Eu não testei em uma CPU com turbo desabilitado onde o clock do núcleo sem reforço é exatamente igual ao clock de referência do TSC. Isso poderia levar mais facilmente a padrões ruins se a rdtsctaxa de transferência fosse uma potência de 2 ou algo assim, talvez favorecendo alguma sequência que permite o bloqueio da previsão de ramificação.

Todos os meus testes foram com uma invocação da função por inicialização do processo. Um executável estático do Linux é muito eficiente para inicializar, mas ainda é muito mais caro do que chamar a função em um loop de dentro do processo.

Answer 22

C (gcc) , 56 53 52 bytes

Editar: -3 bytes graças ao AZTECCO, -1 byte graças ao roofcat

x;y;r(n){for(x=y=1;--n;)x=~-(rand()&2)*y+(y=x);x=y;}

Experimente online!

Resposta não recursiva em C.
Função que retorna o elemento n(baseado em um) da sequência aleatória de fibonacci.

x;y;                # x & y hold last and last-but-one elements;
r(n){               # n is index of element we're looking for;
for(x=y=1;          # initialise first two elements to 1;
 --n;)              # now loop by decreasing n until it is zero,
 x=                 # update x to become equal to:
   ~-(rand()&2)*y   # plus-or-minus y...
   +(y=x)           # plus x
                    # (while updating y to equal the current x).
    ;x=y;}          # after looping, return y.

Nota : Após alguma discussão nos comentários aqui e na resposta do AZTECCO , chegou-se a um consenso de que não é necessário inicializar a semente aleatória dentro de uma função . Claro, isso significa que o programa de chamada deve fazê-lo, ou a função pode fornecer a mesma sequência de saída pseudo-aleatória toda vez que o programa de chamada for executado. Uma variante de 74 bytes da função pode inicializar a própria semente aleatória (mas apenas na primeira chamada, de modo que as chamadas subsequentes da mesma execução de programa fornecem uma saída diferente).

Answer 23

Bash , 65 bytes

a=1;b=1;while :;do echo $a;t=$b;:$[b+=$RANDOM&1?$a:-$a];a=$t;done

Experimente online!

Produz infinitamente a versão melhor e mais recente da sequência.

Answer 24

Swift , 77 bytes

sequence(first:(1,1)){a,b in(b,.random() ?a+b:a-b)}.lazy.forEach{print($0.0)}

Saídas até o Intestouro.

Answer 25

Lua , 81 bytes

t={1,1}for i=1,...do t[i]=t[i]or t[i-1]+t[i-2]*(math.random(2)*2-3)print(t[i])end

Experimente online!

Requer número de membros para ser impresso como um argumento. Substitua ...por 1/0 para imprimir a seqüência para sempre em const de um byte.