кто подскажет?

← →
problemmmm (2007-10-12 11:57) [0]

Доброго времени суток.
N<=10000000
Нужно найти количество чисел от 1 до N имеющих сумму цифр M.
Куда копать то хоть? :(

← →
stone © (2007-10-12 12:01) [1]

в сторону перподавателя
... или военкомата, в зависимости от ситуации

← →
problemmmm (2007-10-12 12:03) [2]

а если серьезно, не надоело стебаться?

← →
Игорь Шевченко © (2007-10-12 12:04) [3]

> а если серьезно

а откуда задача возникла ?

← →
KSergey © (2007-10-12 12:04) [4]

А нужно "по-умному" или лишь бы как?

← →
problemmmm (2007-10-12 12:07) [5]

мне решение не нужно, мне нужно объяснение...
Ну ничего в голову не приходит.
Решаю для себя.
Задача с тимуса

← →
stone © (2007-10-12 12:11) [6]

> problemmmm (12.10.07 12:03) [2]
> а если серьезно, не надоело стебаться?

Не надоело. Это ж такое удовольствие в пятницу :)

> мне решение не нужно, мне нужно объяснение...
> Ну ничего в голову не приходит.

если

> от 1 до N

то сюда в первую очередь войдут попарно все числа от 1 до М-1
т.е 1 и M-1, 2 и М-2 и т.д

если количество чисел, составляющих в сумме М может быть любое, то алгоритм усложняется.

← →
Плохиш © (2007-10-12 12:14) [7]

> problemmmm (12.10.07 12:03) [2]
> а если серьезно, не надоело стебаться?

Сначала ответь что тебе не даётся, перебор чисел, нахождение цифр в числе, суммирование?

← →
problemmmm (2007-10-12 12:26) [8]

Перебор, в тупую перебирать все числа, точно не годится, я так думаю, уж слишком много времени это занимает...
Перебор не знаю как "рационально" организовать

← →
Azize © (2007-10-12 12:37) [9]

> problemmmm (12.10.07 12:26) [8]

придумай какую нибудь эвристику
потом перебор нужно делать не от 1 до N а от М до N
Примеры эвристики
1. Если неполная сумма цифр N>M, то дальнейшее вычисление суммы цифр числа нет необходимости делать
2. Начинать считать сумму с первых разрядов при превышении суммы цифр, пропускать все числа до смены разряда в котором произошло превышение

← →
Сергей М. © (2007-10-12 12:45) [10]

> Нужно найти количество чисел от 1 до N имеющих сумму цифр M.

Пусть M = 5

Тогда

Количество = 1 (5)
Количество = 2 (1 + 4 = 2 + 3)

И какое из этих "количеств" тебя интересует ?

← →
Думкин © (2007-10-12 13:29) [11]

> Сергей М. © (12.10.07 12:45) [10]

Ты о чем?

Числа до 100, сумма цифр 5.

5, 14,23,32,41,50.

Возможных чисел не так уж много - порядка 10*lg(n). Для чисел до 1000 всего 28 ячеек со значениями сумм цифр и далее растет не так уж быстро. Отсюда и ключ к решению надо искать.

← →
Сергей М. © (2007-10-12 13:44) [12]

> Думкин © (12.10.07 13:29) [11]
> Ты о чем?

Я о некорректности самой постановки задачи.

← →
Думкин © (2007-10-12 13:47) [13]

> Сергей М. © (12.10.07 13:44) [12]

Да, И в чем же она выражается? Некорректность только в том, что не указана система счисления.

← →
Azize © (2007-10-12 14:15) [14]

Задача проста
Выражаешь N через массив разрядов
X- число перебора также, а дальше

> Azize © (12.10.07 12:37) [9]

и никаких проблемм, бымтро и эффективно

← →
Думкин © (2007-10-12 14:36) [15]

> Azize © (12.10.07 14:15) [14]

Может это и быстро и эффективно, только ни разу не понятно что делать.
Надо заполнять таблицы - количество чисел дающих суммы от 0 до 9*К для чисел от 0 до 10^K-1. Причем К берется как максимальное такое, что 10^K<N. А дальше дело техники. Таблицы заполняются очень быстро, даже для больших чисел.

← →
Думкин © (2007-10-12 14:38) [16]

и надо для всех К меньше К так. :))

Задача несложная, только с другой стороны надо зайти
Намек - составлять M как сумму набора чисел 1..9

Вота. Делал рекурсией. Правда числа иногда повторяются, ну да отсортировать это не проблема.
http://webfile.ru/1554567
Это екзешник. Исходник немного кривоват, щас причешу малость и тоже выложу.

← →
problemmmm (2007-10-12 15:34) [20]

Все, я понял :)
Спасибо :)
2mbo, отдельное спасибо :)

> problemmmm (12.10.07 11:57)

Прямой перебор спасет тебя.
Цикл не очень большой.

← →
problemmmm (2007-10-12 17:23) [22]

Такс...
Есть набор цифр, от 0 до 9.
Есть массив из 10 елементов, где 1ый элемент обязательно либо 1 либо 0 (т.к. число до 1000000000).
Нужно перебрать все возможные способы заполнения массива цифрами. И подсчитывать сумму.
Все ли верно?

> Сергей М. © (12.10.07 14:45) [18]

Бывает. :) А то я и смотрю - что-то ты не про то говоришь. :)

> problemmmm (12.10.07 17:23) [22]

Не так. Я же русским по белому прописал.
Вот смотори: Допустим число до 100 и сумма 50. Ясно что таких нет. Почему? Потому что максимум - 18(99 дает). Следовательно всего 19 ячеек. Для 999 - 28. И т.д. Растет не быстро. Последующие таблицы заполняются на основании предыдущих.
Поэтому ответ для чисел вида степень 10 минус 1 все совсем просто - для любого числа скажем таким образом. Тонкость появляется лишь если числа имеют другой вид. Но там ничуть не сложнее. Для того и голова, чтобы не только в нее кушать.

Задача имеет общую базу с задачей про счастливые билеты.

кто подскажет? Найти похожие ветки