Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Задана конечная последовательность чисел. Для удобства использования загоним ее в курсор
|
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Без дополнительных пояснений, видимо, не получится. Ну для первого приближения: теоретический максимум n*500, где n - количество взятых чисел. Типа если ну очень повезет. ;)
|
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Нет, нужно не теоретический, а для совершенно конкретно заданной последовательности, которая получается при запуске приведенного кода.
|
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Написать программу на фоксе, селект?
Или интересуют теоретические построения? Исправлено 1 раз(а). Последнее : Prudivus, 21.01.08 16:27 |
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Собственно задание - получить результат (число), каким способом - все равно. Если теоретические построения помогут - ради бога. Если программа справится - тоже хорошо.
|
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Ну вот решение "в лоб":
|
Re: Максимум суммы | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Вадим!
Как я понимаю у тебя частичное решение - для случая отбора именно 10 чисел. Надо закрутить ещё один цикл - по этому самому n - от 1 до cnt. Однако оптимальность такого "перебора в лоб" вызывает большие сомнения. Кстати хранить все суммы не требуется, так что вместо заполнения второго курсора и последующего SELECT MAX() сгодится более простой IF m.s > m.GrandTotal m.GrandTotal = m.s ENDIF Найти более интересный вариант поиска пока не могу... ------------------ WBR, Igor |
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Привет, Игорь!
С поправками согласен. Но если принимать буквально условие: Цитата:то цикла по n не нужно, можно сразу брать n=cnt. ;) |
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Привет, Вадим и Игорь!
Вадим, Игорь абсолютно прав, максимумум нужно искать по всем возможным значениям n. Вот это неправильно, поскольку там есть отрицательные числа, то полная сумма может не дать максимума. Например, если взять последовательность -1,1,1,-1, то ответом будет 2 - сумма второго и третьего чисел. Опять же Игорь прав, что полным перебором вряд ли можно воспользоваться - слишком долго считать будет. Задача - найти способ посчитать то же самое побыстрее. Могу сообщить, что у меня xbase-ный способ просчитал примерно за полторы секунды, а SQL-ный примерно за десять. |
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Вопрос: алгориитм как-то связан с особенностями реализации функции rand()? Или можно считать что дан произвольный (случайный) ряд чисел?
|
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Нет, rand() тут совершенно не при чем. Алгоритм для любой последовательности должен работать. |
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Я думаю что уже пора раскрыть секрет фокуса.
Лично я - пас. |
Re: Максимум суммы | |
---|---|
Бураков Сергей Сообщений: 280 Откуда: Calgary Дата регистрации: 07.02.2005 |
Для начала найдем число m такое, что сумма от 1-го до m-го будет минимальна. Если данная сумма отрицательна, то m+1 -е число будет первым числом искомого набора, иначе набор начинается с первого числа. Аналогично, ищем n такое, что сумма от n-го до 1000000-го числа минимальна. Последовательность от m+1 -го до n-1 -го числа и даст максимальную сумму.
|
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
А нельзя ли пояснить работу данного алгоритма хотя бы на такой простой последовательности -2, -1, -3?
|
Re: Максимум суммы | |
---|---|
Бураков Сергей Сообщений: 280 Откуда: Calgary Дата регистрации: 07.02.2005 |
Минимум суммы дотигается при m=3. Отсюда - последовательность начинается с 4-го числа, то есть состоит из 0 членов.
|
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Но ведь для этой последовательности как раз очевидно, что максимум суммы равен -1 и достигается при суммировании чисел со второго по второе. |
Re: Максимум суммы | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
Я представляю процедурный алгоритм так: Идём по последовательности, суммируя числа от базового элемента до текущего (при запуске базовый и текущий - это первый элемент). Запоминаем MAX достигнутую сумму (заодно можно запомнить и номера базового и текущего элемента когда этот MAX случился). Если сумма стала отрицательной - берём за базовый и текущий следующий элемент последовательности. И так до конца. Допущения - в последовательности есть положительные элементы, ИЛИ решение SUM=0, для выборки из 0 элементов (пустой выборки) допустимо. Если это не допустимо - тогда надо добавить предварительный шаг - поиск MAX элемента - если он отрицательный - то он и будет решением. Но вот то что у тебя, как ты намекнул, есть декларативный аглоритм (на SQL-е) - это очень интересно, пока не могу додуматься до такого ------------------ WBR, Igor |
Re: Максимум суммы | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Привет, Игорь!
С первого взгляда показалось, что в алгоритме что-то не так, а со второго, что вроде все в порядке. Вечером сравню результаты, и завтра выложу. У меня алгоритм другой, по крайней мере внешне. SQL-ный вариант - это точно тот же алгоритм, только реализованный на SQL. И я бы не назвал его декларативным, скорее "с использованием процедурных возможностей фоксовского SQL". |
Re: Максимум суммы | |
---|---|
Prudivus Сообщений: 4283 Откуда: Кишинев Дата регистрации: 14.12.2006 |
Можно внести улучшение в алгоритм: если базовый элемент отрицательный, то сразу переходим на следующий. Посмотрел более внимательно и понял что в базовом описании это уже предусмотрено. Исправлено 1 раз(а). Последнее : Prudivus, 24.01.08 19:03 |
Re: Максимум суммы | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Привет Леонид!
Вот реализация.
Чтоб не возникал законный вопрос о "лишнем" действии - последнее сравнение можно и строгим делать (m.CurSum < 0), но тогда будут потенциальные "чересчур длинные" последовательности (те в которых "сбоку" есть кусок с нулевой суммой - ничего не решающий), а так они автоматом вырежутся. ------------------ WBR, Igor |
© 2000-2024 Fox Club  |