Форум » Поиск путей в графе » задание 5699 из базы заданий 1 вариант генератора » Ответить
задание 5699 из базы заданий 1 вариант генератора
Aniri: В этом задании не сходится ответ. Получается 55, а в ответе 69. Прошу помочь. Мое решение на рисунке. https://postimg.cc/ZBxxz7QD
Ответов - 8
bibiel: 15+38+16=69 Всё верно. https://postimg.cc/xkqwBDcJ
s11kai: bibiel пишет: 15+38+16=69 Всё верно. bibiel, Вы правы, ответ действительно будет 69, но только вот промежуточные значения указаны неверно, они будут такими 15 + 14 + 40 = 69
Aniri: Спасибо за решение. Прошу, пожалуйста, немного словесно пояснить - по какому принципу нужно убирать дуги в каждом графе
rinandreevna: Добрый день! Пришли к ответу, опираясь на следующий алгоритм удаления ребер в графе: 1. Рассмотрели все пути, которые начинаются с префикса ЖЗ, но при этом не используют в начале пути Д 2. Рассмотрели все пути, которые начинаются с префикса ЖЗД 3. Рассмотрели все пути, которые начинаются с префикса ЖН https://postimg.cc/m1ZmKNRR
ТеплыхИБ: [pre2] d={'А':'Б','Б':'В','В':'ЖЕГ','Г':'ЕД','Д':'ЕЖК','Е':'Ж','Ж':'ЗН','З':'ЛКД','К':'Л','Л':'М','М':'АНЗ','Н':'АБВ'} def f(tek_gorod, put): global otv if tek_gorod=='Ж' and len(put)>1: otv+=1 print(otv,put) else: if put.count(tek_gorod)<=1: for x in d[tek_gorod]: f(x,put+x) otv=0 f('Ж','Ж') [/pre2]
s11kai: Aniri пишет: В этом задании не сходится ответ. Получается 55, а в ответе 69 Если исходить из рисунка, представленного Aniri, то в нем нет связей ДК и ЗД, которые присутствуют в решении ТеплыхИБ, что не соответствует решению задачи, предложенной Aniri, а решение соответствующее рисунку может быть таким: [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] запустив на исполнение, убеждаемся, что ответ для представленного рисунка будет действительно равен 55, как это и сказала Aniri
s11kai: ТеплыхИБ пишет: d={'А':'Б','Б':'В','В':'ЖЕГ','Г':'ЕД','Д':'ЕЖК','Е':'Ж','Ж':'ЗН','З':'ЛКД','К':'Л','Л':'М','М':'АНЗ','Н':'АБВ'} если судить по этой строке, то разговор идет о задаче: то решение может быть таким: [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('Ж','Ж')) и в отом случае ответ будет правильным - 69 [/pre2]
s11kai: Решение данного задания ручным способом можно посмотреть здесь:показать подробно
полная версия страницы