Позиционные системы счисления
В позиционной системе с основанием P цифра в разряде k весит , поэтому число равно сумме цифр, умноженных на степени основания. В десятичную систему переводят по развёрнутой записи, из десятичной в P-ичную — делением на P с остатком. Степени основания пишутся единицей с нулями, а разность степеней — цепочкой старших цифр, и на этом стоит ручное решение задания 14.
Позиционная запись числа
В системе с основанием есть цифр от 0 до . Цифра в разряде (разряды считают справа с нуля) весит .
- Перевод в десятичную систему: , где — цифра в разряде . В Python —
int(s, p). - Перевод из десятичной системы: делите число на с остатком, пока частное не станет 0. Остатки, прочитанные снизу вверх, — цифры записи.
- Число из цифр: . Последняя цифра равна остатку .
- — единица и нулей. при — это цифр и нулей.
- Двоичная, восьмеричная и шестнадцатеричная системы связаны: одна восьмеричная цифра — три двоичных, одна шестнадцатеричная — четыре.
Основание, цифры и развёрнутая запись
Позиционная система счисления — система, в которой значение цифры зависит от её места в записи числа. Основание — число цифр системы. В двоичной системе цифры 0 и 1, в восьмеричной — от 0 до 7. Если , цифры от 10 и больше обозначают латинскими буквами: , , …, , и так далее до . Основание пишут индексом справа внизу: , .
Развёрнутая запись — сумма цифр, умноженных на степени основания. Разряды целой части нумеруют справа налево с нуля, разряды дробной части — с . Цифру в разряде обозначают : . Цифра в каждом разряде меньше основания: записи не бывает.
Пример
Запишите в развёрнутой форме число и найдите его десятичное значение.
- 1.В двенадцатеричной системе цифры от 0 до 11, цифра .
- 2.Разряды справа налево: 5 — разряд 0, — разряд 1, 3 — разряд 2.
- 3..
Ответ:
Перевод из P-ичной системы в десятичную
Чтобы перевести число из системы с основанием в десятичную, вычислите его развёрнутую запись. Каждую цифру умножьте на в степени её разряда и сложите. Для дробной части степени отрицательные: , .
В Python целое число переводит функция int(s, p): она читает строку s как запись в системе с основанием p от 2 до 36. Буквы можно писать большие или маленькие. Программа ниже печатает 419 и 23.
Пример
Переведите число в десятичную систему.
- 1.Целая часть: .
- 2.Дробная часть: .
- 3.Складываем: .
Ответ:
Перевод целого числа из десятичной системы в P-ичную
Разделите число на с остатком. Остаток — последняя цифра записи. Частное снова разделите на , остаток — предпоследняя цифра. Повторяйте, пока частное не станет 0. Остатки, прочитанные снизу вверх, дают запись числа. Каждый остаток меньше , остаток 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.: последняя цифра 2.
- 2.: следующая цифра 1.
- 3.: цифра 1.
- 4.: цифра 1, частное 0, деление закончено.
- 5.Остатки снизу вверх: 1, 1, 1, 2. Проверка: . Программа делает те же шаги и печатает 1112.
Ответ:
Перевод десятичной дроби в P-ичную
Дробную часть числа умножьте на . Целая часть произведения — первая цифра после запятой. Дробную часть произведения снова умножьте на и возьмите следующую цифру. Остановитесь, когда дробная часть станет 0 или когда цифр хватит для нужной точности. Целую часть числа переводят отдельно, делением.
Конечная десятичная дробь в другой системе может стать бесконечной: . Поэтому компьютер хранит такое число приближённо.
Пример
Переведите число в двоичную систему.
- 1.: первая цифра после запятой 0.
- 2.: цифра 1, дальше умножаем дробную часть .
- 3.: цифра 1, дробная часть 0, перевод закончен.
- 4.Проверка: .
Ответ:
Двоичная, восьмеричная и шестнадцатеричная системы
и . Поэтому каждая восьмеричная цифра — это ровно три двоичные цифры (триада), а каждая шестнадцатеричная — ровно четыре (тетрада). Чтобы перевести двоичное число, разбейте его на группы по три или по четыре цифры от запятой: целую часть — справа налево, дробную — слева направо. Неполную группу дополните нулями с краю. Каждую группу замените одной цифрой.
Обратный перевод: каждую восьмеричную цифру замените тремя двоичными, шестнадцатеричную — четырьмя, а нули в начале записи уберите. Между восьмеричной и шестнадцатеричной системами переводят через двоичную.
Пример
Переведите число в восьмеричную и шестнадцатеричную системы.
- 1.Триады справа налево: . Левую группу дополняем нулями: .
- 2.Заменяем триады цифрами: , , , . Получаем .
- 3.Тетрады справа налево: , левая группа .
- 4.Заменяем тетрады цифрами: , , . Получаем .
Ответ: и
Шестнадцатеричные цифры
| Цифра | Значение | Тетрада |
|---|---|---|
| 0 | 0 | 0000 |
| 1 | 1 | 0001 |
| 2 | 2 | 0010 |
| 3 | 3 | 0011 |
| 4 | 4 | 0100 |
| 5 | 5 | 0101 |
| 6 | 6 | 0110 |
| 7 | 7 | 0111 |
| 8 | 8 | 1000 |
| 9 | 9 | 1001 |
| A | 10 | 1010 |
| B | 11 | 1011 |
| C | 12 | 1100 |
| D | 13 | 1101 |
| E | 14 | 1110 |
| F | 15 | 1111 |
Количество цифр в записи числа
Наименьшее число из цифр в системе с основанием — единица и нулей, то есть . Наибольшее — цифр , то есть . Значит, запись числа содержит цифр, если . Нули в начале записи не пишут, поэтому значащие цифры — все цифры от первой ненулевой до последней.
Чтобы найти число цифр, найдите наименьшую степень основания, которая больше : её показатель и есть . В Python длина двоичной записи — len(bin(n)) - 2.
Пример
Сколько цифр в двоичной записи числа 1000?
- 1.Степени двойки рядом с 1000: и .
- 2., значит и .
Ответ:
Последние цифры и делимость на основание
Последняя цифра P-ичной записи числа равна остатку от деления на . Отсюда признак делимости: число делится на , только если его P-ичная запись оканчивается нулём. Так же последние цифр записи — это остаток от деления на , и делится на , если запись оканчивается нулями.
Если справа приписать к записи цифру , число станет равно . Если зачеркнуть последнюю цифру, получится частное n // p. Эти правила нужны для дописывания разрядов в задании 5.
Пример
К двоичной записи числа 13 справа приписали цифры 01. Какое число получилось?
- 1., это число нечётное: последняя цифра 1.
- 2.Приписать две цифры — дважды умножить на 2 и прибавить новые цифры, то есть .
- 3.Проверка: .
Ответ:
Запись степеней основания
в системе с основанием — единица и нулей: . Если , то — цифра и нулей. Сумма таких слагаемых с разными степенями записывается сразу: каждый коэффициент становится цифрой своего разряда, а в остальных разрядах стоят нули.
Если основание выражения не совпадает с основанием системы, сначала приведите все степени к основанию системы. Например, , а нечётная степень тройки в девятеричной системе даёт коэффициент: . Коэффициенты одного разряда сложите. Если коэффициент получился не меньше , выделите из него перенос в следующий разряд.
Пример
Значение выражения записали в девятеричной системе. Сколько значащих нулей в этой записи?
- 1.Приводим к степеням девятки: .
- 2.Слагаемые , и стоят в разных разрядах, коэффициенты меньше 9, переносов нет.
- 3.Запись: . Цифр шесть, из них ненулевых три, поэтому нулей тоже три.
Ответ:
Разность степеней и вычитание небольшого числа
— это цифр : , . Отсюда при — это цифр , за которыми идут нулей: .
Чтобы вычесть из небольшое число , подберите степень , которая больше . Тогда . Первая скобка — цифр и нулей, а вторая скобка меньше и занимает только последние разрядов.
Пример
Значение выражения записали в троичной системе. Сколько цифр 2 в этой записи?
- 1., поэтому .
- 2. — четыре двойки и два нуля: .
- 3., эти цифры встают на место двух нулей: .
- 4.Проверка: .
Ответ:
Выражение из нескольких степеней
Приведите все степени к основанию системы и упорядочьте слагаемые от старшей степени к младшей. Разбейте выражение на пары «плюс большая степень, минус меньшая». Каждая пара даёт цепочку цифр и нули, а последнее небольшое вычитаемое разберите по правилу вычитания небольшого числа. Если пары занимают разные разряды, цифры каждой пары считают отдельно и складывают.
Пример задания
Открытый банк ФИПИ
Значение арифметического выражения 4700 + 4100 - 16100 - 64 записали в системе счисления с основанием 4. Сколько цифр «3» содержится в этой записи?
Подсчёт цифр программой
Целые числа в Python не ограничены по размеру, поэтому выражение со степенями вроде вычисляется точно. Цифры записи получают тем же делением с остатком: n % p — последняя цифра, n //= p её отбрасывает. Цикл идёт, пока число больше нуля, поэтому он перебирает только значащие цифры.
Условие в if меняют под вопрос: n % p == 0 для нулей, n % p > 9 для цифр больше 9, n % p % 2 == 0 для чётных цифр. Программа ниже считает цифры 5 в шестеричной записи числа и печатает 48.
Пример задания
Открытый банк ФИПИ
Значение арифметического выражения
записали в системе счисления с основанием 25. Сколько значащих нулей содержится в этой записи?
Проверьте себя
00