@Mrsnek007

Как посчитать кол-во возможных исходов?

Есть доска M на N клеток. Возможно ходить безконечно, но только вниз или вправо. Нужно пройти от левого верхнего края до правого нижнего
Задача: посчитать, сколько возможных исходов существует
Пример доски:
1 1 1 1
1 1 1 1
1 1 1 1
  • Вопрос задан
  • 151 просмотр
Решения вопроса 2
wataru
@wataru
Ответ - количество сочетаний по n-1 из (n+m-2), или сколько способов выбрать n-1 объект из n+m-2.

Это потому что нужно обязательно сделать n-1 шагов вниз и m-1 шагов вправо. Вопрос только, в каком порядке их делать. Всего будет сделано n-1+m-1 шагов и из них надо выбрать какие-то n-1 вниз, остальные будут шаги вправо. Вот и получаются сочетания.

Можно считать треугольником Паскаля, получится в точности то же, что описал poznavaka,
можно считать по формуле факториалов: (n+m-2)! / (n-1)! / (m-1)!

Для вашего примера, где N=3 и M=4 ответ будет 5!/2!/3! = 120/2/6 = 10.
Ответ написан
poznavaka
@poznavaka
Программист под Android, Web-разработчик
Правый верхний угол задает кол-во ячеек вверх и вправо и означает кол-во проходов:
1 5 15  35  70
1 4 10  20  35
1 3  6  10  15
1 2  3   4  5
0 1  1   1  1

K(n,m) = K(n-1,m) + K(n,m-1)
K(n,m) = n*m, при n или m равное 2
K(n,m) = 1, при n или m равное 1  
K(n,m) = 0, при n и m равное 1


Это можно реализовать рекурсией, останавливая его при n или m равное 2.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
Griboks
@Griboks
Нисколько. Прийти в правый Нижний угол невозможно.
Ответ написан
@4iloveg
Full-Stack HTML Developer
Это же просто: 0 возможных исходов. Как указано в условии - из верхнего левого угла невозможно дойти до нижнего правого угла, так как доступен только ход вниз или влево.
Ответ написан
@dmshar
Ответ - 10.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
от 50 000 руб.
АО «НИИМЭ» Зеленоград
от 100 000 до 170 000 руб.
O.Vision Санкт-Петербург
от 200 000 до 280 000 руб.