Результаты решения. Введем во входной файл матрицу вида:

Введем во входной файл матрицу вида:

5 4

4 5 6 4 3 6 5 6 -1 7

4 4 4 5 5 6 5 6 -1 6

6 7 5 5 5 7 7 8 -1 9

6 -1 6 -1 7 -1 7 -1 -1 -1

Здесь в первой строке содержится число точек по оси высоты и число точек по оси скорости. Следующие 4 строки содержат объемы расхода топлива в зависимости от скорости и высоты (см. график).

Запустив программу в выходном файле получим:

r 4 u 8 r 12 r 17 r 22 u 28 u 37

Здесь r означает движение вправо по графику, а u – движение вверх. После каждой из букв стоит объем расходуемого топлива к моменту нахождения на данном шаге.

Как видно из вывода, итоговый объем израсходованного топлива равен 37, что совпадает с результатами решения, выполненного вручную. Также совпадает стратегия решения.

 

Задача о сетевом графике

Постановка задачи

Сетевой граф – граф, отражающий работы проекта и связи между ними.

Может строиться в двух вариантах:

а) вершины графа отображают состояния некоторого объекта (например, строительства), а дуги — работы, ведущиеся на этом объекте;

б) вершины графа отражают работы, а связи между ними - зависимости между работами.

Около дуг проставляется время выполнения текущей стадии работы.

Задача состоит в составлении графика выполнения проекта и определения последовательностей с наименьшим затрачиваемым временем или с наибольшим.