На перекрестке A автомобилист разбил стекло левой фары (см. рис.), и теперь ему надо кратчайшим путем попасть в ремонтную мастерскую B, не попав при этом в пункт M . Скольки- ми способами он может выбрать маршрут?
alt text

задан 9 Апр 0:20

15 вроде...

(9 Апр 0:32) all_exist

@all_exist, Вы просто перебором пользовались? А нельзя ли как-то с помощью комбинаторных формул описать эти случаи?

(9 Апр 0:35) Lion

@all_exist, какие могут быть сомнения))

(9 Апр 0:36) spades

@spades, считал почти в уме... )))

(9 Апр 0:40) all_exist

@Lion, ну, это как бы не совсем перебор... а что-то из динамического программирования... ))

(9 Апр 0:43) all_exist

@Lion, если в точку Х можно попасть напрямую из точек Y и Z, то количество способов добраться до точки Х будет суммой кол-ва способов до Y и Z. Ставьте в соседние узлы с А по единице и заполняйте, пока в конечную точку не попадете

(9 Апр 0:49) spades

@Lion: если бы запрета на появление в точке M не было, то получились бы числа Каталана. А для квадратной доски -- числа треугольника Паскаля. Если же в какие-то точки нельзя заходить, то получиться может уже что угодно, и там готовых формул, скорее всего, не будет. Поэтому здесь динамическое программирование с постепенным заполнением узлов числами. Куда нельзя заходить, там сразу пишем 0. Быстро получается ответ 15, а без запретов было бы 42.

(9 Апр 4:19) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,266

задан
9 Апр 0:20

показан
63 раза

обновлен
9 Апр 4:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru