На циферблате часов написано IX, в начале главы книги — XIV, а в памяти компьютера — 1001. Всё это числа, просто записанные на разных «языках». И запись 101 не всегда означает «сто один»: в десятичной системе это сто один, а в двоичной — 5. Чтобы узнать значение числа, нужно знать, в какой системе счисления оно записано. На этом уроке разберём, как устроены системы счисления, как переводить числа из любой системы в десятичную и из десятичной в двоичную и как решать задачи «сосчитай нули и единицы», которые часто встречаются в заданиях ГЭЦ.
Непозиционные системы: римские цифры
Система счисленияОпределение
Совокупность правил записи и чтения чисел с помощью знаков — цифр. В непозиционной системе значение цифры не зависит от её места в записи числа, в позиционной — зависит.
Самая простая непозиционная система — счёт палочками: ||||| = 5. Самая известная — римские цифры: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. В числе XX оба X означают 10: цифра не становится в 10 раз больше, если стоит левее. Правила такие: цифры обычно пишут от больших к меньшим и складывают; меньшая цифра перед большей вычитается (только в парах IV, IX, XL, XC, CD, CM); одна и та же цифра подряд пишется не больше трёх раз, а V, L и D вообще не повторяются.
Представь римские цифры как монеты: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. Число — это сумма монет в кошельке: XXVI = 10 + 10 + 5 + 1 = 26. Монета стоит одинаково, где бы она ни лежала: X везде означает 10 — это и есть непозиционная система. Есть лишь одна хитрость: если меньшая монета стоит перед большей, её вычитают: IV = 5 − 1 = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900. И ещё правило: один и тот же знак подряд пишут не больше трёх раз (4 — это IV, а не IIII), а V, L и D вообще не повторяются.
Метод монет
Задача
Прочитай число MCDXLIV.
Показать решениеСкрыть решение
Решение
M = 1000
CD: C меньше D → 500 − 100 = 400
XL: 50 − 10 = 40
IV: 5 − 1 = 4
Итого: 1000 + 400 + 40 + 4 = 1444.
Римские цифры
Задача
1) Запиши числа MMXXVI, XLIX и CDXCIV в десятичной системе.
2) Запиши число 1994 римскими цифрами.
Показать решениеСкрыть решение
Решение
XLIX = XL + IX = (50 − 10) + (10 − 1) = 40 + 9 = 49.
CDXCIV = CD + XC + IV = 400 + 90 + 4 = 494.
2) Раскладываем число по разрядам: 1994 = 1000 + 900 + 90 + 4 = M + CM + XC + IV = MCMXCIV.
Чтобы читать дальше, зарегистрируйся бесплатно
Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.
Позиционная система: основание и развёрнутая запись
В позиционной системе у каждой цифры два свойства: её собственное значение и разряд, в котором она стоит. Количество цифр системы — её основание (b). В системе с основанием b используются цифры 0, 1, …, b − 1, а веса разрядов растут справа налево: 1, b, b², b³, … Основание пишут маленьким нижним индексом: 352₆, 1101₂. В задачах системы часто называют по основанию: «2-ичная», «8-ричная», «16-ричная». В любой системе само основание записывается как 10: 10₂ = 2, 10₆ = 6. Цифры могут обозначаться и буквами: в наборе {0, 1, 2, k, m} 5 цифр, значит, это 5-ричная система (k = 3, m = 4); такие задачи подробно разобраны на уроке «Системы счисления: задачи с неизвестным основанием».
Сравни позиционную систему со счётом на пальцах. В десятичной системе после 9 цифры заканчиваются: при 9 + 1 разряд единиц «переполняется», в нём пишут 0, а 1 уходит влево — в разряд десятков: 10. Теперь представь, что считаешь только на одной руке: цифры — 0, 1, 2, 3, 4 (5 цифр — основание системы b = 5). На пятом пальце рука заполнена: откладываешь один камешек (одну «пятёрку») и начинаешь снова, поэтому пять записывается как 10₅, а семь — как 12₅. В двоичной системе всего две цифры, 0 и 1, поэтому разряд заполняется через каждые две единицы. В любой системе само основание записывается как 10, а веса разрядов справа налево равны 1, b, b², …
| Десятичная | 5-ричная | Двоичная |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 10 |
| 3 | 3 | 11 |
| 4 | 4 | 100 |
| 5 | 10 | 101 |
| 6 | 11 | 110 |
| 7 | 12 | 111 |
| 8 | 13 | 1000 |
Где
- N
- значение числа в десятичной системе
- b
- основание системы (b ≥ 2)
- aᵢ
- цифра в i-м разряде, 0 ≤ aᵢ ≤ b − 1
- k
- номер старшего разряда: количество цифр − 1
Развёрнутая запись числа. Разряды нумеруются справа налево, начиная с 0. Вычислив эту сумму, мы переводим число из любой системы в десятичную.
Из любой системы в десятичную
Задача
Переведи в десятичную систему: 1) 1203₄; 2) 352₆; 3) 2011₃.
Показать решениеСкрыть решение
Решение
1) 1203₄ = 1·4³ + 2·4² + 0·4 + 3 = 64 + 32 + 0 + 3 = 99.
2) 352₆ = 3·6² + 5·6 + 2 = 108 + 30 + 2 = 140.
3) 2011₃ = 2·3³ + 0·3² + 1·3 + 1 = 54 + 0 + 3 + 1 = 58.
Пронумеруй разряды
Начни с 0 справа: в числе 321₄ цифра 1 стоит в разряде 0, 2 — в разряде 1, 3 — в разряде 2.
Выпиши веса
Веса разрядов — степени основания: 4⁰ = 1, 4¹ = 4, 4² = 16.
Умножь и сложи
3·16 + 2·4 + 1·1 = 48 + 8 + 1 = 57.
Проверь
Каждая цифра должна быть меньше основания: 3, 2, 1 < 4 ✓
Развёрнутую запись можно сгруппировать иначе — это схема Горнера: N = (…((aₖ·b + aₖ₋₁)·b + aₖ₋₂)·b + …)·b + a₀. Начинаем слева: умножаем на основание, прибавляем следующую цифру и повторяем. Степени отдельно считать не нужно, а умножений на одно меньше, чем цифр, — именно так переводят числа программы. Та же запись доказывает, почему работает метод деления: N = b·Q + a₀, где 0 ≤ a₀ ≤ b − 1, а Q — число без последней цифры. Значит, при делении N на b остаток равен a₀, а неполное частное — Q, и при повторном делении цифры «отпадают» по одной справа налево.
По схеме Горнера
Задача
Переведи в десятичную систему по схеме Горнера: 1) 2011₃; 2) 110101₂.
Показать решениеСкрыть решение
Решение
2) 1 → 1·2 + 1 = 3 → 3·2 + 0 = 6 → 6·2 + 1 = 13 → 13·2 + 0 = 26 → 26·2 + 1 = 53.
В двоичной системе схема Горнера превращается в правило «удвой и прибавь цифру» — его легко выполнять в уме.
Из развёрнутой записи следуют два полезных вывода. У наибольшего k-значного числа все цифры равны b − 1: прибавив 1, получим единицу и k нулей, то есть bᵏ. Наименьшее k-значное число — единица и k − 1 нулей, то есть bᵏ⁻¹.
Где
- k
- количество цифр
- b
- основание системы
Наибольшее и наименьшее k-значные числа в системе с основанием b. Всего таких чисел bᵏ − bᵏ⁻¹ = (b − 1)·bᵏ⁻¹.
Наибольшее и наименьшее числа
Задача
1) Запиши наибольшее и наименьшее трёхзначные числа в 5-ричной системе и переведи их в десятичную.
2) Сколько четырёхзначных чисел в двоичной системе?
3) Возможна ли запись 285₈?
Показать решениеСкрыть решение
Решение
2) От 1000₂ = 8 до 1111₂ = 15: 2⁴ − 2³ = 8 чисел.
3) Нет: в 8-ричной системе цифры 0–7, цифры 8 нет.
Из десятичной в двоичную и обратно
В двоичной системе всего две цифры — 0 и 1, а веса разрядов — степени двойки. Именно в ней работает компьютер: один разряд — это один бит. Если знать наизусть таблицу ниже, любые задачи на системы счисления решаются быстрее.
| n | 2ⁿ | n | 2ⁿ |
|---|---|---|---|
| 0 | 1 | 6 | 64 |
| 1 | 2 | 7 | 128 |
| 2 | 4 | 8 | 256 |
| 3 | 8 | 9 | 512 |
| 4 | 16 | 10 | 1024 |
| 5 | 32 | 11 | 2048 |
Раздели
Раздели число на 2, запиши неполное частное и остаток (0 или 1).
Повтори
Снова дели частное на 2, пока частное не станет равным 0.
Прочитай снизу вверх
Выпиши остатки от последнего к первому: первый остаток — младший разряд.
Проверь
Сложи веса разрядов, где стоят единицы, — должно получиться исходное число.
Смысл метода деления простой. Разложи 13 конфет по парам: получится 6 пар, и 1 конфета останется — значит, в разряде единиц стоит 1. Затем сложи 6 пар в коробки по две пары: 3 коробки, остатка нет — в разряде двоек 0. Снова объедини 3 коробки по две: 1 большая коробка и 1 в остатке — в разряде четвёрок 1. В конце остаётся 1 большая коробка — в разряде восьмёрок 1. Прочитай остатки снизу вверх: 13 = 1101₂ = 8 + 4 + 1.
Где
- q
- неполное частное
- r
- остаток — последняя цифра числа в системе с основанием b
Метод деления работает для любого основания: делим на b. Короткое следствие: двоичное число, оканчивающееся на 0, чётное, а на 1 — нечётное.
Перевод в двоичную и обратно
Задача
1) Переведи 77 в двоичную систему.
2) Переведи 110101₂ в десятичную систему.
3) Переведи 200 в двоичную, разложив его на степени двойки.
Показать решениеСкрыть решение
Решение
38 : 2 = 19, остаток 0
19 : 2 = 9, остаток 1
9 : 2 = 4, остаток 1
4 : 2 = 2, остаток 0
2 : 2 = 1, остаток 0
1 : 2 = 0, остаток 1
Снизу вверх: 77 = 1001101₂. Проверка: 64 + 8 + 4 + 1 = 77 ✓
2) Складываем веса только тех разрядов, где стоит 1: 110101₂ = 32 + 16 + 4 + 1 = 53.
3) Наибольшая степень, не превосходящая 200, — 128: 200 − 128 = 72; 72 − 64 = 8; 8 − 8 = 0.
200 = 2⁷ + 2⁶ + 2³ = 11001000₂.
Интерактив
Дробные числа
Разряды после запятой имеют веса b⁻¹, b⁻², b⁻³, …; в двоичной системе это ½ = 0,5, ¼ = 0,25, ⅛ = 0,125, 1/16 = 0,0625. Чтобы перевести десятичную дробь в двоичную, дробную часть последовательно умножают на 2: целая часть каждого произведения (0 или 1) — очередная цифра, а дробную часть снова умножают. На этот раз цифры читают сверху вниз. Целая часть переводится отдельно, делением.
Представь разряды после запятой как куски пиццы: первый разряд — половина (½), второй — четверть (¼), третий — восьмая часть (⅛). Например, 0,11₂ = ½ + ¼ = 0,75. Чтобы перевести десятичную дробь в двоичную, дробную часть раз за разом умножают на 2: если целая часть произведения равна 1, следующая цифра — 1, если 0 — цифра 0; дальше продолжают с дробной частью. Эти цифры читают сверху вниз. Целая часть переводится отдельно, делением на 2.
Переведи 0,375 в двоичную систему
Задача
Переведи дробь 0,375 в двоичную систему.
Показать решениеСкрыть решение
Решение
0,75 · 2 = 1,5 → 1 (остаётся 0,5)
0,5 · 2 = 1,0 → 1 (дробная часть равна 0, стоп)
Сверху вниз: 0,375 = 0,011₂. Проверка: ¼ + ⅛ = 0,25 + 0,125 = 0,375 ✓
Перевод дробей
Задача
1) Переведи 0,1011₂ в десятичную систему.
2) Переведи 5,75 в двоичную систему.
Показать решениеСкрыть решение
Решение
2) Целая часть: 5 = 101₂.
Дробная часть: 0,75 · 2 = 1,5 → 1; 0,5 · 2 = 1,0 → 1; дробная часть стала 0, останавливаемся.
Сверху вниз: 0,75 = 0,11₂.
Ответ: 5,75 = 101,11₂. Проверка: 4 + 1 + 0,5 + 0,25 = 5,75 ✓
Какие дроби конечны в двоичной системе? Несократимая дробь p/q записывается в системе с основанием b конечной дробью тогда и только тогда, когда все простые делители q являются делителями b. У числа 2 единственный простой делитель — 2, поэтому в двоичной системе конечны только дроби, знаменатель которых — степень двойки. 0,1 = 1/10, а 10 = 2 · 5 — из-за множителя 5 запись бесконечна. Компьютер хранит такие числа ограниченным числом двоичных цифр: у числа «двойной точности» (стандарт IEEE 754) 53 значащих бита, и последний из них округляется.
Конечная или бесконечная?
Задача
Какие из дробей конечны в двоичной системе: 3/8, 1/5, 7/16, 0,3? Запиши конечные в двоичной системе.
Показать решениеСкрыть решение
Решение
1/5: в знаменателе 5 → бесконечная: 0,001100110011…₂ (повторяется группа 0011).
7/16: 16 = 2⁴ → конечная: 7/16 = ¼ + ⅛ + 1/16 = 0,0111₂.
0,3 = 3/10: у 10 есть множитель 5 → бесконечная.
Интересно, что в троичной системе 1/3 = 0,1₃ — конечная дробь, а ½ = 0,111…₃ — бесконечная: конечность зависит не от числа, а от основания.
Сколько цифр, нулей и единиц в двоичной записи
В заданиях ГЭЦ часто спрашивают: сколько цифр в двоичной записи числа, сколько в ней единиц и нулей? Переводить число целиком не нужно — достаточно записать его как сумму различных степеней двойки. Каждая степень даёт одну единицу, старшая степень определяет длину записи, а во всех остальных разрядах стоят нули.
Где
- n
- показатель степени
Число нулей = количество цифр − число единиц. Например, 2⁹ − 1 = 511 = 111111111₂ — девять единиц.
Где
- N
- натуральное число
- k
- количество цифр в двоичной записи N
Если неравенство выполняется, в двоичной записи N ровно k цифр. Например, 512 ≤ 1000 < 1024, поэтому 1000 = 1111101000₂ — десятизначное число.
Неравенство 2ᵏ⁻¹ ≤ N < 2ᵏ можно записать через логарифм: k = [log₂N] + 1, где [x] — целая часть x. С другими основаниями то же самое: например, число десятичных цифр N равно [lg N] + 1. Эта формула находит «длину» огромных чисел, не переводя их.
Длина больших чисел
Задача
1) Сколько цифр в двоичной записи числа 10⁹? 2) Сколько цифр в десятичной записи числа 2¹⁰⁰ (lg 2 ≈ 0,30103)?
Показать решениеСкрыть решение
Решение
2) lg 2¹⁰⁰ = 100 · lg 2 ≈ 30,103 ⇒ [30,103] + 1 = 31 цифра.
Быстрый способ: 2¹⁰ = 1024 ≈ 10³, поэтому каждые 10 двоичных цифр — это примерно 3 десятичные.
Закрытое задание в стиле ГЭЦ
Задача
На сколько в двоичной записи числа 300 нулей больше, чем единиц?
A) 1 B) 2 C) 3 D) 4 E) 5
Показать решениеСкрыть решение
Решение
300 = 2⁸ + 2⁵ + 2³ + 2² = 100101100₂.
Старшая степень 2⁸ → 9 цифр; четыре степени → четыре единицы; нулей: 9 − 4 = 5.
5 − 4 = 1. Правильный ответ: A) 1.
Числа, заданные степенями
Задача
1) Сколько нулей в двоичной записи числа 2¹⁰ + 2⁴ + 1?
2) Сколько единиц в двоичной записи числа 2⁹ − 1?
Показать решениеСкрыть решение
Решение
2) 2⁹ − 1 = 511 = 111111111₂ — 9 единиц.
Олимпиадная задача: считаем единицы
Задача
1) Сколько чисел от 0 до 255 (в 8-битной записи) содержат ровно три единицы? 2) Сколько всего единиц во всех их двоичных записях вместе?
Показать решениеСкрыть решение
Решение
2) В каждой позиции единица стоит ровно у половины из 256 чисел: 128. Для 8 позиций: 8 · 128 = 1024. В общем случае в записях чисел 0…2ⁿ − 1 всего n · 2ⁿ⁻¹ единиц.
Здесь комбинаторика встречается с системами счисления: каждое n-битное число — это выбор позиций, в которых стоят единицы.
То же самое умеет считать программа: число делится на 2, и на каждом шаге проверяется остаток. В письменном задании экзамена число вводится с клавиатуры, и первая строка программы — n = int(input()); здесь, чтобы программа работала в браузере, взято n = 300. Более сложные случаи (квадраты, 2ⁿ − 2ᵐ) разобраны на уроке «Системы счисления: задачи с неизвестным основанием».
n = 300
ones = 0
zeros = 0
while n > 0:
if n % 2 == 1:
ones = ones + 1
else:
zeros = zeros + 1
n = n // 2
print(ones, zeros)Ожидаемый результат
4 5
Дальше: на уроке «Восьмеричная и шестнадцатеричная системы счисления» научимся коротко записывать двоичные числа, а на уроке «Арифметические действия в различных системах счисления» — считать в этих системах столбиком.
Запомни
- В непозиционной системе (римские цифры) значение цифры не зависит от места; в позиционной вес каждого разряда — степень основания.
- В системе с основанием b цифры 0…b − 1; развёрнутая запись N = aₖ·bᵏ + … + a₁·b + a₀ переводит число из любой системы в десятичную.
- Из десятичной в двоичную: дели на 2 и читай остатки снизу вверх; дробную часть умножай на 2 и читай целые части сверху вниз.
- Наибольшее k-значное число равно bᵏ − 1, наименьшее — bᵏ⁻¹.
- Число единиц в двоичной записи равно числу различных степеней двойки; количество цифр находят из 2ᵏ⁻¹ ≤ N < 2ᵏ; нули = цифры − единицы.