Implementa la sequenza casuale di Fibonacci
La sequenza casuale di Fibonacci è definita come segue:
$$ 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 $$
cioè se il termine successivo è la somma o la differenza dei due precedenti è scelto a caso, indipendentemente dai termini precedenti. Il tuo compito è implementare questa sequenza.
Ogni realizzazione casuale della sequenza deve utilizzare valori coerenti. Ad esempio, se \$f_3 = 2\$, \$f_4\$deve quindi essere \$2+1 = 3\$o \$2-1 = 1\$. Questo può essere pensato come la sequenza che "ricorda" i valori precedenti. Ciò significa che questo programma di esempio non è valido, poiché i valori precedenti nella sequenza non vengono mantenuti dai valori successivi. Inoltre, dovresti spiegare come il tuo programma incontra il \$1/2\$ requisito di probabilità.
Come è standard per le sfide in sequenza , puoi eseguire una delle tre attività:
- Prendi un numero intero positivo \$n\$come input e output \$f_n\$
- Prendi un numero intero positivo \$n\$come input e output \$f_1, f_2, ..., f_n\$
- Emette la sequenza indefinitamente senza fine
Di nuovo, come standard, puoi usare uno \$0\$o \$1\$indicizzazione, ma i due valori iniziali \$f_1 = f_2 = 1\$ deve essere usato.
Questo è code-golf , quindi il codice più breve, in byte, vince.
Esempi
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
Risposte
05AB1E , 8 7 byte
λ₂D(‚Ω+
-1 byte grazie a @ovs .
Stampa la sequenza infinita.
Provalo online.
Spiegazione:
λ # 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)
APL (Dyalog Unicode) , 20 byte
{⍵,(¯1*?2)⊥¯2↑⍵}/⎕⍴1
Provalo online!
Prende n da stdin e stampa i primi n termini.
{⍵,(¯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
Japt , 14 13 11 byte
Emette il ntermine esimo, indicizzato 1. Utilizza JavaScript Math.random()come visto qui .
@Zä+iÍö)Ì}g
Provalo , controlla i primi ntermini o visualizza le distribuzioni su 10.000 esecuzioni
@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
Per spiegare come funziona l'abuso di scorciatoie qui: Íè la scorciatoia di Japt per la n2<space>quale è destinata principalmente ad essere utilizzata per convertire stringhe binarie in numeri interi (ad esempio "1000"Í="1000"n2 =8). Tuttavia, quando si passa una scorciatoia di 2 caratteri + spazio come quella a un altro metodo, in questo caso i, lo spazio viene utilizzato per chiudere quel metodo ei 2 caratteri vengono divisi e passati a quel metodo come argomenti separati. Il che è utile qui poiché il imetodo per le stringhe si aspetta che un argomento contenente la stringa venga inserito e un altro argomento intero opzionale per l'indice in cui deve essere inserito.
Gelatina , 10 byte
Sono abbastanza sicuro che 10 è buono come lo sarà in Jelly; Ho avuto soluzioni molto più lunghe lungo la strada.
1ṫ-ḅØ-XṭƲ¡
Un collegamento monadico che accetta un numero intero, che restituisce tutti i valori fino all'indice indicizzato 0
(ovvero \$n \to [f_0, f_1,\cdots, f_n]\ |\ f_0=f_1=1 : f_n = f_{n-1} \pm f{n-2} \$).
Provalo online!
Come?
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]
perl -061 -M5.010,
46
43 byte
say$,while($,,$/)=($/,$/+$,-2*$,*(.5<rand))
Provalo online!
Questo stampa la serie infinita.
Salvati tre byte utilizzando un suggerimento di Nahuel Fouilleul.
Come funziona?
Il primo trucco è l'interruttore della riga di comando -061. Questo imposta il record di input su 1(poiché il valore ASCII di 1è 49, noto anche come 61 in ottale). Il separatore del record di input è $/.
Quindi usiamo due variabili per mantenere lo stato, $,che inizialmente è la stringa vuota, ma Perl la tratterà come 0se fosse un numero. $/è impostato su 1, come discusso sopra. In un ciclo infinito, impostiamo $,su $/e $/su $, + $/, quindi, con probabilità 0,5, sottraiamo 2 * $,da quest'ultimo. Quindi stampiamo $,.
Wolfram Language (Mathematica) , 45 byte
Emette f (n) utilizzando RandomInteger 0 o 1
#&@@Nest[+##|(-1)^Random@0[[0]]#&@@#&,0|1,#]&
Provalo online!
-6 byte da @att
Ho provato anche questo 46 bytes
If[#>1,#0[#-1]+(-1)^RandomInteger[]#0[#-2],#]&
ma la sequenza non poteva "ricordare" i valori precedenti
Python 2, 66 64 byte
Emette la sequenza all'infinito.
from random import*
a=b=1
while 1:print a;a,b=b,b+choice([-a,a])
Provalo online!
Python 2, 73 byte
Emette l'ennesimo termine della sequenza.
from random import*
a,b=0,1
exec"a,b=b,b+choice([-a,a]);"*input()
print a
Provalo online!
J , 28 22 byte
-6 grazie a Bubbler!
0{1&({,]#.~_1^?@2)&1 1
Provalo 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
JavaScript (ES6), 68 67 66 53 52 byte
Salvato 2 byte grazie a @Shaggy
Restituisce l' n -esimo termine, 0-indicizzato.
f=(n,p=1,q=0)=>n?f(n-1,Math.random()<.5?p+q:p-q,p):p
Provalo online!
Commentato
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
> <> , 22 byte
1|.00<-x+40.08&:{&:}n:
Provalo online!
Questo di solito è un linguaggio terribile per le sfide che coinvolgono la casualità, poiché l'unica fonte di casualità in> <> è x.
Ma in questo caso le cose vanno bene. xinvia il puntatore dell'istruzione in una direzione casuale, quindi si avvolge su se stesso nella direzione y oppure colpisce a +o -con uguale probabilità.
C (gcc) , 58 57 47 byte
a,b;f(x){a=--x?f(b=x),b+=rand(x=b)%2?a:-a,x:1;}
Provalo online!
- Salvato 1 grazie a @ceilingcat
- 10 salvati grazie a @Dominic van Essen
Soluzione ricorsiva che avvia tutte le chiamate necessarie prima di eseguirle, l'ultima chiamata inizializza i valori.
a, b; - variabili aux
f (x) {- funzione che inserisce un intero n e
restituendo n- esimo termine 1 indicizzato.
a = - ritorno tramite registro eax
--x? f (b = x) - chiama in modo ricorsivo prima di eseguire il lavoro
x = b - x locale usato come temp
, b + = rand ()% 2? a: -a - rnd passo fib
, x - assegna temp (x) a a
: 1;} - interrompe la ricorsione e inizializza a su 1
R , 69 ... 55 byte
-1 byte grazie a Giuseppe (che ha portato a ulteriori -4 byte), e -1 byte grazie a Dominic van Essen (che ha portato a un ulteriore -1 byte)
F=0:1;repeat cat(" ",{F=F[2]+F[1]*(0:-1)^sample(2)}[1])
Provalo online!
Stampa la sequenza indefinitamente, separata da spazi.
Fviene inizializzato come vettore [1 1].
Ad ogni passaggio, disegna una permutazione casuale del vettore [1 2]con sample(2). Ciò significa che (0:-1)^sample(2)è [0^1 (-1)^2]=[0 1]o [0^2 (-1)^1]=[0 -1](con probabilità 1/2 ciascuno). In entrambi i casi, F[1]prende il valore precedente di F[2]e, a seconda dell'estrazione casuale, F[2]diventa F[2]+F[1]o F[2]-F[1]. Termina il passaggio stampando il primo valore di F.
Nota che posso accorciare questi 2 byte utilizzando uno stupido delimitatore tra i valori della sequenza: prova online una versione a 53 byte che utilizza la stringa TRUE come delimitatore.
Raku , 26 byte
{1,1,*+* *(-1,1).pick...*}
Provalo online!
Emette un elenco infinito pigro. Questo è praticamente identico al normale programma Fibonacci, ma con *(-1,1).pickapplicato per capovolgere casualmente il segno del secondo parametro.
Python 3 , 77 byte
from random import*
f=lambda n,t=0,o=1:o if n<2else f(n-1,o,o+choice((-t,t)))
Una funzione ricorsiva che accetta \$n\$e fornisce un possibile \$f_n\$.
Provalo online! Oppure guarda i primi come distribuzioni da 10K campionate .
Rosso , 75 byte
func[n][a: b: 1 loop n - 1[set[a b]reduce[b b +(a * pick[1 -1]random 2)]]a]
Provalo online!
Restituisce il nesimo termine.
Wolfram Language (Mathematica) , 38 byte
Stampa la sequenza indefinitamente. Adattato dalla risposta di J42161217 .
#0[Echo@+##,RandomChoice@{#,-#}]&[0,1]
Provalo online!
Ungolfed:
f[a_, b_] := ( Echo[a+b]; f[a+b, RandomChoice[{a,-a}]] );
f[0, 1]
R , 55 54 53 52 51 49 48 47 byte
Modifica: -1 byte, e ancora -1 byte grazie a Giuseppe, -1 byte grazie ad AZTECCO
cat(1);repeat cat(" ",T<-sign(rt(1,1))*F+(F=T))
Provalo online! oppure controlla la distribuzione n = 6 .
Programma completo che non richiede input. Restituisce la sequenza di fibonacci casuale completa.
Il programma per restituire nl'elemento utilizzando lo stesso approccio è di 48 byte .
Commentato:
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.
Dotty, 75 byte
val| :Stream[Int]=1#::1#::(|zip|.tail map(_*((math.random*2).toInt*2-1)+_))
Provalo online
Come di seguito.
Scala, 91 87 85 84 byte
4 byte salvati grazie a corvus_192
val| :Stream[Int]=1#::1#::(|zip|.tail map{t=>t._2+t._1*((math.random*2).toInt*2-1)})
Provalo online
|è un Streammodo che gli elementi precedenti vengano ricordati. Per ottenere l'ennesimo elemento, puoi usare |(n-1)(è indicizzato 0). Per ottenere i primi n elementi, usa |.take(n)( l.take(n).toListper forzarlo).
Carboncino , 28 byte
≔⁰θ≔¹ηＦＮ«≔⁺η×θ⊖⊗‽²ι≔ηθ≔ιη»Ｉθ
Provalo online! Il collegamento è alla versione dettagliata del codice. Emette il nnumero esimo. Spiegazione:
≔⁰θ≔¹η
Inizia con 0 come iesimo numero e 1come i+1esimo numero.
ＦＮ«
nTempi di loop .
≔⁺η×θ⊖⊗‽²ι
Calcola il numero successivo.
≔ηθ≔ιη
Mescola i valori.
»Ｉθ
Emette il nnumero esimo.
29 byte per produrre i primi nnumeri:
Ｆ²⊞υ¹ＦＮ⊞υ⁺§υ±¹×§υ±²⊖⊗‽²Ｉ✂υ⁰±²
Provalo online! Il collegamento è alla versione dettagliata del codice. Spiegazione:
Ｆ²⊞υ¹
Inizia con 1il primo e il secondo numero.
ＦＮ
nTempi di loop .
⊞υ⁺§υ±¹×§υ±²⊖⊗‽²
Calcola il numero successivo.
Ｉ✂υ⁰±²
Emetti tutti i numeri tranne due.
Icona , 70 byte
procedure n()
f:=[1,1]
while write(f[2])&push(f,f[1]+?[1,-1]*f[2])
end
Provalo online!
Stampa la sequenza indefinitamente.
codice macchina x86, 21 byte
La versione rdtsc ha le stesse dimensioni per il codice macchina x86-64.
rdrand reg(3 byte) ci dà un numero veramente casuale. La ramificazione sulla sua punta di segno è economica. Testando solo 1 bit, la probabilità 50/50 è ovviamente soddisfatta esattamente con zero bias.
rdtsc(2 byte) ci dà un timestamp "ciclo di riferimento" i cui bit bassi sono un po ' casuale (ci vogliono almeno 25 cicli per eseguire back-to-back istruzioni RDTSC, ma il contatore non è in esecuzione che molto più veloce di noi siamo di campionamento it). Testare un bit con test al, 1porta a una correlazione significativa tra decisioni consecutive, ma test al,al/ jnp(ramo sul flag di parità, xor orizzontale degli 8 bit bassi) dà risultati sorprendentemente buoni e potrebbe essere utilizzato su macchine pre-IvyBridge che mancano rdrand. Entrambi giocano con le stesse dimensioni complessive in modalità a 32 bit.
Provalo online! Elenco NASM per rdrandversione EAX rfib(ECX):, richiamabile da C con 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
Nota che in xaddrealtà non salva alcun byte rispetto a xchg eax, edx/ add eax, edx. È solo divertente. Ed è "solo" 3 uops, invece di 4 totali, su Intel Skylake con operandi di registro. (Normalmente l'istruzione viene utilizzata solo con il lockprefisso e una destinazione di memoria, ma funziona completamente con i registri).
Scenario di test:
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 messa in vendita per rdtscla versione : EBX rfib2(ECX). Questa versione avrebbe le stesse dimensioni nella modalità a 64 bit; non necessita di 1 byte inc. RDTSC scrive EAX e EDX quindi non possiamo trarne vantaggio nell'init cdq.
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
Risultati del test per 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. con test al, 1/ jnzper utilizzare solo il bit basso del TSC come valore casuale:
# 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,4capita di funzionare ragionevolmente bene per lunghi periodi sulla mia CPU Skylake (i7-6700k) che aumenta fino a 3,9 GHz alla energy_performance_preference = balance_performance che sto utilizzando, rispetto a una frequenza di riferimento (TSC) di 4008 MHz ( maggiori informazioni sulla costante x86 - Roba da TSC ). Immagino che ci sia una strana alchimia della predizione dei rami e che rdtscabbia una velocità effettiva di ~ 25 cicli (core clock) su Skylake (https://uops.info).
I risultati sono generalmente distribuiti meglio con test al,al/ jnp, quindi preferisci che prenda l'entropia da tutti gli 8 bit bassi. Quando la frequenza della CPU è bassa (idle), quindi il TSC non è vicino alla stessa frequenza del core, prendere l'entropia da un singolo bit potrebbe funzionare anche meglio, sebbene la parità degli 8 bit bassi sia probabilmente ancora la migliore.
Non ho provato su una CPU con turbo disabilitato dove il core clock non boost è esattamente uguale al clock di riferimento TSC. Ciò potrebbe portare più facilmente a schemi errati se la rdtscvelocità effettiva è una potenza di 2 o qualcosa del genere, forse favorendo una sequenza che consente di agganciare la previsione del ramo.
Tutti i miei test sono stati con una chiamata della funzione per l'avvio del processo. Un eseguibile statico di Linux è abbastanza efficiente da avviare, ma è ancora molto più costoso che chiamare la funzione in un ciclo dall'interno del processo.
C (gcc) , 56 53 52 byte
Modifica: -3 byte grazie ad AZTECCO, -1 byte grazie a Ceilingcat
x;y;r(n){for(x=y=1;--n;)x=~-(rand()&2)*y+(y=x);x=y;}
Provalo online!
Risposta non ricorsiva in C.
Funzione che restituisce l' nelemento (in base uno) della sequenza casuale di 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 : a seguito di alcune discussioni nei commenti qui e nella risposta di AZTECCO , è stato raggiunto un consenso sul fatto che non è necessario inizializzare il seme casuale all'interno di una funzione . Ovviamente, ciò significa che il programma chiamante dovrebbe farlo, oppure la funzione può fornire la stessa sequenza di output pseudocasuali ogni volta che viene eseguito il programma chiamante. Una variante di 74 byte della funzione può inizializzare essa stessa il seme casuale (ma solo alla prima chiamata, in modo che le chiamate successive dallo stesso programma eseguito forniscano un output diverso).
Bash , 65 byte
a=1;b=1;while :;do echo $a;t=$b;:$[b+=$RANDOM&1?$a:-$a];a=$t;done
Provalo online!
Produce all'infinito l'ultima e migliore versione della sequenza.
Swift , 77 byte
sequence(first:(1,1)){a,b in(b,.random() ?a+b:a-b)}.lazy.forEach{print($0.0)}
Uscite fino a Intoverflow.
Lua , 81 byte
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
Provalo online!
Richiede la stampa del numero di membri come argomento. Sostituisci ...con 1/0 per stampare la sequenza per sempre a const di un byte.