Задание 14 · Позиционные системы счисления
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — сколько четвёрок в пятеричной записи 5²³ + 25¹² − 10 — прошла через подтемы, и каждая добавляла к решению новый способ. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Запись и значение»: цифры записи — остатки от деления. Точками отмечены новые строки.
- Подтема 2, «Степени блоками»: qᵐ − qⁿ — блок цифр q − 1.
- Подтема 3, «Цифры программой»: тот же ответ — циклом % и //.
- Подтема 4, «Параметр x»: вместо 10 — x: перебор диапазона. Ответ задачи темы — 21; в изменённой задаче с x — 1876.
Ответ 21 получен дважды — блоками и циклом, — и каждый способ проверяет другой. Подтема 5 ставит неизвестную цифру в саму запись, а дополнительный урок ищет неизвестное основание.
Карта темы
Каждая подтема дала один приём, и любое решение собирается из них. Сверху — путь от выражения к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Букваx — число в выражении или цифра?
- Значениестепени, int(s, q) или value
- Цифры% q и // q — ответ
1Запись числа и её значение
- 2304₅2 · 125 + 3 · 25 + 0 · 5 + 4 = 329
- A, B, …одна цифра: 10, 11, …
n % qпоследняя цифра записи
2Запись суммы и разности степеней
- qᵏединица и k нулей
- qᵏ − 1k цифр q − 1
- qᵐ − qⁿm − n цифр q − 1 и n нулей
3Цифры значения выражения программой
while n > 0цифра n % q, затем n = n // q**степень; ^ в Python — не степень
4Выражение с параметром x
- x — числовесь диапазон условия, цифры заново
- наибольшее xпоследнее подходящее при переборе вверх
5Неизвестные цифры
- x — цифраот 0 до q − 1
int(s, q)значение записи с подставленной цифрой- две цифрысравнить все пары
6Неизвестное основание и признаки делимостидополнительный урок
- основаниеперебор от наибольшей цифры + 1
- q − 1делимость по сумме цифр
Как решать
Любое задание 14 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- десятичные цифры
str(n).count('4')→ цифры системы q — через n % q. Спроси себя: в какой системе я считаю цифры?подтема 1- 5 ^ 23
5 ^ 23→5 ** 23. Спроси себя: сколько цифр у получившегося числа?подтема 3- деление через /
n = n / 5→n = n // 5. Спроси себя: не стало ли число дробным?подтема 3- блоки налезают
- сложили блоки, которые делят разряды → разложить на части в разных разрядах. Спроси себя: нет ли переносов между частями?подтема 2
- x как цифра
- параметр x перебрали от 0 до q − 1 → x в выражении — весь диапазон условия. Спроси себя: x — это число или цифра записи?подтема 4
- диапазон цифры
- цифру x перебрали до 9 при основании 18 → от 0 до q − 1. Спроси себя: какие цифры есть в системе q?подтема 5
- первая пара
- при двух цифрах взяли первую пару → сравнить все пары. Спроси себя: точно ли эта пара лучшая?подтема 5
- x вместо частного
- в ответ записана цифра x → ответ — то, что спрашивают. Спроси себя: что просит последняя фраза?подтема 5
Итог
Тема пройдена: задача темы решена и блоками, и программой — ответ 21. Вот что взять с собой.
- ПорядокБуква, значение, цифры, перебор, ответ.
- Цифрыn % q — последняя, n // q — остальные.
- Блокиqᵐ − qⁿ: m − n цифр q − 1 и n нулей.
- Буква xЧисло — весь диапазон, цифра — от 0 до q − 1.
- Задача темы1 0 44…44 30 — 21 четвёрка.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Как выглядит 7⁵ − 1 в семеричной записи?
ОтветСкрыть ответ
66666₇ — пять цифр 6.
Как выглядит 3⁸ − 3³ в троичной записи?
ОтветСкрыть ответ
22222000₃: пять двоек и три нуля.
Почему цифры записи в системе q считают через n % q, а не через str(n)?
ОтветСкрыть ответ
str(n) даёт десятичную запись. Остаток n % q — последняя цифра в системе q, а n // q отрезает её.
В записи 3x5₁₂ неизвестна цифра x. Какие значения перебирать?
ОтветСкрыть ответ
От 0 до 11: в двенадцатеричной системе 12 цифр, A и B — это 10 и 11.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Шестёрки в семеричной записи
Значение арифметического выражения 2 · 49¹⁰ + 7¹² − 7⁴ − 3 записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?
Введите число.
Подсказка
Приведи 49¹⁰ к основанию 7, вычитаемое раздели на блоки.
Решение
2 · 49¹⁰ = 2 · 7²⁰. Вычитаемое: 7¹² − 7⁴ − 3 = (7¹² − 7⁵) + (7⁵ − 7⁴ − 3). Запись 200000000666666656664₇, шестёрок 10.
def digits(n, q): if n == 0: return [0] result = [] while n > 0: result.append(n % q) n = n // q result.reverse() return result n = 2 * 49 ** 10 + 7 ** 12 - 7 ** 4 - 3print(digits(n, 7).count(6))Ответ: 10
Цифры больше 9 при основании 36
Значение арифметического выражения 3 · 6⁸⁰ + 6⁵⁰ − 6²⁰ − 1000 записали в системе счисления с основанием 36. Определи количество цифр с числовым значением, превышающим 9.
Введите число.
Подсказка
Цифры 36-ричной записи — числа от 0 до 35.
Решение
Программа собирает цифры списком и считает те, что больше 9. В записи 3000000000000000ZZZZZZZZZZZZZZYZZZZZZZZ88₃₆ это Z и Y — 23 цифры.
def digits(n, q): if n == 0: return [0] result = [] while n > 0: result.append(n % q) n = n // q result.reverse() return result n = 3 * 6 ** 80 + 6 ** 50 - 6 ** 20 - 1000print(sum(1 for d in digits(n, 36) if d > 9))Ответ: 23
Ровно три нуля
Значение арифметического выражения 6⁸ + 6³ − x, где x — натуральное число, не превышающее 1000, записали в шестеричной системе счисления. Определи наибольшее значение x, при котором в записи ровно три нуля.
Введите число.
Подсказка
Перебирай x до 1000 и запоминай последнее подходящее.
Решение
Ровно три нуля — у x = 432, 648 и 864. Наибольшее — 864.
def digits(n, q): if n == 0: return [0] result = [] while n > 0: result.append(n % q) n = n // q result.reverse() return result print(max(x for x in range(1, 1001) if digits(6 ** 8 + 6 ** 3 - x, 6).count(0) == 3))Ответ: 864
Частное от деления на 10
Операнды арифметического выражения записаны в системе счисления с основанием 21: 9x36₂₁ + 3x7Ax₂₁. Переменной x обозначена неизвестная цифра из алфавита 21-ричной системы счисления. Определи значение x, при котором значение выражения кратно 20. Для найденного x вычисли частное от деления значения выражения на 10.
Введите число.
Подсказка
Кратность проверяют на 20, а делят на 10.
Решение
Подходит только x = 14: сумма 806000 кратна 20. Спрашивают частное от деления на 10: 80600.
def value(ds, q): v = 0 for d in ds: v = v * q + d return v for x in range(21): s = value([9, x, 3, 6], 21) + value([3, x, 7, 10, x], 21) if s % 20 == 0: print(s // 10)Ответ: 80600
Две цифры в основаниях 7 и 8
Операнды арифметического выражения записаны в системах счисления с основаниями 7 и 8: 1xy3₇ + y2x₈. Переменными x и y обозначены допустимые в данных системах счисления неизвестные цифры. Определи значения x и y, при которых значение выражения будет наименьшим и кратно 13. Для найденных значений вычисли частное от деления значения выражения на 13.
Введите число.
Подсказка
Нужна наименьшая сумма, а не первая пара.
Решение
Сравниваем все пары: наименьшая сумма, кратная 13, — 533 при x = 2, y = 1. Первая найденная пара x = 1, y = 5 дала бы 767. Частное 533 / 13 = 41.
def value(ds, q): v = 0 for d in ds: v = v * q + d return v best = Nonefor x in range(7): for y in range(7): s = value([1, x, y, 3], 7) + value([y, 2, x], 8) if s % 13 == 0 and (best is None or s < best): best = sprint(best // 13)Ответ: 41