Олег Деревенец - Песни о Паскале

• При решении задач на графах в его узлах размещают информацию, нужную для решения данной задачи. Иногда такую информацию размещают и в ребрах, для этого в структуру ребер вводят необходимые поля.

А) Изобразите граф, содержащий не менее 20 вершин, обозначьте вершины латинскими буквами и поищите в этом графе кратчайшие пути программой «P_58_2».

Б) Пусть узлы графа – это города, а ребра – дороги между ними. Расстояния между городами разные и они известны. Как отразить в структуре графа эти расстояния? Предложите что-нибудь.

В) Пусть расстояния между городами указаны в поле mDist записи TLink.

TLink = record { Тип список связей }

mLink : PNode; { указатель на смежный узел }

mDist : integer; { расстояние между городами }

mNext : PLink; { указатель на следующую запись в списке }

end;

Предложите формат входного файла, содержащего в числе прочего расстояния между городами.

Г) Пусть выбран следующий формат входного файла, содержащий расстояния между городами (приведена одна строка).

A C 20 E 40

Здесь первый символ, как и ранее, обозначает текущий узел. Затем перечисляются его соседи с указанием расстояний до них. Например, между узлами «A» и «C» 20 км, а между узлами «A» и «E» – 40 км. Напишите процедуру ввода графа из такого файла.

Д) Напишите программу для поиска кратчайшего пути с учетом расстояний между городами. Подсказка: измените процедуру обхода в ширину так, чтобы серый кандидат исследовал всех соседей (не только белых), проверяя в них поле расстояния mDist. Если путь к соседу через кандидата окажется короче того, что уже отмечен в соседе, то следует изменить как расстояние, так и обратную ссылку в соседе. Вдобавок если сосед не серый, он ставится в очередь.

Е) Предположим, что купцам интересны не расстояния между столицами, а размер пошлин, вносимых при пересечении границ. Эти пошлины зависят от пересекаемой границы (то есть от пары стран). Годится ли для этого случая рассмотренная выше модель с разными расстояниями между городами?

Ж) С некоторых пор купцы учредили свой ежегодный съезд – Континентальный Купеческий Конгресс, где обсуждали свои проблемы. Каждая страна отправляла на съезд по одному делегату, а расходы на пересечение границ (визы) оплачивались из общей кассы. Посчитайте эти расходы (1 пиастр за каждое пересечение), если известна страна проведения конгресса. Учтите, что купцы следовали на съезд кратчайшими маршрутами.

З) Напишите программу для определения страны, где можно провести съезд с наименьшими издержками (см. задачу Ж).

И) Решите задачи Ж и З для случая разной стоимости виз на границах.

Вы заметили, насколько разбухли наши программы? Если так пойдет и дальше, то скоро вам понадобятся инструменты, применяемые в крупных проектах.

Пока я возился с новой программкой, мой холодильник опустел, а на кухне скопилась немытая посуда. Впрочем, это пустяки в сравнении с заботами наших предков – крестьян, что жили сотни лет назад. Смотрите: вот мужик в окружении десятка голодных ртов, а там ещё князь с дружиной. И всех накорми, одень, согрей. А делать все самому: пахать и сеять, избу рубить, ткать, шить и лапти плести. Эта морока называлась натуральным хозяйством.

С годами жизнь помаленьку наладилась: явились купцы, оживили торговлю и ремесла. Многие крестьяне бросили плуг, и ушли кто в кузнецы, кто в башмачники, а тот стал ткачом, – так возникло разделение труда. Потом появились фабрики и первые станки. И вот настало наше время – время огромных фабрик и сложнейших станков.

Взять хотя бы производство автомобиля – не самого сложного изделия по нынешним временам. А сколько народу копошится вокруг! Автомобильные заводы грандиозны, хотя здесь лишь собирают машины из частей, что делают на других заводах. Части сложных изделий называют узлами или модулями. Модуль – это часть изделия, которую можно изготовить и проверить отдельно от целого. Сборка изделий из модулей дала и высокое качество товара, и бешеную производительность труда. Так новые технологии породили и роскошные машины, и свободное время, убиваемое нами в автомобильных пробках.

Говорят, что история повторяется, ведь с технологиями программирования случилось то же самое, но гораздо быстрее. Ещё полвека назад одну программу мастерил один человек, – то была эпоха первых компьютеров и «натурального хозяйства» в программировании. По мере развития компьютеров росли и аппетиты пользователей, усложнялись решаемые задачи. Сообразно задачам усложнялись программы, и производство их в одиночку стало немыслимо. Потребовались разделение труда и специализация программистов, – точь-в-точь как в промышленности. И теперь производством сложных программ заняты программистские «фабрики».