numero Conte di possibili percorsi fino scaletta

Question

io non riesco a venire con un algoritmo per risolvere il seguente problema, ho provato ad utilizzare una serie di for-loop, ma è diventato troppo complicato:

A Ladder ha n passaggi, uno può salire la scala utilizzando qualsiasi combinazione di passaggi di 1 o passaggi di 2. Quanti modi possibili sono lì per uno a salire la scala?

Così, per esempio, se la scala aveva 3 passi, questi sarebbero possibili percorsi:

• 1-1-1
• 2-1
• 1-2

E per 4 passi

• 1-1-1-1
• 2-1-1
• 1-2-1
• 1-1-2
• 2-2

Tutta la comprensione quanto a come ciò potrebbe essere fatto sarebbe molto apprezzato. Inoltre, sto lavorando in Java.

Modifica: Avevo davvero intenzione di utilizzare i valori piccoli n, ma sarebbe certamente utile sapere come gestirli con quelli più grandi.

Answer 1

È interessante notare che esiste una soluzione semplice a questo problema. È possibile utilizzare la ricorsione:

public static int countPossibilities(int n) { 
    if (n == 1 || n == 2) return n; 
    return countPossibilities(n - 1) + countPossibilities(n - 2); 
} 

Ogni volta che sei di fronte a questo tipo di problema "difficile", tenere a mente che la soluzione è spesso molto elegante, e sempre controllare per vedere se qualcosa può essere fatto con la ricorsione .

EDIT: Stavo assumendo che avete a che fare con relativamente piccoli n valori in questo problema, ma se avete a che fare con quelle più grandi, allora il metodo di cui sopra sarà probabilmente prendere una buona quantità di tempo per terminare. Una soluzione sarebbe quella di utilizzare un Map che mapperebbe n a countPossibilities(n) - in questo modo, non ci sarebbe tempo perso a fare un calcolo che hai già fatto. Qualcosa di simile a questo:

private static Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
static { 
    map.put(1, 1); 
    map.put(2, 2); 
} 

public static int countPossibilities(int n) { 
    if (map.containsKey(n)) 
     return map.get(n); 

    int a, b; 

    if (map.containsKey(n - 1)) 
     a = map.get(n - 1); 
    else { 
     a = countPossibilities(n - 1); 
     map.put(n - 1, a); 
    } 

    if (map.containsKey(n - 2)) 
     b = map.get(n - 2); 
    else { 
     b = countPossibilities(n - 2); 
     map.put(n - 2, b); 
    } 

    return a + b; 
} 

Prova questo con n = 1000. Il secondo metodo è letteralmente di ordine di grandezza più veloce del primo.

Answer 2

Vorrei utilizzare la programmazione dinamica e ogni volta risolvo un problema in cui la scala è 1 piolo o 2 pioli più corto.

def solveLadder(numOfRungs): 
    if numOfRungs<=2: 
    return numOfRungs 
    return solveLadder(numOfRungs-1)+solveLadder(numOfRungs-2) 

Answer 3

È un albero con ricorsione. Potrebbe essere necessario tornare indietro per quei casi che non possono funzionare (ad esempio 2-2 per una scala di tre scale).

Answer 4

Questo è infatti strettamente legato alla Fibonacci sequence, come menzionato solo brevemente in uno dei commenti finora: Ogni passo n può essere raggiunta da entrambi i due passaggi seguenti (n-2) o un gradino sotto (n-1), così il numero di possibilità per raggiungere quel passo è la somma delle possibilità di raggiungere quegli altri due passaggi. Infine, c'è esattamente una possibilità per raggiungere il primo passo (e lo zeroth, cioè stare a terra).

Inoltre, poiché il numero di possibilità per passo n dipende solo i risultati per passo n-1 e n-2, non è necessario memorizzare tutti i valori intermedi in una mappa o in un array - le ultime due sono abbastanza!

public static long possForStep(int n) { 
    // current and last value, initially for n = 0 and n = 1 
    long cur = 1, last = 1; 
    for (int i = 1; i < n; i++) { 
     // for each step, add the last two values and update cur and last 
     long tmp = cur; 
     cur = cur + last; 
     last = tmp; 
    } 
    return cur; 
} 

Questo non solo riduce la quantità di codice da una buona azione, ma anche dà una complessità di O (n) nel tempo e O (1) nello spazio, al contrario di O (n) nel tempo e spazio quando si memorizzano tutti i valori intermedi.

Tuttavia, dal momento che anche il tipo long rapidamente troppo pieno come n si avvicina al 100 in ogni caso, lo spazio complessità O (n) non è davvero un problema, in modo da poter altrettanto bene andare con questa soluzione, che è molto più facile leggere.

public static long possForStep(int n) { 
    long[] values = new long[n+1]; 
    for (int i = 0; i <= n; i++) { 
     // 1 for n==0 and n==1, else values[i-1] + values[i-2]; 
     values[i] = (i <= 1) ? 1 : values[i-1] + values[i-2]; 
    } 
    return values[n]; 
} 

Aggiornamento: noti che questo si trova vicino a, ma non proprio la stessa come la sequenza Fibonacci, che inizia 0, 1, 1, 2, 3,... mentre questo va 1, 1, 2, 3, 5, ..., cioè possForStep(n) == fibonacci(n+1).

Answer 5

Questa è la serie di fibonacci. Si può risolvere con eleganza utilizzando la ricorsione in coda ricorsiva:

let ladder n = 
     let rec aux n1 n2 n = 
      if n=0 then (n1 + n2) 
      else aux n2 (n1+n2) (n-1) 
     aux 1 1 (n-2) 

Un più facile da capire non coda codice ricorsiva sarebbe:

let rec ladder n = 
     if n<=2 then n 
     else ladder (n-1) + ladder (n-2) 

si può facilmente tradurre che a Java.

Answer 6

1. voce dell'Elenco

Questo è semplice serie di Fibonacci, se il no di passo che possiamo fare è di 1 o 2 per

• No della scala possibile caso

  1 ------------------ 1

  2 -------------- ---- 2

  3 ------------------ 3

  4 ---------------- --5

  5 ------------------ 8

  6 ------------------ 13

e così via