Версия для печати темы

Автор: AND 11.10.2008 21:55

Да, задача скорее математическая, НО решение предполагается выполнить в Паскале.
Задано некоторое число - N. Пусть число (2N) - число цифр(разрядов) в числе. Необходимо найти количество "счастливых номеров" (номеров, где сумма цифр правой части = сымме цифр левой) от 0 до 10N-1 (понятно - в числах с N разрядами, включая нули в начале). Методом перебора такая задача не решается - это очевидно (можно прикинуть сколько времени будет считаться ответ, если N=1000).
Что я надумал. Рассмотрим 1 часть числа (например правую). Сумма цифр там будет принадлежать промежутку (0; 9N). Каждое целое значение из этого промежутка можно разложить на сумму в левой части определённым количеством раз. Сумма возможных вариантов разложения всех чисел промежутка и будет ответом на поставленный вопрос. Логично?
Что касается разложений. Зависимость количества его вариантов от суммы при изменении N меняется (при N=2 прямо пропорционально, при N>2 уже по другим законам, из графика с моими знаниями ничего не понятно, единственное что следует из графика - то что он симметричен относительно 9N/2).
С другой стороны я раскладывал числа и заметил сходство с треугольником Паскаля - число разложений для каждой суммы равно в треугольнике сумма=номер строки, а N=номер столбца. Например для N=3 (1,3,6,10,15,21,28...), для N=4 (1,4,10,20,35,56....). Для перехода от треугольника к формулам пришлось вспомнить комбинаторику, а именно бином Ньютона. И вот на этом месте я застрял. Вроде как даже получается осмысленная сумма перестановок ©, но ни к чему, что можно было бы представить в паскале, я не пришел.
Кто что может предложить? И, возможно есть еще пути решения?

Автор: volvo 11.10.2008 22:33

Велосипед изобретаешь? http://kvant.mirror1.mccme.ru/1976/12/eshche_raz_o_schastlivyh_bilet.htm - там есть рекуррентное соотношение... Дальше справишься?

Автор: AND 11.10.2008 23:34

Цитата(volvo @ 11.10.2008 19:33)