Нахождение количества чисел между двумя натуральными числами
Данный калькулятор определяет количество натуральных числел между двумя натуральными числами.
РУКОВОДСТВО
Введите в каждое поле по одному натуральному числу и нажмите кнопку «Рассчитать»
ТЕОРИЯ
Для того, чтобы узнать количество чисел между двумя натуральными числами, нужно из наибольшего числа вычесть наименьшее и дополнительно вычесть единицу.
Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна?
Здравствуйте.
Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.
Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.
Программа получает два натуральных числа A и B, не превосходящих 10^9, A Программа должна вывести одно число — количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.
Решение, что приходит на ум: два цикла (цикл в цикле) — В первом перебираем сами числа, а во втором цифры каждого числа.
Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)
Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого — путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).
Кстати, странно, что у таких чисел еще нет названия 🙂
Заранее благодарен, Артем.
- Вопрос задан более трёх лет назад
- 15796 просмотров
Анализ алгоритма
Пусть f( n ) равно количеству чисел на отрезке [0; n ], делящихся на x. Пусть f(a, b) равно количеству чисел на отрезке [a; b], делящихся на x. Тогда количество искомых чисел на отрезке [a; b] равно количеству чисел на отрезке [0; b] минус количество чисел на отрезке [0; a – 1]. То есть
f( a, b) = f(b) – f(a – 1)
Количество чисел от 0 до n включительно, делящихся на x, равно n / x + 1. То есть
f( n ) = n / x + 1
Если изначально a = 0, то ответом будет одно слагаемое f(0, b), так как значение f(0, a – 1) не имеет смысла.
В приведенном тесте следует вычислить значение
Найдем количество чисел от 0 до 10 включительно, делящихся на 3. Это будут числа 0, 3, 6 и 9. Их количество равно f(10) = 10 / 3 + 1 = 4.
Найдем количество чисел от 0 до 4 включительно, делящихся на 3. Это будут числа 0 и 3. Их количество равно f(4) = 4 / 3 + 1 = 2.
f(5, 10) = f(10) – f(4) = 4 – 2 = 2
Читаем входные данные.
Вычисляем k = f(b), l = f(a – 1).
При a = 0 ответом будет значение k = f( b).
При a ≠ 0 ответ равен f(a, b) = f(b) – f(a – 1) = k – l.
if (a == 0) res = k; else res = k — l;
printf( «%lld\n» ,res);
import java.util.*;
public class Main
public static long a , b , x ;
public static long f( long n )
return n / x + 1;
public static void main(String[] args )
Scanner con = new Scanner(System. in );
a = con .nextLong();
b = con .nextLong();
x = con .nextLong();
System. out .println(f( b ) — f( a -1));
a, b, x = map ( int , input ().split())
return n // x + 1
print (f(b) — f(a — 1 ))
Как посчитать количество чисел-палиндромов в большом промежутке?
Нужно посчитать количество палиндромов в промежутке от a до b. Решается легко, если промежуток — до 10000 Но, как решить задачу, где нужно найти количество палиндромов в промежутке от 1.026.376 до 10**15 (квадриллиона)? И желательно за быстрое время. Перебором слишком долго, может есть какие-то формулы, где можно просто числа брать, не проверяя каждое на палиндромность?
Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 19 мая в 16:15
11 2 2 бронзовых знака
Для суммы последовательных палиндромов можно вывести формулы без прямого суммирования всех палиндромов. Решение будет примерно за k или k^2, где k число цифр верхней границы.
19 мая в 16:55
сопоставьте заголовок вопроса с текстом, пожалуйста. сейчас из заголовка следует, что вам нужна сумма, а из текста вопроса — количество чисел.
19 мая в 18:32
@n1tr0xs, я разбился в лепёшку и решил для суммы. Гм. (Количество идёт в качестве бесплатного приложения).
19 мая в 18:33
@n1tr0xs, поменял название, простите!
20 мая в 15:33
Добавьте в вопрос код вашего решения. Не важно что оно медленное, важно чтобы оно было. Иначе вопрос закроют.
20 мая в 15:35
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Я предлагаю от 1.026.376 до следующего разряда 10 000 000 проверить перебором, а далее поразрядно 10^7 .. 10^8 ..10^n по формуле: если n четное, то количество палиндромов 10^(n//2)-10^(n//2-1), если n не четное, то количество палиндромов 10^((n+1)//2)-10^((n+1)//2-1)
например: 10^2 количество палиндромов 9 10^3 количество палиндромов 90 10^4 количество палиндромов 90 10^5 количество палиндромов 900 10^6 количество палиндромов 900 s=0 for i in range(1026376,10**7): sss=str(i) if sss==sss[::-1]: s+=1 print('->',s) for n in range(8,15+1): # Ошибочно начинал с 10^7 if n%2==0: s+=10**(n//2)-10**(n//2-1) else: s+=10**((n+1)//2)-10**((n+1)//2-1) print(s) -> 8973 109997973
Отслеживать
ответ дан 19 мая в 18:22
2,100 1 1 золотой знак 8 8 серебряных знаков 9 9 бронзовых знаков
Проверьте свои формулы, например, для диапазонов 100-1000 и 1000-10000
20 мая в 2:07
@MBo вы правы, формула была не верна, исправил на другую, прогнал до 10^7
20 мая в 8:26
Можно еще проще 9*10**((n-1)//2) в обоих случаях, т.е. if не нужен. И для данной конкретной границы можно пройти короткий диапазон 1000000..1026376, вычитая единицы, а потом пройти диапазоны, включая 10^6..10^7. Результат, кстати, у меня 109997973
20 мая в 10:32
Это еще одна ошибка, до 10^7 уже сосчитал, и нужно начинать с 10^8
20 мая в 14:04
Перебор это не спортивно. Есть решение без перебора.
20 мая в 15:35
f(k) — число чисел-палиндромов из k разрядов. Тогда
Девятка отвечает за цифры старшего разряда — от единицы до девяти. Степень десятки — за остальные разряды из старшей половины числа.
g(k) — число чисел-палиндромов из не более чем k разрядов. Тогда
- g(2k) = 2·10 k — 2;
- g(2k + 1) = 11·10 k — 2.
Доказывается по индукции (g(n + 1) = g(n) + f(n + 1)).
h(n) — число чисел-палиндромов не более n. Я покажу на примере как его можно сосчитать быстро. Пусть n = 345678. Разобъём все палиндромы не более n на группы:
? - палиндромы длины один. Их f(1) ?? - палиндромы длины два. Их f(2) . - палиндромы длины три. Их f(3) . - палиндромы длины четыре. Их f(4) . - палиндромы длины пять. Их f(5) 1. 1 - таких палиндромов 100 (все палиндромные цифровые строки длины 4) 2. 2 - тоже самое (первые цифры от единицы до 3 - 1) 30??03 - таких палиндромов 10 (все палиндромные цифровые строки длины 2) 31??13 - тоже самое 32??23 - тоже самое 33??33 - тоже самое (вторые цифры от нуля до 4 - 1) 340043 - такой палиндром один (все палиндромные цифровые строки длины 0) 341143 - тоже самое 342243 - тоже самое 343343 - тоже самое 344443 - тоже самое (третьи цифры от нуля до 5 - 1) 345543 - такой палиндром один, но надо отдельно проверить что он не больше n
Получается такая программа:
def ps_count(k): """ число палиндромных строк длины k """ return 10 ** ((k + 1) // 2) def p_count_10p(k): """ число чисел-палиндромов не более k разрядов """ return 10 ** ((k + 1) // 2) + 10 ** (k // 2) - 2 def p_count(n): """ число чисел-палиндромов не более n """ if n == 0: return 0 digits = tuple(map(int, str(n))) m = len(digits) # короткие палиндромы c = p_count_10p(m - 1) for i in range((m + 1) // 2): # палиндромы вида ABC. CBA c += (digits[i] - (0 if i > 0 else 1)) * ps_count(m - 2 * (i + 1)) if digits[:m // 2 - 1::-1]
echo 1026376 1_000_000_000_000_000 | python pcount.py 109997973
Программа работает за логарифмическое время. Её можно переделать для расчёта суммы палиндромов. Первоначально так и было, но вопрос изменился и ответ упростился.