Презентация по информатике Использование теории графов при решении заданий ЕГЭ

Использование теории графов при решении заданий ЕГЭ по информатике Учитель информатики и ИКТЗеленкова Алена Александровна Задание 1 Между населенными пунктами А, В, С, D, Е, F построены дороги, протяженность которых приведена в таблице (отсутствие числа означает, что пря мой дороги нет)Определить длину кратчайшего пути между пунктами А и F. (Передвигаться можно только по построенным дорогам) A B C D E F A 2 4 B 2 1 7 C 1 3 4 D 3 3 E 7 3 3 2 F 2 Варианты ответов:1. 9 2. 10 3. 11 4. 12 Решение: B A D C F E 2 1 4 7 3 2 3 4 A B C D E F A 2 4 B 2 1 7 C 1 3 4 D 3 3 E 7 3 3 2 F 2 B A D C F E 2 1 4 7 3 2 3 4 А В Е E E F D Е F С С D F E F F 2 1 3 4 7 3 2 2 2 4 3 3 2 2 1 путь: 2+1+3+3+2=112 путь: 2+1+4+2=93 путь: 2+7+2=114 путь: 4+3+3+2=125 путь: 4+4+2=10 4 Варианты ответов:1. 9 2. 10 3. 11 4. 12 Ответ: 1 Задание 2 У исполнителя Утроитель две команды, которым присвоены номера1. Прибавь 1;2. Умножь на 3.Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд. 22 21 20 7 19 6 1 1 команда 2 команда 4 команда 3 команда 18 5 5 команда 17 6 2 4 -1 -1 -1 -1 -1 -1 -1 :3 :3 -1 -1 :3 Ответ: 12121 1+1*3+1*3+1=22 Решение: Пойдём от обратного Задание 3 Сколько существует различных путей из города А в город К? А Б Г В Д Е Ж И К Решение: А Б В Г В Д К К И К Д Ж И К К Д Ж Е К К И К В Ж Д И К Ж К К К К Ответ: 13 Задание 4 У Исполнителя Кузнечик 2 команды:1. Прибавь 3;2. Вычти 2.Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд. Решение:  1 4 -1 7 2 0 -3 -5 5 6 10 11 16 1 команда 2 команда 3 команда 4 команда 5 команда 13 8 -2 3 -7 1 -4 -9 +3 +3 +3 +3 +3 +3 +3 +3 +3 +3 +3 +3 -2 -2 -2 -2 -2 +3 +3 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 Ответ: 6 +3 Задание 5 У исполнителя Устроитель две команды, которым присвоены номера:1. Прибавь 1;2. Умножь на 3.Программа для Устроителя – это последовательность команд. Сколько есть программ, которые преобразуют 1 в число 29? Решение: 1 2 3 3 6 4 8 7 9 6 27 5 9 28 29 10 11 29 29 29 29 29 12 15 29 13 18 21 24 . . . . . . . . . . . . . . . . . . 1 прг. 2 прг. 9 прг. 5 прг. Ответ: 23 5+9+9=23 +1 +1 +1 +1 +1 +1 +1 +1 *3 *3 *3 *3 *3 *3 *3 *3 *3 +1 +1 +1 +1 +1 +1 +1 1 прг. 1 прг. 1 прг. 1 прг. 1 прг. 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 игрок