Презентация по информатике на тему Разбор задач ЕГЭ по теме Алгоритмы (задания № 6,11,14)

Разбор задач ЕГЭ по информатике по теме «Алгоритмы» (задачи №6, 11, 14) Учитель информатики МБОУ СОШ № 7Рожкова С.В. Г. Георгиевск31.03.2017г. Разбор 6 задания Задание базового уровня сложности.Примерное время выполнения задания 4 минуты.Проверяемые элементы содержания: формальное исполнение алгоритма, записанного на естественном языке или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд.Элементы содержания, проверяемые на ЕГЭ: Формализация понятия алгоритма. Построение алгоритмов и практические вычисления. Пример Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.1. Складываются первая и вторая, а также вторая и третья цифры исходного числа.2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).Пример. Исходное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Результат: 127.Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.Ответ: ________ Решение Очевидно, что результат 1711 получился из двух чисел 17 и 11.Теперь находим наименьшее трехзначное число.Так как ищем наименьшее число, то и начинать будем с наименьшей суммы (11), чтобы получить наименьшую первую цифру.11 – 9 = 2. Таким образом, число 11 получается как сумма 2 и 9: 2 + 9 = 11.Число 17 получается как сумма 9 и 8: 9 + 8 = 17.Теперь составляем искомое наименьшее трехзначное число и получаем 298.Проверяем 2 + 9 = 11 и 9 + 8 = 17Ответ: 298 Разбор 11 задания Это задание базового уровня сложности. Примерное время выполнения задания 5 минут.Проверяемые элементы содержания: умение исполнить рекурсивный алгоритм.Элементы содержания, проверяемые на ЕГЭ: индуктивное определение объектов. Пример Ниже на пяти языках программирования записан рекурсивный алгоритм F.Чему равна сумма напечатанных на экране чисел при выполнении вызова F(10)?Ответ: ________ Решение procedure F(n: integer);beginif n > 2 then beginwriteln(n);F(n – 3);F(n – 4)endend;После каждого вызова на экран выводится значение параметра функции, если выполняется условие n>2. Запишем все вызовы в виде дерева Складываем все значения параметров, которые больше 2 Получаем ответ: 10+7+4+3+6+3=33Ответ: 33 Разбор 14 задания Это задание повышенного уровня сложности. Примерное время выполнения задания 6 минут.Проверяемые элементы содержания: умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд.Элементы содержания, проверяемые на ЕГЭ: Вычислимость. Эквивалентность алгоритмических моделей. Пример Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.А) заменить (v, w).Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение командызаменить (111, 27)преобразует строку 05111150 в строку 0527150.Если в строке нет вхождений цепочки v, то выполнение командызаменить (v, w) не меняет эту строку.Б) нашлось (v).Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется. Цикл ПОКА условие последовательность команд КОНЕЦ ПОКАвыполняется, пока условие истинно.В конструкции ЕСЛИ условие ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИвыполняется команда1 (если условие истинно) или команда2 (если условие ложно). Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 69 идущих подряд цифр 8? В ответе запишите полученную строку.НАЧАЛОПОКА нашлось (3333) ИЛИ нашлось (8888) ЕСЛИ нашлось (3333) ТО заменить (3333, 88) ИНАЧЕ заменить (8888, 33) КОНЕЦ ЕСЛИКОНЕЦ ПОКАКОНЕЦОтвет: ________ Решение Программа будет работать до тех пор, пока в строке есть цепочка цифр 3333 или цепочка цифр 8888.Если в строке встречается 3333, то заменяем на 88.Если в строке нет цепочки 3333, но встречается цепочка 8888, то заменяем ее на 33.Наша строка состоит из 69 идущих подряд цифр 8.1) меняем первые 8888 на 33 и получаем 33 и (65 цифр 8)2) меняем следующие 8888 на 33 и получаем 3333 и (61 цифру 8)3) теперь у нас появилась цепочка 3333, поэтому мы должны заменить ее на 88 получаем строку состоящую из 63 цифр 8 Анализируем что произошло!А получилось следующее, за 3 шага мы заменили 8 восьмерок на 2 (или удалили 6 восьмерок из нашей строки).Становится понятно, что за каждые 3 шага мы будем удалять по 6 восьмерок.63-6=57 57-6=5151-6=45 45-6=3939-6=33 33-6=2727-6=21 21-6=1515-6=9 9-6=3 останется строка состоящая из 3 идущих подряд 8 (888)Ответ: 888