Составьте программу, вычисляющую критический путь в сетевом графике. Языком реализации программы выбран язык Java, точкой входа в программу должен являться метод main класса Cpm. Формат входных данных Программа должна считывать описание сетевого графика из стандартного потока ввода. Описание состоит из предложений, разделённых точкой с запятой. Каждое предложение записывается как последовательность зависимых работ: работа < работа < ... < работа Знак « BoilAll [color = red] BuyFood -> CutCabbage BuyFood -> CutMeat [color = red] BuyFood -> CutOnion BuyFood -> PeelPotatoes CutCabbage -> BoilAll CutMeat -> BoilMeat [color = red] CutOnion -> FryOnion CutPotatoes -> BoilAll FryOnion -> ServeUp PeelPotatoes -> CutPotatoes } Формат выходных данных Программа должна выводить в стандартный поток вывода описание сетевого графика в виде орграфа в формате DOT. Вершины критического пути и соединяющие их дуги должны быть отмечены красным цветом. Если сетевой график содержит несколько критических путей, все они должны быть отмечены. Учитывая, что формат входных данных не гарантирует того, что сетевой график получится ациклическим, программа должна уметь обрабатывать циклические зависимости работ. Такие работы по понятным причинам не могут быть никогда выполнены и, следовательно, не могут входить в критический путь. Вершины сетевого графика, соответствующие работам, которые никогда не могут быть выполнены из-за циклических зависимостей, а также дуги, исходящие из этих вершин, должны быть отмечены синим цветом (см. пример на рис. 2).

N кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объёма, то важное значение приобретает психологическая совместимость членов экипажа. Путём тестирования были установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице размера N?N. Если на пересечении ii-той строки и jj-го столбца таблицы находится знак «+», то участие ii-го и jj-го кандидатов в одной экспедиции нежелательно. Составьте программу, разделяющую кандидатов на две группы для участия в экспедициях. Если такое разделение невозможно, программа должна выводить сообщение «No solution». В противном случае, программа должна выводить номера кандидатов, принадлежащих первой группе. Первой группой мы будем считать группу, в которой меньше кандидатов. Естественно, хорошо написанная программа должна стремиться к тому, чтобы размеры групп не очень сильно отличались. Поэтому, если возможно несколько разбиений на группы, программа должна выбирать разбиение с минимальной разностью количеств кандидатов в группах. При этом в случае, если разбиений с минимальной разницей всё равно получается несколько, для определённости выбирается разбиение, в котором первая группа лексикографически меньше, чем первые группы остальных разбиений. Java -- язык реализации, точкой входа в программу должен являться метод main класса Mars. Программа должна считывать со стандартного потока ввода количество кандидатов и матрицу размера N?N Входные данные 1: 2 - - - - 2: 3 - - - - - + - + - 3: 4 - - + - - - - - + - - - - - - - 4: 5 - - - - - - - - - - - - - - + - - - - - - - + - - 5: 6 - - - - - - - - - - - - - - - + + - - - + - + - - - + + - - - - - - - - 6: 7 - - - - + - - - - - - - - - - - - - - + - - - - - - - - + - - - - + - - - + - + - - - - - - - - - 7: 8 - - - - - - - - - - - - - - - - - - - - - + - - - - - - - - - - - - - - - - - + - - + - - - - - - - - - - - - - - - - - + - - - Выходные данные: 1: 1 2: 2 3: 1 2 4: 1 3 5: No solution 6: 1 2 6 7: 1 2 3 5

Пусть имеется некоторый набор формул, задающих зависимости между переменными. Например, объём V пирамиды, в основании которой лежит прямоугольник со сторонами a=10 и b=15, а высота равна полусумме сторон основания, определяется следующим набором формул: V = S*h / 3 S = a * b a, b = 10, 15 h = (a + b) / 2 Обратите внимание на то, что каждая формула состоит из левой и правой частей, разделённых знаком «=». Левая часть является списком переменных, а правая часть – списком соответствующих этим переменным выражений. Переменные в левой части и выражения в правой части разделяются запятыми. Формулы могут быть записаны в любом порядке, но, если в них нет циклических зависимостей, их можно расположить в порядке, в котором нужно выполнять вычисления. Например, существуют два варианта порядка формул для вычисления объёма пирамиды: Вариант 1 a, b = 10, 15 h = (a + b) / 2 S = a * b V = S*h / 3 Вариант 2 a, b = 10, 15 S = a * b h = (a + b) / 2 V = S*h / 3 Составьте программу, осуществляющую топологическую сортировку формул. Языком реализации программы выбран язык Java, точкой входа в программу должен являться метод main класса FormulaOrder. Для решения задачи нужно построить орграф, вершинами которого являются формулы, а дуги задают зависимости между ними. То есть, если формула v зависит от формулы u, то в графе существует дуга ?v,u?. Затем следует выполнить топологическую сортировку вершин этого орграфа, то есть расположить вершины в таком порядке, чтобы дуги вели от больших вершин к меньшим. Этот порядок, как не трудно догадаться, совпадает с порядком превращения «серых» вершин в «чёрные» в процессе обхода графа в глубину. Формулы подаются в программу через стандартный потока ввода. Они отделяются друг от друга символом перевода строки. Выражения в составе формул содержат знаки четырёх арифметических операций, круглые скобки, десятичные числа и имена переменных. Имя переменной – это последовательность латинских букв и десятичных цифр, начинающаяся с буквы. Программа должна выводить сообщение «syntax error», если какая-нибудь формула содержит синтаксическую ошибку, или если некоторая переменная присутствует в левой части нескольких формул, или если не существует формулы для вычисления какой-нибудь переменной. Программа должна выводить сообщение «cycle» в случае обнаружения циклической зависимости формул. Для обнаружения циклической зависимости следует проверять наличие обратных дуг при обходе графа в глубину. Напомним, что обратная дуга ведёт в «серую» вершину. Если ошибки в формулах не обнаружены, то программа должна выводить в стандартный поток вывода отсортированный набор формул. В случае существования нескольких вариантов взаимного расположения формул, требуется вывести любой из них. Ввод: V = S*h / 3 S = a * b a, b = 10, 15 h = (a + b) / 2 Вывод: a, b = 10, 15 h = (a + b) / 2 S = a * b V = S*h / 3