|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
19.11.2009, 22:07 | #21 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Выражение (Время: 1 сек. Память: 16 Мб Сложность: 56%) Даны N целых чисел X1, X2, …, XN. Требуется расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому S. Входные данные Входной файл INPUT.TXT в первой строке содержит числа N и S. В следующей строке располагается N чисел, разделенных пробелом. Ограничения: 2 <= N <= 24, 0 <= Xi <= 5*107, -10^9 <= S <= 10^9. Выходные данные В выходной файл OUTPUT.TXT выведите «No solution», если такой результат получить невозможно, иначе выведите получившееся равенство. Если решение не единственное, выведите любое. Сдесь перебор 2 в 23ем вариантов показал на тестировании 0.2 секунды. Вспомнил, что обещал написать код к задаче с этого форума, сел переделывать (ведь переделывать почти готовое решение всегда проще, чем писть с ноля), переделал, вот код: Код:
2. Плюсы. Главный плюс - укладываеться в заявленые для 30 чисел 1 минуту. На моем рабочем компе в фрипаскале 2.сколькототам (влом сейчас лезть и смотреть точную версию) показывает для 30 случайных чисел время от 28.1 до 29.5 в зависимости от количества промежуточных лучших ответов и загружености компа в данный момент. Среднее время по 10 тестах - 28.47 секунды. Вижу места, где можно написать еще оптимальней (писал так, как привык, так как надо было просто, "что бы прошло", можно доделать "так, как лучше" вместо "так, как привычней"). Последний раз редактировалось LeBron; 19.11.2009 в 22:17. |
|
20.11.2009, 00:38 | #22 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
p.s. и ещё, мне кажется, что TC давно потерял интерес к данной теме... |
|
20.11.2009, 00:58 | #23 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
З.Ы. Ну а по поводу ТС - мне как то с самого начала это было не особо важно. Я обычно берусь за задачу, если меня интересует задача. А не тогда, когда во мне вдруг просыпаеться мораль и желание помочь человеку (хм... когда такое в последний раз со мной было?) |
|
21.11.2009, 22:34 | #24 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Приношу свои извинения. код действительно рабочий. всё работает! единственное, Цитата:
но, имхо, это и так достаточно сложная задача, и добавление проверки на наибольшее число слагаемых, явно скажется отрицательно на быстродействии.. p.s. LeBron, а почему Вы так жутко пишете код?! неужели так не лучше/понятнее/нагляднее/проще?!?!? Код:
|
||
21.11.2009, 23:46 | #25 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
По поводу кода - сюда я его бросаю еще довольно красивым, разбивая на блоки "по назначению" и частично выделяя циклы и т.д. Мой рабочий код бывает хоть немного отформатированым только если задача достаточно сложная и я могу в ней запутаться. Если же я, начиная писать код, уже полностью знаю решение "в голове", то использую только обрезание по краю экрана, так мне удобней в том плане, что меньше надо скролить и код больше напоминает "обычный текст". В большинстве случаев у меня нету необходимости, что бы мой код кто-то читал (решаю олимпиадные задачи), поэтому я и не делаю его таким, что бы кому-то было удобно читать. З.Ы. А реализция тупого перебора в этой задаче - еще не самое сложное, главное пряморуко написать. |
|
24.11.2009, 13:22 | #26 |
Регистрация: 12.11.2009
Сообщений: 9
|
чего то я уже не понимаю Вас... и не только Вас..свою идею уже не понимаю.. и сомневаюсь в ней..
все же если перебирать из сортированных чисел - полчится выборка близкая к правде (с учетом epsilon) ..вобщем далеко от правды |
24.11.2009, 16:44 | #27 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Можно математическую модель алгоритма? А то я Вас тоже не особо понимаю, и как-то не верю в полезность последующих попыток понять... А пока нечего анализировать, то и анализироать не получаеться.
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
работа с выборкой | Inveerto | Общие вопросы Delphi | 3 | 10.04.2011 19:32 |
Вопрос с выборкой | MHz | Microsoft Office Access | 2 | 13.11.2008 23:19 |
Помогите с выборкой | VRF | Microsoft Office Excel | 5 | 06.11.2008 01:45 |
Помогите, пожалуйста, с выборкой | Chel | БД в Delphi | 24 | 05.06.2008 05:00 |