Содержание Решение задач по теме «Обход дерева. Графы» Государственное автономное учреждение дополнительного профессионального образования «Саратовский областной институт развития образования» Методический семинар «Методика подготовки обучающихся к ГИА по информатике» Учитель информатики МОУ «СОШ 51» Кировского района г. Саратова Васинькина Наталия Николаевна

Содержание Из презентации Барабонина С.Ю. Информационная модель может быть построена с помощью графов Граф может быть задан разными способами: списком дуг, графически или таблицей. С помощью графа удобно представить модель населённых пунктов, связанных дорогами. Содержание

Предистория ЕГЭ-2016 на сайте «Успешно сдать ЕГЭ по информатике» г.г. Предистория ЕГЭ Типы задач ЕГЭ-2016, решаемых с помощью графов: Типы задач ЕГЭ-2016, решаемых с помощью графов – 3: три задачи 3: три задачи – 5: два способа решения одной задачи 5: два способа решения одной задачи – 6: три задачи 6: три задачи – 15: два способа решения одной задачи – без дерева! 15: два способа решения одной задачи – без дерева! – 22: 8 задач, дерево в Р-06 только для наглядности 22: 8 задач дерево в Р-06 только для наглядности Источники информации

Содержание Это интересно на сайте «Успешно сдать ЕГЭ по информатике» г.г. Предистория ЕГЭ-2016 Решение задач демо ЕГЭ (графы) Однотипные задания выделены одним цветом на сайте. Задачи 2013 года: А2 Определить длину кратчайшего пути между пунктами. В1 Записать порядок команд в программе преобразования одного числа в другое. В9 Определить количество путей между двумя пунктами (городами). B13 Определить количество программ, которые преобразуют одно число в другое. C3 Определить количество камней в начале игры двух игроков А2 Определить длину кратчайшего пути между пунктами. В1 Записать порядок команд в программе преобразования одного числа в другое. В9 Определить количество путей между двумя пунктами (городами). B13 Определить количество программ, которые преобразуют одно число в другое. C3 Определить количество камней в начале игры двух игроков Задачи 2012 года: А2 Определить длину кратчайшего пути между пунктами. В2 Записать порядок команд в программе преобразования одного числа в другое. В9 Определить количество путей между двумя пунктами (городами). В13 Определить количество чисел, которые можно получить из заданного числа с помощью программы C3 Определить количество программ, которые преобразуют одно число в другое. А2 Определить длину кратчайшего пути между пунктами. В2 Записать порядок команд в программе преобразования одного числа в другое. В9 Определить количество путей между двумя пунктами (городами). В13 Определить количество чисел, которые можно получить из заданного числа с помощью программы C3 Определить количество программ, которые преобразуют одно число в другое. Задачи 2011 года: А6 Определить самое раннее время прибытия путешественника в заданный населенный пункт. В3 Записать порядок команд в программе преобразования одного числа в другое. C3 Определить, кто из игроков выиграет в игре. Указать его первый выигрышный ход. А6 Определить самое раннее время прибытия путешественника в заданный населенный пункт. В3 Записать порядок команд в программе преобразования одного числа в другое. C3 Определить, кто из игроков выиграет в игре. Указать его первый выигрышный ход. Задачи 2010 года: А10 Определить самое раннее время прибытия путешественника в заданный населенный пункт. B5 Указать наименьшее число команд в программе, управляющей роботом. В6 Решить задачу с логическими высказывания с помощью графа C3 Определить, кто из игроков выиграет в игре. Указать его первый выигрышный ход. А10 Определить самое раннее время прибытия путешественника в заданный населенный пункт. B5 Указать наименьшее число команд в программе, управляющей роботом. В6 Решить задачу с логическими высказывания с помощью графа C3 Определить, кто из игроков выиграет в игре. Указать его первый выигрышный ход. Задачи 2009 года: А10 Определить самое раннее время прибытия путешественника в заданный населенный пункт. A12 Решить задачу с логическими высказываниями с помощью графа В5 Записать порядок команд в программе преобразования одного числа в другое. В6 Решить задачу с логическими высказывания с помощью графа C3 Определить, кто из игроков выиграет в игре. Указать его первый выигрышный ход. А10 Определить самое раннее время прибытия путешественника в заданный населенный пункт. A12 Решить задачу с логическими высказываниями с помощью графа В5 Записать порядок команд в программе преобразования одного числа в другое. В6 Решить задачу с логическими высказывания с помощью графа C3 Определить, кто из игроков выиграет в игре. Указать его первый выигрышный ход.

Содержание «Успешно сдать ЕГЭ по информатике» Раздел информатики ЕГЭ2013ЕГЭ2012ЕГЭ 2011ЕГЭ2010ЕГЭ 2009 ГРАФЫА2,В1,В9,В13,СЗА2,В2,В9,В13,СЗA6,B3,C3A10,B5,B6,C3А10,В5,СЗ

Содержание Демо ЕГЭ2016 Содержание

Демо-ЕГЭ 2016 На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). 3 Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число - так, как оно указано в таблице. В В Е Е 5 ребер при вершине В Ответ: 20 4 ребра при вершине Е

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

Нарисуем путь из пункта А в F. Начнем с конца, с пункта F. В него идет дорога из Е. В пункт Е ведут дороги из B, C и D В пункт B ведет дорога из A, в С ведет дорога из В, в D ведет дорога из B В пункт В ведет дорога из А Видим, что из А в F ведут 3-и пути. Надо найти кратчайший путь из трех. Добавим в граф значение расстояний между пунктами 1-й путь: ABEF=3+7+3=13 2-й путь: ABCEF= =18 3-й путь: ABDEF= =12 Получили кратчайший путь: ABDEF. Его длина равна Ответ: 2 3

Содержание Я делаю иначе: AF min = AB + BE min + EF BE min = min (7, 4+2, 7+5) = min (7, 6, 12) = 6 AF min = = 12 От удачной схемы зависит простота решения Ответ: 2 3

4. «Эх, дороги…» Между городами А, Б, В, Г, Д построены дороги, протяжённость которых указана в таблице. Отсутствие числа в ячейке означает, что прямой дороги между соответствующими городами нет. Найти длину кратчайшего пути между пунктами А и Д, проходящего через пункт В, если передвигаться можно только по указанным дорогам. АБВГД А31215 Б342 В143 Г222 Д 32 3 Содержание

Решение Строим по таблице граф дорог: 4. «Эх, дороги…» А Б ВГ Д Дальше нужно искать все возможные пути из А в Д, отбрасывая те, которые не проходят через город В, подсчитывать их длину и искать путь с минимальным значением его суммарной длины. 3 Содержание

Решение Чтобы ускорить решение, можно сразу исключить пути «в обход» города В: 4. «Эх, дороги…» А Б ВГ Д А Б ВГ Д Получили совсем простой граф (тем более, что в город Г теперь вообще ни одна дорога из А не идет, так что путь ГД тоже можно исключить). 3 Содержание

Решение В этом графе только два возможных пути: АБВД с длиной = 10, АВД с длиной = 4. Кратчайший из них – путь АВД. Его длина равна 4. Ответ: «Эх, дороги…» А Б В Д Содержание

1. Снова Фано Для кодирования последовательности символов, состоящей из букв К, И, Н, О, используется неравномерный двоичный код, удовлетворяющий условию Фано. При этом для буквы К использован код 0, а для буквы И – код 11. Требуется определить наименьшую возможную суммарную длину всех кодовых слов указанных букв. 1) 8 2) 9 3) 10 4) 11 5 Содержание

1. Снова Фано Решение Условие Фано: Закодированное сообщение можно однозначно декодировать с начала, если никакое кодовое слово не является началом другого кодового слова. Для проверки на соответствие кодов условию Фано нужно попарно сравнивать между собой коды по следующим правилам: когда длина обоих сравниваемых кодов совпадает, проверяется равенство этих кодов: если один код совпадает с другим, то такая пара кодов неправильна (не удовлетворяет условию Фано); когда длина сравниваемых кодов различна, более короткий код записывается под более длинным с выравниванием обоих кодов по левому краю: если все знаки более короткого кода совпадают с соответствующими знаками в начале более длинного кода, то такая пара кодов неправильна (не удовлетворяет условию Фано). 5 Содержание

1. Снова Фано Решение Будем подбирать коды для буквы Н, перебирая возможные двоичные числа с возрастающей длиной (чтобы получить наименьшую возможную суммарную длину кодов). Код буквы К Код буквы И Предполагаемы й код буквы Н Комментарий Нельзя, так как совпадает с началом кода буквы И 00 Нельзя – код буквы К совпадает с его началом 01 Нельзя – код буквы К совпадает с его началом 10 Допустимый код (не совпадает с двузначным кодом буквы И, а код буквы К не совпадает с его началом) 5 Содержание

1. Снова Фано Решение Предположим, что первый код найден. Удастся ли найти код для оставшейся буквы О? (Коды, которые не подошли для буквы Н, можно сразу отбросить, так как код буквы О должен удовлетворять тем же требованиям при сравнении с кодами букв К и И.) 000, 001, 010, 011 Нельзя – код буквы К совпадает с его началом Код буквы К Код буквы И Код буквы Н Предполагаемый код буквы О Комментарий Нельзя – совпадает с кодом буквы И 100, 101 Нельзя – код буквы Н совпадает с его началом 110, 111 Нельзя – код буквы И совпадает с его началом Далее с увеличением числа разрядов в предполагаемом коде буквы О будет сохраняться та же тенденция: ни один код не пригоден. 5 Содержание

Код буквы К Код буквы И Код буквы Н Предполагаемый код буквы О Комментарий Снова Фано Решение Причина: выбрав для буквы Н код 10, мы «закрыли» возможность дальнейшего расширения нашей кодовой системы. Поэтому вместо кода 10 придется выбрать для буквы Н более длинный код, – например, 100. Повторим попытку поиска кода для буквы О: 101 Допустимый код (не совпадает с трехзначным кодом буквы Н, а коды букв К и И не совпадают с его началом) 5 Содержание

1. Снова Фано Решение Решение найдено: Суммарная длина этих кодов (в знаках): = 9. КИНО Ответ: 2). 5 Содержание

2 способ решения «Снова Фано» В решении рисуем дерево на принципе неравномерного кодирования. Минимальная суммарная длина= = = 9 Для кодирования последовательности символов, состоящей из букв К, И, Н, О, используется неравномерный двоичный код, удовлетворяющий условию Фано. При этом для буквы К использован код 0, а для буквы И – код 11. Требуется определить наименьшую возможную суммарную длину всех кодовых слов указанных букв. 1) 8 2) 9 3) 10 4) 11 кино Ответ: 2 5 «Когда дерево во благо»

Содержание «Когда дерево во благо» Исполнитель Вычислитель У исполнителя Вычислитель три команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 3. прибавь 3 Первая из них уменьшает число на экране на 1, вторая утраивает его, а третья увеличивает на 3. Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд. Например, 211 это алгоритм: 2. умножь на 3 1. вычти 1 1. вычти 1, который преобразует число 7 в 19. Решение В2 в 2012 г. 6 в

Содержание Исполнитель Вычислитель 1. вычти 1 2. умножь на 3 3. прибавь 3 Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд. 5 * *3 +3 * * I II III Ответ: 321 Для решения данной задачи полезно построить дерево. Строим! 2) В2 в 2012 г. 6 в

Содержание Исполнитель Конструктор У исполнителя Конструктор две команды, которым присвоены номера: 1. приписать 2 2. разделить на 2. Первая из них приписывает к числу на экране справа цифру 2, вторая – делит его на 2. Запишите порядок команд в алгоритме получения из числа 1 числа 16, содержащем не более 5 команд, указывая только номера команд (например, – это алгоритм: разделить на 2 приписать 2 разделить на 2, который преобразует число 8 в число 6.) Если таких алгоритмов более одного, запишите любой из них. Решение 1. З В2 в 2012 г. 6 в

Содержание СКИ: 1. приписать 2 2. разделить на 2. Получить из числа 1 число 16 (максимум за 5 команд) I II III IV V Ответ: Исполнитель Конструктор 1. Р В2 в 2012 г. 6 в

Содержание Из Демо-2012: У исполнителя Кузнечик две команды: 1. прибавь 3, 2. вычти 2. Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются). Программа для Кузнечика – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? Ответ: ___________________________. В13 в 2012 г. 6

Содержание Сколько различных чисел можно получить из числа 1 в программах, содержащих 5 команд: 1. прибавь 3, 2. вычти 2. Первая из них увеличивает число на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются) Эталон от К.Ю.Полякова В13 в 2012 г. 6 Содержание

1 способ: 1 способ: Рассмотрение пути от конца маршрута с подсчётом количества входов в каждую вершину. После заполнения первых 2-х столбцов начинается подсчёт во 2-м с заполнением 3-его СНИЗУ вверх. (Рекомендуется выполнить топологическую сортировку – я её выполняю в процессе заполнения 3-его столбца) 15 Содержание

N A =1 N Б =N Д =N А =1 N Г =N А +N Д =1+1=2 N В =N Б +N А +N Г =1+1+2=4 N Е =N Б +N В =1+4=5 N З =N В +N Г +N Д =4+2+1=7 N Ж =N Е +N В +N З =5+4+7=16 N И =N Е +N Ж +N З =5+16+7=28 N К =N Л =N И =28 N М =N К +N Л =28+28=56 Ответ: 56 2 способ: 2 способ: У каждой вершины указывать количество входов, учитывая входы в предыдущие вершины Слайд из презентации Гудковой Ирины Анатольевны (Гимназия 87) с семинара от в МАОУ «Гимназия 108» 15

Содержание С3. (30 мин) высокий Проверяемые элементы содержания: Умение построить алгоритм для решения поставленной задачи Виды деятельности: Применение знаний и умений в новой ситуации Требования к уровню подготовки выпускников, достижение которого проверяется на ЕГЭ: Создавать программы на языке программирования по их описанию С3 в 2012 г. 22 в

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

Содержание Верны следующие соотношения: Если n не делится на 3, то тогда R(n) = R(n-1), так как существует единственный способ получения n из предыдущего шага прибавлением единиц. Пусть n делится на 3. Тогда R(n) = R(n/3) + R(n-1)= R(n/3) + R(n-3) (если n >3). При n =3 R(n)=2 (два способа: прибавлением двух единиц или однократным умножением на 3). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных трем и не превосходящих 29: сначала вычисляем R(1), затем R(3), R(6) и т.д. Имеем: Решение С3 С3 в 2012 г. 22 в

Содержание R(2) = 1 R(3) = 2 = R(4) =R(5) R(6) = R(2)+R(3) = 1+2 = 3 = R(7)=R(8) R(9) = R(3)+R(6) = 2+3 = 5 = R(10)=R(11) R(12) = R(4)+R(9) = 2+5 = 7= R(13)=R(14) R(15) =R(5)+R(12) = 2+7 = 9 = R(16)=R(17) R(18) = R(6)+R(15) = 3+9 = 12 = R(19)=R(20) R(21) = R(7)+R(18) = 3+12 = 15 = R(22)=R(23) R(24) = R(8)+R(21) = 3+15 = 18 = R(25)=R(26) R(27) = R(9)+R(24) = = 23 = R(28)=R(29) Ответ: 23 Решение С3. 1 способ С3 в 2012 г. 22 в

Содержание i RiRi i RiRi Решение С3. 2 способ СКИ Утроитель : 1. прибавь 1, 2. умножь на 3. Сколько есть программ: 1 29? Ответ: 23 С3 в 2012 г. 22 в

Содержание Р-06. Исполнитель Июнь 15 (От Полякова К.Ю.) Р-06. Исполнитель Июнь 15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь 15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25? 22

Содержание Р-06. Сколько существует программ: 2 29, при этом 14 траектории, 25 траектории СКИ Июнь 2015: 1. прибавь 1, 2. умножь на 2. Дерево только для наглядности: как 14 траектории и 25 траектории 22 Содержание

Р-06. Сколько существует программ: 2 29, при этом 14 траектории, 25 траектории i RiRi = =33 2+3= =77 3+7= = 13 i RiRi СКИ Июнь 2015: 1. прибавь 1, 2. умножь на 2. Пример работы 2-й формулы на R 10 = R 5 + R 9 = = 7 22 Р-06. Решение

Содержание Р-05. Исполнитель Удвоитель (От Полякова К.Ю.) У исполнителя Удвоитель две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»? 22

Содержание Сколько существует программ: 4 24, при этом предпоследней командой является «1» СКИ Удвоитель : 1. прибавь 1, 2. умножь на 2. i RiRi Р-05. Решение Предпоследняя команда – 1, последняя команда может быть как 1, так и 2. Нужно получить количество программ вида «*11» и «*12» (звёздочка любые команды) Если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число 24 – 1 – 1 = 22; поэтому нужно найти число программ для преобразования 4 в 22 Если программа заканчивается на «12», это значит, что до выполнения цепочки «12» у нас было число (24/2) – 1 = 11; поэтому нужно найти число программ для преобразования 4 в 11, берём его из таблицы: 3 ответ к задаче – сумма двух значений, выделенных цветом: = 18, мы рассмотрели все варианты программ, в которых предпоследняя команда 1 Ответ: Содержание

Р-04. Исполнитель Удвоитель (От Полякова К.Ю.) У исполнителя Удвоитель две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16,

Содержание Р-04. Сколько существует программ: 1 21, при этом 10 траектории i RiRi СКИ Удвоитель: 1. прибавь 1, 2. умножь на 2. Ответ: 28 Р-04. Решение 22

Содержание Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 2 3. прибавь следующее Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Калькулятор– это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число Р-04. Исполнитель Удвоитель (От Полякова К.Ю.)

Содержание Р-04. Сколько существует программ: 2 10 i RiRi СКИ Калькулятор. 1. прибавь 1 2. прибавь 2 3. прибавь следующее Ответ: 47 Р-04. Решение Число i может быть получено: увеличением на 1 числа i -1; увеличением на 2 числа i -2; из некоторого числа X увеличением на X+1 (следующее число), так что i = X + X + 1, откуда X = ( i – 1) / 2; таким образом (командой 3.) могут быть получены только нечетные числа. 22

Содержание Р-03. Исполнитель Май 4 преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 2 3. прибавь 4 Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья – на 4. Программа для исполнителя Май 4 – это последовательность команд. Сколько есть программ, которые число 21 преобразуют в число 30? Р-03. Исполнитель Май 4 (От Полякова К.Ю.) 22

Содержание Р-03. Сколько существует программ: СКИ Май прибавь 1 2. прибавь 2 3. прибавь 4 22 i RiRi Ответ: 96 Р-03. Решение

Содержание Р-01. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. увеличь вторую с конца цифру на 1 Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд. Сколько есть программ, которые число 15 преобразуют в число 28? Р-01. Исполнитель Калькулятор (От Полякова К.Ю.) 22

Содержание Р-01. Сколько существует программ: СКИ Калькулятор: 1. прибавь 1 2. увеличь вторую с конца цифру на 1: увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется 22 i RiRi Ответ: 5 Р-01. Решение

Содержание Р-00. Исполнитель Калькулятор (От Полякова К.Ю.) 22 Р-00. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 1 2. увеличь две младшие цифры на 1 Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 какая- либо из двух младших цифр равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд. Сколько есть программ, которые число 23 преобразуют в число 48?

Содержание Р-00. Сколько существует программ: СКИ Калькулятор: 1. прибавь увеличь две младшие цифры на 1 : увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 какая-либо из двух младших цифр равна 9, она не изменяется 22 Ответ: 26 Примечание. Возможны особенные варианты для команды 2: увеличения только младшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+1») – для всех чисел от 91 до 99, но в нашем диапазоне [23..48] таких нет увеличения только старшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+10») – для всех чисел, больших 34 и имеющих 9 на конце; в нашем случае под этот вариант подходит только число 39 Р-00. Решение i RiRi

Содержание Источники информации – 22: перебор вариантов, динамическое программирование : перебор вариантов, динамическое программирование – Программа-тренажёр для решения задач на динамическое программирование Программа-тренажёр для решения задач на динамическое программирование «Успешно сдать ЕГЭ по информатике» Презентации: Barabonun Барабонин Сергей Юрьевич ЕГЭ.ppt – «Аттестация учащихся 9-х классов по информатике и ИКТ» (Семинар ) В1 В13 ВасинькинаНН ppt – Методика подготовки к ЕГЭ по информатике. Задания В1, В13. Раздел «Элементы теории алгоритмов» (Семинары от , ) Богомолова О.Б., Усенков Д.Ю. Тренаж по информатике: «разбор полётов» Содержание