ottimizza la mia soluzione

-1

Ho appena risolto questo problema, ma voglio conoscere un modo più efficiente di fare moltiplicazione di matrici

M :
------
1 1 0
0 0 5
3 2 0 

f [n] = M ^ n

Ho implementato utilizzando Exponentiation_by_squaring

C'è più efficienza di questo?

    
posta HybrisHelp 04.09.2014 - 08:49
fonte

1 risposta

4

Poiché N può essere grande come 10 ^ 12, dovrebbe essere chiaro che iterare da 1 a N non è la soluzione desiderata. L'intuizione chiave è che la ricorsione può essere riscritta come V (i) = M * V (i-1), dove

 V(i) = [RR(i), MM(i), PP(i)] (a column vector)

così

 V(0) = [ 3 1 0 ]

e

 M = | 1 0 3 |
     | 1 0 2 |
     | 0 5 0 |

Ora V (N) = M ^ N * V (0)

Possiamo calcolare M ^ N nel tempo log (N) da ripetutamente a squadro :

M^2 = M * M
M^4 = M^2 * M^2
...

Esegui tutti i calcoli mod 100000006 per evitare di accumulare numeri grandi.

Per arrivare a questa soluzione, aiuta ad avere una familiarità di base con l'algebra lineare.

    
risposta data 04.09.2014 - 11:52
fonte

Leggi altre domande sui tag