:: Игры Разума
Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Задана конечная последовательность чисел. Для удобства использования загоним ее в курсор
LOCAL m.cnt, m.i
m.cnt=1000000
RAND(1)
CREATE CURSOR tmp (f1 N(14,4))
FOR i=1 TO m.cnt
IF i%100=0
WAIT WINDOW ALLTRIM(STR(m.i))+"/"+ALLTRIM(STR(m.cnt)) NOWAIT
ENDIF
INSERT INTO tmp VALUES (round((RAND()-0.5)*1000,4))
NEXT
WAIT CLEAR
Если из заданной последовательности выбрать произвольное количество идущих подряд чисел и проссумировать, получим некое число. Найти максимальное значение, которое это число может принимать.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Без дополнительных пояснений, видимо, не получится. Ну для первого приближения: теоретический максимум n*500, где n - количество взятых чисел. Типа если ну очень повезет. ;)
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Нет, нужно не теоретический, а для совершенно конкретно заданной последовательности, которая получается при запуске приведенного кода.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Написать программу на фоксе, селект?

Или интересуют теоретические построения?



Исправлено 1 раз(а). Последнее : Prudivus, 21.01.08 16:27
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Собственно задание - получить результат (число), каким способом - все равно. Если теоретические построения помогут - ради бога. Если программа справится - тоже хорошо.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Ну вот решение "в лоб":
LOCAL m.cnt, m.i
m.cnt=1000000
RAND(1)
CREATE CURSOR tmp (f1 N(14,4))
FOR m.i=1 TO m.cnt
IF i%100=0
WAIT WINDOW ALLTRIM(STR(m.i))+"/"+ALLTRIM(STR(m.cnt)) NOWAIT
ENDIF
INSERT INTO tmp VALUES (round((RAND()-0.5)*1000,4))
NEXT
WAIT CLEAR
LOCAL n, s, f, l
m.n = 10 && количество "идущих подряд чисел"
m.s = 0 && сумматор
GO TOP IN tmp
m.f = tmp.f1 && значение первого элемента в наборе
* получаем сумму первого набора
FOR m.i=1 TO m.n
GOTO m.i IN tmp
m.s = m.s + tmp.f1
NEXT
m.l = tmp.f1 && значение последнего элемента в наборе
* таблица рассчитанных сумм
CREATE CURSOR tmp2 (f1 N(14,4))
* заполяем её
FOR m.i=2 TO m.cnt - m.n + 1
IF i%100=0
WAIT WINDOW ALLTRIM(STR(m.i))+"/"+ALLTRIM(STR(m.cnt)) NOWAIT
ENDIF
INSERT INTO tmp2 VALUES (m.s)
* расчет i-й суммы
m.s = m.s - m.f
GOTO m.i IN tmp
m.f = tmp.f1 && значение первого элемента в наборе
GOTO m.i+m.n-1 IN tmp
m.l = tmp.f1 && значение последнего элемента в наборе
m.s = m.s + m.l
NEXT
INSERT INTO tmp2 VALUES (m.s)
* считаем максимум
SELECT MAX(f1) FROM tmp2
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Привет, Игорь!

С поправками согласен. Но если принимать буквально условие:
Цитата:
Если из заданной последовательности выбрать произвольное количество идущих подряд чисел и проссумировать, получим некое число. Найти максимальное значение, которое это число может принимать.
то цикла по n не нужно, можно сразу брать n=cnt. ;)
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Привет, Вадим и Игорь!
Вадим, Игорь абсолютно прав, максимумум нужно искать по всем возможным значениям n.
Prudivus
то цикла по n не нужно, можно сразу брать n=cnt. ;)
Вот это неправильно, поскольку там есть отрицательные числа, то полная сумма может не дать максимума. Например, если взять последовательность -1,1,1,-1, то ответом будет 2 - сумма второго и третьего чисел. Опять же Игорь прав, что полным перебором вряд ли можно воспользоваться - слишком долго считать будет. Задача - найти способ посчитать то же самое побыстрее. Могу сообщить, что у меня xbase-ный способ просчитал примерно за полторы секунды, а SQL-ный примерно за десять.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Вопрос: алгориитм как-то связан с особенностями реализации функции rand()? Или можно считать что дан произвольный (случайный) ряд чисел?
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Prudivus
Вопрос: алгориитм как-то связан с особенностями реализации функции rand()? Или можно считать что дан произвольный (случайный) ряд чисел?
Нет, rand() тут совершенно не при чем. Алгоритм для любой последовательности должен работать.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Я думаю что уже пора раскрыть секрет фокуса.
Лично я - пас.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Бураков Сергей

Сообщений: 280
Откуда: Calgary
Дата регистрации: 07.02.2005
Для начала найдем число m такое, что сумма от 1-го до m-го будет минимальна. Если данная сумма отрицательна, то m+1 -е число будет первым числом искомого набора, иначе набор начинается с первого числа. Аналогично, ищем n такое, что сумма от n-го до 1000000-го числа минимальна. Последовательность от m+1 -го до n-1 -го числа и даст максимальную сумму.
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
А нельзя ли пояснить работу данного алгоритма хотя бы на такой простой последовательности -2, -1, -3?
Ratings: 0 negative/0 positive
Re: Максимум суммы
Бураков Сергей

Сообщений: 280
Откуда: Calgary
Дата регистрации: 07.02.2005
Минимум суммы дотигается при m=3. Отсюда - последовательность начинается с 4-го числа, то есть состоит из 0 членов.
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Бураков Сергей
Минимум суммы дотигается при m=3. Отсюда - последовательность начинается с 4-го числа, то есть состоит из 0 членов.
Но ведь для этой последовательности как раз очевидно, что максимум суммы равен -1 и достигается при суммировании чисел со второго по второе.
Ratings: 0 negative/0 positive
Re: Максимум суммы
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Привет Леонид!

Я представляю процедурный алгоритм так:
Идём по последовательности, суммируя числа от базового элемента до текущего (при запуске базовый и текущий - это первый элемент). Запоминаем MAX достигнутую сумму (заодно можно запомнить и номера базового и текущего элемента когда этот MAX случился). Если сумма стала отрицательной - берём за базовый и текущий следующий элемент последовательности. И так до конца.
Допущения - в последовательности есть положительные элементы, ИЛИ решение SUM=0, для выборки из 0 элементов (пустой выборки) допустимо.
Если это не допустимо - тогда надо добавить предварительный шаг - поиск MAX элемента - если он отрицательный - то он и будет решением.

Но вот то что у тебя, как ты намекнул, есть декларативный аглоритм (на SQL-е) - это очень интересно, пока не могу додуматься до такого


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Максимум суммы
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Привет, Игорь!
С первого взгляда показалось, что в алгоритме что-то не так, а со второго, что вроде все в порядке. Вечером сравню результаты, и завтра выложу. У меня алгоритм другой, по крайней мере внешне. SQL-ный вариант - это точно тот же алгоритм, только реализованный на SQL. И я бы не назвал его декларативным, скорее "с использованием процедурных возможностей фоксовского SQL".
Ratings: 0 negative/0 positive
Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата регистрации: 14.12.2006
Igor Korolyov
Идём по последовательности, суммируя числа от базового элемента до текущего (при запуске базовый и текущий - это первый элемент). Запоминаем MAX достигнутую сумму (заодно можно запомнить и номера базового и текущего элемента когда этот MAX случился). Если сумма стала отрицательной - берём за базовый и текущий следующий элемент последовательности.
Можно внести улучшение в алгоритм: если базовый элемент отрицательный, то сразу переходим на следующий.

Посмотрел более внимательно и понял что в базовом описании это уже предусмотрено.



Исправлено 1 раз(а). Последнее : Prudivus, 24.01.08 19:03
Ratings: 0 negative/0 positive
Re: Максимум суммы
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Привет Леонид!

Вот реализация.

LOCAL cnt, i
cnt=1000000
RAND(1)
CREATE CURSOR tmp (i1 I, f1 N(14,4))
FOR i=1 TO m.cnt
IF m.i%100=0
WAIT WINDOW ALLTRIM(STR(m.i))+"/"+ALLTRIM(STR(m.cnt)) NOWAIT
ENDIF
INSERT INTO tmp (i1, f1) VALUES (m.i, round((RAND()-0.5)*1000,4))
NEXT
WAIT CLEAR
LOCAL MaxSum, CurSum, BaseIndex, LastIndex, FirstIndex
CLEAR
SELECT MAX(f1) MaxItem FROM tmp INTO CURSOR MaxItem
MaxSum = MaxItem.MaxItem
IF m.MaxSum <= 0
? "MaxSum = ", m.MaxSum
RETURN
ENDIF
CurSum = 0
BaseIndex = 1
SELECT tmp
SCAN ALL
CurSum = m.CurSum + tmp.f1
IF m.CurSum > m.MaxSum
MaxSum = m.CurSum
FirstIndex = m.BaseIndex
LastIndex = tmp.i1
ENDIF
IF m.CurSum <= 0
CurSum = 0
BaseIndex = tmp.i1 + 1
ENDIF
ENDSCAN
? "MaxSum = ", m.MaxSum
? "FirstIndex= ", m.FirstIndex, "LastIndex = ", m.LastIndex

Чтоб не возникал законный вопрос о "лишнем" действии - последнее сравнение можно и строгим делать (m.CurSum < 0), но тогда будут потенциальные "чересчур длинные" последовательности (те в которых "сбоку" есть кусок с нулевой суммой - ничего не решающий), а так они автоматом вырежутся.


------------------
WBR, Igor
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 2 (Гостей: 2)

© 2000-2024 Fox Club 
Яндекс.Метрика