Форум » Поиск путей в графе » Задача №138 из темы 13. Опечатка ли? » Ответить
Задача №138 из темы 13. Опечатка ли?
GP_LOU: Доброй ночи. Подскажите пожалуйста, верно ли что ответ к этой задаче 9? 138) (Е. Джобс) На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, которые начинаются и оканчиваются в городе Е и проходят через промежуточные города не более одного раза?
Ответов - 3
s11kai: GP_LOU пишет: верно ли что ответ к этой задаче 9 Лично у меня получилось их только 3, но, зная Джобса, могу предположить, что он нашел какую-то заморочку, которая простому смертному не сразу поддается!
s11kai: Попробовал решить ее программно: [pre2] s = 'АБ БД ВА ГБВЕ ДЖ ЕКВ ЖГ ЗДЖ КЗ' d ={c[0]:c[1:] for c in s.split()} def f(s,end): if len(s)>1 and s[-1]==end: print(s) return 1 return sum(f(s+c,end)for c in d[s[-1]]if c not in s or c==end ) print(f('Е','Е')) ЕКЗДЖГЕ ЕКЗЖГЕ ЕВАБДЖГЕ 3 [/pre2] Не знаю, может что и упустил, во всяком случае, все его задачи по данной теме этим способом решались сразу!
s11kai: А вот если бы условие было таким: На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов, которые оканчиваются в городе Е и проходят через промежуточные города не более одного раза? т.е. без - "начинаются и", то в этом случае ответ будет уже - 13 АБДЖГЕ БДЖГЕ ВАБДЖГЕ ГЕ ДЖГЕ ЕКЗДЖГЕ ЕКЗЖГЕ ЕВАБДЖГЕ ЖГЕ ЗДЖГЕ ЗЖГЕ КЗДЖГЕ КЗЖГЕ
полная версия страницы