Форум » Поиск путей в графе » Задания 13 автор А.Калинин » Ответить
Задания 13 автор А.Калинин
ganilova: Добрый день! Можно попросить автора рассказать, как решать предложенные задачи? Видео с разбором Кабанова, я посмотрела, но предложенный там граф решается легко, а вот графы А.Калинина этим способом не решаются, раздвоение начальной вершины тоже не помогает. Сама, к сожалению, придумать что-то путнее не смогла!
Ответов - 9
Поляков: Автор сделал разбор одной из своих задач, его можно посмотреть в этом файле.
Nadegda: В этом номере у меня получается ответ 16, а не 14 https://postimg.cc/2V3h8xF3 - демонстрация решения
s11kai: Nadegda пишет: В этом номере у меня получается ответ 16, а не 14 Увы и ах, вы ошибаетесь, правильный ответ - 14, вот программное решение: [pre2] s='АБЖ БВЗ ВГ ГДЕЖЗ ДЕ ЕЖА ЖЗ ЗАВ' d ={c[0]:c[1:] for c in s.split()} def f(s,end): if len(s)>1 and s[-1]==end: return 1 return sum(f(s+c,end)for c in d[s[-1]] if c not in s or c==end) print(f('З','З')) [/pre2]
Nox:
s11kai: ganilova пишет: а вот графы А.Калинина этим способом не решаются А как их решать, если у него нет половины букв, например, в задачах 115, 116, 117... это с одной стороны, а с другой, зачем мучиться писать программу, если задачка вручную решается за пару минут! Программу разумно писать для задачек вроде 131 или 135
s11kai: Исganilova пишет: а вот графы А.Калинина этим способом не решаются У меня в графах Калинина почему то указаны не все Вершины, но если, глядя на рисунок участника Nox, и предположить, что вершины указаны так,как я дорисовал в паинте: , то решение данной задачи, опираясь на идею Алексея Кабанова, может выглядеть примерно так: [pre2] pam=set() s='АБЖ БВЗ ВГ ГДЖЗ ДКЕАЖ ЕИА ЖЗ ЗАВ ИА КЕ' d ={c[0]:c[1:] for c in s.split()} def f(s,end): if s[-1]==end: pam.add(s) return 1 return sum(f(s+c,end)for c in d[s[-1]] if c not in s) f('А','З') f('В','З') print(len(pam)) [/pre2]
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: return 1 return sum(f(s+c,end)for c in d[s[-1]] if c not in s or c==end) print(f('З','З')) [/pre2] Ответ:18
s11kai: ganilova пишет: а вот графы А.Калинина этим способом не решаются Оказывается, не так страшны "графы Калинина"! Вот нашел в ege13 еще одно программное решение на его задачу : Р-07 (А. Калинин) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе И, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза. [pre2] G = { 'А': "БК", 'Б': "В", 'В': "Г", 'Г': "ДЕ", 'Д': "Е", 'Е': "ВЖЗ", 'Ж': "БЗИМ", 'З': "БВ", 'И': "АБК", 'К': "", 'Л': "АИ", 'М': "ЛИ", } count = 0 def findPath( path, target ): global count lastTown = path[-1] if lastTown == target and len(path) > 1: count += 1 print( path ) return for town in G[lastTown]: if not town in path or town == target: findPath( path+town, target ) findPath( 'И', 'И' ) print( count ) [/pre2]
s11kai: s11kai пишет: Р-07 (А. Калинин) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Определите количество различных путей ненулевой длины, которые начинаются и заканчиваются в городе И, не содержат этот город в качестве промежуточного пункта и проходят через промежуточные города не более одного раза. А вот ее же решение, только более компактным кодом: [pre2] s='АБ БВ ВГ ГДЕ ДЕ ЕВЖЗ ЖМИБЗ ЗБВ ИАБ ЛАИ МЛИ' d ={c[0]:c[1:] for c in s.split()} def f(s,end): if len(s)>1 and s[-1]==end: return 1 return sum(f(s+c,end)for c in d[s[-1]] if c not in s or c==end) print(f('И','И')) [/pre2]
полная версия страницы