Задание 5
тема 2 из 3

Позиционные системы счисления

В позиционной системе с основанием P цифра в разряде k весит PkP^k, поэтому число равно сумме цифр, умноженных на степени основания. В десятичную систему переводят по развёрнутой записи, из десятичной в P-ичную — делением на P с остатком. Степени основания пишутся единицей с нулями, а разность степеней — цепочкой старших цифр, и на этом стоит ручное решение задания 14.

Основа для заданий81315Главная тема в задании14Реже в задании5На карте навыков

Позиционная запись числа

В системе с основанием PP есть PP цифр от 0 до P−1P - 1. Цифра в разряде kk (разряды считают справа с нуля) весит PkP^k.

  • Перевод в десятичную систему: anan−1…a1a0P=an⋅Pn+…+a1⋅P+a0a_n a_{n-1} \ldots a_1 a_0 {}_P = a_n \cdot P^n + \ldots + a_1 \cdot P + a_0, где aka_k — цифра в разряде kk. В Python — int(s, p).
  • Перевод из десятичной системы: делите число на PP с остатком, пока частное не станет 0. Остатки, прочитанные снизу вверх, — цифры записи.
  • Число из kk цифр: Pk−1≤N<PkP^{k-1} \le N < P^k. Последняя цифра равна остатку N mod PN \bmod P.
  • PkP^k — единица и kk нулей. Pk−PmP^k - P^m при k>mk > m — это k−mk - m цифр P−1P - 1 и mm нулей.
  • Двоичная, восьмеричная и шестнадцатеричная системы связаны: одна восьмеричная цифра — три двоичных, одна шестнадцатеричная — четыре.

Основание, цифры и развёрнутая запись

Позиционная система счисления — система, в которой значение цифры зависит от её места в записи числа. Основание PP — число цифр системы. В двоичной системе цифры 0 и 1, в восьмеричной — от 0 до 7. Если P>10P > 10, цифры от 10 и больше обозначают латинскими буквами: A=10\mathrm{A} = 10, B=11\mathrm{B} = 11, …, F=15\mathrm{F} = 15, и так далее до Z=35\mathrm{Z} = 35. Основание пишут индексом справа внизу: 101121011_2, 1A316\mathrm{1A3}_{16}.

Развёрнутая запись — сумма цифр, умноженных на степени основания. Разряды целой части нумеруют справа налево с нуля, разряды дробной части — с −1-1. Цифру в разряде kk обозначают aka_k: a1a0,a−1a−2 P=a1⋅P1+a0⋅P0+a−1⋅P−1+a−2⋅P−2a_1 a_0{,}a_{-1} a_{-2}\,{}_P = a_1 \cdot P^1 + a_0 \cdot P^0 + a_{-1} \cdot P^{-1} + a_{-2} \cdot P^{-2}. Цифра в каждом разряде меньше основания: записи 28828_8 не бывает.

Пример

Запишите в развёрнутой форме число 3B512\mathrm{3B5}_{12} и найдите его десятичное значение.

  1. 1.В двенадцатеричной системе цифры от 0 до 11, цифра B=11\mathrm{B} = 11.
  2. 2.Разряды справа налево: 5 — разряд 0, B\mathrm{B} — разряд 1, 3 — разряд 2.
  3. 3.3B512=3⋅122+11⋅121+5⋅120=432+132+5=569\mathrm{3B5}_{12} = 3 \cdot 12^2 + 11 \cdot 12^1 + 5 \cdot 12^0 = 432 + 132 + 5 = 569.

Ответ: 569569

Перевод из P-ичной системы в десятичную

Чтобы перевести число из системы с основанием PP в десятичную, вычислите его развёрнутую запись. Каждую цифру умножьте на PP в степени её разряда и сложите. Для дробной части степени отрицательные: P−1=1PP^{-1} = \dfrac{1}{P}, P−2=1P2P^{-2} = \dfrac{1}{P^2}.

В Python целое число переводит функция int(s, p): она читает строку s как запись в системе с основанием p от 2 до 36. Буквы можно писать большие или маленькие. Программа ниже печатает 419 и 23.

Пример

Переведите число 101,112101{,}11_2 в десятичную систему.

  1. 1.Целая часть: 1012=1⋅22+0⋅21+1⋅20=4+0+1=5101_2 = 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 4 + 0 + 1 = 5.
  2. 2.Дробная часть: 0,112=1⋅2−1+1⋅2−2=0,5+0,25=0,750{,}11_2 = 1 \cdot 2^{-1} + 1 \cdot 2^{-2} = 0{,}5 + 0{,}25 = 0{,}75.
  3. 3.Складываем: 5+0,75=5,755 + 0{,}75 = 5{,}75.

Ответ: 5,755{,}75

Перевод целого числа из десятичной системы в P-ичную

Разделите число на PP с остатком. Остаток — последняя цифра записи. Частное снова разделите на PP, остаток — предпоследняя цифра. Повторяйте, пока частное не станет 0. Остатки, прочитанные снизу вверх, дают запись числа. Каждый остаток меньше PP, остаток 10 и больше записывают буквой.

В Python остаток — n % p, частное — n // p. Для систем 2, 8 и 16 есть готовые функции: bin(23) даёт строку '0b10111', oct(23) — '0o27', hex(419) — '0x1a3'. Первые два символа — приставка, её отрезают: bin(n)[2:]. То же без приставки даёт format(n, 'b').

Пример

Переведите число 157 в пятеричную систему.

  1. 1.157=31⋅5+2157 = 31 \cdot 5 + 2: последняя цифра 2.
  2. 2.31=6⋅5+131 = 6 \cdot 5 + 1: следующая цифра 1.
  3. 3.6=1⋅5+16 = 1 \cdot 5 + 1: цифра 1.
  4. 4.1=0⋅5+11 = 0 \cdot 5 + 1: цифра 1, частное 0, деление закончено.
  5. 5.Остатки снизу вверх: 1, 1, 1, 2. Проверка: 1⋅125+1⋅25+1⋅5+2=1571 \cdot 125 + 1 \cdot 25 + 1 \cdot 5 + 2 = 157. Программа делает те же шаги и печатает 1112.

Ответ: 111251112_5

Перевод десятичной дроби в P-ичную

Дробную часть числа умножьте на PP. Целая часть произведения — первая цифра после запятой. Дробную часть произведения снова умножьте на PP и возьмите следующую цифру. Остановитесь, когда дробная часть станет 0 или когда цифр хватит для нужной точности. Целую часть числа переводят отдельно, делением.

Конечная десятичная дробь в другой системе может стать бесконечной: 0,1=0,0001100110011…20{,}1 = 0{,}0001100110011\ldots_2. Поэтому компьютер хранит такое число приближённо.

Пример

Переведите число 0,3750{,}375 в двоичную систему.

  1. 1.0,375⋅2=0,750{,}375 \cdot 2 = 0{,}75: первая цифра после запятой 0.
  2. 2.0,75⋅2=1,50{,}75 \cdot 2 = 1{,}5: цифра 1, дальше умножаем дробную часть 0,50{,}5.
  3. 3.0,5⋅2=1,00{,}5 \cdot 2 = 1{,}0: цифра 1, дробная часть 0, перевод закончен.
  4. 4.Проверка: 0,0112=0⋅2−1+1⋅2−2+1⋅2−3=0,25+0,125=0,3750{,}011_2 = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} = 0{,}25 + 0{,}125 = 0{,}375.

Ответ: 0,01120{,}011_2

Двоичная, восьмеричная и шестнадцатеричная системы

8=238 = 2^3 и 16=2416 = 2^4. Поэтому каждая восьмеричная цифра — это ровно три двоичные цифры (триада), а каждая шестнадцатеричная — ровно четыре (тетрада). Чтобы перевести двоичное число, разбейте его на группы по три или по четыре цифры от запятой: целую часть — справа налево, дробную — слева направо. Неполную группу дополните нулями с краю. Каждую группу замените одной цифрой.

Обратный перевод: каждую восьмеричную цифру замените тремя двоичными, шестнадцатеричную — четырьмя, а нули в начале записи уберите. Между восьмеричной и шестнадцатеричной системами переводят через двоичную.

Пример

Переведите число 110101110121101011101_2 в восьмеричную и шестнадцатеричную системы.

  1. 1.Триады справа налево: 1 101 011 1011\ 101\ 011\ 101. Левую группу дополняем нулями: 001001.
  2. 2.Заменяем триады цифрами: 001=1001 = 1, 101=5101 = 5, 011=3011 = 3, 101=5101 = 5. Получаем 153581535_8.
  3. 3.Тетрады справа налево: 11 0101 110111\ 0101\ 1101, левая группа 00110011.
  4. 4.Заменяем тетрады цифрами: 0011=30011 = 3, 0101=50101 = 5, 1101=13=D1101 = 13 = \mathrm{D}. Получаем 35D16\mathrm{35D}_{16}.

Ответ: 153581535_8 и 35D16\mathrm{35D}_{16}

Шестнадцатеричные цифры

ЦифраЗначениеТетрада
000000
110001
220010
330011
440100
550101
660110
770111
881000
991001
A101010
B111011
C121100
D131101
E141110
F151111

Количество цифр в записи числа

Наименьшее число из kk цифр в системе с основанием PP — единица и k−1k - 1 нулей, то есть Pk−1P^{k-1}. Наибольшее — kk цифр P−1P - 1, то есть Pk−1P^k - 1. Значит, запись числа NN содержит kk цифр, если Pk−1≤N<PkP^{k-1} \le N < P^k. Нули в начале записи не пишут, поэтому значащие цифры — все цифры от первой ненулевой до последней.

Чтобы найти число цифр, найдите наименьшую степень основания, которая больше NN: её показатель и есть kk. В Python длина двоичной записи — len(bin(n)) - 2.

Пример

Сколько цифр в двоичной записи числа 1000?

  1. 1.Степени двойки рядом с 1000: 29=5122^9 = 512 и 210=10242^{10} = 1024.
  2. 2.29≤1000<2102^9 \le 1000 < 2^{10}, значит k−1=9k - 1 = 9 и k=10k = 10.

Ответ: 1010

Последние цифры и делимость на основание

Последняя цифра P-ичной записи числа NN равна остатку от деления NN на PP. Отсюда признак делимости: число делится на PP, только если его P-ичная запись оканчивается нулём. Так же последние kk цифр записи — это остаток от деления NN на PkP^k, и NN делится на PkP^k, если запись оканчивается kk нулями.

Если справа приписать к записи цифру dd, число станет равно N⋅P+dN \cdot P + d. Если зачеркнуть последнюю цифру, получится частное n // p. Эти правила нужны для дописывания разрядов в задании 5.

Пример

К двоичной записи числа 13 справа приписали цифры 01. Какое число получилось?

  1. 1.13=1101213 = 1101_2, это число нечётное: последняя цифра 1.
  2. 2.Приписать две цифры — дважды умножить на 2 и прибавить новые цифры, то есть 13⋅22+012=52+1=5313 \cdot 2^2 + 01_2 = 52 + 1 = 53.
  3. 3.Проверка: 1101012=32+16+4+1=53110101_2 = 32 + 16 + 4 + 1 = 53.

Ответ: 5353

Запись степеней основания

PkP^k в системе с основанием PP — единица и kk нулей: 25=10000022^5 = 100000_2. Если a<Pa < P, то a⋅Pka \cdot P^k — цифра aa и kk нулей. Сумма таких слагаемых с разными степенями записывается сразу: каждый коэффициент становится цифрой своего разряда, а в остальных разрядах стоят нули.

Если основание выражения не совпадает с основанием системы, сначала приведите все степени к основанию системы. Например, 16100=420016^{100} = 4^{200}, а нечётная степень тройки в девятеричной системе даёт коэффициент: 37=3⋅36=3⋅933^7 = 3 \cdot 3^6 = 3 \cdot 9^3. Коэффициенты одного разряда сложите. Если коэффициент получился не меньше PP, выделите из него перенос в следующий разряд.

Пример

Значение выражения 2⋅95+37+52 \cdot 9^5 + 3^7 + 5 записали в девятеричной системе. Сколько значащих нулей в этой записи?

  1. 1.Приводим к степеням девятки: 37=3⋅933^7 = 3 \cdot 9^3.
  2. 2.Слагаемые 2⋅952 \cdot 9^5, 3⋅933 \cdot 9^3 и 5⋅905 \cdot 9^0 стоят в разных разрядах, коэффициенты меньше 9, переносов нет.
  3. 3.Запись: 2030059203005_9. Цифр шесть, из них ненулевых три, поэтому нулей тоже три.

Ответ: 33

Разность степеней и вычитание небольшого числа

Pk−1P^k - 1 — это kk цифр P−1P - 1: 103−1=99910^3 - 1 = 999, 24−1=111122^4 - 1 = 1111_2. Отсюда Pk−PmP^k - P^m при k>mk > m — это k−mk - m цифр P−1P - 1, за которыми идут mm нулей: 75−72=6660077^5 - 7^2 = 66600_7.

Чтобы вычесть из PkP^k небольшое число cc, подберите степень PmP^m, которая больше cc. Тогда Pk−c=(Pk−Pm)+(Pm−c)P^k - c = (P^k - P^m) + (P^m - c). Первая скобка — k−mk - m цифр P−1P - 1 и mm нулей, а вторая скобка меньше PmP^m и занимает только последние mm разрядов.

Пример

Значение выражения 36−53^6 - 5 записали в троичной системе. Сколько цифр 2 в этой записи?

  1. 1.5<32=95 < 3^2 = 9, поэтому 36−5=(36−32)+(9−5)3^6 - 5 = (3^6 - 3^2) + (9 - 5).
  2. 2.36−323^6 - 3^2 — четыре двойки и два нуля: 2222003222200_3.
  3. 3.9−5=4=1139 - 5 = 4 = 11_3, эти цифры встают на место двух нулей: 2222113222211_3.
  4. 4.Проверка: 2⋅243+2⋅81+2⋅27+2⋅9+1⋅3+1=724=36−52 \cdot 243 + 2 \cdot 81 + 2 \cdot 27 + 2 \cdot 9 + 1 \cdot 3 + 1 = 724 = 3^6 - 5.

Ответ: 44

Выражение из нескольких степеней

Приведите все степени к основанию системы и упорядочьте слагаемые от старшей степени к младшей. Разбейте выражение на пары «плюс большая степень, минус меньшая». Каждая пара даёт цепочку цифр P−1P - 1 и нули, а последнее небольшое вычитаемое разберите по правилу вычитания небольшого числа. Если пары занимают разные разряды, цифры каждой пары считают отдельно и складывают.

Пример задания

Открытый банк ФИПИ

Значение арифметического выражения 4700 + 4100 - 16100 - 64 записали в системе счисления с основанием 4. Сколько цифр «3» содержится в этой записи?

Подсчёт цифр программой

Целые числа в Python не ограничены по размеру, поэтому выражение со степенями вроде 61006^{100} вычисляется точно. Цифры записи получают тем же делением с остатком: n % p — последняя цифра, n //= p её отбрасывает. Цикл идёт, пока число больше нуля, поэтому он перебирает только значащие цифры.

Условие в if меняют под вопрос: n % p == 0 для нулей, n % p > 9 для цифр больше 9, n % p % 2 == 0 для чётных цифр. Программа ниже считает цифры 5 в шестеричной записи числа 6100+650−366^{100} + 6^{50} - 36 и печатает 48.

Пример задания

Открытый банк ФИПИ

Значение арифметического выражения
3⋅31258+2⋅6257–4⋅6256+3⋅1255–2⋅254–20243 \cdot 3125^{8} + 2 \cdot 625^{7} – 4 \cdot 625^{6} + 3 \cdot 125^{5} – 2 \cdot 25^{4} – 2024
записали в системе счисления с основанием 25. Сколько значащих нулей содержится в этой записи?

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать