Условие задачи
Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?
Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.
Входные данные
Два натуральных числа $m$ и $n$, не превышающие 30.
Выходные данные
Вывести количество способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний.
Тесты
| № | Ввод | Вывод |
| 1 | 4 5 | 10 |
| 2 | 3 14 | 105 |
| 3 | 11 17 | 5311735 |
| 4 | 20 21 | 68923264410 |
| 5 | 30 30 | 30067266499541040 |
Код программы (циклы)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; if (m > n) swap(n, m); long long den = 1, ways = 1; // den - знаменатель, ways - количество способов. for (int i = 0; i < m - 1; i++) { ways *= n + i; if (ways % den == 0) { ways /= den; den++; } } cout << ways; return 0; } |
Решение
Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.
Код программы (динамическое программирование)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #define N 30 int main() { // Создаем треугольную матрицу для хранения всех ответов long *x[N]; for (int i=0; i < N; ++i) x[i] = new long[i+1]; // Находим все ответы x[0][0] = 1; for (int i=1; i < N; ++i) { x[i][0] = 1; for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1]; x[i][i] = 2 * x[i][i-1]; } // Проходим все тесты int m, n; std::cin >> m >> n; std::cout << x[std::max(n,m)-1][std::min(n,m)-1]; } |
Решение
Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.