Скрыть опции темы

[anatolyArts]

Привет.

Мне нужно решить вот такую задачку:
Есть "треугольник" который строится из двух параметров.
1) Начальное число N
2) Стартовое вычитаемое число s
Строится "треугольник" так: из N вычитаются все натуральные числа от s до 3-х включительно. Из каждого получившегося числа (назовём их N1, N2, ... Nx) снова вычитаются s, но для N=N1 -> s=s, для N=N2 -> s=s-1, для N=N3 -> s=s-2, для N=N4 -> s=s-3, для N=Nx -> s=3. С каждым полученым числом всё повторяется снова пока результат вычитания положителен. Сложно? Смотрите картинку, так понятнее.

SPOILER!

Нужно посчитать:
1) СУММУ всех чисел N
2) Колличество нечётных N

Господа-товарищи программисты, убедительная просьба не беспокоится. Я знаю, что эта задачка решается элэментарной рекурсией в три строчки. И уже это сделал, НО! При N=50000 и s=300 эта рекурсия длится несколько дней. Мне нужно МАТЕМАТИЧЕСКОЕ решение с минимальным вычислением и максимальной скоростью.

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

Это сообщение отредактировал(а) anatolyArts - 04-08-2009, 07:37

[Гордый]

QUOTE (anatolyArts @ 01-08-2009, 14:35)

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

Я насчёт по-флудить... а ты уверен, что эта проблема в математике уже решена? Может нобелевку за это дело положено?

[anatolyArts]

Не знаю как с нобелевкой, но если кто решит - за мной не заржавеет

[Ben]

Есть у мну ректальное впечатление, что решение факториально зависит от параметра Н. Нобелевкой здесь, конечно, не очень пахнет, но какая нить премия в теории чисел - стопудово

[Set]

Рекурсией "в лоб" - там совсем нездоровые числа идут. Пихай сумму N и число нечётных N для каждой ветки в хэш-таблицу по её паре (N, s) - тогда не надо будет просчитывать одно и тоже для одинаковых веток.

[anatolyArts]

Set, я примерно так и делаю. Всё равно очень долго. Параметры всё время разнообразные и таблица в короткий срок сильно разростается. Что не приемлемо в этом случае ибо программа должна влазить в 2-3 килобайта. Поэтому, она(таблица) всё время урезается и содержит только базовые пары. Не сильное ускорение.

[FiL]

QUOTE (anatolyArts @ 01-08-2009, 08:35)

Строится "треугольник" так: из N вычитаются все реальные числа от s до 3-х включительно.

Не, ребята. С такими условиями оно работать не будет. Вычитать все реальные числа из некоего промежутка - это задача не для слабонервных

P.S. А что если S = -1 ?

[anatolyArts]

QUOTE (FiL @ 03-08-2009, 16:00)

Не, ребята. С такими условиями оно работать не будет.

Ну почему же? Вот первый шаг я, можно сказать, сделал: ту часть "треугольника" где числа ещё не отпадают я посчитал. Тут на картинке видно.

SPOILER!

Вертикальная сумма каждого этапа (до начала отпада) равна среднему арифметическому всех чисел этапа умноженному на колличество чисел. По природе "треугольника" чтобы посчитать среднее арифметическое, достаточно вычесть из N среднее число s. 25-((5+3)/2) и так по всем этапам. Колличесто же чисел соответствует диагонали номер s-2 треугольника паскаля.

SPOILER!

Всего "не отпадающих" этапов = N/s. Считается просто и быстро.

НО КАК БЫТЬ ДАЛЬШЕ?!!!!

QUOTE

P.S. А что если S = -1 ?

По определению s >= 3. Я просто забыл сказать.

[dmvn]

Чёрт возьми, зачем называть натуральные числа реальными? Исправьте, плз, а то не по-русски получается.

А задачка интересная. Ща подумаем.

[FiL]

чиста от нечего делать попробовал сохранять результаты от итерационных (рекурсивных) вычислений в массиве. По-простому, без всяких там хеш-функций. Не сильно оптимально по использованию памяти, конечно. Да и с точностью некоторые проблемы, ибо там суммы довольно быстро вылазят за 64 бита. Но (50000, 300) считается за 1 минуту и 6 секунд.

Да, я понимаю, что это далеко не 2-3 килобайта. Это даже не 2-3 мегабайта. Но может стоит табличку статично посчитать и держать в файле? И просто дергать из нее значения...

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

[anatolyArts]

QUOTE (dmvn @ 03-08-2009, 18:53)

Чёрт возьми, зачем называть натуральные числа реальными? Исправьте, плз, а то не по-русски получается.

Спасибо, исправил. Я просто плохо перевёл. Никогда не учил математику по русски.

FiL, это на девелопментовой машине и памяти и скорости хватает. А там где оно бежать будет могут быть проблемы.

Это сообщение отредактировал(а) anatolyArts - 04-08-2009, 07:41

[Enot Pk]

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

Хорошая чесалка для мозгов, подвисают.

[FiL]

Енот,
ну писал я такое. И что? делить-то как раз не сложно.

[Lord KiRon]

FiL
LISP ?

[FiL]

QUOTE (Lord KiRon @ 04-08-2009, 12:22)

FiL LISP ?

не, при чем тут лисп? просто нужна была как-то библиотека для работы с целыми числами произвольной длины. Ну и писал что-то подобное. Умножение, деление... сначала реализовав сложение и вычитание.