У завданні №3 ОГЕ з інформатики представлена таблиця з буквами і цифрами. Аналізуючи цю інформацію нам пропонується з'ясувати довжину найменшого шляху.
Між населеними пунктами A, B, C, D, E побудовані дороги, протяжність яких (в кілометрах) приведена в таблиці.
Визначте довжину найкоротшого шляху між пунктами A і Е. Пересуватися можна тільки по дорогах, протяжність яких вказана в таблиці.
ДІІІЧайшая штука, але вирішити її досить просто, потрібно тільки згадати теми: Графічні інформаційні моделі і Табличні інформаційні моделі. Можна звичайно і не згадувати, а відразу перейти до вирішення , Але я вам цього не раджу!
І так, графічні інформаційні моделі необхідні нам для того щоб візуалізувати інформацію з метою її подальшого аналізу. Інформація представлена в графічній формі сприймається людиною простіше ніж текстова або представлена в табличній формі. Пов'язано це з особливостями нашого організму (сприйняття), нашої планети, еволюції та всякою іншою історично-антропологічної ебулди. Згідно з деякими дослідженнями людина 80% інформації про навколишній світ сприймає візуально (очима), а значить система зору це найкращий і якісний інструмент для аналізу будь-якої інформації, потрібно тільки придумати як інформацію уявити візуально (картинкою).
Види графічних інформаційних Медела
- Схема - це уявлення деякого об'єкту в загальних, головних рисах за допомогою умовних позначень.
- Креслення - умовне графічне зображення предмета з точним співвідношенням його розмірів, що отримується методом проектування.
- Графік - лінія, що дає наочне уявлення про характер залежності однієї величини (наприклад, шляхи) від іншої (наприклад, часу).
- Діаграма - графічне зображення, що дає наочне уявлення про співвідношення будь-яких величин або декількох значень однієї величини, про зміну їх значень.
Якщо об'єкти деякої системи зобразити вершинами, а зв'язки між ними - лініями, то ми отримаємо інформаційну модель даної системи в формі графа. Власне поняття ГРАФА є основним у вирішенні завдання 3 ОГЕ з інформатики.
Ось як виглядає граф на прикладі звичайної карти Гугл
Кілька точок пов'язаних між собою лініями. Граф це графічна інформаційна модель, яка складається з вершин, пов'язаних лініями - ребрами. Вершини графа можуть зображуватися колами, овалами, точками, прямокутниками, та чим завгодно, хоч сердечками, просто буквами або загагулінамі. Граф називається зваженим, якщо його вершини або ребра характеризуються деякою додатковою інформацією - вагами вершин або ребер (наприклад відстань між двома точками - це вага ребра графа).
Табличні інформаційні моделі так само важливі як і графічні. В табличних інформаційних моделях інформація про об'єкти представляється у вигляді прямокутної таблиці, що складається з стовпців і рядків.
Вам добре відомо табличне представлення розкладу уроків, в табличній формі представляються розкладу руху автобусів, літаків, поїздів і багато іншого.
І якщо мені необхідно прокласти маршрут по карті, я візьму лінійку, паперову карту і прокладу найкоротший маршрут (мій зір зробить 80% роботи).
Але що якщо я хочу створити програму, яка прокладає найкоротший маршрут з пунтку А в пункт Б? На жаль програми ще не вміють аналізувати картинки і зображення, проте вони добре обробляють числові дані, особливо якщо вони представлені у вигляді таблиці.
Це таже інформація, що і в синьому графі вище . Є міста з умовними іменами A, B, C, D, E вони пов'язані дорогами, протяжність яких вказана на перетині стовпців і рядків (З А в В = 50), але комп'ютера таблицю аналізувати простіше, проте людині простіше аналізувати граф.
Рішення завдання №3 ОГЕ з інформатики:
Для вирішення завдання нам необхідно перетворити табличну інформацію в граф.
крок 1 аналізуємо перший рядок: місто А пов'язаний з містом В (відстань = 2), місто А пов'язаний з містом С (відстань = 5), місто А пов'язаний з містом D (відстань = 1). Будуємо граф:
крок 2 аналізуємо другий рядок: місто B пов'язаний з містом A (відстань = 2 на графі інформація вже є), місто В пов'язаний з містом С (відстань = 1). Добудуємо граф:
крок 3 аналізуємо третю сходинку: місто З пов'язаний з містом А (відстань = 5 на графі інформація вже є), місто З пов'язаний з містом В (відстань = 1 на графі інформація вже є), місто З пов'язаний з містом D (відстань = 3 ), місто з пов'язаний з містом Е (відстань = 2). Добудуємо граф:
крок 4 аналізуємо четверту сходинку: місто D пов'язаний з містом A (відстань = 1 на графі інформація вже є), місто D пов'язаний з містом С (відстань = 3 на графі інформація вже є).
крок 5 аналізуємо п'яту сходинку: місто Е пов'язаний з містом С (відстань = 2 на графі інформація вже є)
крок 6 аналізуємо граф і знаходимо найкоротший шлях з А в Е: А-В-С-Е складаємо відстані 2 + 1 + 2 = 5.
Засноване на підручнику Босов Людмили Леонідівни та даних http://gia.edu.ru/
Будь ласка, оцініть статтю
4.91 з 5. (Всього голосів: 577)
Всі статті розділу
Але що якщо я хочу створити програму, яка прокладає найкоротший маршрут з пунтку А в пункт Б?
