Подтема 6 из 6 · дополнительный урок
Что считает функция
Функции над цифрами числа: сумма цифр, двоичные единицы, вклады цифр и перенос при n + 1 — счёт без перебора огромного диапазона.
Цифры числа
Что считает функция, в которой аргумент делится на 10? Это дополнительный урок: такие задачи встречаются в сборниках, но на экзаменах их пока не было.
Деление на основание системы счисления снимает с числа последнюю цифру, а остаток — это и есть эта цифра. Для 472: 472 // 10 = 47 — число без последней цифры, 472 % 10 = 2 — последняя цифра ().
Теперь функция: F(0) = 0; F(n) = F(n // 10) + n % 10 при n > 0. Для 472: F(472) = F(47) + 2, F(47) = F(4) + 7, F(4) = F(0) + 4. Итого F(472) = 4 + 7 + 2 = 13 — это сумма цифр.
То же для любого основания b: n // b снимает последнюю цифру записи в системе b, n % b — эта цифра. Частые случаи при базе F(0) = 0:
- F(n // 10) + n % 10
- Сумма десятичных цифр
- F(n // 2) + n % 2
- Количество единиц в двоичной записи
- 1 + F(n // 10)
- Количество десятичных цифр положительного числа
- 1 + F(n // b)
- Количество цифр в системе с основанием b
В условии вместо n // 10 и n % 10 могут написать n div 10 и n mod 10 — смысл тот же.
Двоичные единицы
Как без перебора посчитать, сколько чисел дают F(n) = 2 для F(n) = F(n // 2) + n % 2?
Функция считает единицы в двоичной записи. Значит, нужно сосчитать записи с двумя единицами — выбрать для них две позиции. Например, 27 = 11011₂, и F(27) = 4.
В подтеме 5 перебор дал 15 чисел от 1 до 63. Все эти числа записываются шестью двоичными цифрами, если дописать нули слева: 63 = 111111₂. Первую позицию для единицы можно выбрать шестью способами, вторую — пятью. Но так каждая пара посчитана дважды — в одном порядке и в другом. Поэтому 6 · 5 / 2 = 15.
Иногда ту же функцию задают по-другому: F(n) = F(n / 2) при чётном n > 0 и F(n) = 1 + F(n − 1) при нечётном n. Нечётное число оканчивается единицей: её отнимают и считают, а чётное делят на 2 — снимают ноль. Смысл тот же: количество двоичных единиц.
Вклад цифры
А если функция учитывает не все цифры? Например: F(0) = 0; при n > 0 F(n) = F(n // 10) + n % 10, если n чётно, и F(n) = F(n // 10), если n нечётно.
Разбери, что каждая цифра добавляет к ответу, — её вклад. Чётность числа определяет последняя цифра. Чётная цифра прибавляется, нечётная пропускается, затем цифра снимается. Значит, функция считает сумму чётных цифр.
Когда F(n) = 0? Когда в записи нет ни одной положительной чётной цифры: разрешены 0, 1, 3, 5, 7, 9. Ноль разрешён — он ничего не добавляет. Посчитаем трёхзначные числа с такой записью:
- первая цифра — 1, 3, 5, 7 или 9: пять вариантов;
- вторая — любая из шести разрешённых;
- третья — тоже любая из шести.
Всего 5 · 6 · 6 = 180: каждый выбор первой цифры сочетается с каждым выбором второй и третьей.
Перенос при n + 1
Как сравнить сумму цифр n и n + 1, не считая их?
Если последняя цифра меньше 9, сумма цифр растёт на 1. Если n оканчивается девятками, они превращаются в нули, и сумма падает. Например, 243 → 244: сумма 9 → 10. А 2399 → 2400:
Если в конце n стоят t девяток, F(n + 1) = F(n) + 1 − 9t. Значит, F(n) > F(n + 1) ровно тогда, когда n оканчивается на 9.
Теперь вместо перебора огромного диапазона достаточно сосчитать числа 9, 19, 29, … На отрезке [L, R] при L ≥ 1 их (R + 1) // 10 - L // 10. Для 123 ≤ n ≤ 987 это 98 − 12 = 86. Сверим с перебором:
def F(n): if n == 0: return 0 return F(n // 10) + n % 10 count = 0for n in range(123, 988): if F(n) > F(n + 1): count += 1print(count, 988 // 10 - 123 // 10)Тонкости:откуда формула
Чисел, оканчивающихся на 9 и не больших R, ровно (R + 1) // 10: каждый полный десяток содержит одно такое. Из них вычитаем те, что меньше L, — их L // 10.
Таблица вкладов
Что делать, если вклад цифры не равен самой цифре?
Составь таблицу вкладов и рассуждай по ней. Например, функция делит аргумент на 4 и по остатку добавляет: 0 → 0, 1 → 1, 2 → 1, 3 → 2. Это сумма вкладов четверичных цифр:
| Цифра | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Вклад | 0 | 1 | 1 | 2 |
При n + 1 тройки в конце превращаются в нули — каждая такая замена уменьшает F на 2. Цифра перед ними растёт на 1: 0 → 1 даёт +1, 1 → 2 — ничего, 2 → 3 — снова +1.
Найдём наименьшее n, для которого F(n) = 7, а F(n + 1) = 4. F должно упасть на 3: две тройки в конце дадут −4, а рост цифры перед ними 2 → 3 добавит 1. Окончание 233₄ даёт вклад 1 + 2 + 2 = 5, до 7 не хватает 2 — это одна цифра 3 впереди. Получаем n = 3233₄.
Проверка: F(n) = 2 + 1 + 2 + 2 = 7; n + 1 = 3300₄, F(n + 1) = 2 + 2 = 4. В десятичной записи 3233₄ = 3 · 64 + 2 · 16 + 3 · 4 + 3 = 239.
Тонкости:почему не 033₄
Окончание 033₄ тоже даёт падение на 3, но его вклад 0 + 2 + 2 = 4, и до 7 не хватает 3. Одной цифрой вклад 3 не набрать — число выйдет длиннее, а значит, больше 239.
Итого
n // b,n % bснять последнюю цифру записи в системе b и взять её- F(n // 2) + n % 2количество двоичных единиц
- Две единицы из k позицийk · (k − 1) / 2 чисел
- Разрешённые цифрыколичество — произведение вариантов по позициям
- Сумма цифр n + 1F(n) + 1 − 9t, где t — девятки в конце
- Вкладытаблица «цифра → сколько добавляет»
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Сумма цифр 5
F(0) = 0; F(n) = F(n // 10) + n % 10 при n > 0. Сколько натуральных чисел до 999 включительно дают F(n) = 5?
Введите число.
Подсказка
F(n) — сумма цифр. Перебери n от 1 до 999 со счётчиком.
Решение
Функция считает сумму цифр, а диапазон небольшой — хватит перебора со счётчиком:
def F(n): if n == 0: return 0 return F(n // 10) + n % 10 count = 0for n in range(1, 1000): if F(n) == 5: count += 1print(count)Ответ: 21
Сумма цифр 9
F(0) = 0; F(n) = F(n // 10) + n % 10 при n > 0. Сколько чисел от 100 до 500 дают F(n) = 9?
Введите число.
Подсказка
Это сумма цифр: перебери n от 100 до 500 включительно.
Решение
Перебор со счётчиком; правая граница range не входит, поэтому range(100, 501):
def F(n): if n == 0: return 0 return F(n // 10) + n % 10 count = 0for n in range(100, 501): if F(n) == 9: count += 1print(count)Ответ: 30
Сумма цифр 13
F(0) = 0; F(n) = F(n // 10) + n % 10 при n > 0. Сколько чисел от 1000 до 5000 дают F(n) = 13?
Введите число.
Подсказка
F(n) — сумма цифр; четыре тысячи вызовов программа сделает мгновенно.
Решение
Перебор со счётчиком по всем n от 1000 до 5000:
def F(n): if n == 0: return 0 return F(n // 10) + n % 10 count = 0for n in range(1000, 5001): if F(n) == 13: count += 1print(count)Ответ: 260
Произведение цифр 12
F(n) = n при n < 10; F(n) = F(n // 10) · (n % 10) при n ≥ 10. Сколько натуральных чисел до 1000 включительно дают F(n) = 12?
Введите число.
Подсказка
F(n) — произведение цифр; ноль внутри числа обнуляет его.
Решение
Функция перемножает цифры. Перебираем n со счётчиком:
def F(n): if n < 10: return n return F(n // 10) * (n % 10) count = 0for n in range(1, 1001): if F(n) == 12: count += 1print(count)Ответ: 19
Две единицы в двоичной записи
F(0) = 0; F(n) = F(n // 2) + n % 2 при n > 0. Сколько чисел от 1 до 127 дают F(n) = 2?
Введите число.
Подсказка
F(n) — количество единиц в двоичной записи. 127 = 1111111₂ — семь позиций.
Решение
Все числа до 127 записываются семью двоичными цифрами. Нужны две единицы: позиции для них выбираются 7 · 6 / 2 = 21 способом. Проверка перебором:
def F(n): if n == 0: return 0 return F(n // 2) + n % 2 count = 0for n in range(1, 128): if F(n) == 2: count += 1print(count)Ответ: 21
Три единицы до 255
Сколько чисел от 1 до 255 имеют в двоичной записи ровно три единицы?
Введите число.
Подсказка
255 = 11111111₂ — восемь позиций. Выбери три из них для единиц.
Решение
Числа до 255 — это записи из восьми двоичных цифр. Три позиции для единиц: 8 · 7 · 6 считает упорядоченные тройки, а каждая тройка позиций посчитана 6 раз. 8 · 7 · 6 / 6 = 56. Проверка перебором — bin(n) даёт двоичную запись строкой:
count = 0for n in range(1, 256): if bin(n).count('1') == 3: count += 1print(count)Ответ: 56
Задача в формате экзамена: три единицы
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(0) = 0; F(n) = F(n / 2), если n > 0 и при этом n чётно; F(n) = 1 + F(n − 1), если n нечётно. Сколько существует чисел n < 2²⁰, для которых F(n) = 3?
Введите число.
Подсказка
F(n) — число единиц двоичной записи: выбери три позиции из двадцати.
Решение
Числа меньше 2²⁰ — это записи из 20 двоичных цифр. Три позиции для единиц выбираются 20 · 19 · 18 / 6 = 1140 способами: каждая тройка позиций в 20 · 19 · 18 посчитана 6 раз. Проверка перебором — bin(n) даёт двоичную запись строкой:
count = 0for n in range(2**20): if bin(n).count('1') == 3: count += 1print(count)Ответ: 1140
Трёхзначные числа без семёрок
F(0) = 0; при n > 0 F(n) = F(n // 10) + 1, если n % 10 = 7, иначе F(n) = F(n // 10). Сколько трёхзначных чисел дают F(n) = 0?
Введите число.
Подсказка
F(n) считает семёрки в записи числа; F(n) = 0 — семёрок нет.
Решение
Первая цифра — любая, кроме 0 и 7: 8 вариантов. Вторая и третья — любые, кроме 7: по 9. Всего 8 · 9 · 9 = 648. Проверка перебором:
def F(n): if n == 0: return 0 if n % 10 == 7: return F(n // 10) + 1 return F(n // 10) count = 0for n in range(100, 1000): if F(n) == 0: count += 1print(count)Ответ: 648
Без чётных цифр
F(0) = 0; при n > 0 F(n) = F(n // 10) + n % 10, если n чётно, и F(n) = F(n // 10), если n нечётно. Сколько четырёхзначных чисел дают F(n) = 0?
Введите число.
Подсказка
Это сумма чётных цифр. Ноль — когда из чётных цифр есть только нули.
Решение
Разрешены цифры 0, 1, 3, 5, 7, 9. Первая цифра не 0: 5 вариантов, остальные три — по 6. Всего 5 · 6 · 6 · 6 = 1080. Проверка перебором:
def F(n): if n == 0: return 0 if n % 2 == 0: return F(n // 10) + n % 10 return F(n // 10) count = 0for n in range(1000, 10000): if F(n) == 0: count += 1print(count)Ответ: 1080
Задача в формате экзамена: F(n) = 0
Функция F(n), где n — неотрицательное целое число, задана следующими соотношениями: F(n) = 0, если n = 0; F(n) = F(n // 10) + n % 10, если n > 0 и n чётно; F(n) = F(n // 10), если n нечётно. Сколько существует натуральных чисел n, для которых 10⁵ ≤ n ≤ 3 · 10⁵ и F(n) = 0?
Введите число.
Подсказка
F(n) — сумма чётных цифр; ноль, если из чётных цифр есть только нули. Отдельно проверь границу отрезка.
Решение
Числа от 100 000 до 299 999 с разрешёнными цифрами начинаются с 1 (2 — чётная). Остальные пять цифр — любые из 0, 1, 3, 5, 7, 9: 6⁵ = 7776. Плюс само 300 000 — из чётных цифр у него только нули. Итого 7777. Проверка перебором:
def F(n): if n == 0: return 0 if n % 2 == 0: return F(n // 10) + n % 10 return F(n // 10) count = 0for n in range(10**5, 3 * 10**5 + 1): if F(n) == 0: count += 1print(count)Ответ: 7777
Сумма цифр падает
Пусть F(n) — сумма десятичных цифр n. Сколько чисел от 1000 до 5000 дают F(n) > F(n + 1)?
Введите число.
Подсказка
Сумма цифр падает только у чисел, которые оканчиваются на 9.
Решение
Нужны числа от 1000 до 5000, оканчивающиеся на 9: 1009, 1019, …, 4999. По формуле (R + 1) // 10 − L // 10 = 5001 // 10 − 1000 // 10 = 500 − 100 = 400. Проверка перебором:
def F(n): if n == 0: return 0 return F(n // 10) + n % 10 count = 0for n in range(1000, 5001): if F(n) > F(n + 1): count += 1print(count)Ответ: 400
Разность 26
Пусть F(n) — сумма десятичных цифр n. Найди наименьшее n, для которого F(n) − F(n + 1) = 26.
Введите число.
Подсказка
Переход через t девяток меняет сумму цифр на 1 − 9t.
Решение
Нужно 9t − 1 = 26, то есть t = 3: n оканчивается тремя девятками. Наименьшее такое n — 999: F(999) = 27, F(1000) = 1. Проверка перебором:
def F(n): if n == 0: return 0 return F(n // 10) + n % 10 n = 1while F(n) - F(n + 1) != 26: n += 1print(n)Ответ: 999