Вторник, 19.03.2024, 13:41
Хочу сдавать ЕГЭ!!!
Главная Регистрация Вход
Приветствую Вас, Гость · RSS
Ученикам 10-11 кл
Гостевая книга
Википедия
Полезные   ссылки 
  • Школьный    сайт             
  • Банк данных ЕГЭ по информатике
  • Сайт ФИПИ
  • Решу ЕГЭ (тесты on-line)
  • Решение Демо ЕГЭ
  • Каталог сайтов
  • Подготовка к ГИА
    Информатика 9 кл
    Информатика 8 кл
    Информатика 7 кл
    Архив записей
    Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0


     А2 Графы, диаграммы, таблицы

    А2 ЕГЭ  А3 ГИА  Графы, диаграммы, графики.

    (базовый уровень, время – 2 мин)

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

    Для решения з

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

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

    ·      рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

     

    A

    B

    C

    D

    Е

    A

     

     

    3

    1

     

    B

     

     

    4

     

    2

    C

    3

    4

     

     

    2

    D

    1

     

     

     

     

    Е

     

    2

    2

     

     







    Задачи на определение кратчайшего пути

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

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

    1)      11    2)12   3)13    4) 18

    Решение:

    Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.

    Нарисуем путь из пункта А в F. Начнем с конца, с пункта F. В него идет дорога из Е:

    в пункт Е ведут дороги из B, C и D:

    В пункт B ведет дорога из A, в пункт С ведет дорога из В, в пункт D ведет дорога из B:

    В пункт В ведет дорога из А:

    Видим, что из А в F ведет 3-и пути. Надо найти кратчайший путь из трех. Добавим в граф значение расстояний между пунктами:

    1-й путь: A−B−E−F=3+7+3=13

    2-й путь: A−B−C−E−F=3+7+5+3=18

    3-й путь: A−B−D−E−F=3+4+2+3=12

    Получили кратчайший путь: A−B−D−E−F. Его длина равна 12.

    Задачи на соответствие между таблицей и графом

    Пример 1. В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

     

    A

    B

    C

    D

    A

     

    3

     

    1

    B

    3

     

    2

    1

    C

     

    2

     

    4

    D

    1

    1

    4

     

    1)
    2)
    3)
    4)




    Решение

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

    AB=3, Не подходят графы 1), 3)

    АD=1,   2)и 4) графы оба подходят

    АВ=ВА этот вариант мы уже проверяли

    ВС=2, оба графа 2) и 4) подходят

    ВD=1, оба графа 2) и 4) подходят

    СВ=ВС, этот вариант мы уже проверяли

    СВ=4, не подходит 2)   

    Остается вариант 4

     Ответ 4


    Copyright MyCorp © 2024
    Сделать бесплатный сайт с uCoz