Incremento o doppio problema

1

Ho un problema con un compito. In questo incarico devo creare un programma che deve calcolare quante diverse possibilità ci sono per ottenere dal numero a al b. Per ottenere da a a b puoi solo D (doppio) il valore o I (incrementare) il valore.

Quindi puoi avere a = 3 eb = 14. Questo ti porterà 8 diverse possibilità:

DDII = 3*2*2+2 = 14
DID = ((3*2)+1)*2 =14
DIIIIIIII = 3*2+8 =14
IDIIIIII=(3+1)*2+6=14
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=14
IIIIIIIIIII=3+11=14

Nella mia attuale soluzione sto usando una ricerca per ampiezza (BFS) per calcolare tutte le possibilità solo questo è molto lento, perché a volte ci sono molte possibilità e con BFS passerai attraverso tutte loro. Quindi, per esempio, se vuoi calcolare a = 10 eb = 1000, questo mi darà 74.116.423 possibilità.

Questo è quasi impossibile da calcolare con il mio computer e la soluzione che sto attualmente utilizzando.

Qual è l'approccio corretto da adottare per risolvere questo problema? Essendo un incarico, non cerco la risposta, ho bisogno di un algoritmo o di altra spinta nella giusta direzione.

    
posta Danique 29.04.2015 - 23:12
fonte

1 risposta

1

Ad esempio per il numero di modi per passare da 10 a 1000:

Sia A (N) = numero di modi per ottenere da N a 1000. Calcola e archivia A (N) per N = 1000, 999, ..., 10.

Per N = 1000, 999, ..., 501, A (N) = 1 perché non puoi raddoppiare il numero.

Per N ≤ 500, A (N) = A (2N) + A (N + 1), perché puoi raddoppiare e passare da 2N a 1000, o incrementare e passare da N + 1 a 1000.

    
risposta data 30.04.2015 - 01:55
fonte

Leggi altre domande sui tag