Come risolvere recidive lineari che coinvolgono due funzioni?

Question

Come risolvere recidive lineari che coinvolgono due funzioni?

#1 da (1 voti)

-1

In realtà mi sono imbattuto in una domanda in Programmazione dinamica in cui abbiamo bisogno di trovare il numero di modi per affiancare un'area di 2 X N con riquadri di determinate dimensioni .. Ecco la dichiarazione del problema

Ora, dopo un po 'di ricorrenza, sono uscito con questi.
F (n) = F (n-1) + F (n-2) + 2G (n-1) e
G (n) = G (n-1) + F (n-1)

So come risolvere il modello LR in cui è presente una funzione.Per grande N come nel caso precedente, possiamo fare l'esponenziazione della matrice e ottenere il tempo O (k ^ 3log (N)) dove k è il minimo numero tale che per tutti i k > m F (n) non dipende da F (nk). Il metodo per risolvere la recidiva lineare con l'esponenziazione della matrice così come è indicato in quel blog .

Ora per la LR che coinvolge due funzioni chiunque può suggerire un approccio abbastanza fattibile per il grande N.

c++ algorithms dynamic-programming

posta Aditya Bahuguna 06.06.2014 - 17:51

fonte

1 risposta

Leggi altre domande sui tag c++ algorithms dynamic-programming

La conversione automatica ai tipi di raccolta dalla variabile di non raccolta è una buona idea? [chiuso] Approcci per la gestione degli utenti AD all'interno del mio sistema di gestione delle risorse umane [chiuso]

score 1 · Answer 1

Lo stesso metodo funziona: trova una matrice che traduca (F(n-1) F(n-2) G(n-1)) in (F(n) F(n-1) G(n)) . Una matrice ((1 1 2) (1 0 0) (1 0 1)) lo farebbe.

Spiegazione

Ecco come funziona la moltiplicazione matrice per vettore. Un elemento primo di un vettore risultante è un prodotto interno di una riga prima e un vettore iniziale:

1*F(n-1) + 1*F(n-2) + 2*G(n-1)

che secondo la ricorrenza è F(n) . Lo stesso vale per secondo e terzo .