Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.
Сколько существует таких маршрутов в сетке 20×20?
Решение
Размер сетки не имеет никакого значения, поэтому для простоты разберём на примере 2*2.
Маршрут должен вести из левого верхнего угла в правый нижний. Между этими углами по горизонтали 2 шага и по вертикали 2 шага.
Значит, маршрут состоит из 4-х шагов, где 2 шага обязательно горизонтальные и 2 шага обязательно вертикальные. Вот возможные комбинации этих шагов:
ГГВВ, ГВГВ, ГВВГ,
ВВГГ, ВГВГ, ВГГВ
В общем случае нам нужно найти количество комбинаций из N элементов одного типа и M элементов другого типа. Это типичная задача комбинаторики, поэтому можно смело гуглить формулу:
В данной формуле 40 это общее количество элементов (n), а 20 это количество элементов одного из типов (k, соответственно все остальные будут другого типа).
Ответ получен даже без программного кода
Но если эту задачу именно программировать, мы встретим один подвох, а именно вычисление факториалов. Проблема в том, что 40! это ОЧЕНЬ большое число, которое не помещается даже в 64 бита.
Поэтому выходы здесь такие:
- применять арифметику больших чисел в виде готовой библиотеки (да, здесь можно, потому что задача про другое)
- писать эту арифметику самим, если хочется хардкора
- сокращать факториалы, участвующие в дроби.
У нас тут 40! делится на 20!, а потом ещё раз делится на 20!.
Первое деление 40! / 20! сокращается так, что остаётся только произведение чисел с 21 по 40, в связи с чем я модифицировал функцию вычисления факториала, чтобы она считала его не с 1.
Но факториал (21..40) всё равно громадное число. Второе деление уже так просто не сократишь, но очевидно, что в 20! есть множители, на которые делится (21..40)!.
Поэтому я просто на каждом шаге вычисления 40! добавил проверку на деление одним из множителей 20!, так что текущее произведение всё время делится на доступные множители и поэтому не может сильно вырасти. Уже использованные множители помечаются в массиве divs, чтобы не быть использованными второй раз.
Ссылка на онлайн-компилятор языка C с текстом программы
Вся подборка задач:
