Продолжаем наш супер-практикум по системам счисления и ломаем все сложности и непонятности! II часть дополнит наш опыт ручными вариантами решения, которые не уступают по простоте Python и докажут, что естественный интеллект ни чуть не хуже искусственного; хотя понятно, что искусcтвенного его вообще по природе не может быть.
В предыдущей I части практикума мы рассмотрели программное решение этого задания по преобразованию четверичных чисел. Возможно такое решение не всем покажется несложным или понятным. Поэтому в качестве альтернативы у нас всегда, надеюсь, остается голова и можно включить свой природный ПК.
Задание 6: ЕГЭ Зад. 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
a) если число N делится на 4, то к этой записи дописываются две последние четверичные цифры;
b) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.
Полученная таким образом запись является четверичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма, получается число R, меньшее 369.
1. Итак, при ручных решениях задач похожего типа всегда начинаем плясать от известных чисел, в данном случае это R<369, а N – максимальное.
2. Теперь представим 369 в 4-ом виде, можно делить в столбик по классическому архаичному методу, а можно использовать мой метод 256 64 16 4 1 ряда.
Собираем число 256*1; 369-256=113; 64*1; 113-64=49; 16*3; 49-48=1.
Получаем 11301. Теперь у нас есть ориентир по R < 11301.
3. N должно быть максимальным, поэтому уберём сначала крайний младший разряд и получим число 1130, что в 10-ичном 4^3+4^2+3*4^1=64+16+12=92
4. Анализируем, согласно алгоритму, кратность 92 четырём. Нам надо найти некратное четырём, так как при кратности добавится две цифры в результат, а это будет больше исходного R, поэтому ищем ближайшее некратное. Берём 91. Остаток 91/4=3. По условию при некратности остаток умножается на 2, переводится в 4-ичное число и прибавляется к результату: 3*2=6; в 4-ичном – 10 – тоже не подход, так как результат будет на один разряд больше, чем исходный R, А нам надо меньше. Поэтому ищем число, которое при делении на 4 даст остаток, который при умножении на 2 будет обноразрядным, т.е. будет равным 1. Такое ближайшее число 89. 89/4 остаток 1*2=2; прибавляем к 89 в 4-ичном и получаем:
5. 89=64+16+2*4+1=1121+2=11212<11301/ N=89 Ответ: 89
Вот такое ручное решение! Вам выбирать, что для вас легче и быстрее во времени.
При небольших значениях R и N ручной вариант проще, но если теория хромает, то доверьтесь Python.
Задание 7: ЕГЭ Зад. 5
Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Удаляется первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.
Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 10 до 1000?
Решение: в этом задании и ручное и программное решения не сложны, но задание нестандартно и может вызвать ряд затруднений, рассмотрим оба решения.
Программное решение: нужно найти количество разных значений, т.е. множество значений, поэтому формируем пустой массив для их хранения (строка 1). Согласно условию дана последовательность чисел от 10 до 1000, поэтому в строке 2 задаём цикл с диапазоном от 10 до 1001 для перебора чисел. В строке 3 выполняем первый и второй шаги алгоритма – преобразование в 2-ичное представление и поскольку функция bin() не указывает незначащие нули в 2-ичной строке, то мы можем создать срез, убрав признак двоичности -0b и 1 – первую единицу. Результат получаем в виде строки ss. В строке 4 программы выполняем 3 и 4 шаги алгоритма: переводим в 10-ичное ss-двоичное число при помощи уже известной нам функции int() и одновременно находим разность полученного 10 –ичного числа с исходным N числом, записывая эту разность в массив a при помощи метода добавления элементов в массив append(). Все особенности этого метода будем подробно изучать в последующих практикумах. Поскольку требуется вывести количество оригинальных значений полученного массива a, то используем тип данных множество set(a) и функцию len() для определения количества этих различных значений R.
Ручное решение: ручное решение тоже несложное, если включить логику и проанализировать алгоритм в условии задания.
· Берём исходное число 10 в 2-ичном это 1010; результат по алгоритму: 10- 2=8.
· Берём следующее число 11 1011; результат 11-3=8;
· При всех последующих значениях до увеличения разрядности будет значение 8; так как старший разряд по условию задания удаляется, а младшие разряды прибавляются настолько, насколько же и удаляются
· Поэтому достаточно посчитать количество разрядов, которые будут изменяться от10 до 1000, чтобы определить количество разных значений результата
· 1000- это грубо 2^9, а 10 - 2^3; т.е. 8, 16, 32, 64, 128, 256, 512; 7 вариантов старших разрядов - 7 вариантов результата!
Вот такое простое решение руками, но и конечно немного головой!
И ещё на десерт задачу на 3-ичную систему
Задание 8: ЕГЭ Зад. 5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
a) к этой записи справа дописывается 1 - остаток от деления числа N на 3
Полученная таким образом запись является троичной записью искомого числа R. Укажите такое максимальное значение R, которое можно получить в результате выполнения алгоритма для максимального числа N, которое не больше минимального десятиного четырёхзначного числа. В ответе запишите число R в 10-ичной системе счисления.
Решение: решим вручную, так как программно будет во времени неэффективно.
1. Начинаем плясать от известного. Известно, что N < min десятичного четырёхзначного, т.е. 1000. Переводим 1000 в 3-чную. Ряд 729 243 81 27 9 3 1. 729*1; Остаток 1000-729=271;243*1; Остаток 271-243=28; 27*1; Остаток 28-27=1. Получаем 1101001.
2. Известно, что в число входит N и остаток от деления N на 3. Убираем крайний один разряд, так как надо найти максимальное исходное N. Получаем троичное 110100 и переводим его в 10-ичное 243+81+9=333.
3. В условии говорится, что остаток при делении числа N на 3 должен быть 1, При 333/3 остаток будет 0, поэтому число 333 не подходит, увеличиваем (так как ищем N максимальное) 333 на 1; получаем 334. В 3-ичном представлении это 110101.
4. Представляем полученное R с учётом прибавления остатка 1 к N и получаем 110101+1=1101011. В десятичной системе это 729+243+27+3+1=1003. Ответ: 1003.
Надеюсь, что практикум покорил 5 задание ЕГЭ и вы одолеете его на ЕГЭ легко!
Не забываем об энергообмене: подписки, лайки, комментарии, донаты помогут нашему каналу быть и вдохновят на новые классные уроки для вас!
СПАСИБО ВСЕМ ЗА ПОМОЩЬ И УЧАСТИЕ В СУДЬБЕ КАНАЛА!
До новых интересных встреч в школе Дзен!