Подтема 4 из 6
Выражение с параметром x
Если из выражения вычитают неизвестное число x, его перебирают и для каждого заново считают цифры.
x — число, а не цифра
Изменим задачу темы: вместо 10 вычитают неизвестное x. «Значение 5²³ + 25¹² − x, где x — натуральное число, не больше 2030, записали в пятеричной системе. Найди наибольшее x, при котором в записи ровно 22 цифры 4.»
Здесь x — обычное число в выражении, а не цифра записи. Поэтому проверяют все x от 1 до 2030 и для каждого заново считают четвёрки. Подсчёт оформим функцией count4 — это тот же цикл из подтемы 3:
def count4(n): count = 0 while n > 0: if n % 5 == 4: count = count + 1 n = n // 5 return count answer = Nonefor x in range(1, 2031): if count4(5**23 + 25**12 - x) == 22: answer = xprint(answer)Перебор идёт по возрастанию, поэтому последнее запомненное x и есть наибольшее. в начале значит «пока ничего не нашли».
Почему ответ 1876
Откуда взялось 1876? Это можно понять и без программы.
Четвёрка в записи остаётся там, где у числа x − 1 стоит ноль. Вычесть x — всё равно что вычесть сначала 1, а потом x − 1: 5²³ + 25¹² − x = 5²⁴ + (5²³ − 1) − (x − 1). А 5²³ − 1 — это 23 четвёрки (подтема 2). Из четвёрки можно вычесть любую пятеричную цифру без займа, поэтому x − 1 вычитается из них поразрядно.
Значит, 22 четвёрки получаются, когда у x − 1 ровно одна ненулевая цифра, то есть x − 1 = d · 5ᵏ. Самое большое такое число до 2029 — 3 · 625 = 1875. Отсюда x = 1876, как и у программы.
Количество меняется скачками
Можно ли остановить перебор, когда четвёрок стало меньше 22?
Нет: количество цифр меняется скачками и при следующих x может снова вырасти. Посмотри на первые 125 значений x:
Поэтому проверяют все x из условия, а не только до первой неудачи.
Наибольшее и наименьшее x
А если спрашивают наименьшее x — или верхней границы у x нет вовсе?
Наименьшее x — первое подходящее при переборе по возрастанию, наибольшее — последнее. Выбери вопрос:
- Наибольшее x до 2030
- запомнить последнее подходящееили
range(2030, 0, -1)и на первом - Наименьшее x до 2030
breakна первом подходящем- Наименьшее x, границы нет
whileдо первого подходящего- Наибольшее количество цифр
- запоминать лучшее количество и его x
Например, наименьшее x, при котором четвёрок ровно 20, ищут циклом while — он остановится на первом подходящем:
x = 1while count4(5**23 + 25**12 - x) != 20: x = x + 1print(x)Проверка: x − 1 = 31 = 111₅ — три ненулевые цифры, 23 − 3 = 20 четвёрок.
Тонкости:когда перебор идёт слишком долго
Программа проверяет порядка миллиона x в секунду. Если цикл не закончился за несколько секунд, ответ лежит очень далеко, и начало перебора находят рассуждением о блоках записи — это разобрано в дополнительном уроке.
Итого
- x в выражениичисло, перебор по диапазону
- Наибольшеепоследнее подходящее
- Наименьшеепервое и break или while
- Скачкиперебирают все x, без границы
- Проверкаq − 1 остаётся там, где у x − 1 ноль
- Пример22 четвёрки — x = 1876
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Наибольшее x: ровно четыре четвёрки
Найди наибольшее x от 1 до 200, при котором в пятеричной записи 5⁶ − x ровно четыре цифры 4.
Введите число.
Подсказка
Перебирай x как число от 1 до 200, а не как цифру.
Решение
Перебор x от 1 до 200 с подсчётом четвёрок даёт наибольшее подходящее x = 176. Проверка: x − 1 = 175 = 1200₅ — две ненулевые цифры, и из шести четвёрок остаются четыре: 5⁶ − 176 = 443244₅.
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, 201) if digits(5 ** 6 - x, 5).count(4) == 4))Ответ: 176
Ровно 53 нуля
Значение арифметического выражения 7¹⁰⁰ + 7⁵⁰ − x, где x — целое положительное число, не превышающее 3000, записали в семеричной системе счисления. Определи наибольшее значение x, при котором в записи содержится ровно 53 нуля.
Введите число.
Подсказка
Количество нулей меняется скачками — проверь все x.
Решение
Перебор x от 1 до 3000 находит 25 значений с ровно 53 нулями; наибольшее из них — 2744 = 8 · 7³.
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 = 7 ** 100 + 7 ** 50print(max(x for x in range(1, 3001) if digits(n - x, 7).count(0) == 53))Ответ: 2744
Четвёрки в 5⁶ − 1 и 5⁶ − 2
Сколько цифр 4 в пятеричной записи числа 5⁶ − 2?
Введите число.
Подсказка
5⁶ − 2 = (5⁶ − 1) − 1.
Решение
5⁶ − 1 = 444444₅. Вычесть ещё 1 — значит уменьшить последнюю цифру: 444443₅. Четвёрок пять.
n = 5**6 - 2count = 0while n > 0: if n % 5 == 4: count = count + 1 n = n // 5print(count)Ответ: 5
Наименьшее x с наибольшим числом нулей
Значение выражения 5⁶ − x, где x — натуральное число, не превышающее 500, записали в пятеричной системе. Найди наименьшее x, при котором количество нулей в записи максимально.
Введите число.
Подсказка
Сначала найди наибольшее количество нулей, затем первое x с ним.
Решение
Нули в записи 5⁶ − x стоят там, где у x − 1 четвёрки. При x ≤ 500 у x − 1 не больше трёх четвёрок, и первое такое x − 1 = 124 = 444₅. Значит, x = 125.
def digits(n, q): if n == 0: return [0] result = [] while n > 0: result.append(n % q) n = n // q result.reverse() return result zeros = [digits(5 ** 6 - x, 5).count(0) for x in range(1, 501)]print(zeros.index(max(zeros)) + 1)Ответ: 125
Ровно 7 цифр 12
Значение арифметического выражения 11 · 13²⁰ + 13¹⁰ − x, где x — целое положительное число, записали в 13-ричной системе счисления. Определи наименьшее значение x, при котором в записи ровно 7 цифр с числовым значением 12.
Введите число.
Подсказка
Верхней границы нет — перебирай циклом while до первого подходящего x.
Решение
Цифры 12 стоят там, где у x − 1 нули среди десяти младших разрядов. Нужно ровно три ненулевые цифры, наименьшее такое x − 1 = 111₁₃ = 183, поэтому x = 184.
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 = 11 * 13 ** 20 + 13 ** 10x = 1while digits(n - x, 13).count(12) != 7: x += 1print(x)Ответ: 184
Наибольшее количество нулей
Значение арифметического выражения 6¹²⁰ + 6⁶⁰ − x, где x — натуральное число, не превышающее 2000, записали в шестеричной системе счисления. Определи максимальное количество нулей в этой записи.
Введите число.
Подсказка
Спрашивают количество нулей, а не x.
Решение
Перебор x до 2000 даёт наибольшее количество нулей 64. Например, при x = 6⁴ = 1296 число равно 6¹²⁰ + (6⁶⁰ − 6⁴): нули в разрядах 119…60 и 3…0 — их 60 + 4 = 64.
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 = 6 ** 120 + 6 ** 60print(max(digits(n - x, 6).count(0) for x in range(1, 2001)))Ответ: 64