О.Б. Богомолова, Д.Ю. Усенков «По следам ЕГЭ-2011»: сложные задачи

РИСУЮЩАЯ «ЧЕРЕПАШКА» Исполнитель «Черепашка ЛОГО» Команды: перемещение поднять / опустить перо «Виртуальный лист бумаги» X Y (0,0)

РИСУЮЩАЯ «ЧЕРЕПАШКА» Составлена программа для исполнителя: алг чертеж нач вещ U, R, D цел I, N U = 0 R = 1 N = 50 D = 2 * PI / N поднять перо перейти в точку (____________) опустить перо нц для I от 1 до N U = U + D перейти в точку (____________) кц кон Что должно быть записано на месте пропусков, чтобы нарисовать линию, похожую на окружность? 1) R, R 2) R * R, U * U 3) R * cos(U), R * sin (U) 4) R * sin(D), R * cos(D) ? ?

РИСУЮЩАЯ «ЧЕРЕПАШКА» Решение алг чертеж нач вещ U, R, D цел I, N U = 0 R = 1 N = 50 D = 2 * PI / N поднять перо перейти в точку (____________) опустить перо нц для I от 1 до N U = U + D перейти в точку (____________) кц кон Переменная I нигде больше не используется. Значит, этот цикл используется только для отсчета шагов отрисовки окружности Начальное значение переменной U Вычисление угла, соответствующего N-й доле окружности На каждом шаге цикла значение угла U увеличивается на шаг D

РИСУЮЩАЯ «ЧЕРЕПАШКА» Решение алг чертеж нач вещ U, R, D цел I, N U = 0 R = 1 N = 50 D = 2 * PI / N поднять перо перейти в точку (____________) опустить перо нц для I от 1 до N U = U + D перейти в точку (____________) кц кон Тогда эти команды – выход Черепашки из точки (0, 0) в точку начала рисования окружности (угол U = 0) В цикле отрисовывается отрезок, примерно соответствующий очередной дуге окружности

РИСУЮЩАЯ «ЧЕРЕПАШКА» Решение Вспоминаем геометрию… X Y (0,0) R R sin(U) U R cos(U) Координата Y: R * sin(U) Координата X: R * cos(U) ? ?

РИСУЮЩАЯ «ЧЕРЕПАШКА» Решение Вспоминаем геометрию… X Y (0,0) R R sin(U) U R cos(U) Ответ: 3) R * cos(U), R * sin (U)

МАСКИРОВАНИЕ IP-АДРЕСА По заданному IP-адресу и маске определить адрес сети. IP-адрес: Маска: Решение 1) IP-адрес и маску надо представить как двоичные числа. 2) Подписав их друг под другом, провести поразрядную конъюнкцию (операция «И»). Биты IP-адреса, для которых в маске записан нуль, обнуляются; остальные биты IP-адреса переписываются без изменения.

МАСКИРОВАНИЕ IP-АДРЕСА IP-адрес: Маска: Решение & Ответ:

ПРИБАВЛЕНИЕ НУЛЕЙ Имеется некоторое число, записанное в семиричной системе счисления. К нему справа дописали три нуля. Во сколько раз увеличилось исходное число в результате этой операции? Решение Дописывание нулей в десятичной системе счисления: БылоСтало Дописывание нулей в двоичной системе счисления: БылоСтало 111 (= 7)1110 (=14) 1010 (= 10) (= 40) 1011 (= 11) (= 88) Правило: дописывание к числу справа каждого очередного нуля соответствует умножению этого числа на значение основания системы счисления. Ответ: при дописывании к числу, записанному в семиричной системе счисления, трех нулей справа это число увеличится в 7 3 = 343 раза.

РАСПЛЕТАЕМ ЦЕПОЧКИ Из цифр формируются цепочки (строки) по следующему правилу: первая строка состоит из одной цифры 1; вторая строка состоит из двух цифр – 23; далее любая цепочка с номером n составляется из двух цепочек – сначала переписывается цепочка с номером (n – 2), а потом к ней дописывается цепочка с номером (n – 1). Вот первые несколько таких строк: (1) 1 (2) 23 (3) 123 (4) … Сколько нечетных и сколько четных цифр будет в строке с номером 7?

РАСПЛЕТАЕМ ЦЕПОЧКИ Решение Распишем цепочки: цепочки (n) ЦепочкаКол-во четных цифр Кол-во нечетных цифр Числа Фибоначчи Ответ: четных чисел – 8, нечетных – 13.

АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Определить, сколько различных решений имеет система уравнений: Нужно указать именно количество решений системы уравнения, а не записывать сами эти решения.

Решение Логическая операция «тождество» (эквивалентность, логическое равенство) АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Обозначения:, ~, Таблица истинности: AB A B Правило: результат операции «тождество» (эквивалентность) равен 1 тогда и только тогда, когда оба операнда равны друг другу.

Решение Анализируем отдельные уравнения, входящие в систему. АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Операция «тождество»: обе переменные – x 1 и x 5 – должны быть равны друг другу 1

Решение Анализируем остальные уравнения. АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Операция «ИЛИ»: достаточно, чтобы был равен 1 хотя бы один операнд. x 1 = 0, x 2 = 0 или x 1 = 1, x 2 = 1 x 2 = 1, x 3 = 1 x 2 = 0, x 3 = 0

Решение АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Возможные комбинации значений переменных (x 1, x 2, x 3 ): (0 0 0), (0 0 1), (1 1 0), (1 1 1) Если истинна первая часть уравнения, значения остальных не важны (0 1 1), (1 1 1) Если истинна вторая часть уравнения, значения остальных не важны (0 0 0), (1 0 0) Если истинна третья часть уравнения, значения остальных не важны Итого – 6 различных вариантов (x 1, x 2, x 3 ): (0 0 0), (0 0 1), (0 1 1), (1 1 0), (1 0 0), (1 1 1).

Решение Анализируем второе уравнение. АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Операция «ИЛИ»: достаточно, чтобы был равен 1 хотя бы один операнд. x 1 = 0, x 3 = 0 или x 1 = 1, x 3 = 1 x 3 = 1, x 4 = 1 x 3 = 0, x 4 = 0

Решение АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Возможные комбинации значений переменных (x 1, x 3, x 4 ): (0 0 0), (0 0 1), (1 1 0), (1 1 1) Если истинна первая часть уравнения, значения остальных не важны (0 1 1), (1 1 1) Если истинна вторая часть уравнения, значения остальных не важны (0 0 0), (1 0 0) Если истинна третья часть уравнения, значения остальных не важны Итого – тоже 6 различных вариантов (x 1, x 3, x 4 ): (0 0 0), (0 0 1), (0 1 1), (1 1 0), (1 0 0), (1 1 1).

Решение Анализируем третье уравнение. АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Операция «ИЛИ»: достаточно, чтобы был равен 1 хотя бы один операнд. x 1 = 0, x 4 = 0 или x 1 = 1, x 4 = 1 x 4 = 1, x 5 = 1 x 4 = 0, x 5 = 0

Решение АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Возможные комбинации значений переменных (x 1, x 4, x 5 ): (0 0 0), (0 0 1), (1 1 0), (1 1 1) Если истинна первая часть уравнения, значения остальных не важны (0 1 1), (1 1 1) Если истинна вторая часть уравнения, значения остальных не важны (0 0 0), (1 0 0) Если истинна третья часть уравнения, значения остальных не важны Итого – еще 6 различных вариантов (x 1, x 4, x 5 ): (0 0 0), (0 0 1), (0 1 1), (1 1 0), (1 0 0), (1 1 1). Все три первых уравнения – типовые. Поэтому тройки значений соответствующих переменных в них будут всегда одни и те же, сколько бы ни было таких уравнений!

Решение Сводим воедино результаты, полученные для каждого уравнения в отдельности. АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Объединение уравнений в систему означает, что все они должны быть истинными одновременно. =И (&)

Решение АНАЛИЗ СИСТЕМЫ ЛОГИЧЕСКИХ УРАВНЕНИЙ Тогда в предпоследнем уравнении нужно оставить только варианты, в которых x 1 = x 5, т.е. (x 1, x 4, x 5 ) = (0 0 0) и (1 1 1). В этих вариантах x 1 = x 4, тогда во втором уравнении нужно оставить только варианты, в которых x 1 = x 4, т.е. (x 1, x 3, x 4 ) = (0 0 0) и (1 1 1). В этих вариантах x 1 = x 3, тогда в первом уравнении нужно оставить только варианты, в которых x 1 = x 3, т.е. (x 1, x 2, x 3 ) = (0 0 0) и (1 1 1). В этих вариантах x 1 = x 2. Тогда в результате получается, что все переменные во всех уравнениях должны быть равными: x 1 = x 2 = x 3 = x 4 = x 5 Ответ: (x 1, x 2, x 3, x 4, x 5 ) = ( ) или ( ), т.е. возможно два решения данной системы уравнений.

ОБРАБОТКА МАССИВА Дан массив из 30 целых чисел от -10 до 10. Требуется найти максимум среди элементов массива, которые являются простыми числами. (Один такой элемент в массиве точно есть.) Решение Как ищется простой минимум в массиве: 1) в качестве предполагаемого минимума запоминаем в отдельной переменной (min) значение самого первого элемента; 2) запускаем цикл просмотра элементов массива со второго до последнего; 3) на каждом шаге цикла при помощи условного оператора проверяем: если текущий элемент окажется меньше предполагаемого минимума, то перезапоминаем этот текущий элемент в переменной min ; 4) по завершении цикла в переменной min окажется искомый минимум. program simply_min; const n=10; var mas : array[1..n] of integer; i, min : integer; begin for i:=1 to n do read(mas[i]); min:=mas[1]; for i:=2 to n do if mas[i]

ОБРАБОТКА МАССИВА Решение Как ищется простой максимум в массиве: 1) в качестве предполагаемого максимума запоминаем в отдельной переменной (max) значение самого первого элемента; 2) запускаем цикл просмотра элементов массива со второго до последнего; 3) на каждом шаге цикла при помощи условного оператора проверяем: если текущий элемент окажется больше предполагаемого максимума, то перезапоминаем этот текущий элемент в переменной max ; 4) по завершении цикла в переменной max окажется искомый максимум. program simply_max; const n=10; var mas : array[1..n] of integer; i, max : integer; begin for i:=1 to n do read(mas[i]); max:=mas[1]; for i:=2 to n do if mas[i]>max then max:=mas[i]; writeln('Максимум = ', max); end.

ОБРАБОТКА МАССИВА Решение Как изменить программу, чтобы искать минимальный элемент, обладающий определенным признаком (например, нечетный)? 1) в условном операторе надо дописать (через логическую функцию and) условие проверки соответствия текущего элемента заданному признаку; 2) так как самый первый элемент может не соответствовать заданному признаку, лучше (если известен возможный диапазон значений элементов массива) в качестве предполагаемого минимума задать константу, заведомо большую любого элемента массива; цикл просмотра элементов нужно вести с первого до последнего. program min_nechet; const n=10; var mas : array[1..n] of integer; {элементы = от -10 до 10 } i, min : integer; begin for i:=1 to n do read(mas[i]); min:=11; for i:=1 to n do if (mas[i] mod 2 0) and (mas[i]

ОБРАБОТКА МАССИВА Решение Аналогично ищется максимальный элемент, обладающий определенным признаком. 1) в условном операторе надо дописать (через логическую функцию and) условие проверки соответствия текущего элемента заданному признаку; 2) так как самый первый элемент может не соответствовать заданному признаку, лучше (если известен возможный диапазон значений элементов массива) в качестве предполагаемого максимума задать константу, заведомо меньшую любого элемента массива; цикл просмотра элементов нужно вести с первого до последнего. program max_nechet; const n=10; var mas : array[1..n] of integer; {элементы = от -10 до 10 } i, max : integer; begin for i:=1 to n do read(mas[i]); max:=-11; for i:=1 to n do if (mas[i] mod 2 0) and (mas[i]>max) then max:=mas[i]; writeln('Максимум среди нечетных = ', max); end.

ОБРАБОТКА МАССИВА Решение Как найти минимальный элемент, являющийся простым числом? В заданном диапазоне простых чисел немного: 2, 3, 5 и 7. Поэтому достаточно реализовать проверку путем сравнения элемента массива с каждым из этих значений (логическая операция ИЛИ). Простое число – натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. program min_prost; const n=30; var mas : array[1..n] of integer; {элементы = от -10 до 10 } i, min : integer; begin for i:=1 to n do read(mas[i]); min:=11; for i:=1 to n do if ((mas[i]=2) or (mas[i]=3) or (mas[i]=5) or (mas[i]=7)) and (mas[i]