Question

В торговом центре остановился эскалатор, а Андрею срочно нужно спуститься вниз. За один шаг он может спуститься на 1, 2 или 3ступеньки. Найдите количество способов добраться вниз, если всего нужно перешагнуть через 21 ступеньку.Необходимо привести развёрнутое решение и (или) код программы, который решает данную задачу (если выбираете второй способ, то опишите алгоритм программы, а также укажите используемый язык программирования и его версию).СРОЧНООО ПОЖАЛУЙСТА ​

Answer 1

Ответ:

Объяснение:

вот всё что нужно ( я тоже щас эту олимпиаду пишу)

Answer 2

Ответ:

кароче вот код если что

Объяснение:

#include <iostream>

#include <vector>

using namespace std;  

int main() {

   int n;

   cin >> n;

   vector <int> dp(n + 4);

   dp[0] = 0;

   dp[1] = 0;

   dp[2] = 0;

   dp[3] = 1;

   for (int i = 4; i < dp.size(); i++) {

       dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

   }

   cout << dp[dp.size() - 1] << " ";

}

Answer 3

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

pythonCopy code
def count_ways_to_reach_bottom(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4

    # Создаем массив для хранения количества способов для каждой ступеньки
    ways = [0] * (n + 1)

    # Известные базовые случаи
    ways[0] = 0
    ways[1] = 1
    ways[2] = 2
    ways[3] = 4

    # Заполняем массив, начиная с 4-й ступеньки
    for i in range(4, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3]

    return ways[n]

n = 21
result = count_ways_to_reach_bottom(n)
print(f"Количество способов достичь {n} ступенек: {result}")

Этот код вычисляет количество способов достичь 21 ступеньку. Вы можете изменить значение n, чтобы рассчитать количество способов для другого числа ступенек.