Напишите программу для вычисления количества способов подняться по лестнице на Python.
Задача: Имея n ступеней, человек, стоящий внизу лестницы, хочет подняться наверх. Этот человек может сделать 1 шаг или 2 шага за раз. Подсчитайте, сколько способов он или она может добраться до вершины.
Вы можете увидеть пример на картинке. Значение n равно 3, и есть 3 способа подняться на вершину.
Например:
Вход: n = 1 Выход: 1 Есть только один способ подняться на 1 ступеньку Вход: n = 2 Выход: 2 Есть два пути: (1, 1) и (2) Вход: n = 4 Выход: 5 (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)
В этой статье TipsMake.com вместе с вами научится писать программу для подсчета количества способов подняться по лестнице на Python.
Метод 1: мы будем использовать рекурсию для решения этой проблемы
Мы можем легко увидеть рекурсию в этой задаче. Человек может попасть на n-й шаг с n-1-го шага или с n-2-го шага. Поэтому для каждого из n-х шагов попробуем найти количество способов добраться до n-1 и n-2-й ступенек и сложить их, чтобы получить ответ на n-ю ступеньку. При таком подходе имеем следующее выражение:
пути(n) = пути(n-1) + пути(n-2)
Приведенное выше выражение на самом деле является выражением чисел Фибоначчи, но следует отметить, что значение way(n) равно fibonacci(n+1).
способы (1) = выдумка (2) = 1 способы (2) = выдумка (3) = 2 пути (3) = выдумка (4) = 3
Чтобы лучше понять, давайте обратимся к дереву рекурсии ниже:
Ввод: N = 4 fib(5) ‘3″ / fib(4) fib(3) ‘2″ // / fib(3) fib(2)fib(2) fib(1) / ‘1″ ‘1″ // выдумка(1) выдумка(0) выдумка(2) выдумка(1)
Таким образом, мы можем использовать функцию для чисел Фибоначчи, чтобы найти значение путей (n). Вот пример кода:
# Программа Python для подсчета # способов достижения n-й ступеньки # Рекурсивная функция для поиска # N-го числа Фибоначчи def fib(n): if n
Обобщение проблемы
Как посчитать количество способов, если человек может подняться по m ступеням за заданное количество m. Например, m равно 4, тогда человек может подняться по 1 лестнице, 2 лестницам, 3 лестницам или 4 лестницам одновременно.
Чтобы обобщить описанный выше подход, мы можем использовать следующее рекурсивное соотношение:
пути(n, m) = пути(n-1, m) + пути(n-2, m) + . пути(нм, м)
В этом подходе, чтобы добраться до n-й ступеньки, попытайтесь подняться по всем лестницам, меньшим n, чем текущая лестница.
Вот пример кода для этого обзора:
# Программа для подсчета количества способов # добраться до n-й ступеньки # Рекурсивная функция, используемая countWays def countWaysUtil(n, m): if n
Способ 2: запомнить
Мы также можем использовать восходящий подход dp для решения этой проблемы.
Мы можем создать массив dp() и инициализировать его значением -1.
Всякий раз, когда мы видим, что подзадача не решена, мы можем вызывать метод рекурсивно.
В противном случае мы останавливаем рекурсию, если подзадача решена.
Пример кода выглядит следующим образом:
# Программа на Python для подсчета количества # способов добраться до N-й ступеньки # Простая рекурсивная программа для # нахождения N-го числа Фибоначчи def fib(n, dp): if (n
Способ 3: динамическое программирование
Этот способ использует технику динамического программирования для решения проблемы.
Мы создаем таблицу res() восходящим образом, используя следующую связь:
res(i) = res(i) + res(ij) для каждого (ij) >= 0
Таким образом, i-й индекс массива будет содержать количество способов, необходимых для перехода в i-й порядок с учетом всех возможных подъемов (т.е. от 1 до i).
Вот пример кода, следующего за этим подходом:
# Программа для подсчета количества # способов добраться до n-й ступеньки # Рекурсивная функция, используемая countWays def countWaysUtil(n, m): # Создает список res со всеми элементами 0 res = (0 для x в диапазоне (n)) res(0), res(1) = 1, 1 для i в диапазоне (2, n): j = 1, а j
Способ 4: использование раздвижных окон
Таким образом, мы будем более эффективно использовать подход динамического программирования.
В этом подходе для i-й лестницы мы сохраняем окно, содержащее общее количество последних m ступенек, по которым мы можем подняться по i-й лестнице. Вместо запуска внутреннего цикла мы сохраняем результат цикла во временной переменной. Убираем элементы предыдущего окна и добавляем элемент текущего окна.
Вот пример кода:
# Программа на Python3 для подсчета количества # способов добраться до n-й ступеньки, когда # пользователь поднимается на 1 . м лестниц за раз. # Функция для подсчета количества путей # для достижения s-й лестницы def countWays(n, m): temp = 0 res = (1) for i in range(1, n + 1): s = i – m – 1 e = i – 1 if (s >= 0): temp -= res(s) temp += res(e) res.append(temp) return res(n) # Код драйвера n = 5 m = 3 print(‘Số cách là =’, countWays(n, m)) # Этот код предоставлен 31ajaydandge
Способ 5: используйте простую математику
В этом подходе мы просто подсчитываем количество наборов с 2. Этот метод применим только в том случае, если проблема упорядочения во время подсчета шагов не важна.
# Здесь n/2 выполняется для подсчета числа 2 в n # 1 добавляется для случая, когда нет 2. # например: если n=4, то будет 3. # Набор {1,1,1,1}, имеющий нет 2. # Наборы {1,1,2} и {2,2} (n/2), содержащие 2. print(“Количество способов, когда порядок ” “шагов не имеет значения: “, 1 + (n / / 2)) # Этот код предоставлен rohitsingh07052
Метод 6: используйте метод матричной экспонентации
Таким образом, мы используем метод матричной экспонентации для решения проблемы.
Количество способов подняться по n-й лестнице (с учетом порядка) равно сумме количества способов подняться и повернуться на n-1-й лестнице и на n-2-й ступени.
Это соответствует следующему соотношению повторения:
f(n) = f(n-1) + f(n-2) f(1) = 1 f(2) = 2
где f(n) — количество шагов до n-го шага.
Примечание:
f(1) = 1 vì chỉ có 1 cách bước lên đỉnh cầu thang có 1 bậc, n=1, {1} f(2) = 2 vì chỉ có 2 cách bước lên đỉnh cầu thang có 1 bậ в, п=2 , {1,1},{2}
Это своего рода линейное рекуррентное соотношение с постоянными коэффициентами, и мы можем решить их методом матричного возведения в степень. По сути, этот метод находит матрицу преобразования для заданного рекуррентного отношения и итеративно применяет это преобразование к базисному вектору, чтобы найти решение.
F(n) = CN-1F(1)
где C — матрица преобразования, F(1) — базисный вектор, а F(n) — искомое решение.
Следовательно, в нашем случае матрица C будет:
0 1 1 1
C N-1 можно вычислить с помощью метода «разделяй и властвуй» за O((K^3) Log n), где K — размер C.
И F(1):
1 2
Например, для n=4:
F(4) = С 3 F(1)
С 3 =
1 2 2 3
Следовательно, C 3 F(1) =
5 8
Пример кода выглядит следующим образом:
# Вычисляет A*B # где A,B – квадратные матрицы def mul(A, B, MOD): K = len(A); C = ((0 для i в диапазоне (K)) для j в диапазоне (K)) ; для i в диапазоне (1, K): для j в диапазоне (1, K): для k в диапазоне (1, K): C(i)(j) = (C(i)(j) + A(i )(k) * B(k)(j)) % MOD; вернуть С; # Вычисляет A^n def power( A, n): if (n == 1): return A; if (n % 2 != 0): # n нечетно # A^n = A * ( A^(n-1) ) A = mul(A, power(A, n – 1), 1000000007); иначе: # n четно # A^n = (A^(n/2)) * (A^(n/2)) A = power(A, n // 2); А = мул(А, А, 1000000007); вернуть А; defways(n): F = (0 для i в диапазоне (3)); F(1) = 1; F(2) = 2; К = 2; МОД = 1000000007; # создать матрицу K*K C = ((0 для i в диапазоне (K+1)) для j в диапазоне (K+1)); ”’ * Матрица с (i+1)-м элементом как 1 и последней строкой содержит константы ( (0 1 0 0 * . 0) (0 0 1 0 . 0) (0 0 0 1 . 0) (. . . . . . . .) (. . . . . .) (c(k) * c(k-1) c(k-2). c1)) ) ”’ для i в диапазоне (1,K): C( я) (я + 1) = 1; # Последняя строка – это константы c(k) c(k-1) . c1 # f(n) = 1*f(n-1) + 1*f(n-2) C(K)(1) = 1; С(К)(2) = 1; если (п
Обобщение проблемы
Дан массив A{a1, a2, ., am}, содержащий все допустимые шаги, вычислить количество шагов, необходимых для перехода вверх по n-й упорядоченной лестнице.
Например:
Ввод: A = (1,2) n = 4 Выход: 5 Giải thích: Tìm số cách để leo lên bậc thang thứ 4, mỗi lần có thể leo 1 hoặc 2 bước. Số cách là: {1,1,1,1} {1,1,2} {1,2,1} {2,1,1} {2,2} = 5 Ввод: A = (2,4, 5) n = 9. Số cách là: {5,4} {4,5} {2,2,5} {2,5,2} {5,2,2} = 5
Количество способов подняться на n-й шаг определяется следующим рекурсивным соотношением:
Пусть K — наибольший элемент в A.
Шаг 1: вычислить базисный вектор F(1) (включая f(1). f(K))
Это можно сделать за время O(m2K), используя следующий подход к динамическому программированию:
Давайте перевернем A = {2,4,5) в качестве примера. Чтобы вычислить F(1) = {f(1), f(2), f(3), f(4), f(5)}, мы будем поддерживать исходный пустой массив и итеративно объединять Ai с ним и для каждого Ai найдем количество способов достижения (Ai-1, до Ai).
Следовательно, для А = {2, 4, 5)
Пусть T будет исходным пустым массивом:
Итерация 1: T = {2} n = {1,2} dp = {0,1} (количество способов достичь n=1,2 с шагами, заданными T) Итерация 2: T = {2,4} n = {1,2,3,4} dp = {0,1,0,2} (Количество способов достичь n=1,2,3,4 с шагами, заданными T) Итерация 3: T = {2, 4,5} n = {1,2,3,4,5} dp = {0,1,0,2,1} (Количество способов достичь n=1,2,3,4,5 с заданными шагами по Т)
Примечание: поскольку некоторые значения уже рассчитаны (1,2 для итерации 2.), мы можем избежать их в цикле.
После всех итераций массив dp будет: (0,1,0,2,1)
Таким образом, базисный вектор F(1) для A = (2,4,5):
0 1 0 2 1
Теперь, когда у нас есть базисный вектор F(1), довольно легко вычислить C (матрицу преобразования).
Шаг 2: Рассчитать C, матрицу преобразования
Это матрица с элементами Ai, i+1 = 1, а последняя строка содержит константы.
Теперь константы можно определить по присутствию этого элемента в A.
Таким образом, для A = (2,4,5) константы будут c = (1,1,0,1,0) (Ci = 1, если K-i+1) присутствует в A, или 0, если 1
Следовательно, матрица преобразования C для A = (2,4,5):
0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 Шаг 3: вычислить F(n)
Для расчета F(n) используется следующая формула:
F(n) – Cn-1F(1)
Теперь, когда у нас есть C и F(1), мы можем использовать метод «разделяй и властвуй», чтобы найти C n-1 и оттуда найти результат.
Вот пример кода:
# Вычисляет A*B, когда A,B – квадратные матрицы одинаковой # размерности) def mul(A, B, MOD): K = len(A); C = ((0 для i в диапазоне (K)) для j в диапазоне (K)) ; для i в диапазоне (1, K): для j в диапазоне (1, K): для k в диапазоне (1, K): C(i)(j) = (C(i)(j) + A(i )(k) * B(k)(j)) % MOD; вернуть С; def power(A, n): если (n == 1): вернуть A; if (n % 2 != 0): # n нечетно # A^n = A * ( A^(n-1) ) A = mul(A, power(A, n – 1), 1000000007); иначе: # n четно # A^n = (A^(n/2)) * (A^(n/2)) A = power(A, n // 2); А = мул(А, А, 1000000007); вернуть А; def initialize(A): # Инициализирует базовый вектор F(1) K = A(len(A)-1); # Предположим, что A отсортировано F = (0 для i в диапазоне (K+1)); dp = (0 для i в диапазоне (K+1)); дп(0) = 0; дп(А(1)) = 1; # Существует один и только один способ добраться # до первого элемента F(A(1)) = 1; for i in range(2,len(A)): # Перебираем A(i-1) в A(i) и заполняем массив dp для j in range(A(i – 1) + 1,A(i) +1): # dp(j) = dp(jA(0)) + . + dp(jA(i-1)) для k в диапазоне (1,i): dp(j) += dp(j – A(k)); # Будет еще один способ получить A(i) dp(A(i)) += 1; F(A(i)) = dp(A(i)); вернуть F; defways(A, n): K = A(len(A) – 1); # Предполагая, что A отсортирован F = initialize(A); # O(m^2*K) MOD = 1000000007; # создать матрицу K*K C = ((0 для i в диапазоне (K+1)) для j в диапазоне (K+1)); ”’ * Матрица с (i+1)-м элементом как 1 и последней строкой содержит константы ( (0 1 0 0 * . 0) (0 0 1 0 . 0) (0 0 0 1 . 0) (. . . . . . . .) (. . . . . .) (c(k) * c(k-1) c(k-2). c1)) ) ”’ для i в диапазоне (1,K): C( я) (я + 1) = 1; # Последняя строка – это константы c(k) c(k-1) . c1 # f(n) = 1*f(n-1) + 1*f(n-2) для i в диапазоне (1, len(A)): C(K)(K – A(i) + 1 ) = 1; если (п
Примечание. Этот подход идеален, когда n слишком велико для использования циклов.
Пример: Вам следует рассмотреть этот подход, когда 1
Надеюсь, эта статья будет вам полезна.
