Разработка системы задач (алгоритмы-программы) по дискретной математике — страница 11

матрицы (Aold), в которой должны фиксироваться достижимые пункты для каждого робота в предыдущий момент времени. Итак, если Aplace и Aold совпадают и нет ни одной строки, состоящей из одних единиц, то встреча роботов невозможна. Это схема решения первого задания. Решение второго задания отличается от первого тем, что требуется найти время Т2=Т1 – 1 (Т1 – время встречи роботов в одном населенном пункте), в которое все роботы находятся в

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

матрицы Alink. Причем обновление выполнять не для всех роботов одновременно: в нечетные моменты времени 1,3,… для роботов, имеющих скорость 2, а в четные – 2, 4, …для всех роботов. (Текст программы см. Приложение 7) Вожатый в лагере. У вожатого в отряде дети разных возрастов от 10 до 17. каждое утро дети выходят на линейку, где они должны построится по старшинству (сначала старшие, затем младшие), но на первой линейке дети этого не знали и

построились в произвольном порядке. Вожатый составил список возрастов построившихся. Необходимо составить алгоритм – программу, которая бы помогла вожатому как можно быстрее выстроить детей по старшинству. Решение. Входные данные представляют собой список возрастов, который считывается из файла. Пример: 13 10 15 17 14 16 12 11 Выходные данные для данного примера: 17 16 15 14 13 12 11 10 Идея решения: задача решается с использованием методов

сортировки. Так как в задаче указано, что необходимо выстроить детей как можно быстрее, то необходимо применить один из методов быстрой сортировки, например метод Хоара, эффективность данного алгоритма, по Д. Кнуту, составляет С=О(N*logN). Для некоторых исходных данных время сортировки пропорционально О(N2). (Текст программы см. Приложение 8) Егерь. У егеря в лесном хозяйстве 4 станции, уезжая в командировку, он оставил своему молодому

напарнику, подробную карту, на которой изображены все дороги из одной станции в другую. В качестве приложения он оставил таблицу, в которую занес время, которое понадобиться напарнику, чтобы добраться из одной станции в другую, таблица имеет следующий вид: 1 2 3 4 1 0 60 5 5 2 2 0 7 60 3 6 5 0 2 4 3 60 5 0 Где номер строки, это номер станции из которой напарник должен выйти, а номер столбца – это номер станции, в которую он должен попасть. Необходимо