Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна? Здравствуйте.
Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.
Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.
Программа получает два натуральных числа A и B, не превосходящих 10^9, A <= B.
Программа должна вывести одно число - количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.
Решение, что приходит на ум: два цикла (цикл в цикле) - В первом перебираем сами числа, а во втором цифры каждого числа.
Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)
Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого - путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).
Кстати, странно, что у таких чисел еще нет названия :)
Заранее благодарен, Артем.
Алгоритм подсчета количества чисел в промежутке от А до B, сумма цифр которых четна? Здравствуйте.
Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.
Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.
Программа получает два натуральных числа A и B, не превосходящих 10^9, A <= B.
Программа должна вывести одно число - количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.
Решение, что приходит на ум: два цикла (цикл в цикле) - В первом перебираем сами числа, а во втором цифры каждого числа.
Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)
Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого - путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).
Кстати, странно, что у таких чисел еще нет названия :)
Заранее благодарен, Артем.
Помогаю школьникам подготовиться к олимпиаде по программированию. Разбираю решения некоторых задач. Решение одной задачи, на мой взгляд не рационально. Однако найти более оптимальное решение у меня не получается.
Условие задачи: даны два числа A и B. Посчитайте количество натуральных чисел на отрезке от A до B, сумма цифр которых четна.
Программа получает два натуральных числа A и B, не превосходящих 10^9, A <= B.
Программа должна вывести одно число - количество натуральных чисел, больше или равных A и меньших или равных B, сумма цифр которых четна.
Решение, что приходит на ум: два цикла (цикл в цикле) - В первом перебираем сами числа, а во втором цифры каждого числа.
Стоит учитывать, что ребятам приходится писать на линейном языке программирования (поэтому некоторые решения в принципе не могут быть оптимальными, но не настолько)
Хотелось бы получить идею, как реализовать данную программу без второго цикла (а может и без первого - путем математических вычислений) или ваши мысли по поводу алгоритма для нахождения чисел, сумма цифр которых четна, без перебора самих чисел (если возможно).
Кстати, странно, что у таких чисел еще нет названия :)
Заранее благодарен, Артем.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Привет, Артем. Вот возможное оптимальное решение данной задачи:
Давайте разберемся с тем, какие числа имеют сумму цифр, кратную 2. Очевидно, что сумма цифр числа будет кратной 2, если все его цифры также кратны 2. То есть, чтобы сумма цифр числа была четной, все его цифры должны быть четными.Посмотрим на двузначные числа. Всего возможных комбинаций четных цифр в двузначном числе 5: 00, 02, 04, 06, 08.Это означает, что каждые 10 чисел (от 00 до 09, от 10 до 19 и так далее) содержат ровно 5 чисел с четной суммой цифр.Теперь мы можем посчитать сколько четных чисел содержится в промежутке от A до B, используя формулу: (B // 10 - A // 10) * 5. Здесь // означает деление нацело.Остается проверить случай, когда A и B находятся в одном диапазоне четных чисел. Для этого проверяем, являются ли A и B четными числами. Если да, то добавляем 1 к результату.Таким образом, мы можем подсчитать количество чисел с четными суммами цифр в заданном диапазоне без перебора самих чисел. Надеюсь, это решение поможет вам и вашим ученикам. Всего доброго!