Ученики на Учителя.com


Анализ линейного алгоритма на примере задания №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
Скачать материал

Информатика - еще материалы к урокам: