Для начала заметим, что каждое движение по линии сетки изменяет лишь одну из координат, причем ровно на 1 единицу. Значит, оптимальный путь не может состоять менее чем из [tex]6-0=6[/tex] движений по горизонтали и [tex]6-0=6[/tex] движений по вертикали. При этом, нетрудно заметить, путь [tex](0;0)\to(1;0)\to(2;0)\to...\to(6;0)\to(6;1)\to(6;2)\to...\to(6;6)[/tex] состоит ровно из такого числа перемещений. А значит и любой кратчайший путь содержит по 6 движений по вертикали и 6 движений по горизонтали, причем каждое из них (т.к. за одно перемещение координата меняется ровно на 1 единицу) должно увеличивать соответствующую координату. Окончательно, каждый кратчайший путь состоит из 6 движений вверх и 6 движений направо.
Рассмотрим следующую задачу: найти [tex]G_n[/tex] - число кратчайших путей из [tex](0;0)[/tex] в [tex](n;n)[/tex] по линиям сетки. Рассуждая аналогично, получим, что каждый кратчайший путь состоит из n движений вверх и n движений направо.
Тогда количество таких путей совпадает с числом бинарных векторов длины [tex]2n[/tex] (общее число движений), у которых число 0 и 1 равно [tex]n[/tex] (по [tex]n[/tex] движений каждого вида), т.е. [tex]G_n=C_{2n}^n=\dfrac{(2n)!}{n!n!}[/tex]
Посчитаем число путей, содержащих точку [tex](2;2)[/tex]. Оно равно произведению числа путей от [tex](0;0)[/tex] до [tex](2;2)[/tex] и числа путей от [tex](2;2)[/tex] до [tex](6;6)[/tex]. Первый множитель равен [tex]G_2[/tex], а второй, как нетрудно заметить, [tex]G_{6-2}=G_4[/tex] (выполним параллельный перенос координатных осей так, чтобы точка [tex](2;2)[/tex] превратилась в начало координат. Тогда точка [tex](2;2)[/tex] превратится в точку [tex](4;4)[/tex]). Аналогично число путей, содержащих точку [tex](4;4)[/tex], равно [tex]G_4*G_{6-4}=G_4*G_2[/tex]. После вычитания их из общего числа путей получим
[tex]G_6-G_2*G_4-G_4*G_2=G_6-2*G_2*G_4[/tex] - но здесь два раза были учтены пути, содержащие и точку [tex](2;2)[/tex] , и точку [tex](4;4)[/tex], а значит к текущему количеству путей нужно прибавить их число. Аналогичными рассуждениями их количество равно [tex]G_{2-0}*G_{4-2}*G_{6-4}=G_2^3[/tex].
Окончательно, число способов проезда равно [tex]G_6-2*G_2*G_4+G_2^3=\dfrac{12!}{6!6!}-2*\dfrac{4!}{2!2!}*\dfrac{8!}{4!4!}+\left(\dfrac{4!}{2!2!}\right)^3=\\=\dfrac{12*11*10*9*8*7}{6*5*4*3*2}-\dfrac{8*7*6*5}{2}+6^3=11*3*4*7-8*7*3*5+6^3=\\=924-840+216=300[/tex]
2 votes Thanks 2
reygen
Есть простой алгоритм для решения данной задачи , вот только он работает в том случае когда таксист будет двигаться вверх или вправо , тут как раз сказано "коротких путей " значит он будет работать?
igorShap
Естественно, для ячеек 3;3 и 5;5 нужно установить значение 0
igorShap
В начале решения как раз и идет поиск того, какому условию должны удовлетворять все кратчайшие пути
reygen
Да ! Второй способ в этом и заключается в динамическом программировании . Значит оно работает , т.к кратчайшие пути образовываются движением вверх или вправо .
Answers & Comments
Verified answer
Ответ:
300 способов проезда
Объяснение:
Для начала заметим, что каждое движение по линии сетки изменяет лишь одну из координат, причем ровно на 1 единицу. Значит, оптимальный путь не может состоять менее чем из [tex]6-0=6[/tex] движений по горизонтали и [tex]6-0=6[/tex] движений по вертикали. При этом, нетрудно заметить, путь [tex](0;0)\to(1;0)\to(2;0)\to...\to(6;0)\to(6;1)\to(6;2)\to...\to(6;6)[/tex] состоит ровно из такого числа перемещений. А значит и любой кратчайший путь содержит по 6 движений по вертикали и 6 движений по горизонтали, причем каждое из них (т.к. за одно перемещение координата меняется ровно на 1 единицу) должно увеличивать соответствующую координату.
Окончательно, каждый кратчайший путь состоит из 6 движений вверх и 6 движений направо.
-------------------------------------------------------------------------------
Рассмотрим следующую задачу: найти [tex]G_n[/tex] - число кратчайших путей из [tex](0;0)[/tex] в [tex](n;n)[/tex] по линиям сетки.
Рассуждая аналогично, получим, что каждый кратчайший путь состоит из n движений вверх и n движений направо.
Тогда количество таких путей совпадает с числом бинарных векторов длины [tex]2n[/tex] (общее число движений), у которых число 0 и 1 равно [tex]n[/tex] (по [tex]n[/tex] движений каждого вида), т.е. [tex]G_n=C_{2n}^n=\dfrac{(2n)!}{n!n!}[/tex]
-------------------------------------------------------------------------------
Тогда всего путей из А в В [tex]G_6[/tex].
Посчитаем число путей, содержащих точку [tex](2;2)[/tex]. Оно равно произведению числа путей от [tex](0;0)[/tex] до [tex](2;2)[/tex] и числа путей от [tex](2;2)[/tex] до [tex](6;6)[/tex]. Первый множитель равен [tex]G_2[/tex], а второй, как нетрудно заметить, [tex]G_{6-2}=G_4[/tex] (выполним параллельный перенос координатных осей так, чтобы точка [tex](2;2)[/tex] превратилась в начало координат. Тогда точка [tex](2;2)[/tex] превратится в точку [tex](4;4)[/tex]).
Аналогично число путей, содержащих точку [tex](4;4)[/tex], равно [tex]G_4*G_{6-4}=G_4*G_2[/tex].
После вычитания их из общего числа путей получим
[tex]G_6-G_2*G_4-G_4*G_2=G_6-2*G_2*G_4[/tex] - но здесь два раза были учтены пути, содержащие и точку [tex](2;2)[/tex] , и точку [tex](4;4)[/tex], а значит к текущему количеству путей нужно прибавить их число.
Аналогичными рассуждениями их количество равно [tex]G_{2-0}*G_{4-2}*G_{6-4}=G_2^3[/tex].
Окончательно, число способов проезда равно [tex]G_6-2*G_2*G_4+G_2^3=\dfrac{12!}{6!6!}-2*\dfrac{4!}{2!2!}*\dfrac{8!}{4!4!}+\left(\dfrac{4!}{2!2!}\right)^3=\\=\dfrac{12*11*10*9*8*7}{6*5*4*3*2}-\dfrac{8*7*6*5}{2}+6^3=11*3*4*7-8*7*3*5+6^3=\\=924-840+216=300[/tex]