Информатика. Новый полный справочник для подготовки к ЕГЭ. Богомолова О.Б.

Справочник поможет школьнику освежить в памяти основной теоретический материал по всему курсу информатики за 7-11 классы, ознакомиться с принципами решения типовых задач ЕГЭ, предлагавшихся в последние несколько лет, и подготовиться к экзамену. Для школьников, учителей информатики и методистов.
Информатика относится к 12 предметам, сдача ЕГЭ по которым производится учащимися на добровольной основе. Однако перечень вузов и ссузов, требующих наличия свидетельства об успешной сдаче ЕГЭ по информатике для поступления на основные специальности, постоянно растет. Возрастает год от года и сложность заданий, предлагаемых на ЕГЭ по информатике.

Информатика. Новый полный справочник для подготовки к ЕГЭ. Богомолова О.Б.

Информатика. Новый полный справочник для подготовки к ЕГЭ. Богомолова О.Б.

Для всех четырёх уравнений структура и заполнение таблицы возможных значений четырёх используемых в каждом уравнении переменных одна и та же. Смысл решения задачи проявляется во взаимосвязи между этими таблицами, отражающими взаимосвязь между уравнениями.
Следует обратить внимание, что переменные х7 и х8 используются в обоих рассмотренных уравнениях. Поэтому для каждого варианта (набора значений) переменных х7 и х8, приведённого в таблице 2.2, нужно определить количество наборов переменных х7, х8, х10, имеющихся в таблице 1.2.
Раздел 5. Элементы теории алгоритмов
Анализ работы автомата, формирующего число по заданным правилам
О Конспект_
Автомат (греч. automates — самодействующий) — самостоятельно действующее устройство (или совокупность устройств), выполняющее по заданной программе без непосредственного участия человека процессы получения, преобразования, передачи и использования энергии, материала и информации1.
Исполнитель — субъект (человек, животное) или устройство, способное выполнить действия, предписываемые алгоритмом. При этом указанные действия выполняются формально. Исполнитель не знает о цели алгоритма, он лишь выполняет все полученные команды.
Каждый исполнитель характеризуется следующими параметрами:
— среда — условия, в которых функционирует исполнитель (например, исполнитель Черепаха имеет определённую систему координат, исполнитель Робот перемещается по клетчатому полю и т.д.);
— система команд — каждый исполнитель может выполнять команды только из некоторого строго заданного набора, где каждая команда определяет соответствующее элементарное действие.
1 Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.
Разбор типовых задач
Задача 1. Автомат получает на вход два трёхзначных числа. По этим числам строится новое число по следующим правилам:
1. Вычисляются три числа — сумма старших разрядов заданных трёхзначных чисел, сумма средних разрядов этих чисел, сумма младших разрядов.
2. Полученные три числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходные трёхзначные числа: 835, 196. Поразрядные суммы: 9, 12, 11. Результат: 12119.
Определите, какое из следующих чисел может быть результатом работы автомата.
Складывая восьмеричные цифры, которые могут меняться от 0 до 7, оцениваются возможные значения этих сумм. Тогда, согласно правилам восьмеричной арифметики, сумма двух таких цифр может меняться от 0 до 78 + 78 = 168.
Теперь просматриваются предлагаемые варианты ответов.
1. Число 119. Можно представить его как 11 и 9 или как 1 и 19. Однако ни один из этих вариантов записи нам не годится: в первом случае восьмеричная запись суммы не может содержать цифры больше 7, а во втором число 19 не может быть суммой двух восьмеричных цифр.
2. Число 1213. Его можно представить как 12 и 13. Оба эти числа могут быть суммами восьмеричных цифр (так как удовлетворяют допустимому диапазону значений таких сумм). Однако они записаны по возрастанию (а не по убыванию, как требуется в условии задачи). Поэтому данное число не может быть решением.
3. Число 1411. Его можно представить как 14 и 11. Обе эти составляющие могут быть значениями сумм восьмеричных цифр, записаны они по убыванию. Значит, это число может быть решением данной задачи.
4. Число 1715. Может быть представлено как 17 и 15. Поскольку его первая составляющая (17) превышает максимально возможное значение суммы, данное число не может быть решением задачи.
Следовательно, единственный вариант ответа, который может быть результатом работы описанного в задаче автомата, — это число 1411.
Ответ: число 1411 (вариант ответа №3).
Задача 3. Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное число: 6531. Суммы: 6 + 5=11, 3+1 = 4. Результат: 411.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 1113.
Решение
Подобные задачи уже были рассмотрены выше. Но раньше нужно было выбрать подходящие числа из приведённых вариантов ответа, а теперь, наоборот, искать такое число.
1) Числа (по умолчанию) десятичные. Значит, суммы цифр могут быть в диапазоне от 1 (1+0) до 18(9+9).
2) Автомат выдал число 1113. Значит, оно состоит из двух значений сумм, записанных по возрастанию: 11 и 13.
3) Число 11 может быть суммой цифр: 2+9, 3+8, 4+7 или 5+6. Число 13 может быть суммой цифр: 4+9, 5+8, 6+7. Значит, пары цифр в исходном числе могут быть такими: одна пара — 29, 92, 38, 83, 47, 74, 56, 65 и другая пара — 49, 94, 58, 85, 67, 76 (ведь соответствующие цифры могут меняться местами в соответствующих суммах).
4) Наибольшим является число, в которое входят наибольшие цифры, причём они по возможности располагаются слева направо по убыванию (поскольку чем старше разряд, тем больше «вес» цифры). Тогда из доступных нам «для конструирования» наборов пар цифр выберем две наибольшие (по одной из каждого набора): 92 и 94 и запишем их по убыванию: 9492.
Ответ: 9492.
Задача 4. Автомат получает на вход трёхзначное число. По этому числу формируется новое число по следующим правилам.
1. Складываются первая и вторая, а затем — вторая и третья цифры исходного числа.
2. Полученные два числа записываются друг за другом подряд в порядке возрастания.
Пример. Исходное число: 176. Полученные числа: 1 + 7 = 8, 7 + 6 = 13. Результат: 813.
Найдите наибольшее исходное число, для которого автомат выдаст результат 815.
Решение
Сначала определим, как можно «разрезать» результирующее число на два, вычисленных автоматом.
Вспомним, что сумма двух десятичных цифр (которые могут быть равны от 0 до 9) может равняться от О (0+0) до 18 (9+9).
Если пытаться разделить число 815 как 81 и 5, то первое из этих чисел не соответствует этому возможному диапазону значений сумм цифр (да к тому же тогда числа записаны не по возрастанию). Поэтому остается только один вариант: число 815 как 8 и 15.
А теперь — самое главное. По условию, одна сумма — это сумма первой и второй цифры исходного числа, а вторая — это сумма второй и третьей цифры. Вторая цифра, таким образом, должна повторяться в обеих суммах.
Ищем такие две суммы в обеих «подборках» (для числа 8 и для числа 15).
Система команд исполнителя — совокупность команд, которые он способен выполнять.
Алгоритм — запись в той или иной форме (словесной, графической, на языке программирования) последовательности команд для исполнителя. Команды алгоритма должны соответствовать системе команд исполнителя.
Исполнитель РОБОТ — перемещается по клеткам лабиринта.
• Когда начинается очередной проход цикла, проверяется наличие стенки снизу. Если её нет, то выполняется перемещение на 1 клетку вниз. Если же стенка снизу есть, то выполняется перемещение на 1 клетку вправо, причём без проверки наличия стенки справа. Следовательно, все клетки, в которых есть стенки снизу и есть стенки справа, можно было бы сразу пометить как непригодные (начав движение из них, РОБОТ разобьётся). Но это не требуется: ведь такое условие записано в цикле ПОКА, который контролирует каждый отдельный шаг РОБОТа. (Вот если бы в цикле ПОКА было записано два или больше таких оператора ЕСЛИ, то для второго и т.д. такого оператора пришлось бы это исключение клеток сделать.)
• После выполнения одного такого хода проход цикла завершается, и вновь выполняется проверка его условия. Нетрудно понять, что в этом случае движение РОБОТа будет следующим: «идти вниз, пока это возможно (до стенки снизу), а наткнувшись на стенку снизу — пытаться уходить вправо, отыскивая проход вниз в этой стенке».
Именно так мы и будем пытаться «трассировать» движение РОБОТа, «честно» выполняя предложенную программу. Увидев же, куда в итоге придёт РОБОТ, помечаем все пройденные клетки штриховкой (если попадаем в «ловушку»), или закрашиваем (если доходим до клетки F6). Сама же клетка F6 нам тоже подходит: если РОБОТ изначально находится в ней, то он просто никуда не пойдёт и сразу же выполнит условие задачи.
Первоначально переменной-счётчику (в данном примере — переменной г) присваивается начальное значение гн и выполняется тело цикла. После выполнения тела цикла значение счётчика увеличивается на заданную величину шага Ai и выполняется проверка: не превысило ли значение счётчика заданное конечное значение гк. Если не превысило, то вновь выполняется тело цикла. Иначе происходит выход из цикла.
4. Подпрограмма — поименованный блок команд выполняется после их вызова из любого места основной программы. При этом одна и та же подпрограмма может быть вызвана из основной программы любое количество раз и ей каждый раз могут передаваться свои значения переменных (параметров).

[свернуть]

Похожие страницы

Предложения интернет-магазинов

Добавить комментарий

Ваш адрес email не будет опубликован.