Системы счисления · Блок 1§3
SilverTests.ru · Подготовка к ИТМОТеория + задания
системы счисления. Дробные числа
Запись, перевод, период, степени дробей
1Дробь = сумма степеней основания
В системе с основанием b дробь после запятой раскрывается так же, как в десятичной — только степени 10 заменяются степенями b:
примеры// двоичная
0,1₂ = 1/2 = 0,5₁₀
0,11₂ = 1/2 + 1/4 = 0,75₁₀
// шестнадцатеричная (A = 10, B = 11)
0,1₁₆ = 1/16 = 0,0625₁₀
0,A₁₆ = 10/16 = 0,625₁₀
0,AB₁₆ = 10/16+11/256 = 171/256
Никакой магии: дробь — это сумма обычных дробей со знаменателями-степенями b.
2Перевод 10 → b: метод умножения
Алгоритм. Умножаем дробь на b. Целая часть результата — очередная цифра после запятой. Дробную часть умножаем дальше. Стоп — когда дробная часть стала ноль (или начался период).
Цифры собираем сверху вниз, в отличие от целой части.
пример// 0,375₁₀ → bin:
0,375 · 2 = 0,75 ↓
0,75 · 2 = 1,5 ↓
0,5 · 2 = 1,0 ↓ дробная = 0 → стоп
Результат: 0,011₂
// проверка: 1/4 + 1/8 = 0,375 ✓
3Когда дробь конечна, а когда — период
Критерий. Несократимая дробь p/q имеет конечную запись в системе с основанием b тогда и только тогда, когда все простые делители q являются делителями b.
| Дробь |
q |
Делители q |
base 10 (2·5) |
base 2 |
base 16 (2⁴) |
| 1/2 |
2 |
{2} |
конечно |
конечно |
конечно |
| 1/3 |
3 |
{3} |
период |
период |
период |
| 1/5 |
5 |
{5} |
конечно |
период |
период |
| 1/8 |
8 |
{2} |
конечно |
конечно |
конечно |
| 1/10 |
10 |
{2, 5} |
конечно |
период |
период |
Шок-факт: 0,1₁₀ — это бесконечная периодическая дробь в двоичной. Поэтому компьютеры неточно считают 0,1 + 0,2.
4Период через геометрическую прогрессию
Главное тождество, которое нужно знать наизусть:
Откуда берётся
вывод0,(d)b = d/b + d/b² + d/b³ + …
= d · (1/b + 1/b² + 1/b³ + …)
= d · (1/b) / (1 − 1/b)
= d / (b − 1)
// проверки:
0,(3)₁₀ = 3/9 = 1/3 ✓
0,(F)₁₆ = 15/15 = 1 ✓ (sic!)
0,(1)₂ = 1/1 = 1 ✓
Период из k цифр:
пример0,(12)₁₀ = 12 / (100 − 1) = 12/99 = 4/33
0,(A)₁₆ = 10 / (16 − 1) = 10/15 = 2/3
5Степени дробей
Задана hex-дробь, нужно найти последние цифры её N-й степени.
Идея. Записать дробь как обыкновенную:
Тогда:
ключ(0,AB16)N = (171/256)N = 171N / 162N
// знаменатель = сдвиг на 2N hex-цифр
// числитель — целое число
// последние k hex-цифр дроби =
// = последние k цифр числителя в hex
= 171N mod 16k
Задача с дробями свелась к задаче «последние цифры степени» — это уже знакомая техника возведения в степень по модулю.
Проверь себя8 заданий
1 / 8