Все ссылки на статьи и ролики моего канала Old Programmer расположенные по темам тут. А здесь все мои ресурсы по рекурсивному программированию
- Мои материалы по рекурсивному программированию
Еще одна задача из моего архива из олимпиадного программирования. Условия и пояснения к задаче были написана еще тогда, лет 15 назад. Я ничего не менял.
Задача «Резидентура»
Это одна из самых интересных задач, которые были на наших (университетских) олимпиадах. Она не столь сложна (в конечном итоге), но в ней есть изюминка и своя красота.
Условие
Рассмотрим следующую гипотетическую ситуацию. В некотором государстве работают N российских нелегальных разведчика (нелегала). В задачу этих разведчиков входит сбор ценной для нашего государства информации. Разведчики могут обмениваться информацией друг с другом. Ниже схематично изображена схема четырех разведчиков A , B , C , D друг с другом.
A B C D
A 0 1 1 0
B 0 0 1 0
C 0 0 0 1
D 0 0 0 0
Цифра 1 на пересечении строки X и столбца Y означает, что разведчик X получает информацию от разведчика Y (имеет односторонний канал). Цифра 0, означает, что канал получения информации отсутствует. В нашем случае разведчик A получает информацию от разведчиков B и C, разведчик B получает информацию от разведчика C, разведчик C получает информацию от разведчика D, разведчик D не имеет каналов получения информации от других разведчиков. Разумеется, наша руководство заинтересовано, чтобы информация, добытая нелегалами, в конце концов, дошла до них. С другой стороны, чем меньше контактов будет между разведчиком и руководством, тем лучше. Таким образом, необходимо в общем случае найти минимальный набор нелегалов, контакт с которыми позволит получить всю информацию, добытую разведчиками. Например, в ситуации представленной выше достаточно контактировать только с разведчиком A, а в ситуации представленной схематично ниже с разведчиками A и D.
A B C D
A 0 1 1 0
B 0 0 0 0
C 0 0 0 0
D 0 0 0 0
Требования задачи.
Входной файл содержит строки одинаковой длины, состоящие из нулей и единиц. Агенты нашей разведки, таким образом, нумеруются цифрами от 0 до N-1 (для варианта, представленного ниже - от 0 до 4). Но первой строкой всегда идет число, равное количество нелегалов:
5
0 0 0 0 0
1 0 1 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
Необходимо найти группу с минимальным количеством нелегалов, с помощью которых можно получить всю добываемую информацию (всеми разведчиками). В выходном файле должны быть перечислены номера этих агентов. Например, для последней ситуации выходной файл будет содержать строку из двух цифр "1 3" (не забывайте, что нумерация разведчиков ведется от 0).
Имя входного файла input.txt (или стандартный поток ввода), имя выходного файла output.txt (или стандартный поток вывода).
Важные замечания
1. В общем случае, может быть несколько групп, удовлетворяющих заданному условию (количество разведчиков в них минимально), но требуется найти только одну, все равно какую группу.
2. В поставленной выше задаче имеется одна серьезная проблема. Дело в том, что в общем случае информационные потоки между агентами могут замыкаться. Например, агент A получает информацию от агента B, а агент B получает информацию от агента A. Или более сложный вариант: агент A получает информацию от агента B, агент B получает информацию от агента C, агент C получает информацию от агента D, а агент D получает информацию от агента A (круг замкнулся). В случае наличия замыкания должно быть выведено сообщение об ошибке: Error .
3. Примем, что максимальное количество разведчиков-нелегалов не превышает 10.
Решение
Данная задача в сущности может быть описана с помощью графа. Предположим, что на входе мы имеем следующие данные
4
0 0 0 1
1 0 0 0
0 0 0 0
0 0 0 0
На рисунке 1 представлен граф, описывающий данный набор входной информации. Граф ориентирован, так как информация между нелегалами передается только в одну сторону. Мы видим, что информацию от нелегала 2 можно получить только непосредственно от него. Нелегал 0 получает информацию от нелегала 1. Но нелегал 3 получая информацию от нелегала 0, получает тем самым информацию и от нелегала 1. Следовательно правильным ответом (решением) задачи будет последовательность 2 3. В данном случае решение единственное. Как уже было упомянуто, программа должна учитывать тот случай, когда связи между узлами (разведчиками) образуют замкнутую линию. Другими словами, разведчики не добывают новой информации. К тому же случаю относится ситуация, когда узел замыкается сам на себе – разведчик всю информацию выдумывает. Наша задача, таким образом, написать программу обхода всех узлов диаграммы по порядку и выяснения минимального их количества для охвата всего потока информации. Я бы сформулировал задачу и по-другому: после обхода всех узлов должна быть заполнена некоторая структура, из которой уже легко получить правильный ответ.
Программа должна найти минимальное количество нелегалов для получения полной информации
Из структуры исходных данных легко понять, что и в программе легче всего хранить информацию о разведчиках-нелегалах в виду числового массива. Единица на пересечении n -строки и m -ого столбца будет обозначать, что m -й разведчик снабжает информацией n -ого разведчика. Этот же массив можно использовать для хранения динамической картины, когда программа проходит маршруты, по которым проходит поток информации. При этом, можно изменять значение 1 на, скажем, 2, чтобы отмечать уже пройденный узел. При возврате из рекурсии нужно пошагово возвращать прежнее значение узла. Если при переходе в узел его значение окажется равным 2, это будет означать, что поток замкнулся, т.е. программа должна закончить работу и сообщить об ошибке.
Теперь осталось определить структуру, в которую мы будем заносить информацию о том, с какими разведчиками связан данный разведчик. В качестве такой структуры можно взять опять же массив. Номер строки – это конкретный разведчик, единица в положении n , означает, что данный разведчик прямо или через других получает информацию от этого разведчика. После того, как такой массив заполнен остается найти минимальное количество строк (нелегалов) которые содержат ссылки от других строк. Если в строке единиц нет (кроме диагональной – разведчик сам для себя является источником), и нет ссылки на эту строку, то тогда эта строка также включается в результирующий набор строк. Принцип анализа данной структуры прост: 1. Находим строку с минимальным количеством нулей; 2. Результатом будет номер строки и номера нулей в этой строке.
Изложенный словесно алгоритм представлен программой на языке C , в листинге res4000.c.
Комментарий текста программы
Прокомментируем теперь текст программы из листинга res4000.c. Прежде все обратимся к структурам данных. Массив res содержит исходные дынные о нелегальных разведчиках и получаемой ими информации. Он заполняется на основе входного потока. Параллельно в этом же цикле инициируется массив res 1, который будет содержать результирующую информацию анализа потоков данных. Диагональ массива мы сразу заполняем единицами.
После ввода данных в цикле вызывается рекурсивная функция rec , единственным параметром которой является номер нелегала. Один такой вызов проверяет все потоки данных, связанных данным нелегалом. Обратим внимание на следующий фрагмент
for(k=0; k<n; k++){
if(res[ii][k]==2){
printf (" Error \ n ");
exit(1);
}
}
Именно в нем проверяется не оказались ли мы в том месте, где уже были. Если это так, то выдается сообщение об ошибке и осуществляется выход из программы. Мы не анализируем, есть ли еще зацикливания, нам достаточно одного, чтобы закончить работу программы. Второй цикл в рекурсивной процедуре проходит по текущей строке в поисках единицы. В случае, если единица найдена, то снова осуществляется вызов функции rec .
Отметим также роль функции prov . В ней осуществляется поиск строки с максимальным количеством единиц. Нам при этом нужна только одна из таких строк (если их несколько). Результирующие данные будут состоять из номера этой строки и номеров всех нулевых ее элементов.
Замечание
Конечно, можно было бы поступить несколько иначе. Вместо того, чтобы присваивать диагональным элементам значение 1, можно было бы присвоить им значение ноль, и тогда строка содержала бы в себе всю информацию. Мы сделали свой выбор для того, чтобы подчеркнуть значимость этой строки, которая в сущности содержит в себе информацию о всей группе разведчиков, хотя относится только к одному конкретному нелегалу.
До следующих встреч. Программируем рекурсивно. Но: "Не рекурсией единой!". Подписываемся на мой канал Old Programmer, здесь много материалов по разным вопросам программирования.
Список разделов канала Old Programmer, канала о программировании и программистах
