Количество возможных путей вверх по лестнице - программирование

Количество возможных путей вверх по лестнице

Я не могу придумать алгоритм для решения следующей проблемы, я попытался использовать серию for-loops, но это стало слишком сложным:

Лестница имеет шаги n, можно подняться по лестнице, используя любую сочетание шагов 1 или стадий 2. Сколько возможных способов там, чтобы один поднялся по лестнице?

Так, например, если лестница имела 3 шага, это были бы возможные пути:

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

И для 4 шага

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

Любое понимание того, как это можно было бы сделать, было бы весьма полезно. Кроме того, я работаю на Java.

Изменить: я действительно использовал небольшие значения n, но, конечно, было бы аккуратно знать, как управлять большими.

4b9b3361

ОТВЕТЫ

Ответ 1

Интересно, что есть простое решение этой проблемы. Вы можете использовать рекурсию:

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

Всякий раз, когда вы сталкиваетесь с этой "сложной" проблемой, помните, что решение часто бывает довольно изящным и всегда проверяет, можно ли что-то сделать с рекурсией.

EDIT: я предполагал, что вы будете иметь дело с относительно небольшими значениями n в этой задаче, но если вы имеете дело с большими, то метод выше, вероятно, займет много времени Конец. Одним из решений было бы использовать Map, который сопоставлял бы n с countPossibilities(n) - таким образом, не было бы потрачено времени на выполнение сделанного вами вычисления. Что-то вроде этого:

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

Попробуйте это с помощью n = 1000. Второй метод буквально на порядок быстрее первого.

Ответ 2

Это на самом деле тесно связано с последовательностью Фибоначчи, как было сказано вкратце в одном из комментариев: каждый шаг n может быть достигнуто либо с двух шагов ниже (n-2), либо на один шаг ниже (n-1), поэтому количество возможностей для достижения этого шага - это сумма возможностей для достижения этих двух других шагов. Наконец, есть ровно одна возможность достичь первого шага (и нулевого, то есть оставаясь на земле).

Кроме того, поскольку количество возможностей для шага n зависит только от результатов для шага n-1 и n-2, нет необходимости хранить все эти промежуточные значения на карте или в массиве - двух последних достаточно!

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

Это не только уменьшает количество кода за счет хорошей доли, но также дает сложность O (n) во времени и O (1) в пространстве, в отличие от O (n) во времени и пространстве при хранении всех промежуточные значения.

Однако, поскольку даже тип long будет быстро переполняться, поскольку n приближается к 100 в любом случае, сложность пространства O (n) на самом деле не проблема, так что вы можете так же хорошо пойти с этим решением, что много легче читать.

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

Обновление: обратите внимание, что это близко, но не совсем так же, как последовательность Фибоначчи, которая запускает 0, 1, 1, 2, 3,..., в то время как этот идет 1, 1, 2, 3, 5, ..., т.е. possForStep(n) == fibonacci(n+1).

Ответ 3

Я бы использовал динамическое программирование и каждый раз решал проблему, когда лестница 1 ступенька или 2 ступени короче.

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

Ответ 4

Это дерево с рекурсией. Вам может потребоваться отступить для тех случаев, которые не могут работать (например, 2-2 для трех лестничной лестницы).

Ответ 5

Это серия фибоначчи. Вы можете легко решить эту проблему с помощью рекурсивной рекурсии хвоста:

    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)

Легче понять не хвостовой рекурсивный код:

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

Вы можете легко перевести это на Java.

Ответ 6

Последовательность Фибоначчи, сложность O (logn)

def calculate_fibonacci(n):
    # "-1", because the first element of the matrix is Fn+1
    n -= 1
    dict_of_matrices = dict()
    dict_of_matrices[1] = [1, 1, 1, 0]
    # [a,b,c,d] translates to matrix:
    # [a b]
    # [c d]
    j = 1

    # "-2" - skip "0b"
    # "len(bin(n)) - 3" - same as floor(log_2(n))
    max_range = len(bin(n)) - 2 - 1
    for i in range(0, max_range):
        matrix_to_power_2 = multiply_matrices(
            dict_of_matrices[j], dict_of_matrices[j])
        j *= 2
        dict_of_matrices[j] = matrix_to_power_2

    # What we've done here:
    # firstly, read about Fibonacci Q-matrix:
    # http://mathworld.wolfram.com/FibonacciQ-Matrix.html
    # and now: if we want to calculate Fn for n=102,
    # then we need to calculate Q^101
    # in order to do so, we can decomposite 101 to a series of powers of 2, that is
    # 101 = 64 + 32 + 4 + 1
    # 101 dec = 1100101 bin
    # in other words, Q^101 = Q^64 * Q^32 * Q^4 * Q^1
    # and to calculate Qs:
    # Q^2 = Q^1 * Q^1
    # Q^4 = Q^2 * Q^2
    # Q^8 = Q^4 * Q^4
    # Q^16 = Q^8 * Q^8
    # and so on

    string = bin(n)[2:]  # trim "0b"
    result = dict_of_matrices[2 ** (len(string) - 1)]

    for i in range(1, len(string)):
        if string[i] == '0':
            continue
        else:
            result = multiply_matrices(
                result, dict_of_matrices[2 ** (len(string) - i - 1)])

    return result[0]


def multiply_matrices(matrix1, matrix2):
    # matrices look like this:
    # [a b]
    # [c d]
    # and the output matrix:
    # [Fn+1 Fn]
    # [Fn Fn-1]

    Fnp1 = matrix1[0] * matrix2[0] + matrix1[1] * matrix2[2]
    Fn = matrix1[0] * matrix2[1] + matrix1[1] * matrix2[3]
    Fnm1 = matrix1[2] * matrix2[1] + matrix1[3] * matrix2[3]
    return [Fnp1, Fn, Fn, Fnm1]


n = 100
print(format(calculate_fibonacci(n), ',d'))

Ответ 7

  • Элемент списка

Это простой ряд фибоначчи, если нет шага, который мы можем предпринять, это 1 или 2 для

  • Нет возможного случая для лестницы

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

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

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

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

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

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

и т.д.