Задать вопрос
zinkinru
@zinkinru
Делаю красивый веб функциональным

Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна?

Здравствуйте.
Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.

Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.
Программа получает два натуральных числа A и B, не превосходящих 10^9, A <= B.
Программа должна вывести одно число - количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.

Решение, что приходит на ум: два цикла (цикл в цикле) - В первом перебираем сами числа, а во втором цифры каждого числа.

Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)

Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого - путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).

Кстати, странно, что у таких чисел еще нет названия :)

Заранее благодарен, Артем.
  • Вопрос задан
  • 16609 просмотров
Подписаться 6 Комментировать
Подписчики вопроса 6 К ответам на вопрос (3)