Головоломка способностей

Question

Рассмотрим точку P (n, n) в декартовой системе координат. Робот должен начать с начала и достичь этой точки. Единственные шаги Робот может взять:

• 1 единица справа
• 1 единица вверх.

Сколько различных путей может пройти робот до точки P?

Есть ли оптимальный путь к точке P? (Оба шага вверх и вправо происходят одинаково стоимость).

Answer 1

Общее количество путей составляет

(2n choose n)

, поскольку вы должны сделать n правильных шагов и n шагов вверх, чтобы закончиться в точке (n,n), но в порядке, в котором вы делаетешаги не имеют значения.

Таким образом, общее количество шагов составляет 2n, из которых n правильные, а n повышенные.Выберите позиции для правильных шагов (2n choose n) способами, а остальные шаги должны быть шагами вверх.

Ни один путь не лучше любого другого, так как все пути используют одинаковое количество шагов вверх и вправо (оба n).

Answer 2

Прокрутите в этой статье в Википедии (каталонский номер) , пока не дойдете до следующей картинки.Ответ есть.

Таким образом, общее количество путей равно

Примечание: это формальное только для монотонногодорожки, не пересекающие диагональ.Если вы хотите разрешить пересечение диагонали, оно должно немного измениться.Для этого используйте рекурсию:)

Надеюсь, это полезно.

Answer 3

Должно быть (2n!) / (N! * N!).

Объяснение:

Вы должны достичь от начала координат (0,0) до (n, n) Допустим, v - 1 единица по вертикали вверх, а h - 1 единица по горизонтали вправо. Все пути будут выглядеть так - {vvvhhhvhhhvh.... , vvhhvvhhhvvv...,........) с v и h, распределенными по длине числа v + число h, и это должно быть

n + n = 2n.

Теперь общее количество путей будет составлять комбинацию vs и hs в 2n местах. Это будет равно

(п + п)! / (П! * П!)

, поскольку v и h повторяются. Если бы было какое-то другое подразделение, такое как a или b, это также было бы рассмотрено в этом. Я думаю, что это не будет каталонское число , как указано. Rgds, Softy