Оглавление > Пути через таблицу
06.03.2023

Пути через таблицу

Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.

Сколько существует таких маршрутов в сетке 20×20?

Решение (F#)

  • для того, чтобы пройти таблицу N x N, необходимо пройти N клеток вправо и N клеток вниз, совершив при этом 2N передвижений
  • итак имеем 2N шагов из них N вправо, остальные (N) - вниз
  • рассмотрим пример для таблицы 3х3: всего нужно сделать 6 шагов - 3 вправо и 3 вниз в любой последовательности, обозначим движение вниз синим цветом, всего получим 20 возможных путей

варианты для таблицы 3х3

  • это ничто иное как сочетания из 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!)
    • выводим ответ
let rec fact n = 
  if n=1 then bigint 1 else bigint n * fact (n-1)

let answer =
  let f20 = fact 20
  (fact 40)/(f20*f20)

printfn $"the answer is {answer:N0}" //the answer is 137 846 528 820
  • bigint используется из-за того, что промежуточные числа не входят в int64