МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Тема 4. Задача «Маневри»На території деякої держави з сильно перетнутою гірською місцевістю йдуть військові маневри між двома протиборчими сторонами: «Синіми» і «Зеленими». Особливості ландшафту і складні кліматичні умови вимушують підрозділи обох сторін розміщуватися тільки на території деяких населених пунктів. Загальна кількість населених пунктів в цій державі рівна N. Тактика ведення бойових дій «Синіх» розрахована на нанесення супротивнику швидких і раптових ударів, що можливе лише в тому випадку, якщо в операціях використовуються моторизовані частини, а їх пересування відбувається тільки по дорогах. Різноманітність використовуваної бойової техніки призводить до того, що час переміщення різних бойових частин з одного пункту в іншій опиняється різним і визначається величиною Vj — швидкістю руху підрозділів бойової частини, розквартированої в j-м населеному пункті. Використовуючи значну перевагу в техніці, «Сині» планують організувати нічний наліт на бази супротивника (під кодовою назвою «Зелені») і повністю їх розгромити. Всі бойові підрозділи «Синіх» приступають до виконання операції одночасно. Якщо бойова частина «Синіх» уривається в населений пункт, зайнятий «Зеленими», то, враховуючи чинник раптовості, їм вдається повністю розгромити це угрупування. На жаль, блискучому проведенню цієї операції перешкодила та обставина, що через час T після початку операції «Зеленими» було здійснене радіоперехоплення повідомлення про операцію, що почалася. Після радіоперехоплення угрупування «Зелених» миттєво розсіваються в навколишніх горах і залишаються неушкодженими. З'ясуйте, яка кількість угрупувань супротивника і в яких населених пунктах «Синім» все-таки вдасться розгромити «Зелених». Передбачається, що в початковий момент часу угрупування «Зелених» і «Синіх» не можуть знаходитися в одному і тому ж населеному пункті. Якщо сигнал тривоги поступає в той момент, коли бойова частина «Синіх» тільки уривається в населений пункт, зайнятий «Зеленими», то, використовуючи чудове знання місцевості, «Зеленим» все-таки вдається сховатися в горах. Переважна перевага в техніці і живій силі дозволяє бойовим частинам «Синіх» організувати з кожної частини будь-яку кількість експедицій для розгрому «Зелених». Ніщо не заважає одну експедицію за час проведення операції знищити декілька угрупувань. Початкові дані задачі містяться у файлах MAP.IN і TROOPS.IN. Структура файлу MAP.IN описує карту місцевості. У першому рядку цього файлу містяться два цілі числа: N — кількість населених пунктів (0 < N < 256) і К — кількість доріг, що сполучають ці населені пункти (0 ≤К ≤ 1000). Дороги ніде не перетинаються. У подальших К рядках файлу міститься схема доріг. У кожному рядку записана пара двох натуральних чисел i та j і одне додатне дійсне число Lij, що означає, що між населеними пунктами i та j існує дорога завдовжки Lij кілометрів (Lij < 1000). Вміст файлу TROOPS.IN відображає розміщення бойових частин воюючих сторін. Перший рядок файлу містить число MF — кількість бойових частин «Синіх». Кожний з подальших MF рядків містять по два числа. Перше — ціле число j — номер населеного пункту, в якому розміщується частина; друге — дійсне невід‘ємне число Vj — швидкість руху бойових колон цієї частини в кілометрах в годину (Vj < 110). Далі в окремому рядку файлу записане число MB — кількість бойових угрупувань «Зелених», за яким перераховані MB чисел — номерів населених пунктів, де ці угрупування знаходяться. І нарешті, в останньому рядку файлу зберігається додатне дійсне число Т, зміряне в годинах (Т < 24). Всі числа в рядках файлів розділені пропусками. Результат рішення задачі необхідно вивести в текстовий файл VICTORY.OUT. У перший рядок файлу виводиться кількість розгромлених угрупувань, а в другу — номери населених пунктів (у порядку зростання), в яких ці угрупування базувалися. Розглянемо такий приклад: MAP.IN 8 7 1 2 80 2 4 25 4 5 10 6 2 5 2 3 40 7 6 10 8 7 15 TROOPS.IN 1 50 6 20 4 4 5 3 8 2.0 VICTORY.OUT 4 8 Стисло алгоритм рішення задачі може бути описаний так: методом Флойда обчислюємо найкоротші відстані від кожної вершини до кожної. Скласти програму, яка вирішує поставлену задачу. Навести теоретичні виклади про роботу алгоритму Флойда та застосувати основні положення теорії графів. В завданні на курсову роботу скоротити умову до прийнятного вигляду. Програма повинна мати меню, мінімальний склад якого такий: - Авторська заставка - Робота програми - Відомості про програму (інструкція) - Вихід Всі надписи на екрані повинні бути державною мовою, а не англійською. Необхідні файли підключаються через розробку власних бібліотек.
Читайте також:
|
||||||||
|