Дробные числа. Углублённые приёмы

Группировка периодов, ряды, арифметика, поиск оснований

Конечная дробь 0,d₁d₂…dₖ в системе b — это просто целое число из цифр после запятой, делённое на b^k.

примеры
0,34₈  = 34₈ / 8²  = 28₁₀ / 64  = 7/16
0,1A₁₆ = 1A₁₆ / 16² = 26₁₀ / 256 = 13/128
0,101₂ = 101₂ / 2³  = 5 / 8      = 0,625₁₀

Это в разы быстрее, чем раскладывать по степеням. На олимпиаде экономит минуту на каждой задаче.

Формула из §3.1 (предпериод + период) работает для любого основания b. Вот три примера, которые постоянно встречаются на олимпиадах:

двоичная
0,(011)₂ = ?

B = 011₂ = 3₁₀,  n = 3
Знаменатель: 2³ − 1 = 7
Ответ: 3/7

с предпериодом
0,1(001)₂ = ?

A = 1₂ = 1 (m=1),  B = 001₂ = 1 (n=3)
AB = 1001₂ = 9₁₀
Числитель:   9 − 1        = 8
Знаменатель: 2¹ · (2³ − 1) = 2 · 7 = 14
Ответ: 8/14 = 4/7

восьмеричная
0,(007)₈ = ?

B = 007₈ = 7₁₀,  n = 3
Знаменатель: 8³ − 1 = 512 − 1 = 511 = 7 · 73
Ответ: 7/511 = 1/73

Поцифренный перевод (§3.1) работает и для периодических дробей, но здесь легко попасть в ловушку.

Безопасный алгоритм

алгоритм
// Шаг 1: переведи в обыкновенную дробь
// Шаг 2: переведи дробь в нужную систему (умножением)

// Пример: 0,(01)₂ → восьмеричная

// Шаг 1:
0,(01)₂ = 01₂ / (2² − 1) = 1/3

// Шаг 2: перевод 1/3 в base 8
1/3 · 8 = 8/3  = 2 + 2/3
2/3 · 8 = 16/3 = 5 + 1/3
1/3 · 8 = 8/3  = 2 + 2/3  ← повтор!

Ответ: 1/3 = 0,(25)₈

Ловушка: наивная группировка

ошибка!
// НЕПРАВИЛЬНО:
0,(01)₂ = 0,010101…₂
Группируем по 3: 010 | 101 | 010 | 101…
Получаем: 0,(25)₈ ???

// Тут повезло — ответ совпал!
// Но это работает ТОЛЬКО когда НОК(период, группа)
// = размер группы.

// ПРАВИЛЬНО:
// Период = 2 цифры. Группа для oct = 3.
// НОК(2,3) = 6 → выписываем 6 цифр:
// 010101 → группы 010|101 → 2|5 → 0,(25)₈ ✓

ещё примеры
// 0,(1)₂ → hex.  НОК(1, 4) = 4 → 1111 → F
0,(1)₂ = 0,(F)₁₆

// 0,(10)₂ → hex.  НОК(2, 4) = 4 → 1010 → A
0,(10)₂ = 0,(A)₁₆    // 2/3 = 10/15 ✓

На олимпиаде безопаснее всегда идти через обыкновенную дробь.

Связь периода с геом. прогрессией мы показали в §3. Здесь — типовые олимпиадные задачи.

Типовая задача Бельчонка

задача
// S = 0,1₈ + 0,01₈ + 0,001₈ + … (N слагаемых).
// Записать ответ в hex.

// a = 1/8, q = 1/8
S_N = (8ᴺ − 1) / (7 · 8ᴺ)
S_∞ = 1/7

// Перевод 1/7 в hex (умножением):
// 1/7·16 = 2 + 2/7
// 2/7·16 = 4 + 4/7
// 4/7·16 = 9 + 1/7  ← повтор
1/7 = 0,(249)₁₆

// Проверка: 249₁₆ = 585, 16³−1 = 4095
// 585/4095 = 1/7 ✓

Частичная сумма в «красивом» виде

пример
// 0,111…1₂ (N единиц) = ?

S_N = 1 − 1/2ᴺ = (2ᴺ − 1) / 2ᴺ

// N = 4: 0,1111₂ = 15/16
// N → ∞: 0,(1)₂ = 1

Сложение столбиком

пример
// 0,11₂ + 0,101₂

    0,110    ← дополнили нулём справа
  + 0,101
  -------
    1,011₂   ← 1+1 = 10₂, пишем 0, переносим 1

// Проверка: 0,75 + 0,625 = 1,375
// 1,011₂ = 1 + 1/4 + 1/8 = 1,375 ✓

Умножение

пример
// 0,11₂ × 0,11₂
// Шаг 1: 11 × 11 = 1001₂ (как целые)
// Шаг 2: дробных знаков = 2 + 2 = 4
// Ответ: 0,1001₂

// Проверка: 0,75² = 0,5625
// 0,1001₂ = 1/2 + 1/16 = 0,5625 ✓

Перенос из дробной части уходит в целую — следи за запятой:

пример0,11₂ + 0,11₂ = 1,1₂     // 0,75 + 0,75 = 1,5
0,3₅ + 0,4₅ = 1,2₅      // 0,6 + 0,8 = 1,4

Надёжный путь: перевести в обыкновенные дроби, посчитать точно, перевести назад. Периоды умеют сокращаться и комбинироваться:

пример0,(1) + 0,(2) = 1/9 + 2/9 = 3/9 = 1/3 = 0,(3)
0,(3) + 0,(6) = 1/3 + 2/3 = 1          // период исчез
0,(3) · 3   = 1/3 · 3 = 1            // это 0,(9), а 0,(9) = 1

Сумма, разность и произведение конечных дробей всегда конечны — знаменатель остаётся «дружественным» основанию. Если результат периодический, его период считается по несократимому знаменателю тем же правилом, что в §3.1 (через t):

пример0,5 + 0,25 = 0,75             // конечная + конечная = конечная

1/2 + 1/3 = 5/6;   6 = 2·3,  t = 3
период = порядок 3 = 1,  предпериод = 1   →   0,8(3)

На ИТМО это снимает страх перед «сложить две бесконечные дроби»: сводишь к p/q, дальше критерий конечности и формула периода.

Критерий конечности мы вывели в §3. Здесь — техника решения олимпиадной задачи «найти все b, в которых 1/n конечна».

1/12
12 = 2² · 3.  Делители: {2, 3}
b кратно НОК(2, 3) = 6

Ответ: b ∈ {6, 12, 18}   // в диапазоне 2–20

// Проверка: 1/12 · 6 = 1/2 → 0;
// 1/2 · 6 = 3 → стоп.  1/12 = 0,03₆ ✓

1/7
7 — простое.  Делители: {7}
b кратно 7.

Ответ: b ∈ {7, 14}   // 1/7 = 0,1₇ = 0,2₁₄

1/10
10 = 2 · 5.  Делители: {2, 5}
b кратно 10.

Ответ: b ∈ {10, 20}   // вот почему 0,1₁₀ — период везде кроме base 10 и 20

Единственный надёжный путь — привести обе к обыкновенным дробям:

пример
0,4₅ = 4/5 = 0,8
0,3₄ = 3/4 = 0,75

0,8 > 0,75  ⇒  0,4₅ > 0,3₄

Хитрая задача

задача
// В какой системе p верно 0,5ₚ = 0,25₁₀?

0,5ₚ = 5/p = 1/4
5/p = 1/4  ⇒  p = 20

// Проверка: 5 < 20 (цифра допустима) ✓