Между городами a b c d e. Ещё пример задания

Размер: px

Начинать показ со страницы:

Транскрипт

1 Задание 3. Формальные описания реальных объектов и процессов 3.1. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 7 2) 8 3) 9 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 9 2) 10 3) 11 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена

2 1) 8 2) 9 3) 10 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 9 2) 10 3) 11 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 9 2) 8 3) 7 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 4 2) 5 3) 6 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 6 2) 7 3) 8 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена

3 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 6 2) 7 3) 8 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 6 2) 7 3) 8 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 6 2) 7 3) 8 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 4 2) 5 3) 6 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена

4 1) 7 2) 8 3) 9 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена 1) 13 2) 12 3) 11 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость 1) 9 2) 11 3) 13 4) Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость

5 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость 1) 6 2) 7 3) 8 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена

6 Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость 1) 6 2) 7 3) 8 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). 1) 5 2) 6 3) 3 4) Задание Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). 1) 5 2) 6 3) 7 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

7 1) 5 2) 7 3) 3 4) Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). 1) 6 2) 8 3) 10 4) Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого длинного участка кратчайшего пути от Ивана-Царевича до Марьи Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным 1) 1 2) 2 3) 3 4) Иван-Царевич спешит выручить Марью-Царевну из плена Кощея. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Ивана-Царевича до Марьи Царевны (от точки И до точки М). Передвигаться можно только по дорогам, указанным 1) 1 2) 2 3) 3 4) У Пети Иванова родственники живут в 5 разных городах России. Расстояния между городами внесены в таблицу: Петя перерисовал её в блокнот в виде графа. Считая, что мальчик не ошибся при копировании, укажите, какой граф у Пети в тетради.

8 1) 2) 3) 4) У Кати Евтушенко родственники живут в 5 разных городах России. Расстояния между городами внесены в таблицу: Катя перерисовала её в блокнот в виде графа. Считая, что девочка не ошиблась при копировании, укажите, какой граф у Кати в тетради. 1) 2) 3) 4) Учитель Иван Петрович живёт на станции Антоновка, а работает на станции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Антоновка до станции Дружба: 1) 6 2) 2 3) 8 4) Учительница Марья Петровна живёт на станции Васильки, а работает на станции Дружба. Чтобы успеть с утра на уроки, она должна ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Васильки до станции Дружба: 1) 5 2) 6 3) 8 4) Сельская малокомплектная школа находится в поселке Ивановское. Коля Иванов живёт в деревне Вершки. Определите, какое минимальное расстояние ему надо пройти, чтобы добраться до школы:

9 1) 6 2) 9 3) 12 4) Сельская малокомплектная школа находится в поселке Вершки. Рома Орлов живёт в деревне Дальнее. Определите, какое минимальное расстояние ему надо пройти, чтобы добраться до школы: 1) 6 2) 8 3) 11 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых(в километрах) приведена 1) 4 2) 5 3) 6 4) Водитель автомобиля должен добраться из пункта А в пункт D за 5 часов. Из представленных таблиц выберите такую, согласно которой водитель сможет доехать из пункта А в пункт D за это время. В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах. 1) 1 2) 2 3) 3 4) Водитель автомобиля должен добраться из пункта А в пункт C за 6 часов. Из представленных таблиц выберите такую, согласно которой водитель сможет доехать из пункта А в пункт C за это время. В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах.

10 1) 1 2) 2 3) 3 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяжённость 1) 4 2) 6 3) 10 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и B. Передвигаться можно только по дорогам, протяжённость 1) 1 2) 5 3) 3 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и B (при условии, что передвигаться можно только по построенным дорогам). 1) 11 2) 12 3) 13 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и C (при условии, что передвигаться можно только по построенным дорогам).

11 1) 6 2) 7 3) 8 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость 1) 5 2) 6 3) 7 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость 1) 4 2) 6 3) 8 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость 1) 3 2) 5 3) 8 4) Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в км) приведена в таблице. Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость 1) 7 2) 8 3) 9 4) Машинист электропоезда должен добраться из пункта А в пункт C за 6 часов. Из представленных таблиц выберите такую, согласно которой машинист сможет доехать из пункта А в пункт C за это время. В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах.

12 3.48. Машинист электропоезда должен добраться из пункта А в пункт C за 4 часа. Из представленных таблиц выберите такую, согласно которой машинист сможет доехать из пункта А в пункт C за это время. В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.

13 3.50. В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными буквами A, B, C, D и E. Укажите схему, соответствующую таблице.

ЕГЭ по информатике Задания КИМ 3 Раздел 97: ОГЭ: Поиск оптимального пути в графе Раздел 117: ОГЭ: Определение схемы, соответствующей таблице (весовой матрице графа). Всего задач: 22 3 (638) Учительница

Задания 3. Формальные описания реальных объектов и процессов 1. A 1 B 1 2 2 7 C 2 3 D 2 4 E 7 3 4 которых указана в 2. 4) 8 3. 1) 7 2) 8 3) 9 4) 10 4. 1) 9 2) 10 3) 11 4) 12 2019-04-28 1/20 5. 6. 1) 8

Задания 3. Формальные описания реальных объектов и процессов 1. За да ние 3 3. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) A B C D E A 1 B 1 2 2 7 C

Задания 3. Формальные описания реальных объектов и процессов 1. километрах) приведена в таблице: A B C D E A 1 B 1 2 2 7 C 2 3 D 2 4 E 7 3 4 дорогам, протяжённость которых указана в таблице. 3) 7 4) 8

Задания A3. Фор маль ные описания ре аль ных объектов и процессов 1. A 3 3. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) 4) 8 2. A 3 23. Между населёнными

Вариант 1 1. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых(в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно

Задание. Информационное моделирование (базовый уровень, время мин) Задания для самостоятельного решения:) На схеме нарисованы дороги между пятью городами, и указаны протяжённости дорог. Определите,

Вариант 15 1. Для получения годовой оценки по истории ученику требовалось написать доклад на 16 страниц. Выполняя это задание на компьютере, он набирал текст в кодировке Windows. Какой объём памяти (в

Стартовый контроль 10 класс Вариант 1 (Задания 1-12 по 1 баллу) Часть 1 (обведите номер правильного ответа) 1. Главный редактор журнала отредактировал статью, и её объём уменьшился на две страницы. Каждая

Информационные модели Что нужно знать: полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в

Демонстрационный вариант Информатика, 9 класс ЗАДАНИЕ А. А1. Статья, набранная на компьютере, содержит 16 страниц, на каждой странице 32 строк, в каждой строке 25 символа. Определите информационный объём

Уравнение движения. Равномерное движение. 1. В 4 часа вечера пассажир поезда проехал мимо километрового столба, на котором было написано 1456 км, а в 7 часов утра на следующий день мимо столба с надписью

10. Обработка информации 10.1 Обрабатываемые объекты: цепочки символов, числа, списки, деревья. Задачи ГИА 1. (2009) В таблице приведена стоимость перевозок между пятью железнодорожными станциями, обозначенными

Вариант 20 1 (592) В одном из изданий книги М.А. Булгакова «Мастер и Маргарита» 256 страниц. Какой объѐм памяти (в Мбайтах) заняла бы эта книга, если бы Михаил Афанасьевич набирал еѐ на компьютере и сохранял

Задачи на движение навстречу и в противоположных направлениях. Цель: формировать умение решать задачи данного вида. 1.Организационный момент. 2.Устная работа. Вычислите: Ход урока. а) 170+180; б)330-90;

3. Анализ информационных моделей Демонстрационный вариант ЕГЭ 2018 г. задание 3 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой

Вариант 1 1. Реферат, набранный на компьютере, содержит 16 страниц, на каждой странице 50 строк, в каждой строке 64 символа. Для кодирования символов используется кодировка Unicode, при которой каждый

Демонстрационный вариант вступительного испытания в 9 класс Задание 1 Для получения годовой оценки по МХК ученику требовалось написать доклад на 8 страниц. Выполняя это задание на компьютере, он набирал

Вариант 18 1 (590) Для получения годовой оценки по истории ученику требовалось написать доклад на 16 страниц. Выполняя это задание на компьютере, он набирал текст в кодировке Windows. Какой объѐм памяти

К. Поляков, 009-06 (базовый уровень, время мин) Тема: Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку. Что нужно знать: в принципе,

Вариант ОГЭ 19 1 В одном из изданий книги Л.H. Толстого «Война и Мир» 1024 страницы. Какой объѐм памяти (в Мбайтах) заняла бы эта книга, если бы Лев Николаевич набирал еѐ на компьютере в кодировке KOI-8?

МАТЕМАТИКА, класс, УМК 1 Вариант 1, Май 2012 (УМК СОШ г.(р-на), класс ВАРИАНТ 1 минут. 1. При выполнении 1 - заданий нужно указывать только ответы. При МАТЕМАТИКА, класс, УМК 1 Вариант 1, Май 2012 2. Из

Ариант 203243 1. B 3 404. Между населёнными пунктами, С, D, Е, F построены дороги, протяжённость которых приведена в таб ли це: Определите длину кратчайшего пути между пунктами и F. Передвигаться можно

МАТЕМАТИКА, 4 класс Вариант 1, Апрель 2012 СОШ г. (р-на), класс 4 ВАРИАНТ 1 1. Шестьдесят тысяч пятнадцать это... 1) 60015 2) 6015 3) 6000015 4) 615 МАТЕМАТИКА, 4 класс Вариант 1, Апрель 2012 2. Выполните

Проверочная работа по МАТЕМАТИКЕ 5 КЛАСС Вариант 12 Инструкция по выполнению работы На выполнение работы по математике даётся 60 минут. Работа содержит 14 заданий. В заданиях, после которых есть поле со

Вариант 19. 1 (591) В одном из изданий книги Л.H. Толстого «Война и Мир» 1024 страницы. Какой объём памяти (в Мбайтах) заняла бы эта книга, если бы Лев Николаевич набирал её на компьютере в кодировке

Тестирование по математике. 6 класс. 2011г. Вариант 1 Группа А 1. Решите уравнение: 8 x = 3 А. 4 2 9 Б. 2 В. 4 2 9 Г. 3 2. Найти значение выражения 3 2 А. Б. В. Г. 3. Какое из чисел больше 1, но меньше

ОГЭ 9 класс Задание #1 Рассказ, набранный на компьютере, содержит 2 страницы, на каждой странице 24 строки, в каждой строке 64 символа. Определите информационный объём рассказа в Кбайтах в кодировке KOI8-R,

Внимание! Московская методическая комиссия по информатике организует семинары по подготовке к олимпиадам. Приглашаются школьники 7-8 классов, ставшие победителями и призерами окружного этапа Всероссийской

Урок 1 Скорость. Время. Расстояние 1 Миша прошёл на лыжах расстояние 8 м за 2 с, а Игорь 45 м за 15 с. Кто из них прошёл большее расстояние, а кто меньшее Кто шёл больше времени, а кто меньше Кто шёл быстрее,

Тема: Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку. Что нужно знать: в принципе, особых дополнительных знаний, кроме здравого

Диагностическая работа 1. Вариант 0011 (без логарифмов) 3 октября 008 г. Инструкция по выполнению работы На выполнение работы дается 90 мин. Работа содержит 11 заданий (1В 9В, 10С, 11С). В заданиях 1В

Скорость. Время. Расстояние УРОК Задача. Миша прошёл на лыжах расстояние 80 м за 0 с, а Игорь 45 м за 5 с. Кто из них шёл быстрее? (Под расстоянием мы будем понимать длину дороги, соединяющей начало и

Вариант 718051 1. За да ние 3 624. Учитель Иван Петрович живёт на станции Антоновка, а работает на станции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой короткой дороге. Проанализируй

Электронная таблица Материалы для сайта по информатике 9 класс (погружение 2) Учителя: Александрова Т.А. Тема Знать Уметь Банк заданий Что такое электронная таблица, основные параметры электронных таблиц,

Математика Задачи на движение 1. Запиши только ответы в задачах. a) Верблюд в каждый час проходит 35 км. С какой скоростью он идёт? b) Пчела в каждую секунду пролетает 6 м. Чему равна скорость пчелы? c)

Задача 1. Алфавит Совсем недавно Лёша начал изучать в школе английский язык. Как это часто бывает, в некоторых аспектах изучения этого предмета он достиг непревзойдённых высот, а в других, наоборот, столкнулся

К. Поляков, 009 0 (базовый уровень, время мин) Тема: Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку. Что нужно знать: в принципе,

Для составления цепочек используются бусины, помеченные буквами: A, B, C,. На первом месте в цепочке стоит одна из бусин A, C,. На втором любая гласная, если первая буква гласная, и любая согласная, если

Графики движения 1. На уроке физкультуры Петя и Маша бежали вместе по прямой дорожке, стартовав от школы. Затем Петя побежал быстрее, а Маша пошла. Через некоторое время ребята одновременно повернули обратно

Учёный Иванов выезжает из Москвы на конференцию в Санкт-Петербургский университет. Работа конференции начинается в 10: 00. В таблице дано расписание ночных поездов Москва Санкт-Петербург. Номер поезда

1 вариант 1. Ученик в течение недели записывал время, которое он тратит на приготовление уроков: День недели Пн Вт Ср Чт Пт Время (в минутах) 120 80 100 90 110 Сколько в среднем минут уходило у него на

0 Тема: Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку. Что нужно знать: в принципе, особых дополнительных знаний, кроме здравого

«Как к нам добраться» На автомобиле Со стороны Одессы Проедьте по трассе Одесса-Николаев около 45 км до ЦЕНТРА посёлка Коблево. Обращаем внимание на 2 существенных момента: 1. Вам необходимо доехать до

7м7 Скорость. Время. Расстояние Учебник Л.Г. Петерсон, III класс Л.В. СЕЛЬКИНА, кандидат педагогических наук, доцент Д.И. ТАРАСОВА, студентка, Пермский государственный педагогический университет Цели:

Проверочная работа по МАТЕМАТИКЕ 5 КЛАСС Вариант 13 Инструкция по выполнению работы На выполнение работы по математике даётся 60 минут. Работа содержит 14 заданий. В заданиях, после которых есть поле со

Лист 2 ДЕПАРТАМЕНТ ПРОМЫШЛЕННОСТИ И ТРАНСПОРТА ВОРОНЕЖСКОЙ ОБЛАСТИ (полное наименование перевозчика) «УТВЕРЖДАЮ» (уполномоченное должностное лицо) МП (подпись) (ФИО) 20 г. ПАСПОРТ межмуниципального автобусного

(базовый уровень, время мин) Тема: Использование информационных моделей (таблицы, диаграммы, графики). Перебор вариантов, выбор лучшего по какому-то признаку. Что нужно знать: в принципе, особых дополнительных

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

РЕШЕНИЕ

Таким образом, чертим остальные точки, отбрасывая повторяющиеся отрезки. Например, отрезок AB=2 и отрезок BA=2 это одно и тоже, поэтому BA не пишем. После того, как схема готова, необходимо выписать все возможные варианты получившимся отрезков. Отрезки обязательно должны начинаться с A и заканчиваться E, как того требует условие задачи. Удобнее всего выписать отрезки в виде таблицы(см. рисунок). Как видно из таблицы, получилось 3 отрезка: ABCE = 5, ACE=7 и ADCE = 6. В задаче требуется определить длину кратчайшего пути между пунктами A и Е. Кратчайший путь-это минимальное число из получившимся отрезков. Этому требованию соответствует цифра 5, а это 2 вариант ответа.

Ответ: 2

Чтобы получить хороший старт в сфере ИТ и использовать время учебы с максимальной эффективностью, очень важно правильно выбрать .

Самостоятельная работа

На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в таблице.
Ответ напишите в комментариях этого поста

2. Разбор демо варианта 2017

Условие задачи
На рисунке схема дорог Н-ского района изображена в виде графа; в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Решение

Чтобы найти нужные нам вершины Б и В в весовой матрице, подсчитаем степени каждой вершины, т. е. найдем количество ребер, с которыми связана эта вершина. В матрице степень вершины - это количество непустых клето. Ниже в таблице степени вершин показаны в синем столбце (крайнем справа), а на графе показаны рядом с обозначением вершины.

По изображению на графе находим, что вершина Б имеет степень 3, а вершина В – 4. Так как в графе есть только она вершина степени 4, то вершина В - это пункт 5 (П5). Определить однозначно вершину Б мы пока не можем: в таблице это может быть П1, П2 и П4. Разберемся, какой из пунктов П1, П2 и П4 соответствует какой из вершин Б, Г и Д.

Б - единственная из этих вершин, которая соседствует с вершиной степени 2 (это вершина А). В таблице пункт степени 2 - это П6. Пункт П6 связан дорогой с П1 и не связан дорогами с П2 и П4. Поэтому вершина Б - это П1.

Теперь мы определили нужные нам вершины Б (П1) и В (П5) и можем найти ответ в весовой таблице. Смотрим на пересечение строчки П1 и столбца П5 и получаем, что искомое расстояние равно 8.

Ответ : 8.

Бонус : определим остальные вершины.

Заметим, что вершины А и Е определяются однозначно. Из вершины Е выходит одно ребро и это соответствует П3 в таблице. Вершины А имеет степень 2, и ей соответствует П6 из таблицы.

Вершина Е соединена только с одной вершиной Д. В таблице вершина Е (П3) соединена только с вершиной П4. Таким образом П4 в весовой таблице и является вершиной Д на графе.

Оставшаяся вершина П2 в весовой таблице соответствует вершине Г в графе.

3. Пример задания

2.1. Условие задачи.

Задача 2012-А2-1.

2.2. Набросок решения.

2.2.1. Перебор путей с учетом особенностей задачи

Полезно для наглядности нарисовать схему дорог (говоря «математически», - граф), соответствующий таблице. На это уйдет меньше минуты, но дальнейшее решение упростится и уменьшится риск сделать ошибку:

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

В пункт F можно попасть только из пункта E. Поэтому достаточно найти кратчайший путь из A в E.
Из A можно попасть только в B и C. Из B можно попасть в C и E. Нашелся путь ABE. Его длина – 2+7 = 9.
Все остальные пути из A в E ведут через C.
Из А в C есть 2 маршрута: “прямой» AC, его длина 4 и через пункт B, его длина 1+2=3. Т.е. кратчайший путь из A в C имеет длину 3.
Из C в E есть 2 маршрута: “прямой» CE, его длина 4 и через пункт D, его длина 3+3=6. Т.е. кратчайший путь из C в E имеет длину 4.
Таким образом, кратчайший путь из A в E, проходящий через C, - это путь ABCE, его длина 3+4=7. Это меньше, чем длина маршрута ABE. Значит, кратчайший путь из A в E имеет длину 7.
А кратчайший маршрут из A в F – это маршрут ABCEF, его длина 7+2=9.

Ответ: 9.

2.2.2. Систематический перебор вершин

Выпишем все пути из A в F в алфавитном порядке и подсчитаем их длины. Можно рассматривать только пути без «хождения по кругу», то есть не рассматривать маршруты, которые через одну вершину проходят 2 раза. Итак.

Из A можно пойти только в B и C:

Разберемся с путями через B. Из B можно пойти в A (но это будет путь назад!), а также в C и E (это – разумные продолжения). Заменим в нашем списке путь A→B→ на два его возможных продолжения. Получим (новые верщины выделены жирным шрифтом):

A→B→ C →;

A→B→ E →;

Теперь в нашем списке – три неоконченных маршрута, они перечислены в алфавитном порядке. Снова попробуем продолжить первый из них.

Путь A→B→ C→ можно продолжить двумя способами (не считая путей назад): пойти в D или в E. Получим такой список неоконченных путей:

A→B→ C→ D →;

A→B→ C→ E →;

Путь A→B→ C→ D→ можно продолжить до пути в F только одним способом – пойти в E. Получим:

A→B→ C→ D→ E →;

A→B→ C→ E→;

Из E можно пойти только в F. Значит, из пути A→B→ C→ D→ E → мы получили полный путь A→B→ C→ D→E→F. Его длина 2+1+3+3+2 = 11.

A→B→ C→ D→E→ F . Длина 2+1+3+3+2 = 11.

A→B→ C→ E→;

Пути A→B→ C→ E→ и A→B→ E→ тоже можно завершить только одним способом. Теперь наш список путей будет выглядеть так:

A→B→ C→ D→E→ F. Длина 2+1+3+3+2 = 11.

A→B→ C→ E→F . Длина 2+1+4+2 = 9.

A→B→ E→ F . Длина 2+7+2 = 11.

Осталось разобраться с возможными продолжениями неоконченного пути A→C→. Это можно сделать точно так же, как мы поступали с продолжениями пути A→B→. У пути A→C→ есть три продолжения: A→ C→ B→E→ F, A→ C→ D→E→ F и A→C→ E→ F. Таким образом, полный список путей из A в F выглядит так:

1) A→B→ C→ D→E→ F. Длина 2+1+3+3+2 = 11.

2) A→B→ C→ E→ F. Длина 2+1+4+2 = 9.

3) A→B→ E→ F. Длина 2+7+2 = 11.

4) A→C→ B → E → F . Длина 4+1+7+2 = 14.

5) A→C→ D → E→ F . Длина 4+3+3+2 = 12.

6) A→C→ E→ F . Длина 4+4+2 = 10.

Кратчайший путь: A→B→ C→ E→ F, его длина – 9.

Ответ. Длина кратчайшего пути: 9. Правильный вариант ответа: 1.

Замечание. На практике перебор можно уменьшить. Например, если неоконченный путь длиннее, чем уже найденный полный путь, то этот неоконченный можно не продолжать. Другой пример. Сравнивая пути A→B→ C→ D→E→ F и A→B→ C→ E→ F (пути 1) и 2)), мы выяснили, что путь C→ E→ F короче, чем путь C→ D→E→ F. Поэтому при продолжении пути A→C→, вариант A→C→ D→ E→ F можно не рассматривать.

Подобные соображения можно систематизировать и получить более экономный алгоритм поиска кратчайшего пути – алгоритм Дейкстры (Эдгар Дейкстра, 1 мая 1930 г. - 6 августа 2002 – выдающийся голландский ученый, один из создателей современного программирования). Сильным ученикам его можно объяснить, однако для выполнения ЕГЭ в этом нет необходимости.

4. Еще примеры заданий.

3.1. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)



	8

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

3.2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

3.3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

3.4.

Решение. Есть прямой путь из A в Z, его длина 29. Поищем другие пути.

Видно, что сначала нужно попасть из A в C, потом - из C в F и, наконец, из F в Z. И на каждом из этих участков надо выбрать самый короткий маршрут.

Из А в С есть два маршрута – по дороге AC и через пункт B. Второй маршрут короче – его длина 3+2 = 5.

Из C в F есть много маршрутов. Однако дорога DE очень длинная и ехать по ней заведомо не стоит – получится маршрут более длинный, чем по дороге AZ. Осталось сравнить длины двух маршрутов – CDF и CEF. Более короткий маршрут – CEF, его длина 7+5 = 12 (длина маршрута CDF равна 4+11 = 15).

Наконец, из F в Z есть единственная дорога, ее длина 5. Таким образом, кратчайший маршрут из A в Z (не считая прямой дороги AZ) = это маршрут ABCEFZ. Его длина 5+ 12 + 5 = 22 < 29. Таким образом, длмна кратчайшего пути из A в Z равна 22.

Ответ: 22

3.5 Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

Правильные ответы : 3.1: 15; 3.2: 15; 3.3: 20; 3.4: 22; 3.5: 23

В разделе 2 приведены два решения.

Второе решение лучше тем, что оно может быть выполнено «автоматически», в отличие от первого, оно не требует от ученика никаких догадок. Если граф путей по сложности примерно такой, как в демо-версии, или даже немного сложнее, на такое решение вполне хватит двух минут. При переборе можно использовать соображения, приведенные в замечании.

В первом решении используются два дополнительных соображения. Первое соображение – выделение «узких мест», которые разбивают граф на подграфы меньшего размера; такие подграфы можно исследовать независимо или почти независимо друг от друга. В рассмотренном примере «узкие места» - это вершины D и E. Второе соображение – «длинные» ребра можно игнорировать. В примере таким ребром является ребро BE.

Таким образом, при разборе этого задания с учениками можно поступать так.

1) Научить учеников уверенно рисовать граф по заданной таблице.

2) Научить решать задачу полным перебором путей (второе решение).При этом обращать внимание на особенности задачи (как в первом решении).

3) Для сильных учеников – потренироваться в решении задачи с учетом особенностей («длинные ребра», «узловые точки» - как в первом решении).

4) *Для сильных учеников - обсудить аналогию между заданием 2 и заданием 26 (С3). Решение задания 2 с помощью составления таблиц (второе решение задачи 26 (С3)). См. лекцию М.А.Ройтберга "Графы. Подсчет путей и вариантов" в разделе

Задание № 3

Спецификация контрольных измерительных материалов единого государственного экзамена по информатике и ИКТ

Практика

Т.к.теории по данному вопросу практически нет, то перейдем сразу к практике.

Разберем примеры заданий из ЕГЭ прошлый лет.

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

1) 12
2) 13
3) 14
4) 16

Решать данное задание можно и устно, перебирая все возможные передвижения по сетке таблицы из исходного пункта к конечному, например:

В данном случае, длина пути между пунктами A и F равна 2 + 3 + 9 = 14. И так далее.

Можно еще выписывать найденные пути (АВDF = 14, и т.д.) и выбирать из них самый короткий.

Но решая таким образом, легко сделать ошибку - пропустить какой-либо путь. Поэтому я рекомендую решать такое задание полным перебором всех возможных перемещений из пункта А, составляя дерево.

Начало дерева (из пункта А можно попасть в пункты B, C, D и F):

Первый вариант пути найден - 16.

Продолжим построение.

На этом этапе построения мы видим, что до пункта D можно добраться двумя путями и что путь через пункт В короче (2 + 3 = 5), поэтому в дальнейшем мы будем развивать именно эту ветвь дерева.

Продолжим построение.

Здесь также присутствует новый путь до пункта D, но он длиннее 5, поэтому его не будем рассматривать.

Продолжим построение.

Из пункта D можно попасть в 5 пунктов, но путь в пункты A, B и С - это движение назад, поэтому остается только два пункта E и F. При этом мы нашли второй вариант пути - 2 + 3 + 9 = 14.

Продолжим построение.

Находим последний вариант - 2 + 3 + 4 + 3 = 12. Он и является самым коротким.

Ответ: 1.

Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Это задание отличается только тем, что нет вариантов ответов, а решается точно также.

Можете себя проверить (ответ - 23).

Внимание: есть задания, в которых включено дополнительное условие, например, что нельзя проезжать через какой-либо пункт и др. Такие ветки дерева также надо отсекать.

2. Очень хорошо разобраны решения заданий ЕГЭ на сайте К.Полякова ( )

3. И, в заключение, рекомендую пройти онлайн-тест по заданию №5 (В5) на сайте К.Полякова (выбрать ) или на сайте ege.yandex.ru (

Представляю решение 3 задания ОГЭ-2016 по информатике из проекта демоверсии. По сравнению с демоверсией 2015 года, 3 задание не изменилось. Это задание на умение анализировать формальные описания реальных объектов и процессов (формализация описания реальных объектов и процессов, моделирование объектов и процессов).

Скриншот 3 задания.

Задание:

3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

1) 4
2) 5
3) 6
4) 7

На основании таблицы, которая дана в задании, строим граф. Из пункта А можно попасть в пункты В, С и D, а из них — в C, D, E и т.д. Не забываем, что нам нужно именно в пункт E (некоторые варианты можно сразу отбросить, т.к. дорога до пункта Е по ним будет однозначно длинной). Затем подсчитаем длину пути по каждому маршруту и выберем наименьший из них.