java - programacion - Contar el número de rutas posibles en la escalera.

serpientes y escaleras en java

Question

Parece que no se me ocurre un algoritmo para resolver el siguiente problema, intenté usar una serie de bucles for, pero se volvió demasiado complicado:

Una escalera tiene n pasos, uno puede subir la escalera usando cualquier combinación de pasos de 1 o pasos de 2. ¿Cuántas maneras posibles hay para subir la escalera?

Entonces, por ejemplo, si la escalera tuviera 3 pasos , estos serían los caminos posibles:

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

Y para 4 pasos.

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

Cualquier información sobre cómo se podría hacer esto sería muy apreciada. Además, estoy trabajando en Java.

Edit: De hecho, iba a usar valores de n pequeños, pero ciertamente sería bueno saber cómo administrar con valores más grandes.

Answer 1

1. Elemento de lista

Esta es una serie simple de fibonacci si el número de pasos que podemos tomar es 1 o 2 para

• No hay caso de escalera posible

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

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

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

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

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

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

y así

Answer 2

Curiosamente, hay una solución simple para este problema. Puedes usar recursion:

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

Siempre que enfrente este tipo de problema "complicado", tenga en cuenta que la solución a menudo es bastante elegante, y siempre verifique si se puede hacer algo con recursión.

EDITAR : Supuse que usted trataría con n valores relativamente pequeños en este problema, pero si trata con valores grandes, el método anterior probablemente tomará una buena cantidad de tiempo para finalizar. Una solución sería utilizar un Map que countPossibilities(n) n para countPossibilities(n) : de esta manera, no habría tiempo perdido haciendo un cálculo que ya ha hecho. Algo como esto:

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;
}

Intenta esto con n = 1000 . El segundo método es, literalmente, órdenes de magnitud más rápido que el primero.

Answer 3

De hecho, esto está estrechamente relacionado con la secuencia de Fibonacci , como se mencionó brevemente en uno de los comentarios hasta el momento: se puede llegar a cada paso n desde dos pasos a continuación ( n-2 ) o un paso a continuación ( n-1 ). por lo tanto, el número de posibilidades para llegar a ese paso es la suma de las posibilidades para alcanzar esos otros dos pasos. Finalmente, hay exactamente una posibilidad para llegar al primer paso (y al cero, es decir, permanecer en el suelo).

Además, como el número de posibilidades para el paso n depende solo de los resultados del paso n-1 y n-2 , no es necesario almacenar todos esos valores intermedios en un mapa o en una matriz, ¡los dos últimos son suficientes!

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;
}

Esto no solo reduce la cantidad de código en una buena parte, sino que también proporciona una complejidad de O (n) en el tiempo y O (1) en el espacio, a diferencia de O (n) en el tiempo y el espacio cuando se almacenan todos los valores intermedios. .

Sin embargo, dado que incluso el tipo long se desbordará rápidamente cuando n acerque a 100 de todos modos, la complejidad del espacio de O (n) no es realmente un problema, por lo que puede ir con esta solución, que es mucho más fácil de leer.

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];
}

Actualización: Tenga en cuenta que esto está cerca, pero no es lo mismo que la secuencia de Fibonacci, que comienza con 0, 1, 1, 2, 3,... mientras que esta va 1, 1, 2, 3, 5, ... , es decir, possForStep(n) == fibonacci(n+1) .

Answer 4

Es un árbol con recursión. Es posible que deba retroceder en esos casos que no pueden funcionar (por ejemplo, 2-2 para una escalera de tres escaleras).

Answer 5

Esta es la serie de fibonacci. Puedes resolverlo elegantemente usando la recursividad recursiva de la cola:

    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 código recursivo sin cola más fácil de entender sería:

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

Puedes traducirlo fácilmente a Java.

Answer 6

Yo usaría la programación dinámica y cada vez solucionaría un problema donde la escalera es 1 peldaño o 2 peldaños más cortos.

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