Алгоритм подсчета счастливых чисел

← →
V-Isa (2004-02-12 16:40) [0]

Привет мастера!
Есть задача...
Необходим алгоритм поиска за очччень короткое время количества счастливых чисел введенного диапазона. Счастливым считается число, сумма цифр которого слева равна сумме цифр справа...
Напр., 123006 - счастливое.
Результатом должно быть кол-во счастливых чисел от 0 до указанного пользователем числа...

← →
Sandman25 (2004-02-12 16:42) [1]

И в чем проблема? В переводе в строку? В нахождении длины числа? В суммировании?

← →
Тимохов (2004-02-12 16:44) [2]

Наверное, короткое время проблема.
Думаю, перебор форева.

← →
Sandman25 (2004-02-12 16:44) [3]

Хотя, наверное, лучше рассчитывать последнюю цифру, исходя из "счастливости"

← →
V-Isa (2004-02-12 16:50) [4]

Нужно посчитать кол-во счастливых чисел в заданном диапазоне, причем не перебором!!!

← →
Тимохов (2004-02-12 16:51) [5]

> , причем не перебором!!!

Это вы сами придумали или в иходном задании из задачника такое условие?

← →
V-Isa (2004-02-12 16:52) [6]

Сам придумал, просто оччень нужно. Перебор не подойдет, так как в числе может быть до 20 разрядов и более...

← →
Sandman25 (2004-02-12 16:55) [7]

[6] V-Isa © (12.02.04 16:52)

Для 20 разрядов есть как минимум 10^10 степени счастливых чисел, в которых левая часть равна правой. Вы уверены, что все они нужны? :)

Если известна разрядность, то можно организовать вложенные for.
Если неизвестна, то можно рекурсией.

← →
MBo (2004-02-12 16:56) [8]

для шестизначных
тупой перебор:~1000000 операций
умный перебор: ~1000 операций
применение школьной математики: 100 операций

← →
V-Isa (2004-02-12 16:57) [9]

Раскажите подробнее... пожалуйста...

← →
Sandman25 (2004-02-12 16:59) [10]

[8] MBo © (12.02.04 16:56)

Упс, не заметил, что нужно только количество чисел, а не сами числа :)

← →
MBo (2004-02-12 17:00) [11]

Задача предназначена для того, чтобы человек сам подумал, и чему-то научился. Для реализации 2-го варианта достаточно элементарной логики.

← →
Palladin (2004-02-12 17:49) [12]

Эта задача была в колледже где я проходил "обучение", дяди и тети по 20-25 лет возмущались: "Зачем такие сложные задания на курсовик!", "А что нибудь попроще можно?". Это был третий курс и я оттуда ушел через три дня после поступления. Обкакав преподов студентов и прочих прочих прочих...

> V-Isa © (12.02.04 16:57) [9]

ты хочешь быть похожим на этих дяденек и тетенек?

← →
Uncle_Archi (2004-02-13 00:56) [13]

Ну вы блин даёте.... (с)
2MBo
Чё за умный перебор ?
Если не ошибаюсь, то он хочет решить: http://acm.timus.ru/problem.aspx?space=1&num=1044&locale=ru или нечто подобное...
"Умный перебор"... если точнее динамика...
А всё-таки должна быть формула... Влом думать...

← →
MBo (2004-02-13 07:36) [14]

>Uncle_Archi
Да, задача из таких, что любят на ACM задавать - простейший алгоритм очевиден, но по времени не проходит.

>Чё за умный перебор ?
Перебирается половинка.

← →
DDA (2004-02-13 11:40) [15]

55252

← →
Думкин (2004-02-13 12:25) [16]

> [15] DDA © (13.02.04 11:40)

> Необходим алгоритм поиска за очччень короткое время количества счастливых чисел введенного диапазона.

f(i)=?

← →
Думкин (2004-02-13 12:31) [17]

В этой связи - число 55655 - какое?

← →
Alex_Bredin (2004-02-13 14:25) [18]

> >Чё за умный перебор ?
> Перебирается половинка.

имхо,от перебора тут никуда не деться,если нет выражения общего члена последовательности "счастливых" чисел, хотя бы для фиксированного числа разрядов.

← →
MBo (2004-02-13 14:31) [19]

>от перебора тут никуда не деться,
Есть куда деться ;)
Хинт: Для 6-значного номера цикл выполняется 14 раз

← →
nikkie (2004-02-13 14:35) [20]

перебор не нужен - ведь нужно только количество счастливых билетов, а не их список. я бы сделал так:

пусть N(s,n) - количество n-значных чисел, сумма цифр которых равна s.
N(s,n) может быть найдена из рекурентного соотношения
N(s,n) = \sum_{i=0}^9 N(s-i, n-1)
и начального условия N(s,0) = 1 для s=0 и N(s,0) = 0 для s<>0

количество счастливых билетов с 2n цифрами равно
\sum_{s=0}^{9*n} N(s,n)^2

← →
MBo (2004-02-13 14:43) [21]

>nikkie
Ну вот, блин, теперь у всех олимпиадников ACM программа тест скорости пройдет ;)))

← →
Думкин (2004-02-13 14:49) [22]

> [19] MBo © (13.02.04 14:31)
> [20] nikkie © (13.02.04 14:35)

Это все понятно. Но..
> Результатом должно быть кол-во счастливых чисел от 0 до указанного пользователем числа...

Ведь тут вопрос. А когда мы применяем "умный" алгоритм мы теряем его ограничение на "указанное пользователем".
И опять же. Про те что съесть в автобусе - знаем, пишут 006033 - счстливый, а в данной постановке как? Что слева, а что справа?

Или здесь есть что-то еще?

← →
MBo (2004-02-13 15:00) [23]

>Думкин
Честно говоря, на "указанное пользователем" я не обратил внимания ;(
Однако перебор половинок к этому ограничению адаптируется без труда, а, возможно, и комбинаторно-рекуррентный метод тоже.

← →
nikkie (2004-02-13 15:14) [24]

>MBo
извиняюсь, я думал, та задача прошла в 2000-м году. да и сейчас, по ссылкам тыкаясь на http://acm.timus.ru/ , я не вижу, чтобы был какой-то конкурс.

← →
nikkie (2004-02-13 15:17) [25]

>а, возможно, и комбинаторно-рекуррентный метод тоже.
адаптируется-адаптируется. если автору надо, могу объяснить как. только мне кажется, что
>до указанного пользователем числа
это просто неаккуратность в формулировке.

← →
MBo (2004-02-13 15:28) [26]

>nikkie
Да это было в порядке ;)
;)

Есть несколько задача на эту тему:
1. Количество сч. билетов из 2N цифр (N-небольшое)
2. Количество сч. билетов из 2N цифр в рулоне, оборванном на числе M - здесь это, видимо и имелось в виду
3. То же, что и 1, но N может быть велико (сотни)(требуется длинная арифметика)

← →
Sandman25+1 (2004-02-13 16:49) [27]

А слабо эту задачу на SQL решить? :)

← →
DDA (2004-02-13 17:42) [28]

У меня тут книжечка завалялась "Занимательно о физике и матемитике" Ну дак вот ,Тут как раз про ваши счастливые билеты рассказано.Правда только про шестизначные , но суть будет ясна как подсчитывать.Предлагаю текст рассказа в оригинале,если дочитаете до конца :) :
------------------------
РАЗГОВОР В ТРАМВАЕ
А. П. Савин, Л. М. Финк
Я ехал по Ленинграду в трамвае со своим племянником Мишей. Опустив в кассу 6 копеек, я оторвал два билета.
— Чур, этот билет мой! — сказал Миша.
— Пожалуйста, бери любой из них. Они ведь совершенно одинаковые, с любым из них можно проехать весь маршрут.
— Одинаковые, да не совсем. Этот билет самый обыкновенный, на нем номер 286 357. А следующий билет с номером 286 358—«счастливый», сумма первых трех цифр совпадает с суммой последних трех.
Тут я вспомнил, что уже не раз слышал о распространенном поверье: билет с одинаковыми суммами цифр приносит счастье. В данном случае Мише достался билет 286 358, в котором 2+8+6=3+5+8.
— И часто тебе попадаются счастливые билеты? — спросил я.
— Да нет, очень редко. Примерно раз в месяц. А так как я езжу в институт и обратно каждый день, кроме выходных, то, значит, в среднем один счастливый билет приходится на 50 обычных.
— Чепуха, — вмешался один из наших попутчиков. — Я вошел на предыдущей остановке и в той же кассе вытянул тоже счастливый билет — 286 349. Да и сейчас кто-то отрывает билет 286 367, тоже счастливый; скоро появится 286 376, затем 286 385. Так что в каждом десятке билетов есть один счастливый.
— Это не вполне верно, — возразил новый пассажир, оторвавший счастливый билет 286 367. — Ваш
пример ничего не доказывает. В следующем десятке будет еще один счастливый билет — 286 394, а затем счастливых билетов долго не будет, вплоть до номера 286 439, так что здесь между двумя счастливыми билетами будет интервал в 45 билетов. Таких примеров можно привести много. В этой же катушке билетов, начальные цифры которых 286, между билетами 286 097, и 286169, то есть среди 71 билета, нет ни одного счастливого.
— Вот я и говорю, — подхватил Миша, — в среднем один счастливый билет попадается на полсотни.
— Это тоже опрометчивое заявление,. — заметил я. — Чтобы правильно ответить на этот вопрос, нужно его исследовать. А сначала нужно точно его сформулировать. Скажем, так: сколько существует счастливых шестизначных чисел от 000000 до 999999, то есть чисел, у которых равны суммы первых трех и последних трех разрядов?
— Ну что же, — сказал Миша после недолгого размышления, — я сейчас не могу точно ответить на этот вопрос, но могу описать способ, позволяющий его решить, по крайней мере, в принципе. Выпишем подряд все числа от 000000 до 999 999 и проверим каждое из них. Таким образом мы сможем пересчитать число счастливых билетов.
— Да, такой метод решения возможен. Он называется методом перебора. Им можно решать задачи, в которых исследуются свойства конечного набора каких-либо чисел или других объектов. Однако метод перебора имеет два недостатка. Прежде всего, он очень трудоемок. Рассуди сам, необходимо проверить миллион чисел. Если на проверку каждого из них тратить всего 1 секунду, то потребуется 1000000 секунд, то есть почти 278 часов. При восьмичасовой ежедневной работе это займет 35 дней.
— Но ведь можно поручить это электронной вычислительной машине!
— Можно, конечно, но стоит ли палить из пушек по воробьям? Кроме того, метод перебора имеет и другой недостаток, который сохраняется и при расчете на ЭВМ. При переборе получается решение только одной конкретной задачи, которое обычно
не позволяет произвести обобщения или вскрыть какие-либо неизвестные закономерности. Поэтому-то переборные методы решения в известном смысле неинтересны.
— Разрешите мне опять вмешаться в ваш разговор, — сказал обладатель счастливого билета 286 367. — Я заинтересовался вашей задачей и уже нашел ее решение, правда, не точное, а приближенное, вернее, то, что мы, математики, называем оценкой. Да, я не представился, зовут меня Георгий Владимирович, я доцент кафедры математики одного из технических вузов. Так вот, молодой человек, — обратился он к Мише, — давайте введем новое определение счастливого билета или лучше введем новый термин, например, красивый билет. Будем называть билет красивым, если сумма первых трех цифр дает тот же остаток при делении на 9, что и сумма следующих трех цифр. Понятно?
— Понятно, — ответил Миша, — но почему именно на 9?
— А потому, что в нашей десятичной системе счисления всякое число дает тот же остаток при делении на 9, что и сумма его цифр. Это свойство дает возможность легко найти число красивых билетов. Действительно, среди чисел от 1 до 999 ровно 111 дают при делении на 9 остаток 1, столько же остаток 2 и так далее.
Сколько же существует различных красивых чисел с остатком 1? На первом месте может стоять 111
чисел и. за каждым из них следом можно поставить любое из тех же 111 чисел. Таким образом, получаем
111 • 111 = 12 321 красивых билетов с остатком 1. Такое же число красивых билетов дают остатки 2, 3 и так далее. А к числам с остатком 0 или, как мы привыкли говорить, делящимся без остатка, нужно еще прибавить число 000, поэтому их будет не 111, а 112, откуда следует, что красивых чисел с остатком 0 будет
112 • 112 = 12 544. Итак, всего красивых чисел будет 8 • 12 321 + 12 544 = = 111112.
— А при чем же здесь счастливые билеты? — спросил Миша.
— Это уже совсем просто! Ведь если равны суммы цифр, то равны и их остатки при делении на 9, следовательно, каждый счастливый билет является красивым. Однако не всякий красивый билет будет счастливым. Например, билет 100748 будет красивым, но не будет счастливым. Итак, если обозначить число счастливых билетов Через С, то можно написать неравенство
С< 111 112.
— Но это все-таки не полное решение задачи,— сказал Миша.
— Мы получаем, что счастливых билетов меньше 111112, но не знаем
To by continue

← →
DDA (2004-02-13 17:43) [29]

Continue
----------------------
на сколько. А можно ли показать, что их больше какого-то числа? Я слышал, что это называется оценкой снизу.
— Можно дать и оценку снизу,— ответил Георгий Владимирович,— боюсь только, что она будет довольно грубой. Назовем прекрасными билетами такие, у которых номер состоит из двух совершенно одинаковых половинок, например 287 287. Таких билетов ровно 1000, а именно, 000000, далее 001001, 002 002, ... до 999999. Прекрасных билетов, естественно, меньше, чем счастливых, поэтому мы можем записать такую оценку:
1000
111112.
Здесь оценка сверху более чем в 100 раз превышает оценку снизу, так что вряд ли такой результат можно считать решением поставленной задачи.
— Пожалуй, оценку сверху можно несколько улучшить,— сказал я,— используя признак делимости на 11.
— Что это за признак? — спросил Миша.— Мы его не проходили.
— Он очень прост. Сложим все цифры, стоящие в нечетных разрядах, потом отдельно сложим числа, стоящие в четных разрядах. Так вот, если разность полученных сумм делится на 11, то и все число делится на 11, и наоборот, любое число, делящееся на 11, обладает этим свойством.
— Какое же отношение этот пример имеет к счастливым билетам? — удивленно спросил Миша.
— Самое прямое, но скажи сначала, слышал ли ты о билетах, «счастливых по-московски»?
— Ах да! Москвичи считают билет «счастливым», если сумма цифр, стоящих на четных местах, равна сумме цифр, стоящих на нечетных местах. Вот чудаки!
— Во-первых, чудаком являешься ты, если веришь, что «счастливые» билеты могут приносить удачу, а во-вторых, москвичи называют «счастливыми» те же самые билеты, что и ленинградцы, а билеты, которые мы называем «счастливыми по-московски», они называют «счастливыми по-ленинградски». Так, «американские» горки в Америке называют «русскими». Но не в этом дело. Совсем легко проверить, что номера билетов, которые ты называешь «счастливыми по-московски», делятся на 11. Верно?
— Верно,— ответил Миша.
— И этих билетов не больше, чем чисел от 0 до 999999, делящихся на 11.
— То есть не больше 90910! — воскликнул Георгий Владимирович.
— А каких билетов больше,— спросил Миша,— просто счастливых или счастливых по-московски?
— Совсем нетрудно установить, что одних столько же, сколько и других,— ответил я.
— Скажете тоже, «нетрудно»,— хмыкнул Миша,— мы же не знаем, сколько тех и других.
— А это и не нужно,— заметил Георгий Владимирович.— Расставь первые три цифры «счастливого» билета на четные места и ты получишь из счастливого билета билет, счастливый по-московски. И обратно, если у билета, счастливого по-московски, собрать все цифры, стоящие на четных местах, в первой половине номера, а остальные — во второй, то ты получишь счастливый билет. Таким образом, мы установили взаимно однозначное соответствие между теми и другими билетами. А отсюда следует, что их одинаковое количество. Верно?
— Верно! — воскликнул Миша.— Вот здорово! Значит, мы доказали, что счастливых билетов меньше, чем 90 910.
— А какова будет сумма цифр у номера, если в счастливом билете заменить три последние цифры на разности между 9 и этими цифрами? — спросил Георгий Владимирович.
— Сейчас,— задумался Миша,— та-а-к, ... трижды девять — двадцать семь... минус... плюс... Получается 27! А ведь опять получается взаимно однозначное соответствие! Георгий Владимирович, отсюда следует, что счастливых билетов столько же, сколько билетов с суммой цифр 27.
— Правильно,— ответил он.
— Но сколько же все-таки счастливых билетов? — взглянув на меня, спросил Миша.
— Ответ я тебе скажу сейчас: 55 252, то есть в среднем каждый 18-й билет счастливый. А почему их столько, я расскажу тебе как-нибудь в следующий раз. Прощайся с Георгием Владимировичем и пойдем — нам пора выходить.

Алгоритм подсчета счастливых чисел Найти похожие ветки