Question

C++ (Сириус) Пчёлка Представьте себе пчелиные соты — поле из шестиугольных клеток со стороной, состоящей из N клеток. В верхней левой клетке A находится пчёлка. За один ход она может переползти на клетку вниз, на клетку вниз-вправо или на клетку вверх-вправо (вверх и влево пчёлка не ползает). Требуется написать программу, которая найдёт количество способов, которыми пчёлка может переместиться из клетки A в противоположную клетку B по указанным правилам. Входные данные Единственная строка содержит единственное число N — размеры шестиугольного поля (2 ≤ N ≤ 12). Выходные данные Выведите единственное целое число — количество способов. Примеры Ввод Вывод 2 11 3 291

Answer 1

Программа:
С++:

#include <iostream>

using namespace std;

int main() {

   int N, m, i, j;

   cin >> N;

   m = 2 * N - 1;

   

   int fields[m][m];

   for(i = 0; i < m; i++)

       for(j = 0; j < m; j++)

           fields[i][j] = 0;

   

   for(i = 0; i < N; i++)

       fields[i][0] = fields[0][i] = 1;

   

   for(i = 1; i < m; i++)

       for(j = 1; j < m; j++)

           if(N > abs(i - j))

               fields[i][j] = fields[i - 1][j] + fields[i][j - 1] + fields[i - 1][j - 1];

   cout << fields[m - 1][m - 1];

   return 0;

}

Объяснение:

Сначала регистрируем переменные целочисленного типа: N - для ввода, m - для количества сот, i - для циклов, j - для цикла. Далее вводится само N, находится m по формуле: m = 2 * N - 1.

Регистрируется массив из m на m элементов, который заполняется нулями в цикле. Далее, с помощью ещё одного цикла, некоторые элементы заполняются единицами для будущих вычислений в цикле. И в следующем цикле i принимает значения от 1 до m - 1, j принимает значения от 1 до m - 1 (i - номер строки, j - номер столбца). Если N больше абсолютного (положительного) числа разницы i - j, то выполняется определенное действие. Вот и вся логика.

В конце выводится элемент массива с индексом столбца m - 1 и индексом строки m - 1.

Результат:

2

11

3

291

#SPJ1

Answer 2

Для решения этой задачи можно использовать динамическое программирование. Создадим двумерный массив dp, где dp[i][j] будет представлять количество способов, которыми пчёлка может добраться из клетки A в клетку с координатами (i, j).

Изначально установим dp[0][0] = 1, так как пчёлка уже находится в клетке A.

Затем, для каждой клетки (i, j) в поле, мы будем рассматривать три возможных направления движения пчёлки: вниз, вниз-вправо и вверх-вправо. Мы добавим количество способов из клеток, из которых можно попасть в клетку (i, j), чтобы найти общее количество способов для (i, j).

Итак, код в C++ для решения этой задачи выглядит следующим образом:

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

using namespace std;

int main() {
    int N;
    cin >> N;

    // Создаем двумерный массив dp и инициализируем его нулями
    vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));

    // Начальная клетка A
    dp[0][0] = 1;

    // Вычисляем количество способов для каждой клетки
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            if (i + 1 <= N) dp[i + 1][j] += dp[i][j];  // Двигаемся вниз
            if (i + 1 <= N && j + 1 <= N) dp[i + 1][j + 1] += dp[i][j];  // Двигаемся вниз-вправо
            if (j + 1 <= N) dp[i][j + 1] += dp[i][j];  // Двигаемся вверх-вправо
        }
    }

    // Количество способов для клетки B
    int result = dp[N][N];

    cout << result << endl;

    return 0;
}

Этот код считывает значение N, создает массив dp, заполняет его и выводит количество способов для клетки B.