Разложение числа на слагаемые

Сейчас на форуме: UniSoft, laslo, bartolomeo (+5 невидимых)

Посл.ответ	Сообщение
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 12 сентября 2011 20:26 · Поправил: Isaev · Личное сообщение · #1 Тривиальная задача, одно из решений в аттаче (с рекурсией) Проблема в том, что оно работает долго! Каким образом: 1. уйти от рекурсии 2. от использования глобальных переменных В идеале разложение вообще не требуется и возможно существует просто формула нахождения кол-ва возможных вариантов, но я её не нашёл. По формулам комбинаторики, возможно можно вычислить достаточно быстро... Этот пример n(100)=190569292 считает у меня 02 min 33 sec 110 msec n(200) страшно запускать 1af8_12.09.2011_EXELAB.rU.tgz - Unit1.pas ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Kiev78 Ранг: 67.4 (постоянный), 6thx Активность: 0.05↘0 Статус: Участник	Создано: 12 сентября 2011 20:31 · Поправил: Kiev78 · Личное сообщение · #2 ---
vptrlx Ранг: 56.1 (постоянный), 9thx Активность: 0.04↘0 Статус: Участник	Создано: 12 сентября 2011 20:49 · Личное сообщение · #3 Хоть бы сказал, что нужно. Если количество способов разбить число на слагаемые с учётом порядка, то ответ 2^(n-1) <записываем n единичек, между некоторыми ставим плюсики>. Если без учёта, то тут я умею только предлагать динамику d[n][k] = количество способов представить число n в виде суммы чисел, каждое из которых <= k. тогда d[n][k] = d[n-k][k] + d[n][k-1] (так как мы либо используем хотя бы одно число k в разложении, либо нет)
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 12 сентября 2011 20:53 · Поправил: Isaev · Личное сообщение · #4 Kiev78 "Является одним из самых быстрых известных алгоритмов для факторизации больших чисел" Это как-то не в тему вроде совсем ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 12 сентября 2011 21:00 · Поправил: Isaev · Личное сообщение · #5 vptrlx Не то, не то... n(100)=190569292 это я дал для проверки... т.е. программа выше работает правильно, но медленно во-первых из-за рекурсии, во-вторых из-за формирования самих последовательностей, что в общем и не требуется 2^(n-1) - явно не катит vptrlx пишет: d[n][k] = количество способов представить число n в виде суммы чисел, каждое из которых <= k. Я бы сказал нужно: количество способов представить число n в виде суммы чисел, каждое из которых <= n 1+2+3 и 1+3+2 не считаются за разные варианты, т.к. имеют одинаковые слагаемые ps: скомпилил для тех, у кого нет delphi 9453_12.09.2011_EXELAB.rU.tgz - test.exe ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
vptrlx Ранг: 56.1 (постоянный), 9thx Активность: 0.04↘0 Статус: Участник	Создано: 12 сентября 2011 23:13 · Личное сообщение · #6 Isaev пишет: d[n][k] = количество способов представить число n в виде суммы чисел, каждое из которых <= k. Я бы сказал нужно: количество способов представить число n в виде суммы чисел, каждое из которых <= n1+2+3 и 1+3+2 не считаются за разные варианты, т.к. имеют одинаковые слагаемые ответ d[n][n]. Ваш К.О. ;)
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 13 сентября 2011 01:55 · Личное сообщение · #7 vptrlx пишет: ответ d[n][n]. Ваш К.О. ;) а код можно? ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
tundra37 Ранг: 310.8 (мудрец), 29thx Активность: 0.43↘0 Статус: Участник	Создано: 13 сентября 2011 15:47 · Личное сообщение · #8 Isaev Пошукай форум на sources.ru Там недавно решали проблемы "размена денег".
negoday Ранг: 21.5 (новичок), 9thx Активность: 0.02↘0 Статус: Участник	Создано: 13 сентября 2011 16:27 · Поправил: negoday · Личное сообщение · #9 Isaev Я очень плохо учился в школе по математике, но попробовав твою тулзу и вбив туда числа от 1 до 10 как-то интуитивно представил себе график функции примерно такой (см. аттач). Точно помню, что такие в школе решали. Причём ещё точнее помню, что график зеркалился в отрицательную сторону осей и было это всё безобразие как-то связано с тангенсами-катангенсами, синусами косинусами что-ли, но тут я увы точно могу ошибиться. Надеюсь мои убогие воспоминания школьных лет натолкнут тебя на верный путь Посмотри прогу под названием Universal mathematic resolver (UMS) - универсальный математический решатель - я как-то своему сыну скачивал - там были эти графики - сейчас тулзы под рукой нет. Добавлено позже: кажется нашёл - это называется степенная функция y=x в степени a. Степень a может варьировать и в зависимости от неё получается разный график. В твоём случае a либо натуральное число либо простая дробь типа 3\4 2\3 и т.п. Вот тут документъ: --> Link <-- страница 2-4. 63a1_13.09.2011_EXELAB.rU.tgz - n(x).JPG
tundra37 Ранг: 310.8 (мудрец), 29thx Активность: 0.43↘0 Статус: Участник	Создано: 13 сентября 2011 17:04 · Личное сообщение · #10 http://forum.sources.ru/showtopic=49720&st=0 Алгоритм от trainer самый быстрый \| Сообщение посчитали полезным: Isaev
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 13 сентября 2011 18:02 · Личное сообщение · #11 tundra37 пишет: Алгоритм от trainer самый быстрый на счёт самый быстрый, это я ещё погоняю... там писали, что он только из-за вывода самый быстрый, а вывод мне не нужен, за ссыль спс, я как-то не вышел на этот форум ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
depler Ранг: 247.7 (наставник), 3thx Активность: 0.16↘0 Статус: Участник Халявщик	Создано: 13 сентября 2011 21:21 · Поправил: depler · Личное сообщение · #12 Ну первое что в голову приходит - делаем так (если тебе вывод не важен): //Application.ProcessMessages; и получаем: n(100)=190569292 Time: 00:00:15.649 это Core2Duo 2.53GHz А если вывод все же нужен пиши сначала в память, а как алго отработает - выводи ----- Лень - это подсознательная мудрость
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 13 сентября 2011 21:39 · Личное сообщение · #13 tundra37 пишет: Алгоритм от trainer самый быстрый цитата из итогов соревнования в приведенной ветке "самый быстрый алгоритм у tserega" особенно для больших чисел ----- 127.0.0.1, sweet 127.0.0.1
vptrlx Ранг: 56.1 (постоянный), 9thx Активность: 0.04↘0 Статус: Участник	Создано: 13 сентября 2011 22:42 · Личное сообщение · #14 хакеры, блин. 0 секунд: Code: #include <iostream> using namespace std; __int64 d[1000][1000]; int main() { int n; cin >> n; d[0][0] = 1; for (int i = 1; i <= n; ++i) d[0][i] = 1, d[i][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) d[i][j] = d[i-j][j] + d[i][j-1]; for (int j = i+1; j <= n; ++j) d[i][j] = d[i][j-1]; } cout << d[n][n]; cin >> n; } \| Сообщение посчитали полезным: Isaev, uinor
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 14 сентября 2011 01:53 · Поправил: Isaev · Личное сообщение · #15 vptrlx круто по времени, только памяти жрёт слишком много вариант предложенный tserega экономнее по памяти, но работает намного дольше... выделять почти гиг для простой операции это кощунство (особенно, когда её всего гиг) ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
vptrlx Ранг: 56.1 (постоянный), 9thx Активность: 0.04↘0 Статус: Участник	Создано: 14 сентября 2011 08:50 · Личное сообщение · #16 гиг? 1000*1000 int64 это 64 000 000 бит, то есть 8 Мб. И это с запасом, так как для n = 100 нужен массив 101 x 101, а не 1000 x 1000, и можно не int64, а просто int
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 14 сентября 2011 17:40 · Личное сообщение · #17 vptrlx мне просто надо n[15000], потому и гиг... и конечно длинную арифметику прицеплю, ещё дольше станет. т.к. от n[127] уже 64 бита переполняются ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
yagello Ранг: 72.1 (постоянный), 30thx Активность: 0.05↘0 Статус: Участник	Создано: 14 сентября 2011 21:18 · Личное сообщение · #18 Isaev пишет: мне просто надо n[15000] Если не секрет - зачем? Какое практическое применение от этой мега-процедуры будет?
vptrlx Ранг: 56.1 (постоянный), 9thx Активность: 0.04↘0 Статус: Участник	Создано: 14 сентября 2011 21:40 · Личное сообщение · #19 ну от 127, положим, ещё не переполняется, вроде бы, но не суть. а так, ну найди себе своп на несколько гигабайт, если очень надо. если очень хочется, чтобы работало и там, где нету нескольких гигабайт, то предподсчитай и забей константы. Благо для всех k <= n d[k][k] = ответ для k. более оптимального решения afair нету. эта динамика по памяти ну никак не оптимайзится

Для печати