Понятная информатика

Позиционные системы счисления, примеры решения задач

к ЕГЭ - 2023, задание 10, часть 1 

(базовый уровень, примерное время решения – 2 минуты). 

Есть вопросы и замечания - пишите!

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

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

 

Заметим также, что 2^N + 2^N = 2 * 2^N = 2^N+1.    Тогда  2^N = 2^N+1 - 2^N, а  -2^N = -2^N+1 + 2^N.

Проверить правильность этих формул легко, достаточно подставить вместо N любые числа. Проверьте их так же в других системах счисления и сделайте выводы!

 

Рассмотрим различные задачи, которые встречаются в данном задании, и способы их решения. Начнем с самых простых задач, которые вряд ли будут на ЕГЭ, но решение которых научит нас  быстро и просто решать самые сложные задачи.

 

Задача 1.  Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 20 оканчивается на 4.

Решение.  Заметим, что в результате перевода числа 23 в систему счисления с основанием N в нем имеется цифра «4», то есть N ≥ 5.

Вспомним, что последняя цифра числа – это первый остаток от деления числа на основание системы счисления, в которой это число записано.

Тогда 4 – это остаток от деления числа 20  на N – основания систем счисления, которые требуется найти.

Так как значность числа, получаемого после перевода в другую систему счисления, не определена, то условие задачи можно записать как  k * N + 4 = 20.  

Значит, N = (20-4) / k.

Тогда при k = 1 получаем  N = 20 - 4 = 16,  и это максимально возможное основание системы. Остается определить все возможные N ≥ 5. которые будут  делителями  числа 16.

Тогда N =  8,16.

Для проверки поделите 20 на N  и сравните остаток с заданным в условии задачи.

Ответ: 8, 16

 

Задача 2.   Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 75 оканчивается на 23. 

Решение.  Заметим, что в результате перевода числа 75 в систему счисления с основанием N в нем имеется цифра «3», то есть N ≥ 4.

Здесь 3 – это остаток от деления числа 75  на N, а 23 -  это остаток от деления числа 75  на N², где  N - основания систем счисления, которые требуется найти.

Будем считать, что запись числа 75 в системе с основанием  состоит из трех цифр (оставим желающим математикам возможность доказать, что при большем количестве разрядов эта формула также верна), причем две младшие (23) нам даны, а одну (обозначим ее через ) нужно найти:

          75 = k * N² + 2 * N + 3

Тогда   k = (72 - 2 * N) / N²,  

 

Здесь есть две неизвестные переменные k и N, но будем учитывать, что это – натуральные числа и выразим k через N. Тогда задача сводится к тому, чтобы найти и отобрать только те из N,  при которых  k – целое число, то есть N² < 72 – 2 * N  и  4 ≤ N ≤  7.

Выпишем все числа, удовлетворяющие условиям, получаем числа: 4 и 36.

Обратите внимание, что последним (наибольшим) числом в таких задачах  всегда будет N,  при котором числитель равен нулю. Тогда  k = 0  и при переводе  исходного числа в систему счисления с основанием N будет двузначным.

Например, в данной задаче:  75 = 2 * N + 3.

Ответ: 4, 36

 

Задача 3. Запись числа 3210 в системе счисления с основанием N оканчивается на 0 и содержит 3 цифры. Чему равно основание этой системы счисления N?

Решение. Для быстрого решения задачи вспомним, что 0 здесь – это остаток от деления числа 32 на N, а  так как длина полученного при переводе числа равна 4, то   N² ≤  32 < N³.

Тогда нам остается найти такое N, которое будет делителем  числа 32 и удовлетворять неравенству, то есть N = 4.

Ответ: 4

 

Задача 4.   Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 26, запись которых в троичной системе счисления оканчивается на 22?

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

Тогда, если искомые числа Х ≤ 26, то и переведенные в троичную систему счисления, эти числа Х₃  будут меньше результата перевода в троичную систему числа  26 = 222₃.

Остается найти числа, которые меньше 222₃ и оканчиваются на 22₃, это будут: 22₃, 122₃ и 222₃. Переведем их в десятичную систему счисления и получаем результат: 

22₃ = 8, 122₃ = 17, 222₃ = 26.

Ответ: 8, 17, 26.

 

Задача 5.  Десятичное число, переведенное в семеричную и в девятеричную систему, в обоих случаях заканчивается на цифру 0. Какое минимальное натуральное число удовлетворяет этому условию?

Решение.   Если при переводе исходного числа в обе системы счисления результат будет оканчиваться на 0, а найти нужно минимальное число, то нам нужно искать наименьшее общее кратное этих чисел, это будет 7 * 9 = 63.

Ответ: 63

 

Задача 6.   В системе счисления с некоторым основанием десятичное число 83 записывается в виде 123. Укажите это основание.

Решение.  Сравнив исходное число и результат перевода  83 = 123_N, получаем, что:

• N – меньше 10 ;
• в результате деления числа 83 на N в остатке получаем 3:
• N² ≤  83 < N³.

Все эти условия выполняются при N = 8.

Ответ: 8

 

Задача 9.  Укажите, сколько всего раз встречается  цифра 3 в записи чисел 13, 14, 15, …, 23 в системе счисления с основанием 4.

Решение.  Чтобы решить эту задачу быстро, без ошибок и дополнительных проверок, предлагаю нарисовать двух строчную таблицу (хоть это займет немного «лишнего» времени, но сэкономим в дальнейшем отсутствием проверок), в которой перечислим все заданные числа в исходной системе счисления. Переведем в четверичную систему счисления первое и последнее из заданных чисел, а остальное запишем в таблицу, и если получилось так, что количество исходных чисел равно количеству результатов (столбцов хватило для ответов и не осталось пустых), то останется только найти и посчитать цифры 3 во второй строке:

Ответ: 6

 

Задача 10.  В саду 100 фруктовых деревьев – 14 яблонь и 42 груши. Найдите основание системы счисления, в которой указаны эти числа.

Решение. Запишем условие задачи «в столбик»:

                    14

                 +

                    42

                  100

И видим, что 4_^N + 2_N = 10_N

Тогда 4+2 = 6 = 10_N   только при N= 6. Для проверки 1 + 4 + 1 = 6 = 106 .

Ответ: 6

 

Задача 11.  Сколько единиц в двоичной записи числа 4²⁰¹⁵ + 2²⁰¹⁵ – 15?

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

                 4²⁰¹⁵ + 2²⁰¹⁵ – 15 = 2⁴⁰³⁰ + 2²⁰¹⁵ – 2⁴ + 2⁰

Вспомним, что число 2^N–2^K  при K < N в двоичной системе записывается как N–K единиц и K нулей:

                                                      2^N – 2^K = 1…1 0…0₂

                                                                     N-K   K

(аналогично для всех оснований систем счисления). 

 

Число 2⁴⁰³⁰дает одну единицу в результате, запомним это.

Тогда 

                                                 2²⁰¹⁵ – 2⁴ = 1…1 0…0₂ 

                                                                   2011  4

а  +2⁰ добавит одну единицу в конце. Итого получаем 2013 единиц.

Ответ: 2013

 

Задача 12.  Сколько единиц в двоичной записи числа 8²³⁴¹ – 4³⁴² + 2⁶²⁰ – 81?

Решение.  8²³⁴¹ – 4³⁴² + 2⁶²⁰ – 81 = 2⁷⁰²³ – 2⁶⁸² + 2⁶²⁰ – 2⁷ +2⁵ + 2⁴ - 2⁰

Выражение 2⁷⁰²³ – 2₆₈₄ дает 6339 единиц и 684 нуля, 2⁶²⁰ –2⁷  дает еще 613  единиц, 2⁵ + 2⁴ - 2⁰  дает еще 5 единиц. Итого получаем 6339 + 613 + 5 = 6957 единиц.

Ответ: 6957

 

Задача 13.(Е.А. Мирончик) Некоторое число X из десятичной системы счисления перевели в системы счисления с основаниями 16 и 8. Часть символов при записи утеряна. Позиции утерянных символов обозначены знаком *:

X = 1*0₁₆ = 56*₈

Определите число X.

Решение.  Переведем оба числа в двоичную систему счисления:

1 * 0₁₆  = 1  * * * *  0  0 0₂

    56*₈ = 1 0 1 1 1 0 * * *₂

Заменяем звездочки известными значениями, получаем  X =101110000₂ = 560₈ = 368

Ответ: 368