Читать книгу КНИГА-ТРЕНАЖЕР: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс - Евгений Леонидович Сидоркин - Страница 7

Алгоритм – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.

Алгоритм можно задать одним из следующих способов:

• словесное описание последовательности действий на

естественном языке;

• графическое изображение в виде блок-схемы;

• запись при помощи псевдокода (алгоритмического

языка);

• запись на языке программирования.

В этом типе задач рассматривается в основном словесное описание алгоритмов на естественном языке, а потому никаких специальных знаний для решения задачи не требуется. В данных типах задач используются разные исполнители – от чертежника, черепашки до автомата. Рассмотрим основные типы задач, которые здесь могут быть использованы.

Пример 5.1

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:

1. Строится двоичная запись числа N.

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

4. Результат переводится в десятичную систему.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1101.

2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.

3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.

4. Результат работы алгоритма R = 54.

При каком наименьшем числе N в результате работы алгоритма получится R> 170? В ответе запишите это число в десятичной системе счисления.

Решение: Рассмотрим первое попавшееся число, которое больше 170. 171=10101011. У этого числа отделим последние два разряда 171= 101010 | 11 не походит, т.к., выполняя второе правило, алгоритм сложит все единицы, которые стоят слева от вертикальной линии 1+1+1=3, а затем 3 разделим на 2 без остатка и получим 1 и запишем эту единица справа от числа 101010 1. Затем снова применим второе правило к получившемуся числу 101010 | 1. И получим уже новое число 101010 | 10. Получившееся число 10101010=170 по условию задачи должно быть равно 171. Понятно, что 171 не равно 170, поэтому число 171 не подходит. Берем число 172=10101100. Проверяем его на второе правило 2 раза и видим, что число 172 подходит. Осталось только число 10101100 без двух правых нулей перевести в десятичную систему счисления. Получаем 101011=43.

Ответ: 43.

Решение задачи cпособом программирования на языке Python:

Ответ: 43.

Пример 5.2

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются разряды по следующему правилу:

если два последних разряда одинаковые, дописывается 0, иначе дописывается 1.

3) К полученной записи дописывается еще один бит по правилу в пункте 2.

Полученная таким образом запись является двоичной записью искомого числа R.

Укажите минимальное число N, при вводе которого получится значение R больше, чем 61.

В ответе полученное число запишите в десятичной системе.

Решение:

Узнаем, какое число N может быть, чтобы в результате получилось 61.

61 = 111101 ₂

Убираем два младших разряда и исполняем алгоритм.

15=1111 ₂ -> (если два последних разряда одинаковые, то применяем первое правило) -> 11110₂ -> (два последних разряда разные) -> 111101 ₂ = 61.

Следовательно, из числа N = 15 ₁₀ получается R = 61_10. Значит, для того чтобы получить число большее 61, необходимо взять следующее N = 16.

Второй способ решения этой задачи заключается в том, что, как и в первой задаче, мы перебираем по порядку все числа большие 61. Числа 62, 63 под условие алгоритма не подходят, т.к. два последних разряда не соответствуют двум алгоритмам из условия, т.е., например, 62= 111110₂, где, откидывая 2 последних разряда, получаем число 11111_2, и из данного мы не можем получить число 111110₂, применив 2 алгоритма из условия. 64=1000000₂ под условие алгоритма походит, отбрасываем два правых разряда по условию задачи и получаем 10000₂=16.

Ответ: 16.

Пример 5.3

Автомат получает на вход четырехзначное число. По этому числу строится новое число по следующим правилам.

1. Умножаются первая и вторая, а также третья и четвертая цифры исходного числа.

2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 5431. Произведения: 5 * 4 = 20; 3 * 1 = 3. Результат: 320. Укажите максимальное число, в результате обработки которого автомат выдаст число 1216.

Решение:

Рассмотрим число 1216. Так как это два произведения двух одноразрядных чисел, имеем два числа 12 и 16.

12 = 2*6 = 3*4

16 = 2*8

Максимально возможная цифра в найденных произведениях – 8. Т.к. необходимо получить максимальное число по условию задачи, значит, максимальное искомое число начинается на 82. Для получения 12 используется максимальное число – 6. Следовательно, оставшиеся два разряда 62.

Ответ: 8262.

Пример 5.4

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, —3) переместит Чертёжника в точку (6, —1).

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

КОНЕЦ

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ… РАЗ»?

Решение:

Будем считать, что Чертёжник находится в начале координат. После выполнения команды сместиться на (—1, 4) Чертёжник окажется в точке с координатами (—1, 4). После выполнения цикла Чертёжник переместится, по оси икс Чертёжник сместится на -1+n (-1+x) -23 и по игреку на 4+n (-2+y) -12, где n, x, y – неизвестные. В результате последнего перемещения Чертёжник должен переместиться в начало координат, то есть:

– 1+n (-1+x) -23=0 и 4+n (-2+y) -12=0

В первом и втором уравнении перенесем цифры в правую часть и получим 1+23=24 и 12—8=8. Остается только найти наибольший общий делитель чисел 24 и 8. Это число 8.

Ответ: 8.

Пример 5.4

Исполнитель Робот существует в лабиринте – поле, представленном в виде квадрата 6х6. Робот имеет две команды: влево и вниз, вверх, вниз, которые перемещают его на клетку влево или вниз соответственно. При попытке выхода за границы лабиринта или столкновения со стеной Робот разрушается.

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и закончит работу в клетке начала движения?

НАЧАЛО

ПОКА <снизу свободно>

вниз

КОНЕЦ ПОКА

ПОКА <слева свободно>

влево

КОНЕЦ ПОКА

ПОКА <сверху свободно>

вверх

КОНЕЦ ПОКА

ПОКА <справа свободно>

вправо

КОНЕЦ ПОКА

КОНЕЦ

Решение:

1) Заметим, что в общем случае Робот идет сначала до стены вниз, затем влево, потом вверх и заканчивает маршрут движением вверх, до стены.

Один из главных приёмов в решении этой задачи – проверять клетки группами, а не по одной.

Проверим почти все клетки Робота на предмет того, подходит ли алгоритм:

– A6 – маршрут вниз-вверх – подходит;

– F6 – маршрут влево-вправо – подходит;

– D5 – маршрут вниз-влево, вверх, вправо – подходит;

– E5 – маршрут вниз-влево, вверх, вправо (остановка в D5) – не подходит;

– B4 – маршрут вниз-вверх-вправо (остановка в D4) – не подходит;

– C4 – не двигается, стоит на одном месте – подходит;

– C2 – не двигается, стоит на одном месте – подходит;

– F5 – маршрут вниз-вверх – подходит;

– F4 – вниз-вверх (остановка F5) – не подходит;

– F3 – вниз-вверх (остановка F5) – не подходит;

– F2 – вниз-вверх (остановка F5) – не подходит;

– F1 – вверх (остановка F5) – не подходит;

– A2 – вверх (остановка в А6) – не подходит;

– A1 – не двигается – подходит;

– E1 – влево-вверх-вправо (остановка в D4) – не подходит.

Задача, конечно, нудная, т.к. проверять нужно все клетки, в которых вы сомневаетесь. Понятно, что клетки пустые, где нет стенок, в них Робот начать и остановиться не сможет, поэтому эти клетки можно не проверять. Иногда такие задачи дают на экзамене, и лучше вычеркивать клетки в приложении «Ножницы». Здесь нужна высокая степень концентрации.

Ответ: 7.

Задачи для самостоятельного решения

Задача 5.5

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если N нечётное, справа дописывается сначала единица, а затем ноль.

Например, двоичная запись 100 числа 4 будет преобразована в 10001₂, а двоичная запись 111 числа 7 будет преобразована в 11110₂.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R – результата работы данного алгоритма.

Укажите минимальное число R, которое больше 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Задача 5.6

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, —3) переместит Чертёжника в точку (6, —1).

Цикл

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ… РАЗ»?

Задача 5.7

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.

Команды-приказы: вверх, вниз, влево, вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: