Пути через таблицу
Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо,
существует ровно 6 маршрутов до правого нижнего угла сетки.
Сколько существует таких маршрутов в сетке 20×20?
Решение (F#)
- для того, чтобы пройти таблицу N x N, необходимо пройти N клеток вправо и N клеток вниз, совершив при этом 2N передвижений
- итак имеем 2N шагов из них N вправо, остальные (N) - вниз
- рассмотрим пример для таблицы 3х3: всего нужно сделать 6 шагов - 3 вправо и 3 вниз в любой последовательности, обозначим движение вниз синим цветом, всего получим 20 возможных путей
- это ничто иное как сочетания из 6 по 3, значит для решения не будем перебирать все возможные маршруты а воспользуемся формулой
числа сочетаний: Число сочетаний из N по K равно биномиальному коэффициенту N! / ( K! * (N-K)! )
- для N=6 и K=3 получим 1*2*3*4*5*6/(1*2*3 * 1*2*3) = 20
- тогда код решения будет весьма тривиален:
- объявляем рекурсивную функцию нахождения факториала fact, здесь нет хвостовой рекурсии - нет смысла усложнять, потому что максимальная глубина рекурсии не превышает 40 в нашем случае
- считаем 40!/(20! * 20!)
- выводим ответ
- bigint используется из-за того, что промежуточные числа не входят в int64