Разбор задач на системы счисления
Задачи на системы счисления проверяют не только умение переводить числа, но и понимание разрядной записи, свойств остатков и арифметики в разных основаниях. Ниже собраны универсальные приёмы для задач на перевод, поиск цифр и разрядов, перебор оснований, делимость и вычисления.
1. Основание и разрядная запись
В позиционной системе счисления основание \(q\) показывает, сколько различных цифр используется: от \(0\) до \(q-1\). Значение цифры зависит от её позиции. Начинайте решение с алгоритма перевода в десятичную систему, если число записано не в десятичной системе.
Число \(a_na_{n-1}\ldots a_1a_0\) в системе с основанием \(q\) означает сумму произведений цифр на веса разрядов. Старший разряд имеет вес \(q^n\), единицы — вес \(q^0=1\). Подробный вид записи приведён на странице разрядная запись числа.
Например, \((231)_4=2\cdot4^2+3\cdot4+1=45\). Цифра \(3\) допустима в системе с основанием \(4\), а цифра \(4\) — недопустима. При первом упоминании разряда полезно различать его номер и вес: номер единиц равен \(0\), но вес этого разряда равен \(1\).
В системе с основанием \(q\) каждая цифра удовлетворяет условию \(0\le a_i<q\). Поэтому основание всегда строго больше максимальной цифры, встречающейся в записи.
Для факториальной системы веса разрядов устроены иначе: справа налево они равны \(1!,2!,3!,\ldots\). При необходимости используйте страницы веса факториальных разрядов, алфавит факториальной системы счисления и перевод из факториальной системы.
2. Перевод чисел и выбор способа
Чтобы перевести целую часть числа из системы с основанием \(q\) в десятичную, раскройте скобки по разрядам. Для перевода из десятичной системы применяют последовательное деление на новое основание с записью остатков снизу вверх. Полный алгоритм можно повторить на странице алгоритм перевода из десятичной системы.
Если требуется сравнить несколько записей, удобно перевести их в десятичную систему. Если требуется получить запись одного числа в новой системе, используйте деление с остатком. Если основания связаны степенью двойки, например \(2\), \(4\), \(8\) или \(16\), можно группировать двоичные цифры по \(2\), \(3\) или \(4\).
При переводе делением последний полученный остаток становится первой цифрой результата. Это одна из самых частых причин обратной записи ответа.
Какое равенство верно?
3. Последняя цифра и остатки
Последняя цифра числа в системе с основанием \(q\) совпадает с остатком от деления его значения на \(q\). Поэтому для нахождения последней цифры не всегда нужно полностью переводить число. Если число задано выражением, сначала ищите остаток всего выражения по модулю \(q\).
Например, последняя цифра \(N=7^{100}+3\) в системе счисления с основанием \(5\) определяется остатком: \(7\equiv2\pmod5\), поэтому нужно вычислить \((2^{100}+3)\bmod5\). Степени часто повторяются циклически, и достаточно найти длину цикла.
В системе с основанием \(q\) число делится на \(q\), если его последняя цифра равна нулю. Число делится на \(q^k\), если последние \(k\) цифр образуют число, кратное \(q^k\). Это напрямую следует из разрядной записи: все более старшие слагаемые содержат множитель \(q^k\).
Для двоичной системы последняя цифра сообщает чётность: \(0\) — число чётное, \(1\) — нечётное. В десятичной системе остаток по модулю \(10\) — последняя цифра, а остаток по модулю \(100\) — последние две цифры.
Найдём последнюю цифру числа \(2^{20}+5\) в системе счисления с основанием \(7\). Сначала вычислим остаток по модулю \(7\): \(2^3=8\equiv1\pmod7\). Так как \(20=3\cdot6+2\), имеем \(2^{20}\equiv2^2=4\pmod7\). Тогда \(2^{20}+5\equiv4+5=9\equiv2\pmod7\). Ответ: последняя цифра равна \(2\).
4. Поиск основания, цифры и разряда
Если основание неизвестно, заменяйте его буквой \(q\) и составляйте уравнение по разрядной записи. Например, \((12q)_q\) означает \(1\cdot q+2=q+2\), а не произведение цифры \(12\) на основание. После решения обязательно проверяйте ограничение \(q>2\) и целочисленность основания.
Если неизвестна цифра, обозначайте её переменной, например \(x\), и учитывайте \(0\le x<q\). Если нужно определить разряд числа \(N\), найдите такое \(k\), что \(q^k\le N<q^{k+1}\). Тогда старший разряд имеет номер \(k\), а количество цифр равно \(k+1\).
В системе с основанием \(q\) все числа с \(n\) цифрами лежат в диапазоне от \(q^{n-1}\) до \(q^n-1\). Это помогает быстро определить число цифр и проверить полученный ответ.
В задачах с несколькими основаниями не смешивайте запись и значение: \(101_2\), \(101_3\) и \(101_{10}\) — разные числа. Основание относится ко всей записи и обычно пишется нижним индексом.
5. Арифметика в системах счисления
Складывать и вычитать можно непосредственно в исходной системе, если помнить правило переноса. При сложении разрядная сумма, равная или превышающая основание, оставляет в текущем разряде остаток, а единица переносится в следующий. Для тренировки используйте сложение с переносом.
Здесь \(s\) — сумма цифр с учётом входящего переноса, \(r\) — цифра текущего разряда, \(c\) — перенос в следующий разряд. Умножение и деление столбиком выполняются по тем же принципам, что и в десятичной системе, но таблица умножения ограничена цифрами до \(q-1\).
После вычисления переведите результат в десятичную систему или оцените его диапазон. Например, произведение двух положительных чисел не может быть меньше каждого множителя, если оба множителя больше единицы.
Уравнения в разных системах удобно решать после раскрытия разрядной записи. Страница решение уравнений в системах счисления посвящена этому приёму подробнее. Также полезно помнить значение степени основания в каждом разряде: степень основания в разряде определяется номером разряда, считая справа с нуля.
Не забывайте указывать основание у каждого числа; не читайте остатки при переводе снизу вверх наоборот; не используйте цифру, равную основанию или большую него; не путайте номер разряда с его весом; при сложении не переносите единицу, если сумма меньше основания; после решения уравнения проверяйте допустимость цифр и основания.
6. Универсальный алгоритм решения
- Определите, что требуется найти: значение, цифру, основание, разряд, остаток или результат арифметического действия.
- Запишите основание каждой системы и проверьте допустимость цифр.
- Выберите метод: разрядная запись, деление с остатком, вычисление по модулю, перебор оснований или арифметика столбиком.
- Выполните вычисления без смешения систем счисления.
- Проверьте ответ обратным переводом, диапазоном или подстановкой.
Любое число в позиционной системе — это сумма цифр, умноженных на веса разрядов. Почти все экзаменационные задачи сводятся к правильному использованию этой записи и свойства остатков.
Проверь себя
Главное
- Разрядная запись переводит число из любой позиционной системы в сумму степеней основания.
- При переводе делением остатки читают снизу вверх.
- Последняя цифра в системе с основанием \(q\) равна остатку числа по модулю \(q\).
- Неизвестное основание обозначают \(q\), раскрывают запись и проверяют условие \(q>\max(a_i)\).
- В арифметике перенос выполняется каждый раз, когда разрядная сумма достигает основания.
- Любой ответ нужно проверить обратным переводом, диапазоном или подстановкой.