Анализ линейного алгоритма на примере задания №5 ЕГЭ по информатике

Конспект

«Анализ линейного алгоритма на примере задания №5 ЕГЭ по информатике»

Что такое линейный алгоритм?

Линейный алгоритм - это алгоритм, образуемый командами, которые выполняются однократно и именно в той последовательности, в которой записаны.

Универсальный способ решения задания №5.

1)      Читаем в условии, на сколько в новой записи больше разрядов, чем в исходной!

2)      Берем число R, результат больше которого нам нужно обязательно получить с помощью алгоритма!

3)      Переводим число R в двоичную систему счисления и с конца убираем столько цифр R, сколько мы прочитали в первом шаге (в условии).

4)      Получаем какое-то новое значение, назовем его N! Дальше применяем алгоритм из условия, получаем число. Проверяем, больше ли оно числа R. Если нет, то увеличиваем N на единицу и снова применяем алгоритм!

5)      В итоге мы получим число N, к которому можно применить алгоритм и получить число R, которое будет больше данного в условии значения!

Пример типового задания №5.

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

число R следующим образом:

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

2) Затем справа дописываются два разряда: символы 01, если число N четное,

и 10, если нечётное.

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

Решение типового задания №5.

1)      Переведем число 81 в двоичную систему счисления и получим число:  1010001.

2)      Уберем два правых разряда и получим двоичное число 10100.

3)      101002 = 2010. Число N является четным, следовательно, добавим справа к двоичной записи символы 01.

4)      Переведем полученный результат программы в десятичную систему счисления  R = 10100012 = 8110. Данное число не больше числа 81, следовательно, увеличим N на 1. N = 20 + 1 = 2110 = 101012.

5)      Число N - нечетное, следовательно, прибавим к двоичной записи данного числа символы  10 и получим двоичное число - 1010110. Переведем данное число в десятичную систему счисления и получим - 86.

6)      Минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее, чем число 81 - 21.

Ответ: 21

Функции и методы языка Python, используемые для решения задач данного типа:

Алгоритм решение типового задания №5 на Python:

1)      Первым делом создаем массив, в котором будем хранить все значения R.

2)      C помощью цикла перебираем все значения N.

3)      Переводим число N в 2 с/с.

4)      Смотрим с помощью оператора if, является ли число N четным. Если да, то добавляем к числу набор символов ‘01’.

5)      Если нет, то добавляем к числу набор символов ‘10’.

6)       Переводим полученное число в 10 с/с.

7)      Смотрим с помощью оператора if, больше ли 81 полученное число.

8)       Если да, то добавляем данное число в массив всех значений R.

9)      Выводим минимальное и большее 81 значение R на экран

Ответ: 21