Слайд 2ЕГЭ 5
Алгоритмы для формальных исполнителей
![ЕГЭ 5 Алгоритмы для формальных исполнителей](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-1.jpg)
Слайд 3Задача 1. Бит четности
Автомат обрабатывает натуральное число N по следующему алгоритму:
Строится
![Задача 1. Бит четности Автомат обрабатывает натуральное число N по следующему алгоритму:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-2.jpg)
двоичная запись числа N.
Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2.
Предыдущий пункт повторяется для записи с добавленной цифрой.
Результат переводится в десятичную систему и выводится на экран.
Какое наибольшее число, меньшее 50, может появиться на экране в результате работы автомата?
Слайд 6Вывод
N искать проще
Какое наибольшее число, меньшее 50, может появиться на экране в
![Вывод N искать проще Какое наибольшее число, меньшее 50, может появиться на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-5.jpg)
результате работы автомата?
R?max = 49 = 1100012
Что дописали?
1100012
Nmax7= 11002
R = 1100002
48
Слайд 7Задача 2
Автомат обрабатывает трёхзначное натуральное число N по следующему алгоритму.
Из цифр, образующих
![Задача 2 Автомат обрабатывает трёхзначное натуральное число N по следующему алгоритму. Из](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-6.jpg)
десятичную запись N, строятся наибольшее и наименьшее возможные двузначные числа (числа не могут начинаться с нуля).
На экран выводится разность полученных двузначных чисел.
Пример. Дано число N = 351. Алгоритм работает следующим образом.
1. Наибольшее двузначное число из заданных цифр – 53, наименьшее – 13.
2. На экран выводится разность 53 – 13 = 40.
Чему равно наименьшее возможное трёхзначное число N, в результате обработки которого на экране автомата появится число 40?
Слайд 8Рассуждения
Расставим цифры числа в порядке возрастания: a, b, c
Пусть a =
![Рассуждения Расставим цифры числа в порядке возрастания: a, b, c Пусть a](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-7.jpg)
b = 0, c ≠ 0;
МАХ=MIN=10c
MAX-MIN = 0
Пусть a = 0, b ≠ 0 и c ≠ 0;
MAX = 10c + b, MIN = 10b;
MAX – MIN = 10c + b – 10 b = 10 (c-b) + b
среди цифр нет нулей;
MAX = 10c + b, MiN = 10a + b;
MAX – MIN = 10c + b – 10a – b = 10 (c-a)
c - a = 4
Ответ: 115.
Слайд 9Задача 3
Автомат получает на вход натуральное число X. По этому числу строится
![Задача 3 Автомат получает на вход натуральное число X. По этому числу](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-8.jpg)
трёхзначное число Y по следующим правилам.
Первая цифра числа Y (разряд сотен) – остаток от деления X на 2.
Вторая цифра числа Y (разряд десятков) – остаток от деления X на 3.
Третья цифра числа Y (разряд единиц) – остаток от деления X на 5.
Укажите наименьшее двузначное число, при обработке которого автомат выдаёт результат 104.
Слайд 10Интерпретация
X mod 2 = 1
X mod 3 = 0
X mod 5 =
![Интерпретация X mod 2 = 1 X mod 3 = 0 X mod 5 = 4](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-9.jpg)
4
Слайд 11Подбор
X mod 2 = 1
X mod 3 = 0
X mod 5 =
![Подбор X mod 2 = 1 X mod 3 = 0 X mod 5 = 4](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-10.jpg)
4
Слайд 12Исключение 1
X mod 2 = 1
X mod 3 = 0
X mod 5
![Исключение 1 X mod 2 = 1 X mod 3 = 0](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-11.jpg)
= 4
Слайд 13Исключение 2
X mod 2 = 1
X mod 3 = 0
X mod 5
![Исключение 2 X mod 2 = 1 X mod 3 = 0](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-12.jpg)
= 4
Слайд 14Не задача, но еще одно важное замечание
![Не задача, но еще одно важное замечание](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/957325/slide-13.jpg)