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