Форум » Поиск путей в графе » задание № 102 » Ответить
задание № 102
Juliya70: Здравствуйте! В задании № 102 у меня не сходится ответ: всего 72 пути, и вычитаем все короткие пути (менее 7 дорог). Таких дорого насчитала 21. Ответ: 72-21=51. В ответе 62 Не подскажите, где ошибка? Спасибо!
Ответов - 4
Поляков: Коротких путей всего 10: AБЕИКМ AБЕИЛМ AВЖИКМ AВЖИЛМ AГЖИКМ AГЖИЛМ AДЖИКМ AДЖИЛМ AДЗИКМ AДЗИЛМ
s11kai: Juliya70 пишет: Таких дорого насчитала 21. Ответ: 72-21=51. В ответе 62 можно получить ответ программно, примерно так: [pre2] s='АБВГД БВЕ ВЖГ ГДЖ ДЖЗ ЕВЖИ ЖИ ЗЖИ ИКЛ КМ ЛКМ' d ={c[0]:c[1:] for c in s.split()} k=0 def f(s,end): global k if s[-1]==end: if len(s)<7: k+=1 return 1 return sum(f(s+c,end)for c in d[s[-1]]) print(f('А','М')-k) [/pre2] 238 символов вместе с пробелами!
s11kai: Juliya70 пишет: Таких дорого насчитала 21 Программно посмотреть короткие дороги можно так: [pre2] s='АБВГД БВЕ ВЖГ ГДЖ ДЖЗ ЕВЖИ ЖИ ЗЖИ ИКЛ КМ ЛКМ' d ={c[0]:c[1:] for c in s.split()} def f(s,end): if s[-1]==end: if len(s)<7: print(s) return 1 return sum(f(s+c,end)for c in d[s[-1]]) print(f('А','М')) АБЕИКМ АБЕИЛМ АВЖИКМ АВЖИЛМ АГЖИКМ АГЖИЛМ АДЖИКМ АДЖИЛМ АДЗИКМ АДЗИЛМ [/pre2] Спасибо за идею Алексею Кабанову!
s11kai: Вот тоже интересный способ решения: [pre2] G = {} G['А'] = ["Б", "В", "Г", "Д"] G['Б'] = ["В", "Е"] G['В'] = ["Г", "Ж"] G['Г'] = ["Д", "Ж"] G['Д'] = ["Ж", "З"] G['Е'] = ["В", "Ж", "И"] G['Ж'] = ["И"] G['З'] = ["Ж", "И"] G['И'] = ["К", "Л"] G['К'] = ["М"] G['Л'] = ["К", "М"] def valid(way): return len(way) >= 7 count = 0 def allWays( fro, to, prev ): global count if fro == to: if valid(prev): print( prev ) count += 1 return for c in G[fro]: if not c in prev: allWays( c, to, prev+c ) allWays( "А", "М", "A" ) print( count ) [/pre2] Недостаток, 495 символа, почти в два раза больше, чем предыдущий код! С учетом того, что начальный допустимый минимум печати секретаря-референта 120 знаков в минуту. Стало быть школьнику понадобится минут 10 только на набор текста, а думать когда? Рекомендуемое время на решение всего 3 минуты!!! Уж лучше ручками
полная версия страницы