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

Question

[Артем Зинкин]

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

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

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

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

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

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

Заранее благодарен, Артем.

Answer 1

[Mrrl]

На каждом отрезке от 10*n до 10*n+9 таких чисел ровно 5. Поэтому нам достаточно посчитать число таких полных отрезков, и обработать краевые отрезки. Пусть sumdig(n) - функуция, которая выдаёт остаток от деления суммы цифр n на 2. Тогда: int s0=(B/10-A/10-1)*5; int s1=(10+sumdig(A/10)-A%10)/2; int s2=(2+B%10-sumdig(B/10))/2; return s0+s1+s2;

Answer 2

[alex1234]

А если банально (1+B-A)/2 (без дробной части) ? Вроде как сходится для малых чисел :-)

Comments

[alex1234]

Смысл в том, что чётность/нечётность сумм чередуется

[Артем Зинкин]

Да, верно. Четность/нечетность действительно чередуется, но для чисел без нуля. Числа, содержащие нуль выпадают из чередования.

[alex1234]

Имеете в виду набор вида, например, 99-100-101? Если да - так зная число цифр и граничные, можно определить число таких "неучтённых". Хотя похоже на костяль.

[Артем Зинкин]

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

[alex1234]

Пример для A=99 B=10001 получим некорректный учёт : 100,300,500,700,900,1000,2000,3000,5000,7000,9000 т.е. 2 цикла : - перебор количества цифр (3,4), определение соответсвующей степени десятки (10^2,10^3) - внутри - перебор нечётных вариантов (1*10^x,3*10^x,...) Ну и наверное,можно оптимизировать за счёт границ, но это, ИМХО - экономия на спичках :-) ИМХО, достаточно просто. А перебор цифр вроде как и не нужен (ну, разве что считать это как раз перебором)

[alex1234]

Точнее - вариантов с нечётной суммой :-)

[Артем Зинкин]

Возможно, я не совсем понял. Но числа 101, 110, 120, 130... тоже выпадают.

[alex1234]

Точно. Других идей пока нет

[alex1234]

Хотя, надо прикинуть все ли числа с нулём выпадут. Иначе, думаю, можно посчитать их количество в диапазоне.

[Артем Зинкин]

Мне приходила идея: в каждом десятке (от 0 до 9) ровно 5 чисел сумма которых четна и столько же с нечетной суммой. Однако каждый переход к новому десятку требует пересчета. И между A и B не всегда целое количество десятков.

[alex1234]

Про нецелое - так в чём проблема? Округлим A до десятков в большую, B-в меньшую, вычтем и умножим на 5 (или в чём-то ошибаюсь?) И потом посчитаем циклами граничные

Answer 3

[T-D-K]

Берём число A, определяем для него чётность суммы чисел, потом рассуждаем так: если A нечётно, то A+1 будет чётно, если A чётно, то A+1 - нечётно. Исключение делаем для перехода xx9 - xy0 (там по-моему xx9 и xy0 имет одинакоую чётность). В общем, так чередуясь бежим до B. Я бы делал так.

Comments

[Артем Зинкин]

Дело в том, что числа с нулем внутри x0y, x0yz тоже не подходят под чередование. А чтобы найти нуль в числе - нужно перебрать все его цифры - или есть другой способ??

[T-D-K]

Вот это добро накидал сейчас. Работает int A = 99; int B = 10001; int count1 = 0; int sum = 0; int a = A; while(a != 0) { sum += a % 10; a /= 10; } a = A; bool parity = false; if(sum % 2 == 0) { count1++; parity = true; } while(a < B) { a++; if(a % 10 != 0) parity = !parity; if(parity) count1++; } int count2 = 0; for(int i = A; i <= B; i++) { sum = 0; int temp = i; while(temp != 0) { sum += temp % 10; temp /= 10; } if(sum % 2 == 0) count2++; } Console.WriteLine(count1); Console.WriteLine(count2); Console.ReadLine();

[T-D-K]

код съелся парсером http://pastebin.com/02RRfKaU

[Артем Зинкин]

Спасибо за вариант решения. Код работает, но не быстрее чем перебор каждого числа отдельно. Но он явно сложнее, чем обычным перебором. Будем искать еще варианты решения.

[T-D-K]

Я написал неработающую хрень. Извиняюсь. Выше про "разбить на десятки и умножить на пять" - имхо, наиболее лучший ответ.

[Артем Зинкин]

На чем именно провалился код??

[T-D-K]

там вообще две проверки в коде - одна по моему способу (через чередование), а другая - в тупую через два цикла. Потом они сравниваются. Суть в том, что если взять A = 1, B = 10^7 - не совпадает количество нужным нам чисел (разница была в 1). Стал копать дальше, а код врёт уже после 100.

Answer 4

[Игорь]

Правильно ли я понял условия задачи?

Выдается произвольный диапазон, например от 2000 до 5000. Нужно для каждого числа, например 2013 сложить цифры, 2 + 0 + 1 + 3 и в случае если полученное число четно, увеличить счетчик на 1 ?

т.е. лобовое решение

1) Цикл: создали массив с данными в заданном диапазоне 2) Цикл: Разобрали числа на составляющие, сложили, разделили на два, определили четное или нет 3) Если четное увеличили счетчик на 1 4) Вывели результат по окончанию работы программы

Самым быстрым будет в данном случае математическое решение без циклов, но школьный ли это уровень?

Comments

[Артем Зинкин]

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