Question

С++ Количество маршрутов в прямоугольной таблице В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку.

Answer 1

Ответ:

#include <iostream>

using namespace std;

int x, y, value = 0;

void calc(int px, int py){

   if(px == x - 1 && py == y - 1) {

       value++;

       return;

   }

   if(px + 1 < x) calc(px + 1, py);

   if(py + 1 < y) calc(px, py + 1);

}

int main(){

   cin >> x >> y;

   calc(0, 0);

   cout << value;

   return 0;

}

Объяснение:

Сделал "по-тупому": рекурсией.

P. s. Если Вам помог ответ, отметьте его как лучший и жмякните на "Спасибо", пожалуйста. Это мотивирует продолжать давать ответы дальше.

Answer 2

Эта задача может быть решена с использованием динамического программирования. Количество способов достичь каждой клетки (i, j) будет равно сумме количества способов достичь клеток сверху (i-1, j) и слева (i, j-1).

Для каждой клетки (i, j) вычислим количество способов достичь эту клетку (num_ways[i][j]) используя следующее рекуррентное соотношение:

$\text{num\_ways}[i][j] = \text{num\_ways}[i-1][j] + \text{num\_ways}[i][j-1]$

Начнем с заполнения базовых случаев:

$\text{num\_ways}[0][j] = \text{num\_ways}[i][0] = 1$ для всех $0 \leq i < N$ и $0 \leq j < M$.

Используя это, мы можем заполнить всю таблицу и найти количество способов достичь правой нижней клетки (N-1, M-1).

Вот пример кода на C++ для решения этой задачи:

cppCopy code
#include <iostream>
#include <vector>

int countRoutes(int N, int M) {
    // Создаем двумерный вектор для хранения количества способов
    std::vector<std::vector<int>> num_ways(N, std::vector<int>(M, 0));

    // Инициализируем базовые случаи
    for (int i = 0; i < N; ++i)
        num_ways[i][0] = 1;

    for (int j = 0; j < M; ++j)
        num_ways[0][j] = 1;

    // Заполняем таблицу согласно рекуррентному соотношению
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < M; ++j) {
            num_ways[i][j] = num_ways[i - 1][j] + num_ways[i][j - 1];
        }
    }

    // Возвращаем количество способов достичь правой нижней клетки
    return num_ways[N - 1][M - 1];
}

int main() {
    int N, M;
    std::cout << "Введите размеры таблицы N и M: ";
    std::cin >> N >> M;

    int ways = countRoutes(N, M);
    std::cout << "Количество способов достичь правой нижней клетки: " << ways << std::endl;

    return 0;
}

Этот код вычисляет количество способов достичь правой нижней клетки в прямоугольной таблице размера N × M, используя динамическое программирование.