Образование


Ответить в тред Ответить в тред

Check this out!
<<
Назад | Вниз | Каталог | Обновить тред | Автообновление
2 2 2

Сап двач, помоги с решением задачи из типовика. Аноним 03/11/19 Вск 16:10:33 7069601
image.png (9Кб, 272x149)
272x149
Сап двач, помоги с решением задачи из типовика.
Определите число деревьев в глубинном остовном лесу (перебор вершин производить строго в лексикографическом порядке).

Понимаю что нужно делать при помощи поиска в глубину, но никак не могу понять что делать если после первого прохода алгоритма я захожу в тупик. Скину полтос за решение.
Grand 03/11/19 Вск 17:59:30 7069732
Безымянный.png (57Кб, 1520x2064)
1520x2064
Если судить логически, то откатываться на объект предыдущего листа, который ты должен был записать при инициализации очередного листа ветви, и еще n число раз, если опять вышел тупик. Как уже быть дальше - зависит сугубо от твоей реализации, при этом с подсчетом тупиков/успешных вариков в глобальной переменной)
Будучи на срочке, будучи успешно выпиленным со 2 курса ВУЗа, в РМП сослуживцы подкинули задачку на перебор графа (пикча), в кратце, нарисовать фигуру не отрывая руки, что если бы я знал правила по которым это можно было сделать не заняло бы время, потраченное на написание проги на местном компе,. Я для придумал такую штуку, как карта линии(стороны) - фактически 11 битовое поле, в котором 1 - сторона может соединиться с другой стороной, 0 -нет, на примере стороны "1", смотрящей налево: 11000110010 (11 бит отвечает за направление стороны влево/вправо или же низ/верх, от чего карта меняется), соответственно стороны 2,4,6,10 - будут потенциальными продолжениями этой стороны. В свойствах листа я хранил: карту, id стороны, глобальную карту (эта карта отвечает за стороны, по которым граф еще не проходился), и локальную копию глобальной карты (которая, в случаях отката, заменяла собой глобалку). При переходе на следующий лист, в старом листе занулялся бит == id стороны, куда перешло древо, а так же бралась карта к объекту и через логическое "И" с глобальной картой, давало нам потенциальные дальнейшие пути хода. Концом считалось, если глобальная карта = 0(успешное решение) или карта связи самого листа = 0 и глобалка!=0(тупик). В случае отката, проверялось условие конца, с восстановлением глобальной карты из копии. Одной из сложностей была возможность того, что у стороны есть два направления(влево/вправо, вверх/низ), что накладывало свой отпечаток на алгоритм.
Аноним 03/11/19 Вск 20:46:46 7070003
>>706973
задачи не погромисткая, а по дискретной математике.
Настройки X
Ответить в тред X
15000 [S]
Макс объем: 40Mб, макс кол-во файлов: 4
Кликни/брось файл/ctrl-v
Стикеры X
Избранное / Топ тредов