Una frazione continua è una serie di divisioni di questo tipo:algoritmo ottimale per calcolare il risultato di una frazione continua
depth 1 1+1/s
depth 2 1+1/(1+1/s)
depth 3 1+1/(1+1/(1+1/s))
. . .
. . .
. . .
La profondità è un intero, ma s è un numero decimale.
Quale sarebbe un algoritmo ottimale (in termini di prestazioni) per calcolare il risultato per una frazione di tale profondità?
Suggerimento: srotolare ciascuna di queste formule utilizzando algebra di base. Vedrai un modello emergere.
te lo mostrerò i primi passi in modo diventa evidente:
f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1)/(s + 1)
/* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2)/(2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3)/(3*s + 2)
...
Hint2: se non si vede il motivo evidente forma emergente di cui sopra, il più ottimale l'algoritmo implicherebbe il calcolo dei numeri di Fibonacci (quindi avresti bisogno di google per il generatore di Fibonacci ottimale).
NOTA: non avendo imparato l'algebra di base in inglese, spero di non aver mescolato "denominatore" e "nominator" nel commento sopra - spero che le formule siano abbastanza ovvie per se stesse anche se ho mescolato la terminologia. – DVK
No, credo che tu abbia corretto. Il numeratore è il numero sulla "cima" della divisione, e il denominatore è sul "fondo". IE, 2/3 -> Numeratore = 2; Denominatore = 3 – Daenyth
@Daenyth - Thx! – DVK
Odori come ricorsione della coda (ricorsione (ricorsione (...))).
(In altre parole -! Loop)
Generalmente C non supporta la ricorsione della coda. –
@James Black Ma qualsiasi algoritmo ricorsivo può essere srotolato :-) Non modifica la complessità del tempo di esecuzione. (Non sto sostenendo che questa sia una buona risposta per l'algoritmo "ottimale".) –
@James Black: Come @ pst cita, sto sostenendo la trasformazione del problema ricorsivo della coda (a livello concettuale) in un ciclo (a livello di codice) che è probabilmente un processo piuttosto banale. È qui che arriva il mio commento "loop it", anche se suppongo che avrebbe potuto essere più chiaro. –
Vorrei iniziare con il calcolo 1/s, che chiameremo a.
Quindi utilizzare un ciclo for, in quanto, se si utilizza la ricorsione, in C, si può verificare un overflow dello stack.
Dato che questo è compito a casa non darò molto codice, ma, se inizi con un ciclo semplice, di 1, quindi continua ad aumentare, fino ad arrivare a 4, quindi puoi andare solo n volte.
Dato che dividerete sempre 1/s e la divisione è costosa, è sufficiente una sola volta per eseguire le prestazioni.
Mi aspetto che, se ci lavori, puoi effettivamente trovare un modello che ti aiuterà a ottimizzare ulteriormente.
Potrebbe essere utile un articolo come questo: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/.
Io presumo dal punto di vista della prestazione intendete che volete che sia veloce, indipendentemente dalla memoria utilizzata, btw.
È possibile notare che se si memorizzano nella cache i valori calcolati, ad ogni passaggio, è possibile riutilizzarli, anziché ripetere un calcolo costoso.
Personalmente farei 4-5 passi a mano, scrivendo le equazioni e i risultati di ogni passaggio, e vedere se qualsiasi schema emerge.
Aggiornamento:
GCC ha aggiunto ricorsione in coda, e non ho mai notato, in quanto cerco di limitare la ricorsione pesantemente in C, per abitudine. Ma questa risposta ha una rapida spiegazione delle diverse ottimizzazioni fatte da gcc in base al livello di ottimizzazione.
http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s
i tuoi algoritmi non sono decisamente i più ottimali, sebbene sia l'implementazione ottimale di quel particolare algoritmo. – DVK
@DVK - Non sto cercando di fornire l'algoritmo più ottimale, dato che è stato elencato come compito a casa, ma per indicare un modo per trovare un algoritmo migliore, motivo per cui ho suggerito di fare diversi passaggi a mano per trovare un modello , in modo che una soluzione migliore di quella che ho suggerito possa essere trovata. –
mi piacerebbe approfondire un po 'sul DVK's excellent answer. Continuerò con la sua notazione f(d,s) per indicare il valore ricercato per la profondità d.
Se si calcola il valore f(d,s) per il grande d, si noterà che i valori convergono con incrementi di d.
Lasciate φ = f (∞, s). Cioè, φ è il limite come d tende all'infinito, ed è la frazione continua completamente espanso. Si noti che φ contiene una copia di se stesso, in modo che possiamo scrivere φ = 1 + 1/φ. Moltiplicando entrambi i lati da φ e riordinando, si ottiene l'equazione quadratica
φ - φ - 1 = 0
che può essere risolta per ottenere
φ = (1 + √ 5)/2.
Questa è la famous golden ratio.
Troverete che f(d,s) è molto vicino a φ come d diventa grande.
Ma aspetta. C'è più!
Come DVK sottolineato, la formula per f(d,s) coinvolge termini dalla sequenza di Fibonacci. In particolare, implica rapporti di termini successivi della sequenza di Fibonacci. C'è un closed form expression for the nth term of the sequence, vale a dire
(φ n - (1- φ) n)/√ 5.
Dal 1- φ è inferiore a uno, (1- φ) n diventa piccolo come n diventa grande, quindi una buona approssimazione per l'ennesimo termine di Fibonacci è φ n/√ 5. E tornando alla formula di DVK, il rapporto dei termini successivi nella sequenza di Fibonacci tenderà a φ n + 1/φ n = φ.
Quindi questo è un secondo modo per arrivare al fatto che la frazione continua in questa domanda è pari a φ.
questo non è compito a casa perché la mia scuola è chiusa lo scorso luglio, ora sono seduto a casa e sto solo cercando di risolvere qualche problema –
Dal momento che molto probabilmente vorrai risolvere da solo, per il miglior effetto di apprendimento, penso è bello trattare questa domanda come se fosse compito a casa. – Svante