Количество маршрутов в прямоугольной таблице

@Prositka453 · Регистрация: 24.07.2022

Author24 — интернет-сервис помощи студентам

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

Входные данные

Вводятся два числа N и M — размеры таблицы 1⩽N⩽10,1⩽M⩽10.

Выходные данные

Выведите искомое количество способов.
Пример:
Ввод:
1 10
Вывод:
1

~~Verevkin~~ · 31.07.2022, 13:47

Сообщение от Байт

Да все же очевидно!

@jongl · 31.07.2022, 21:47

Извините за моветон, я делаю это, потому что лень проверять вылет за границы массива.

@TheCalligrapher · 31.07.2022, 22:25

Сообщение от Байт

Вы каждому пути ставите соответствие такой расклал "апельсинов" по корзинам:
k шагов вправо в ряду L - в корзину номер L кладется k апельсинов. Ход вниз - корзина L остается пустой.

Можно и так.

Тогда апельсины - это шаги вниз. Их всего N-1.

А шаги вправо - это промежутки между корзинами. Так как шагов вправо всего M-1, количество корзин равно M.

Далее применяем готовую формулу количества разложений числа N-1 на кортежи из M неотрицательных слагаемых.

@N1per · 30.08.2022, 13:59

Вот это вот работает

:

C++

#include <iostream>
using namespace std;
int main(){
int n,m,i;
cin >> n >> m;
--n; --m;
unsigned long long p = 1;
for(int i = n+1; i <= n+m; ++i) p*= i;
for(int i = 2; i <= m; ++i) p/= i;
 
cout << p;
}

@TheCalligrapher Вездепух 11695 / 6374 / 1724 Регистрация: 18.10.2014 Сообщений: 16,068
	31.07.2022, 22:25	23
	Сообщение от Байт Вы каждому пути ставите соответствие такой расклал "апельсинов" по корзинам: k шагов вправо в ряду L - в корзину номер L кладется k апельсинов. Ход вниз - корзина L остается пустой. Можно и так. Тогда апельсины - это шаги вниз. Их всего N-1. А шаги вправо - это промежутки между корзинами. Так как шагов вправо всего M-1, количество корзин равно M. Далее применяем готовую формулу количества разложений числа N-1 на кортежи из M неотрицательных слагаемых. 0

@Prositka453 0 / 0 / 0 Регистрация: 24.07.2022 Сообщений: 26
		1
	Количество маршрутов в прямоугольной таблице 29.07.2022, 08:49. Показов 6737. Ответов 23 Метки нет (Все метки) В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько у игрока есть способов попасть в правую нижнюю клетку. Входные данные Вводятся два числа N и M — размеры таблицы 1⩽N⩽10,1⩽M⩽10. Выходные данные Выведите искомое количество способов. Пример: Ввод: 1 10 Вывод: 1 0

~~Verevkin~~ Заблокирован
	31.07.2022, 13:47	21
	Сообщение от Байт Да все же очевидно! 0

@jongl 3 / 2 / 2 Регистрация: 04.12.2020 Сообщений: 35
	31.07.2022, 21:47	22
	Извините за моветон, я делаю это, потому что лень проверять вылет за границы массива. 0

	30.08.2022, 13:59