Использование теории графов при решении заданий ЕГЭ по информатике Дикусар Раиса Анатольевна МОУ « Тираспольская средняя школа 15» Учитель математики, информатики и ИКТ

Задание А 2, 2013 год Между населенными пунктами А, В, С, D, Е, F построены дороги, протяженность которых приведена в таблице ( отсутствие числа означает, что пря мой дороги нет ) Определить длину кратчайшего пути между пунктами А и F. ( Передвигаться можно только по построенным дорогам ) ABCDEF A24 B217 C134 D33 E7332 F2 Варианты ответов:

Решение : B A D C F E ABCDEF A24 B217 C134 D33 E7332 F2

B A D C F E А В Е E E F D Е F С С D F E F F путь: =11 2 путь: =9 3 путь: 2+7+2=11 4 путь: =12 5 путь: 4+4+2=10 4 Варианты ответов: Ответ: 1

Задание В 2, 2013 год У исполнителя Устроитель две команды, которым присвоены номера 1. Прибавь 1; 2. Умножь на 3. Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд.

команда 2 команда 4 команда 3 команда команда :3 :3 Ответ: *3+1*3+1=22 Решение:

Задание В 9, 2013 год Сколько существует различных путей из города А в город К ? А Б Г В Д Е Ж И К

Решение: А Б ВГ В Д К КИКДЖ ИКК ДЖЕ К КИ К В Ж Д ИК ЖК ККК Ответ: 13

Задание В 13, 2013 год У Исполнителя Кузнечик 2 команды : 1. Прибавь 3; 2. Вычти 2. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд.

Решение : команда 2 команда 3 команда 4 команда 5 команда Ответ: 6 +3

Задание С 3, 2013 год У исполнителя Устроитель две команды, которым присвоены номера : 1. Прибавь 1; 2. Умножь на 3. Программа для Устроителя – это последовательность команд. Сколько есть программ, которые преобразуют 1 в число 29?

Решение : прг. 2 прг. 9 прг.5 прг. Ответ: =23 +1 * прг.

Задание С 3, 2011 год Даны три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой - нибудь куче, или добавить по 2 камня в каждую из всех трех куч. Выигрывает тот, после чьего хода в какой - нибудь куче становится больше или равно 15 камней или во всех трех кучах суммарно становится больше либо равно 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок ?

Решение: 2, 3, 4 камня. За один ход можно или удвоить количество камней в 1 куче, или добавить в каждую по 2 камня. Если в одной куче больше или равно 15 или во всех кучах больше либо равно 25, то это выигрыш. 1 игрок 2 игрок 1 игрок 2, 3, 4 4, 3, 4 8, 3, 4 16, 3, 4Выигрывает 1 игрок 4, 6, 4 8, 6, 4Выигрывает 2 игрок 4, 12, 4Выигрывает 2 игрок 6, 8, 6Выигрывает 2 игрок 4, 3, 8 4, 3, 16Выигрывает 1 игрок 6, 5, 6 12, 5, 6Выигрывает 2 игрок 6, 10, 6Выигрывает 2 игрок 8, 7, 8Выигрывает 2 игрок 2, 6, 4 4, 6, 4Выигрывает 2 игрок 2, 12, 4Выигрывает 1 игрок 2, 6, 8Выигрывает 1 игрок 4, 8, 6Выигрывает 1 игрок 2, 3, 8 4, 3, 8Выигрывает 1 игрок 2, 6, 8Выигрывает 1 игрок 2, 3, 16Выигрывает 2 игрок 4, 5, 10Выигрывает 1 игрок 4, 5, 6 8, 5, 6Выигрывает 1 игрок 4, 10, 6Выигрывает 1 игрок 4, 5, 12Выигрывает 1 игрок 6, 7, 8Выигрывает 1 игрок

Используемая литература : 1. Демонстрационные материалы ЕГЭ по информатике 2011, 2013 г.