На рисунке показана схема лабиринта, в клетку A которого поместили мышь, а в клетку B положили кусочек сыра. Мышь всегда двигается между клетками лабиринта так, что с каждым шагом приближается к сыру. Шагом будем считать перемещение из одной клетки в другую. Маршрутом будем называть совокупность клеток, в которых побывала мышь прежде, чем добраться до сыра. Сколько возможных маршрутов есть у мыши в этом лабиринте?
update
Ответ
126.
Число путей, ведущих к любой клетке, равно сумме числа путей двух клеток, из которых мышь приходит в выбранную клетку. Таким способом можно подсчитать возможные варианты.
Число путей, ведущих к любой клетке, равно сумме числа путей двух клеток, из которых мышь приходит в выбранную клетку. Таким способом можно подсчитать возможные варианты.
116.
ОтветитьУдалитьЧисло возможных путей к клетке равно сумме чисел возможных путей к клетке сверху от нее и к к клетке слева от нее, а число путей к клеткам верхнего и левого рядом равняется единице.
http://s017.radikal.ru/i444/1304/fa/4e4f28f22952.png
Ошибочка в расчётах закралась.
Удалить21+35=56
Удалить126.
ОтветитьУдалитьРешил полным перебором.
Решил заполняя клеточки таблицы начиная с клеточек имеющих общую сторону с пунктом B. Число в клетке - количество маршрутов соединящих данную клетку и пункт B.
Аналитическую формулу лень выводить.
Этот комментарий был удален автором.
Удалить"Решил полным перебором." - лишнее. Тут нет тега зачёркивание (((
УдалитьДлина = 9, 4 вниз, 5 вправо. Число сочетаний
ОтветитьУдалитьС^4_9 = C^5_9 = 9!/4!*5! = 126
Такое же решение.
Удалитьхехе)) изложу свои домыслы)) я так понял по диагонали двигаться нельзя. Возвращаться назад на клетку по горизонтали или вертикали в процессе тоже нельзя. Рискну предположить, что любой путь это 9 шагов. Обозначив клетки как координаты начнем перебирать шаги
ОтветитьУдалить11 - след. шаг на 12 или 21
из 21 шаги на 31 или 22
из 12 шаги на 22 или 13 и т.д.
на каждой итерации количество шагов удваивается
и на 9 итерации получается
2^9 = 512 шагов
может и не верно, но у меня больше всех пока)))
Удалитькак сообщения удалять?
УдалитьЕсли входить не через аккаунт google, то может быть кнопка для удаления сообщения не появляется, не знаю.
Удалитьподтверждаю 126)
ОтветитьУдалитьСпособ решения на картинке dbsergey показан правильно, просто ошибка в числах. Должно получиться 126.
ОтветитьУдалить