Ответы на вопрос:
Для начала попробуем разобрать один из способов решения подобных . рассмотрим контрольный пример. входные данные: 5 - это количество врачей, т.е. нижеследующих строчек. 2 3 5 - 1-й врач. у него 2 предшественника - врачи 3 и 5 2 3 5 - 2-й врач. у него 2 предшественника - врачи 3 и 5 1 5 - 3-й врач. у него 1 предшественник - врач 5 3 1 3 5 - 4-й врач. у него 3 предшественника - врачи 1, 3 и 5 0 - 5-й врач. у него нет предшественников. вариант результата: 5 3 1 2 4 - в таком порядке посещаются врачи. изобразим эти данные графически. в кружочках проставим номера врачей и соединим кружочки стрелками, отображающими взаимосвязи (первое вложение). полученный рисунок - ни что иное, как ориентированный граф. решение будет состоять в поиске порядка посещения всех вершин графа ("врачей") в соответствии с доступными путями ("очередностью"). очевидно, что первой нужно посетить вершину, из которой пути только выходят. если ни одной такой вершины нет - решения не имеет. в нашем случае такая вершина есть - номер 5 и она помечена зеленым. после посещения мы удаляем эту вершину и все ведущие из нее пути. получаем картину, представленную вторым вложением. повторяем наше рассуждение и находим вершину 3. снова удаляем её и выходящие из нее пути. в третьем вложении мы видим, что доступны сразу две вершины - 1 и 2. их можно посетить в любом порядке, т.е. решение не единственное. будем придерживаться порядка возрастания и и вычеркнем 1 с путём, а затем и 2. в чевертом вложении остается свободная вершина 4. посещаем её, вычеркиваем - граф исчез, решена. и порядок посещения совпал с контрольным решением. теперь, когда "ручное" решение понятно, можно строить алгоритм. мы использовали граф, а граф в программировании представляется парой множеств: множеством вершин и множеством путей, их соединяющих.эти множества классически представляются двумя матрицами - матрицей смежности (отображает вершины и наличие связей) и матрицей инцидентности (отображает направление связей и, возможно, длины путей). другие варианты - списки или деревья, но они требуют набора процедур для соответствующих манипуляций.в связи с относительной простотой был выбран собственный вариант отображения графа на квадратную матрицу размера (n+1)×n, где n- количество вершин (врачей). первая строка матрицы является служебной, остальные отображают граф. в пятом вложении принятая схема отображения. собственно, из этой схемы понятна основная идея реализации. создаем матрицу, расписываем её нулями, затем заносим единицы, создавая связи. решение состоит в последовательном переборе колонок до нахождения столбцов, содержащих все нули. найденный столбец "вычеркивается" (записывается 1 в нулевой строке), а его номер - это номер посещенной вершины. процесс повторяется, пока в служебной строке не будут все единицы, либо пока не будет n раз сделан проход по столбцам (от зацикливания при отсутствии решения).поскольку программа может показаться нетривиальной, в нее внесены операторы отладки, позволяющие по шагам проследить решение. как отладкой, ясно из комментариев. если отладка не нужна, достаточно из программы удалить все строки, отмеченные \\-// pascalabc.net 3.2, сборка 1417 от 28.03.2017// внимание! если программа не работает, обновите версию! begin var n: =readinteger; // первая строка - число врачей var a: =matrfill(n+1,n,0); // матрица посещений var t: integer; for var i: =1 to n do begin // цикл ввода по каждому врачу var k: =readinteger; // количество врачей-предшественников for var j: =1 to k do begin read(t); a[t,i-1]: =1 end; end; t: =0; var res: =''; var debug: =true; //- debug: =false блокирует отладочную выдачу if debug then begin //- writeln('исходная матрица'); //- a.println(2); writeln //- end; //- for var m: =1 to n do begin for var j: =1 to n do begin var c: =a.col(j-1); if c[0]=0 then begin if c.all(x-> x=0) then begin res+=j+' '; if debug then writeln(res); //- a[0,j-1]: =1; for var i: =0 to n-1 do a[j,i]: =0; if debug then begin //- a.println(2); writeln //- end //- end end; end; if a.row(0).all(x-> x=1) then begin t: =1; break end; end; if t=0 then writeln(-1) else writeln(res)end.пример решения с выключенной отладкой52 3 52 3 51 53 1 3 505 3 1 2 4 пример со включенной отладкой (можно исходные данные для удобства все писать в одной строке) 5 2 3 5 2 3 5 1 5 3 1 3 5 0 исходная матрица 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 5 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 5 3 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 3 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 3 1 2 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 3 1 2 4 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 3 1 2 4
Реши свою проблему, спроси otvet5GPT
-
Быстро
Мгновенный ответ на твой вопрос -
Точно
Бот обладает знаниями во всех сферах -
Бесплатно
Задай вопрос и получи ответ бесплатно
Популярно: Информатика
-
nikkun8026.02.2023 22:37
-
Dasha07Dasha18.10.2020 18:20
-
workout777423.03.2021 11:09
-
hghfYES15.10.2022 14:54
-
tatyanamasenko15.07.2020 11:11
-
Dragnil2919.01.2020 18:14
-
AnastasiaPonomarenko08.06.2023 06:27
-
Викуська253109.03.2022 08:27
-
PavelKyiv23.04.2021 18:41
-
дамчок09.05.2023 16:47
Есть вопросы?
-
Как otvet5GPT работает?
otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса. -
Сколько это стоит?
Проект находиться на стадии тестирования и все услуги бесплатны. -
Могу ли я использовать otvet5GPT в школе?
Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое! -
В чем отличия от ChatGPT?
otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.