|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
17.02.2010, 14:47 | #1 |
Пользователь
Регистрация: 09.12.2009
Сообщений: 20
|
Разбиение числа на слагаемые
Мне недавно попалась задачка про разбиения чила на не повторяющиеся слагаемые. Уже неделю как мучаюсь.. но без толку.. кто-нибудь знает как его решать? формулу-то я знаю.. вот как его применять это неизвестно.
|
17.02.2010, 15:30 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
В чем конкретно задача? посчитать число разбиений? Или найти все разбиения (вывести их, к примеру)? В первом случае формулой или динамикой, во втором я чаще всего пишу циклическую генерацию лексикографически предидущего или лексикографически следующего разбиения (повторять до тех пор, пока возможно, и выводить, что получается).
Какие ограниения?. |
17.02.2010, 18:57 | #3 |
Пользователь
Регистрация: 09.12.2009
Сообщений: 20
|
выводить количество. n может быть от 5ти до 500
|
17.02.2010, 23:04 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Так если у Вас формула, есть, то в чем проблема?
Хотя при 500 даже оптимально написанная кубическая динамика должна проходить в пределах секунды. |
21.02.2010, 19:01 | #5 |
Пользователь
Регистрация: 09.12.2009
Сообщений: 20
|
по времени не совпадает..
а если ввести массив то по памяти не будет совпадать |
21.02.2010, 20:38 | #6 |
Старожил
Регистрация: 26.04.2008
Сообщений: 2,645
|
Ну можно тупо в лоб и сразу на вывод. Памяти не требует, скорость - миллиард за 3 секунды обрабатывает
Код:
|
22.02.2010, 17:24 | #8 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Задачка откуда? И важен ли порядок чисел в разбиении? Если нет - детски простая динамика пишется легко и точно проходит (взгляните на задачу 1017 на Тимусе, я использовал там именно такую динамику, ограничения по времени 1 секунда, по памяти 16 мб, проходит, у меня 1017 C++ Accepted 0.078 2 813 КБ). Если да - надо подумать над более красивым решением, можно просунуть и такое, но его надо будет дописать и доделать в ущерб красоте и простоте. |
|
22.02.2010, 23:56 | #9 |
Старожил
Регистрация: 26.04.2008
Сообщений: 2,645
|
Я что-то не понял? Задача разбить на неповторяющиеся слагаемые. Вводим, например 19. 19=1+2+3+4+9. Всё! 9 не разбить уже, т.к 9 = 1+8 или 2+7 или 3+6 или 4+5.
В count'e количество слагаемых. Зачем динамика? о_О |
23.02.2010, 00:32 | #10 | |||
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Цитата:
Цитата:
И задача не про разбиение, а про разбиения, следовательно, от нас требуется не розбить, а найти количество всех. Согласен, если бы "задача" была именно в выводе одного произвольного разбиения - Ваше решение верное, к нему особых претензий нету. Только тогда это назвать задачей трудновато, так как это кодинговое упражнение. И придумать "формулу" тоже трудно. |
|||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Разбиение на колонки | zenner | Microsoft Office Excel | 13 | 05.10.2009 09:31 |
Разбиение записей | Лубышев | Microsoft Office Access | 0 | 17.03.2009 08:27 |
Все возможные слагаемые | anGeee | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 04.12.2008 20:22 |
Разбиение на части | MAcK | Общие вопросы .NET | 4 | 18.09.2008 13:56 |
Разложение числа на слагаемые | Oleg-vp | Общие вопросы Delphi | 5 | 30.10.2007 10:43 |