базовый уровень, время – 3 мин)
Тема: Использование информационных моделей (таблицы, диаграммы, графики). Что нужно знать: · в принципе, особых дополнительных знаний, кроме здравого смысла и умения перебирать варианты (не пропустив ни одного!) здесь, как правило, не требуется · полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания · чаще всего используется взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки · рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет
· обратите внимание, что граф по заданной таблице (она еще называется весовой матрицей) может быть нарисован по-разному; например, той же таблице соответствует граф, показанный на рисунке справа от нее · в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так) · желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот Пример задания: Р-06.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам. Решение: 1) поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:
2) дальше действуем так же, как показано при решении следующих далее разобранных задач; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е 3) первый шаг от А (в скобках указаны длины маршрутов): АС (4), AD (8) прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E 4) второй шаг ACD (7), ADC (11), ADE (13) маршрут ADF не рассматриваем, потому что он не проходит через пункт E 5) третий шаг: ACDE (12), ADEF (18) маршрут ADEF дошел до пункта назначения; маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были; маршрут ACDF не рассматриваем, потому что он не проходит через пункт E 6) четвертый шаг: ACDEF(17) 7) этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем 8) Ответ: 17. Ещё пример задания: Р-05.Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя. Решение: 1) обратим внимание, что числа в таблице нас совсем не интересуют – достаточно знать, что между данными пунктами есть дорога 2) нам нужно найти все пути, которые проходят через 6 и более пунктов, считая начальный и конечный; то есть между A и Z должно быть не менее 4 промежуточных пункта 3) начнем с перечисления всех маршрутов из А, которые проходят через 2 пункта; по таблице видим, что из A можно ехать в B, C и Z; количество пунктов на маршруте будем записывать сверху:
4) маршрут AZ нас не интересует, хотя он и пришел в конечный пункт, он проходит меньше, чем через 6 пунктов (только через 2!); здесь и далее такие «неинтересные» маршруты из A в Z будем выделять серым фоном 5) теперь ищем все маршруты, проходящие через 3 пункта; из B можно ехать только в C, а из С – в D и Z:
6) далее из C едем в D и Z, а из D – в E, F и Z:
7) строим следующий уровень только для тех маршрутов, которые ещё не пришли в Z:
8) следущие два уровня дают «интересные» маршруты, проходящие через 6 или 7 пунктов:
9) на последней схеме зелёным фоном выделены «интересные» маршруты, их всего 6; красным фоном отмечены маршруты, в которых получился цикл – они дважды проходят через один и тот же пункт; такие маршруты запрещены и мы далее их не рассматриваем 10) Ответ: 6. 11) можно было нарисовать схему возможных маршрутов в виде дерева: Ещё пример задания: Р-04.Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам). Решение: 9) начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, C или сразу в G (в скобках показаны длины маршрутов): AB(5), AD(12), AG(25) заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25 10) строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!) ABD (5 + 8 = 13) этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12 11) из D можно ехать в B и C: ADB (12 + 8 = 20) ADC (12 + 2 = 14) 12) третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D 13) продолжаем маршрут ADC (14): ADCE (14 + 4 = 18) ADCF (14 + 5 = 19) ADCG (14 + 10 = 24) в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее 14) четвёртый шаг: продолжаем маршрут ADCE: ADCEG (18 + 5 = 23) и маршрут ADCF: ADCFG (19 + 5 = 24) 15) других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23. 16) Ответ: 23. 17) Заметим, что эти рассуждения можно зарисовать в виде дерева возможных маршрутов. После первого шага:
После второго шага: После третьего шага:
После четвёртого шага:
Ещё пример задания: Р-03.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам). Решение (вариант 1, использование схемы): 1) построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4): 2) для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее 3) например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7): 4) новые маршруты из С – в D и E (длины путей соответственно 3 и 4): 5) новый маршрут из D – в E (длина пути 3): 6) новый маршрут из E – в F (длина пути 2): 7) нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E 8) попробуем перечислить возможные маршруты из А в Е: А – В – Е длина 9 А – В – С – Е длина 7 А – В – C – D – Е длина 9 А –C – Е длина 8 А –C – B – Е длина 12 А –C – D – Е длина 10 9) из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9 10) таким образом, правильный ответ – 9. Решение (вариант 2, с начала маршрута): 1) составим граф, который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A: 2) видно, что напрямую в пункт F из A не доехать 3) строим граф возможных путей дальше: определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно); из B можно ехать только в A (обратно), в C и в E; 4) узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»; 5) строим маршруты из пункта C; кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем: 6) из пункта D, кроме как в С и E, ехать некуда; путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину 6 + 3 = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7 7) из пункта E можно ехать в F, длина полного маршрута 7 + 2 = 9 8) Ответ: 9 Решение (вариант 3, с конца маршрута): 1) можно точно так же начинать с пункта F и искать кратчайший маршрут до A; судя по таблице, из F можно ехать только в E:
2) из E ведут дороги в B, C и D 3) из B можно сразу попасть в A, длина пути будет равна 11: 4) из пункта C есть прямая дорога в A длиной 4, таким образом, существует маршрут длиной 5) кроме того, есть дорога C-B, которая дает маршрут F-E-C-B-A длиной 9 6) рассмотрение пути C-D не позволяет улучшить результат: оптимальный маршрут имеет длину 9 7) Ответ: 9
Ещё пример задания: Р-02.Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними: Аэропорт вылета Аэропорт прилета Время вылета Время прилета СОСНОВО КРАСНЫЙ 06:20 08:35 КРАСНЫЙ ОКТЯБРЬ 10:25 12:35 ОКТЯБРЬ КРАСНЫЙ 11:45 13:30 БЕРЕГ СОСНОВО 12:15 14:25 СОСНОВО ОКТЯБРЬ 12:45 16:35 КРАСНЫЙ СОСНОВО 13:15 15:40 ОКТЯБРЬ СОСНОВО 13:40 17:25 ОКТЯБРЬ БЕРЕГ 15:30 17:15 СОСНОВО БЕРЕГ 17:35 19:30 БЕРЕГ ОКТЯБРЬ 19:40 21:55 Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО. 1) 15:40 2) 16:35 3)17:15 4) 17:25 Решение: 1) сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25: ОКТЯБРЬ СОСНОВО 13:40 17:25 2) посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой 3) можно лететь, через КРАСНЫЙ, но, как следует из расписания, ОКТЯБРЬ КРАСНЫЙ 11:45 13:30 … КРАСНЫЙ СОСНОВО 13:15 15:40 путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ 4) можно лететь через БЕРЕГ, БЕРЕГ СОСНОВО 12:15 14:25 … ОКТЯБРЬ БЕРЕГ 15:30 17:15 но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится 5) поскольку даже перелеты с одной пересадкой не стыкуются по времени, проверять варианты с двумя пересадками в данной задаче бессмысленно (хотя в других задачах они теоретически могут дать правильное решение) 6) таким образом, правильный ответ – 4 (прямой рейс).
Решение (вариант 2, граф): 1) для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ 2) из аэропорта ОКТЯБРЬ есть три рейса: ОКТЯБРЬ СОСНОВО 13:40 17:25 ОКТЯБРЬ КРАСНЫЙ 11:45 13:30 ОКТЯБРЬ БЕРЕГ 15:30 17:15 3) построим граф, около каждого пункта запишем время прибытия 4) проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс «БЕРЕГ-СОСНОВО», вылетающий в 12:15 5) таким образом, правильный ответ – 4 (прямой рейс). Еще пример задания: Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час. 1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа Решение: 1) нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе): 2) разделив числитель на знаменатель, получим время движения по каждой дороге 3) ехать из А в B можно · напрямую, это займет 4 часа, или … · через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге 4) таким образом, правильный ответ – 3.
Еще пример задания: Р-01.Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
Решение (вариант 1): 1) нужно рассматривать все маршруты из А в В, как напрямую, так и через другие станции 2) рассмотрим таблицу 1: · из верхней строки таблицы следует, что из А в В напрямую везти нельзя, только через C (стоимость перевозки А-С равна 3) или через D (стоимость перевозки из А в D равна 1)
· предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4
· таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7 · кроме того, из С можно ехать не сразу в В, а сначала в Е:
а затем из Е – в В (стоимость также 2),
так что общая стоимость этого маршрута равна 3 + 2 + 2 = 7 · теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:
· таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется 3) аналогично рассмотрим вторую схему; возможные маршруты из А в В: · , стоимость 7 · , стоимость 7 · таким образом, минимальная стоимость 7, условие не выполняется 4) для третьей таблицы: · , стоимость 7 · , стоимость 6 · , стоимость 7 · таким образом, минимальная стоимость 6, условие выполняется 5) для четвертой: · , стоимость 9 · , стоимость 8 · минимальная стоимость 8, условие не выполняется 6) условие «не больше 6» выполняется только для таблицы 3 7) таким образом, правильный ответ – 3.
Решение (вариант 2, с рисованием схемы): 1) для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:
2) теперь по схемам определяем кратчайшие маршруты для каждой таблицы: 1: или , стоимость 7 2: или , стоимость 7 3: , стоимость 6 4: , стоимость 8 8) условие «не больше 6» выполняется только для таблицы 3 9) таким образом, правильный ответ – 3.
Еще пример задания[1]: Р-00.Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними: Аэропорт вылета Аэропорт прилета Время вылета Время прилета ВОСТОРГ ГОРКА 16:15 18:30 ОЗЕРНЫЙ ЗАРЯ 13:40 15:50 ОЗЕРНЫЙ ВОСТОРГ 14:10 16:20 ГОРКА ОЗЕРНЫЙ 17:05 19:20 ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20 ЗАРЯ ОЗЕРНЫЙ 16:20 18:25 ВОСТОРГ ЗАРЯ 14:00 16:15 ЗАРЯ ГОРКА 16:05 18:15 ГОРКА ЗАРЯ 14:10 16:25 ОЗЕРНЫЙ ГОРКА 18:35 19:50 Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА. 1) 16:15 2) 18:15 3)18:30 4) 19:50 Решение («обратный ход»): 1) сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30: ВОСТОРГ ГОРКА 16:15 18:30 2) посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА: ЗАРЯ ГОРКА 16:05 18:15 ОЗЕРНЫЙ ГОРКА 18:35 19:50 3) это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05 4) смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05: ОЗЕРНЫЙ ЗАРЯ 13:40 15:50 5) дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40 ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20 6) таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении 7) поэтому оптимальный маршрут 8) и правильный ответ – 2.
[1] Крылов С.С., Ушаков Д.М. ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь. — М.: Экзамен, 2010. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|