Информатика — это техническая наука, систематизирующая методы создания, хранения, воспроизведения, обработки и передачи данных с помощью компьютерной техники, а также принципы работы и методы управления этими средствами.
Информационные технологии (ИТ, также называемые информационно-коммуникационными технологиями ИКТ): процессы и методы поиска, сбора, хранения, обработки, предоставления и распространения информации, а также методы осуществления таких процессов и методов Индустрия ИТ связана с созданием, развитием и эксплуатацией информационных систем (ИС) ИТ играют важную роль в жизни человека и во всех сферах современного общества Она рационально разработана и основана на использовании современных достижений компьютерной техники и других высоких технологий, современных средств связи, программного обеспечения и практического опыта для решения проблемы эффективной организации информационных процессов с целью снижения затрат времени, труда, энергии и материальных ресурсов во всех сферах жизни человека и современного общества. Информационные технологии Информационные технологии взаимодействуют с услугами, управлением, промышленным производством и социальными процессами и часто являются их частью.
Если у вас нет времени на выполнение заданий по информатике, вы всегда можете попросить меня, пришлите задания мне в
Сколько стоит помощь?
Какой срок выполнения?
Если требуется доработка, это бесплатно?
Могу ли я не платить, если меня не устроит стоимость?
Каким способом можно оплатить?
Какие у вас гарантии?
В какое время я вам могу написать и прислать задание на выполнение?
Задачи накопления (хранения), обработки и передачи информации стояли перед человечеством на всех этапах его развития. Каждому этапу соответствовал определенный уровень развития средств информационного труда, прогресс развития которых всякий раз придавал человеческому обществу новое качество. Долгое время средства хранения, обработки и передачи информации развивались отдельно по этим трем направлениям табл. 1.1. Этот период в истории развития информатики можно назвать ее предысторией.
В течение долгого времени основными инструментами для решения задач обработки и передачи информации были мозг, язык и слух человека. Первое кардинальное изменение пришло с приходом письменности (по мнению ученых, речь возникла более тысячи веков назад, изобретение письменности относится к третьему тысячелетию до н. э.). Это привело к гигантскому качественному и количественному скачку в развитии общества, появилась возможность передачи знаний от поколения к поколению. Изобретение книгопечатания (середина XV века) радикально изменило индустриальное общество, культуру, организацию деятельности.
Возможно, вас также заинтересует эта ссылка:
Эти два этапа (письменность и книгопечатание) создали принципиально новую технологию накопления и распространения (передачи) информации, избавившую человечество от необходимости всецело полагаться на такой зыбкий и ненадежный инструмент, каким является человеческая память.
Конец XIX века ознаменован изобретением электричества, благодаря которому появились телеграф, телефон, радио, позволяющие оперативно передавать и накапливать информацию в любом объеме.
Бурное развитие науки и промышленности в XX веке, неудержимый рост объемов поступающей информации привели к тому, что человек оказался не в состоянии воспринимать и перерабатывать все ему предназначенное. Возникла необходимость классифицировать поступления по темам, организовать их хранение, доступ к ним, понять закономерности движения информации в различных изданиях и т. д. Исследования, позволяющие разрешить возникшие проблемы, стали называть информатикой. В этом смысле информатика — научная дисциплина, изучающая структуру и общие свойства научной информации, а также закономерности всех процессов научной коммуникации.
Информатика, являясь базой библиотечного дела, многие годы так и занималась узкоконкретной областью изучения структуры и общих свойств научной информации, передаваемой посредством научной литературы. Постановка вопроса о завладении информатикой всем кругом вопросов, который связан с разработкой эффективных методов сбора, хранения, обработки и преобразования имеющейся информации в знания, прежде была неправомерной, так как не существовало почти ничего общего в методах сбора и обработки информации у медиков, географов, психологов, физиков, филологов и т. д. С этой точки зрения много общего между собой имели математика и физика, химия и медицина. Примеров отдельных связей было много, но общего стержня, вокруг которого объединились бы все науки, не было. Положение существенно изменилось с появлением электронно-вычислительных машин (ЭВМ).
Первые ЭВМ создавались для проведения расчетов в атомной физике, в летательной и ракетной технике. Последовавшее далее внедрение ЭВМ в области административного управления и экономики дало не только большой экономический эффект, но и привело к созданию и бурному росту новой промышленной отрасли — средств и методов электронной обработки информации. Электронно-вычислительные машины стали обрабатывать числовую, текстовую, графическую и другую информацию. Появились новые ЭВМ, новые методы и средства общения с ними. Информация стала товаром.
Вычислительная техника сразу же показала свою эффективность в тех областях человеческой деятельности, где широко использовались методы математического моделирования — точные количественные методы. Сюда относятся физика, механика, химия, геофизика и т. д.
Развитие электронно-вычислительной техники, средств и методов общения с ней, создание автоматизированных информационно-поисковых систем, методов распознавания образов привели к тому, что ЭВМ стали эффективным инструментом и для «описательных» наук, которые раньше считались недоступными для методов математического моделирования (биология, юридические науки, история и т. п.). В них шло накопление отдельных фактов, давалось качественное описание объектов и событий. Использование нового рабочего инструмента значительно повысило эффективность проведения описательного анализа изучаемых объектов в таких науках. Появилось новое направление исследований, связанное с машинным моделированием человеческих интеллектуальных функций, — разработка «искусственного интеллекта».
Миниатюризация средств вычислительной техники, снижение ее стоимости позволили создавать станки с программным управлением, гибкие автоматизированные производства, станки-роботы, в которых ЭВМ решает задачи сбора, хранения, обработки, преобразования информации и на основании ее анализа вырабатывает соответствующие решения. В более сложных задачах человек, используя электронную технику, берет ответственность за принятие решения на себя. В этом случае ЭВМ анализирует огромные объемы информации и предлагает возможные варианты. Человек, познакомившись с этими вариантами, либо выбирает лучший, с его точки зрения, либо ставит перед машиной новые условия и ждет следующего совета. Так, в режиме диалога происходит процесс принятия решения.
В ходе эксперимента информацию надо принять и записать, обработать по специальным алгоритмам, преобразовать к удобному для анализа виду. Далее, исследуя полученные результаты, необходимо сделать выводы. При этом не имеет значения, какой это эксперимент — физический, биологический, химический и т. д., передают ли датчики данные прямо в ЭВМ или показания приборов сначала записывают в тетрадь, а потом вводят их в машину. Главное в том, что нужны алгоритмы сбора данных и записи их в запоминающие устройства в таком виде, который позволяет находить эти данные повторно, считывать и анализировать.
На следующем этапе активно используются программы преобразования данных к удобному для исследования виду (построение графиков, таблиц, рабочих чертежей и т. д.) и их выдача (отображение информации) или передача другим участникам эксперимента, находящимся на значительном расстоянии. Как правило, такие программы не ориентированы на конкретную предметную область, они достаточно универсальны.
Таким образом, мы выделили задачи, которые являются общими для всех наук при обработке информации с помощью ЭВМ. Научным фундаментом для их решения и стала новая наука — информатика. В этом смысле слово «информатика» второй раз появляется в научной среде. Теперь— как перевод с французского informatique. Французский термин informatique (информатика) образован путем слияния слов information (информация) и automatique (автоматика) и означает «информационная автоматика или автоматизированная переработка информации». В англоязычных странах этому термину соответствует синоним computer science (наука о вычислительной технике).
Появление ЭВМ сыграло решающую роль в оформлении информатики как науки, но и сама ЭВМ, ее создание, функционирование и применение — тоже предмет изучения информатики. Практика показала, что использование ЭВМ резко повысило производительность труда на производстве и в науке, оказало сильное влияние на научно-технический прогресс. В то же время существует и обратное влияние — задачи науки и практики предъявляют конструкторам и разработчикам программ требования для создания новых, более высокопроизводительных ЭВМ, ориентированных на решение конкретных проблем. Раннее употребляемый в русском языке термин «информатика», связанный с узкоконкретной областью изучения структуры и общих свойств научной информации, передаваемой с помощью научной литературы, в современных условиях приобретает более широкое значение — название комплексной научно-технической дисциплины, призванной создавать новые информационные технологии и средства для решения проблем информатизации в различных областях человеческой деятельности: производстве, управлении, науке, образовании, торговле, финансовой сфере, медицине и др.
Информатика — комплексная научно-техническая дисциплина, занимающаяся изучением структуры и общих свойств информации, информационных процессов, разработкой на этой основе информационной техники и технологии, а также решением научных и инженерных проблем создания, внедрения и эффективного использования компьютерной техники и технологии во всех сферах общественной практики.
Помощь с заданием по информатике
Расположение островов в море представлено с помощью сетки размером Каждый остров обозначается символом в узле этой сетки. Задача заключается в том, чтобы восстановить карту морских островов по закодированной информации о распределении островов по горизонталям и вертикалям.
Для иллюстрации принципа кодирования рассмотрим следующую карту и соответствующие ей коды (рис. 4.1).
Числа справа от карты на этом рисунке являются кодами и представляют порядок и размер групп островов в соответствующих горизонталях сетки. Например, цифры «1 2» в первой строке означают, что первая горизонталь содержит группу из одного острова, за которой следует группа из двух островов. Слева и справа от каждой группы островов расположено море произвольной протяженности.
Аналогично, последовательность «1 1 1* в первом столбце под картой островов означает, что первая вертикаль содержит три группы островов, в каждой из которых один остров, и так далее.
Постановка задачи. Написать программу, которая выполняет следующие действия (шаги) до тех пор, пока данный входной файл, содержащий несколько независимых блоков информации, не будет прочитан полностью:
1. Считывает очередной блок информации из входного -файла (структура этого файла приведена в примере 1) и отображает его на экране.
Пример 2: Блок входной информации
Для этих данных не существует карты.
Этим данным удовлетворяют две различные карты.
Каждый блок информации начинается с размеров квадратной сетки, за которыми следует кодовая информация о горизонтальном и вертикальном распределении octdobob. Код для каждой отдельной горизонтали и вертикали является отдельной строкой файла и представляет собой последовательность чисел, разделенных пробелами. Заканчивается каждая строка нулем. При этом сначала идет информация обо всех горизонталях, а затем — обо всех вертикалях.
2. Восстанавливает карту (или все карты в случае не единственного решения, как в примере 4) и отображает ее (их) на экране.
3. Добавляет карту (карты) в конец выходного -файла. Каждое пустое место в сетке должно быть представлено двумя пробелами, а каждый остров — символом (звездочка и пробел). В случае неоднозначного решения различные карты должны быть отделены друг от друга пустой строкой. Если карту восстановить невозможно, в соответствующей строке выходного файла написать «по тар». Решения, относящиеся к различным блокам информации входного файла, должны быть отделены в выходном файле строкой с надписью «next problem».
Введем понятие символьного кода строки и столбца. Из строки (столбца) карты удалим лишние пробелы; — другими словами, сделаем так, чтобы после каждой группы островов (в том числе последней) шел в точности один пробел. Все начальные пробелы, находящиеся перед самой первой группой островов, также удаляются. Получившуюся при этом цепочку символов мы назовем символьным кодом взятой строки (столбца). Например, символьный код второй строки карты, приведенной в Условии задачи, равен
Коды по строкам и по столбцам, считанные из файла, преобразуем в символьные коды и запишем в матрицы соответственно. На рис. 4.2 показано это преобразование.
Восстановление карты осуществляется слева направо и сверху вниз. При этом используется стандартный прием решения задач такого рода — перебор с возвратом (backtracking).
Введем массивы и для хранения текущих (символьных) кодов всех строк и столбцов, т. е. кодов уже заполненных их частей. Их использование повышает наглядность обсуждения.
Рекурсивный алгоритм пытается заполнить клетки карты, начиная с клетки всеми возможными способами. Первоначально в клетку записывается символ а затем — В обоих случаях текущие коды строки и столбца модифицируются. Если новые текущие коды не противоречат кодам, считанным из файла, вызывается процедура или либо найденная карта проверяется на предмет совпадения текущих кодов с заданными Причем в последнем случае коды типа (см. ранее показанный пример) считаются « равными
Методическое отступление. «Ручная» трассировка логики алгоритма (при ) с использованием одного из возможных способов реализации (см. далее по тексту) позволяет достичь ясного понимания школьником сути метода перебора с возвратом.
Заметим, что в окончательном (оптимизированном) варианте программного кода строковые массивы и можно исключить. В них нет необходимости, поскольку их элементы являются началами соответствующих элементов массивов и поэтому достаточно хранить лишь длины этих начал.
Информационные процессы и системы
Последовательность действий, выполняемых с информацией, называют информационным процессом. Системы, реализующие информационные процессы, называют информационными системами.
Основными этапами (фазами) обращения информации в системах являются:
Так как материальным носителем информации является сигнал, то реально это будут этапы обращения и преобразования сигналов (рис. 1.3).
На этапе восприятия информации осуществляется целенаправленное извлечение и анализ информации о каком-либо объекте (процессе), в результате чего формируется образ объекта, проводятся его опознание и оценка. Главная задача на этом этапе — отделить полезную информацию от мешающей (шумов), что в ряде случаев связано со значительными трудностями. Простейшим видом восприятия является различение двух противоположных состояний: наличия («да») и отсутствия («нет»), более сложным — измерение.
На этапе подготовки информации осуществляется ее первичное преобразование. На этом этапе проводятся такие операции, как нормализация, аналого-цифровое преобразование, шифрование. Иногда этап подготовки рассматривается как вспомогательный на этапе восприятия. В результате восприятия и подготовки получается сигнал в форме, удобной для передачи, хранения или обработки.
На этапе передачи информация пересылается из одного места в другое (от отправителя получателю — адресату). Передача осуществляется по каналам различной физической природы, самыми распространенными из которых являются электрические, электромагнитные и оптические. Извлечение сигнала на выходе канала, подверженного действию шумов, носит характер вторичного восприятия.
На этапах обработки информации выявляются ее общие и существенные взаимозависимости, представляющие интерес для системы. Преобразование информации на этапе обработки (как и на других этапах) осуществляется либо средствами информационной техники, либо человеком.
В общем случае под обработкой информации понимается любое ее преобразование, проводимое по законам логики, математики, а также неформальным правилам, основанным на «здравом смысле», интуиции, обобщенном опыте, сложившихся взглядах и нормах поведения. Результатом обработки является тоже информация, но либо представленная в иных формах (например, упорядоченная по каким-то признакам), либо содержащая ответы на поставленные вопросы (например, решение некоторой задачи). Если процесс обработки формализуем, он может выполняться техническими средствами. Кардинальные сдвиги в этой области произошли благодаря созданию ЭВМ как универсального преобразователя информации, в связи с чем появились понятия данных и обработки данных.
Данными называют факты, сведения, представленные в формализованном виде (закодированные), занесенные на те или иные носители и допускающие обработку с помощью специальных технических средств (в первую очередь ЭВМ).
Обработка данных предполагает производство различных операций над ними, в первую очередь арифметических и логических, для получения новых данных, которые объективно необходимы (например, при подготовке ответственных решений).
На этапе хранения информацию записывают в запоминающее устройство для последующего использования. Для хранения информации используются в основном полупроводниковые, магнитные и оптические носители. Решение задач извлечения хранимой информации (поиска информации) связано с разработкой классификационных признаков и схем размещения хранимой информации, систематизацией, правилами доступа к ней, порядком ее пополнения и обновления, т. е. всем тем, что определяет возможность целенаправленного поиска и оперативного извлечения хранимой информации.
Этап отображения информации должен предшествовать этапам, связанным с участием человека. Цель этого этапа — предоставить человеку нужную ему информацию с помощью устройств, способных воздействовать на его органы чувств.
Информационные системы можно классифицировать по различным признакам. Так, по сфере применения информационные системы подразделяются на: административные, производственные, учебные, медицинские, военные и др. По территориальному признаку: информационные системы района, города, области и т. п. С точки зрения возможности организации конкретных информационных процессов различают информационно-справочные, информационно-поисковые системы, системы обработки и передачи данных, системы связи.
Большинство автоматизированных информационных систем являются локальными системами и функционируют на уровне предприятий и учреждений. В настоящее время происходит интенсивный процесс интеграции таких систем в корпоративные системы и далее — в региональные и глобальные системы.
Системы более высокого уровня становятся территориально рассредоточенными, иерархичными как по функциональному принципу, так и по их технической реализации. Обеспечение взаимодействия территориально рассредоточенных систем требует протяженных высокоскоростных и надежных каналов связи, а увеличение объема обрабатываемой информации — ЭВМ высокой производительности. Это приводит к необходимости коллективного использования дорогостоящих средств автоматизации (ЭВМ и линий связи) и обрабатываемой информации (баз данных). Техническое развитие как самих электронных вычислительных машин, так и средств связи, позволило решить эту проблему путем перехода к созданию распределенных информационно-вычислительных сетей коллективного пользования.
Централизация различных видов информации в одной сети дает возможность использовать ее для решения широкого спектра задач, связанных с административным управлением, планированием, научными исследованиями, конструкторскими разработками, технологией производства, снабжением, учетом и отчетностью.
Если поставляемая информация извлекается из какого-либо объекта (процесса), а выходная применяется для целенаправленного изменения состояния того же объекта (процесса), причем абонентом, использующим информацию для выбора основных управляющих воздействий (принятия решения), является человек, то такую автоматизированную информационную систему называют автоматизированной системой управления (АСУ). Передача Управление и информация служат основными понятиями кибернетики — науки об общих принципах управления в различных системах: технических, биологических, социальных и др. V
Управление — функция организованных систем различной природы (технических, биологических или социальных), направленная на реализацию их целевых установок и поддержание внутренне присущей им структуры.
Кибернетика — наука, изучающая с единых позиций связь и управление (самоуправление) в организованных системах любой физической природы.
Таким образом, кибернетическая система (система управления) может рассматриваться как совокупность двух систем — управляющего объекта и объекта управления. При этом управляющая система воздействует на объект управления, подавая на него управляющие сигналы (управляющие воздействия). Для выработки управляющих решений, обеспечивающих достижение цели управления, управляющая система получает информацию о состоянии объекта управления по линии обратной связи.
Автоматизированные системы управления нашли широкое применение во всех сферах современного общества, в первую очередь как системы управления технологическими процессами и коллективами людей. АСУ технологическими процессами служат для автоматизации различных функций на производстве. Они широко используются при организации поточных линий, изготовлении микросхем, для поддержания технологического цикла в машиностроении и т. п. Информационные системы организационного управления предназначены для автоматизации функций управленческого персонала, например информационные системы управления банками, гостиницами, торговыми фирмами и т. п.
Задача с решением 1.
Задана таблица размером в каждой клетке которой, кроме двух, содержится одно из чисел от 1 до 14 (все числа разные). Оставшиеся две клетки пустые. Пример — табл. 2.1.
Правило перемещения. Число из любой клетки может быть перемещено в любую незанятую соседнюю клетку по горизонтали или по вертикали. Клетка, в которой ранее размещалось число, становится пустой.
Цель. Необходимо с помощью указанного правила выполнять по шагам преобразование произвольной исходной таблицы в конечную табл. 2.2.
Задание. Написать программу, которая:
осуществляет ввод с клавиатуры исходной таблицы и вывод ее на экран (пустые клетки могут быть закодированы нулями);
выполняет преобразование введенной таблицы в табл. 2.2;
на каждом шаге выдает на экран слева матрицу до хода, справа — матрицу после хода и указывает номер хода (1, 2, 3 и т. д.) так, что в конце работы программы будет показано полное число сделанных ходов;
минимизирует число ходов, требуемых для решения задачи.
В дальнейшем, по аналогии с известной игрой (Пятнадцать), мы будем называть числа, стоящие в клетках, фишками. Про пустую же клетку мы будем говорить, что в ней находится пустая фишка. Для начала решим задачу с упрощенным правилом перемещения. Пусть разрешается обмен между соседними клетками независимо от того, заняты они или нет. Реализуем пункты задания при этом правиле. Если мы это сделаем, то затем останется только добавить логику учета перемещения фишек через пустые клетки.
В массиве А фиксируем местоположения всех фишек. Так, если то фишка с номером 10 находится во второй строке и в третьем столбце. Столбцы нумеруются слева направо, строки — сверху вниз.
Общая логика сводится в этом случае к одной-единственной строке:
Обозначим через координаты клетки, в которой находится фишка с номером л, а через — место, где она должна находиться (рис. 2.1).
На рис. 2.1 выделен путь перемещения фишки на свое место. Он состоит из отдельных шагов:
В целом же полное перемещение реализуется с помощью процедуры:
Таким образом, если бы в задаче не было пустых клеток, а правило перемещения сводилось к обмену значений в соседних клетках, то задание было бы выполнено.
Перейдем к дальнейшему рассмотрению задали. Итак, у нас есть две пустые клетки, а перемещение фишки на свое место возможно только через пустую клетку. Идея решения в этом случае достаточно проста. Перед каждым ходом на пути из клетки в клетку необходимо ставить пустую фишку. Координаты пустой фишки мы обозначим через . При этом мы выбираем ближайшую к клетке пустую фишку, кроме особых случаев.
На какое место ставить пустую фишку? Это клетка с координатами при перемещении по оси при перемещении по оси Процедура Move при этом незначительно изменится. Необходимо поменять местами пустую фишку и фишку с номером а также запомнить новое место пустой фишки. Кроме того, мы будем придерживаться следующих ограничений, упрощающих логику расстановки фишек: во-первых, фишку с номером которую мы устанавливаем на свое место, при перемещении пустой фишки перемещать не разрешается, а во-вторых, ранее установленные на свои места фишки больше трогать нельзя.
Один из основных вопросов, который возникает при решении этой задачи: зачем нужны две пустые фишки? Ответ на него дают особые случаи в расстановке фишек. Пусть на своем месте находятся фишки с номерами 1, 2, 3 (рис. 2.2а).
Наши действия: помещаем в клетку (1, 4) пустую фишку (рис. 2.2а), а затем обычным образом ♦гоним» фишку с номером 4 на свое место, устанавливая каждый раз перед ней другую пустую фишку (рис. 2.2а). Коллизий при этом не возникает, так как есть две пустые фишки и одна из них стоит на том месте, куда мы должны поставить фишку с номером 4. Аналогичная ситуация — с фишкой 8, когда фишки 1, 2, 3, 4, 5, 6, 7 уже стоят на своих местах (рис. 2.26). Чтобы реализовать эту идею для фишек с номерами 13 и 14, фишку 13 необходимо устанавливать на свое место после фишки 9 (рис. 2.2в), а фишку 14 — после фишки 10. Поэтому данные фишки мы будем устанавливать в следующем порядке: 1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 10, 14, 11, 12.
В общем случае при каждом передвижении устанавливаемой фишки нам необходимо выбирать одну из двух пустых фишек. Будем выбирать ту из них, для перемещения которой на нужное место требуется наименьшее число ходов. Его, для перемещения пустой фишки из клетки в клетку можно оценить снизу выражением В особых случаях требуемое количество ходов не равно этой оценке, а больше нее на 2 или 4: ведь сами эти случаи возникают из-за того, что при перемещении пустой фишки мы не имеем права трогать устанавливаемую и ранее установленные фишки.
Задача с решением 2.
В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар — моментов начала и конца дежурства i-ro сторожа из интервала
Для заданного расписания стражи требуется:
а) проверить, в любой ли момент в галерее находится не менее двух сторожей;
если условие пункта а) не выполняется, то:
б) перечислить все интервалы времени с недостаточной охраной (менее двух сторожей);
в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства так, чтобы получить правильное расписание, удовлетворяющее условию пункта а);
г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать время дежурства каждого сторожа с сохранением длительности его дежурства;
д) при положительном ответе на пункт г) составить расписание с наименьшим числом сдвигов.
Входные данные (все моменты времени задаются в целых минутах):
EndTime — момент окончания стражи (момент начала — 0);
— число сторожей;
— моменты начала и окончания дежурства сторожа;
• Length — длительность дежурства каждого дополнительного сторожа.
Примечание. Программа должна допускать независимое тестирование пунктов в), г), д).
Рассмотрим первые два пункта задания. Подсчитаем для каждого от 0 до EndTime 1 в элементе массива количество сторожей, которые находятся в галерее в промежуток времени Если для какого-то значения их больше двух, то записывать в мы будем только двойку.
После заполнения массива time имеем:
Данные в массиве time являются исходными для получения ответа на первое задание (пункт а) и для формирования интервалов времени с недостаточной охраной. Эти интервалы фиксируются в массиве В каждой строке массива при этом записывается начальное время, конечное время и количество дежурящих сторожей (0 или 1).
Пример. Пусть EndTime = 5, количество сторожей а интервалы дежурств: (0, 1), (0, 1), (3, 4), (3, 4), (3, 5) и (0, 2). Тогда массив time = (2,1, 0, 2, 1), а массив NoGuard будет выглядеть, как показано в табл. 2.3, итерация 1.
Для завершения выполнения второго пункта задания (пункт б) нам остается вывести значения элементов массива NoGuard. Рассмотрим третий пункт задания (пункт в). Пусть мы ввели длительность дежурства, равную 2.
В анализируемом приоре при первой итерации массив NoGuard имеет вид, приведенный в табл. 2.3. Добавим одного сторожа с интервалом дежурства (1, 3) и после этого вновь сформируем массив NoGuard (табл. 2.3, итерация 2). Примем на работу еще одного сторожа с интервалом дежурства (2, 4) и опять проверим достаточность охраны (табл. 2.3, итерация 3). Так как у нас по прежнему есть интервал с недостаточной охраной, то добавим очередного сторожа с интервалом дежурства (3, 5).
После этого в любой момент времени в галерее будет находиться не менее двух сторожей.
Рассмотрим четвертый пункт задания (пункт г). Идея решения заключается в разбиении множества дежурств сторожей на два подмножества так, чтобы сумма времени дежурств сторожей в каждом из подмножеств была больше или равна EndTime. Очевидно, что достаточно найти одно такое подмножество, так как второе получается его дополнением до всего множества дежурств сторожей. Нахождение подобного разбиения возможно только в случае, если сумма времени дежурств всех сторожей (Sum) больше или равна
При этом сумма времени дежурств сторожей из первого подмножества (cnt) должна удовлетворять условию: иначе сторожа из второго подмножества не смогут обеспечить необходимой охраны галереи. При нахождении же такого разбиения график дежурства сторожей из каждого подмножества составляется по принципу: когда первый заканчивает дежурство, второй начинает дежурить.
Логика поиска разбиения на подмножества приведена ниже:
Вызывать процедуру Разбиение необходимо следующим образом:
Пятый пункт задания (пункт д) предполагает решение задачи для небольших значений При этом мы сначала рассматриваем всевозможные сдвиги времени дежурства одного сторожа (вначале первого, затем второго и так далее) и пытаемся «залатать дыры» в расписании. Бели это не удается, то переходим к двухэлементным» сдвигам, т. е. к сдвигам времени дежурств каких-либо двух из наших сторожей, затем — к «трехэлементным» и т. д. до «-элементных» сдвигов, пока не будет найдено правильное расписание:
Итак, одна из подзадач здесь — это генерация -элементных подмножеств -элементного множества. Она хорошо известна и не требует разъяснений. Вторая подзадача — перебор всех возможных способов «затыкания дыр» в расписании с помощью сторожей из выбранного подмножества. Ее решение — модификация пункта (в) основной задачи.
