Категория B9 • задача №1

 
 
 

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

Дано:
на соревнованиях по спортивному ориентированию участник должен пробежать от старта до финиша, преодолевая наименьшее число препятствий (их число на каждом отрезке пути указано на рисунке).

 

Найти:
какое наименьшее число препятствий может преодолеть спортсмен?

 

Решение

I этап: разбор представленной схемы.

Очевидно, что участник начинает свое движение из пункта "Старт" и заканчивает маршрут в пункте "Финиш". Также как видно из схемы, существует несколько вариантов траекторий, позволяющих участнику достичь пункта "Финиш", причем, только единственный вариант является оптимальным.

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

 

II этап: устранение избыточных траекторий.

Рассмотрим изображение:




Очевидно, что путь синего цвета содержит 7-мь препятствий, а путь красного цвета содержит 8-мь препятствий, следовательно, путь красного цвета можно безболезненно устранить, так как данный маршрут не будет оптимальным.

 

 

 



Очевидно, что путь синего цвета содержит 7-мь препятствий, а путь красного цвета содержит также 7-мь препятствий (6 + 1 = 7) следовательно, любой из выделенных путей можно устранить. Удалим часть пути красного цвета.

 

 

 



Очевидно, что путь синего цвета содержит 8-мь препятствий, а путь красного цвета содержит также 8-мь препятствий (2 + 6 = 8) следовательно, любой из выделенных путей можно устранить. Удалим часть пути красного цвета.

 

 

Как видно из последней схемы, начальная карта существенно упрощена, и теперь, можно воспользоваться элементарным перебором, чтобы детерминировать оптимальный путь участника.

 

III этап: определение оптимального маршрута.

Выпишем в табличном варианте всевозможные маршруты участника от старта до финиша:

Маршрут участникаКоличество препятствий
2 + 2 + 711

 

Маршрут участникаКоличество препятствий
2 + 2 + 711
2 + 2 + 3 + 2 + 110

 

Маршрут участникаКоличество препятствий
2 + 2 + 711
2 + 2 + 3 + 2 + 110
8 + 3 + 718

 

Маршрут участникаКоличество препятствий
2 + 2 + 711
2 + 2 + 3 + 2 + 110
8 + 3 + 718
8 + 2 + 111

 

Как видно из заполненной таблицы, минимальное количество препятствий равно 10-ть: 2 + 2 + 3 + 2 + 1, следовательно, данный маршрут является оптимальным.

 

Вывод:

10 - наименьшее число препятствий, которые может преодолеть спортсмен

Резюме

  1. разобрали предложенную маршрутную схему;

  2. отсекли избыточные варианты;

  3. среди оставшихся маршрутов выделили оптимальный путь.

 

Ответ:

10

 
Рейтинг:
 
Проголосовало: 0
Количество просмотров: 2971
 
 
 

Категория B9 • задача №1

 

Комментарии

Для комментирования или зарегистрируйтесь
 

Остальные решения из билета №1 для подготовки к ЕГЭ по информатике 2013

 
Условие задачи
(наведите курсор мыши на ссылку)
Аудиовизуальное
решение
Мультимедийная
видеопрезентация
Решение в формате
слайд-шоу
Текстовое
решение
Категория A1
/sites/default/files/slides/inf/1211/inf_A1_01_01_t4S.jpg
Перейти Перейти Перейти Перейти
Категория A2
/sites/default/files/slides/inf/804/inf_A2_01_01_knN.jpg
Перейти Перейти Перейти Перейти
Категория A3
/sites/default/files/slides/inf/805/inf_A3_01_01_53B.jpg
Перейти Перейти Перейти Перейти
Категория A4
/sites/default/files/slides/inf/806/inf_A4_01_01_HXr.jpg
Перейти Перейти Перейти Перейти
Категория A5
/sites/default/files/slides/inf/877/inf_A5_01_01_phpTD0463.jpg
Перейти Перейти Перейти Перейти
Категория A6
/sites/default/files/slides/inf/1225/inf_A6_01_01_CRr.jpg
Перейти Перейти Перейти Перейти
Категория A7
/sites/default/files/slides/inf/890/inf_A7_01_01_Ado.jpg
Перейти Перейти Перейти Перейти
Категория A8
/sites/default/files/slides/inf/898/inf_A8_01_01_JJV.jpg
Перейти Перейти Перейти Перейти
Категория A9
/sites/default/files/slides/inf/2159/inf_A9_01_01_phpUpivnW.jpg
Перейти Перейти Перейти Перейти
Категория A10
/sites/default/files/slides/inf/2170/inf_A10_01_01_phpl32P1w.jpg
Перейти Перейти Перейти Перейти
Категория A11
/sites/default/files/slides/inf/994/inf_A11_01_01_KyH.jpg
Перейти Перейти Перейти Перейти
Категория A12
/sites/default/files/slides/inf/1295/inf_A12_01_01_TJK.jpg
Перейти Перейти Перейти Перейти
Категория A13
/sites/default/files/slides/inf/1310/inf_A13_01_01_VsS.jpg
Перейти Перейти Перейти
Категория B1
/sites/default/files/slides/inf/899/inf_B1_01_01_php1fwK8N.jpg
Перейти Перейти Перейти Перейти
Категория B2
/sites/default/files/slides/inf/2193/inf_B2_01_01_phpUx4Mvg.jpg
Перейти Перейти Перейти Перейти
Категория B3
/sites/default/files/slides/inf/2202/inf_B3_01_01_phpUx4Mvg.jpg
Перейти Перейти Перейти Перейти
Категория B4
/sites/default/files/slides/inf/1364/inf_B4_01_01_iKq.jpg
Перейти Перейти Перейти Перейти
Категория B5
/sites/default/files/slides/inf/1341/inf_B3_01_01_i5V.jpg
Перейти Перейти Перейти Перейти
Категория B6
/sites/default/files/slides/inf/2213/inf_B6_01_01_phpEyxdxU.jpg
Перейти Перейти Перейти Перейти
Категория B7
/sites/default/files/slides/inf/2221/inf_B7_01_01_phpo5DDL8.jpg
Перейти Перейти Перейти Перейти
Категория B8
/sites/default/files/slides/inf/2228/inf_B8_01_01_phpLRZYf4.jpg
Перейти Перейти Перейти Перейти
Категория B10
/sites/default/files/slides/inf/2271/inf_B10_01_01_phpBoQYXv.jpg
Перейти Перейти Перейти Перейти
Категория B11
/sites/default/files/slides/inf/2281/inf_B11_01_01_phpi8udor.jpg
Перейти Перейти Перейти Перейти
Категория B12
/sites/default/files/slides/inf/2290/inf_B12_01_01_phpE00GlF.jpg
Перейти Перейти Перейти Перейти
Категория B13
/sites/default/files/slides/inf/2310/inf_B13_01_01_phpwzFLNF.jpg
Перейти Перейти Перейти Перейти
Категория B14
/sites/default/files/slides/inf/2324/inf_B14_01_01_php64fzgb.jpg
Перейти Перейти Перейти Перейти
Категория B15
/sites/default/files/slides/inf/2330/inf_B15_01_01_phpKZvkiX.jpg
Перейти Перейти Перейти Перейти
Категория C1
/sites/default/files/slides/inf/901/inf_C1_01_01_VWF.jpg
Перейти Перейти Перейти Перейти
Категория C2
/sites/default/files/slides/inf/902/inf_C2_01_01_DuJ.jpg
Перейти Перейти Перейти Перейти
Категория C3
/sites/default/files/slides/inf/903/inf_C3_01_01_P64.jpg
Перейти Перейти Перейти Перейти
Категория C4
/sites/default/files/slides/inf/904/inf_C4_01_01_kuu.jpg
Перейти Перейти Перейти Перейти
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?