for flooders
:: Главная :: Решения :: Статьи :: Сайт М. Дроздова :: Файловый архив :: Книга по VFP 9 :: Русский Help Online :: OFF-LINE Форум
   Л и с о в о д ы   в с е х   с т р а н,  о б ъ е д и н я й т е с ь !!!  

Список Форумов  :: Игры Разума
   :: Помощь сайту :: 

Максимум суммы
leonid
Автор

Сообщений: 2617
Откуда: Рига
Дата: 21.01.08 13:00:57ОтветитьЦитировать
Задана конечная последовательность чисел. Для удобства использования загоним ее в курсор
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
Откуда: Кишинев
Дата: 21.01.08 15:11:44ОтветитьЦитировать
Без дополнительных пояснений, видимо, не получится. Ну для первого приближения: теоретический максимум n*500, где n - количество взятых чисел. Типа если ну очень повезет.
Ratings: 0 negative/0 positive

Re: Максимум суммы
leonid
Автор

Сообщений: 2617
Откуда: Рига
Дата: 21.01.08 15:17:40ОтветитьЦитировать
Нет, нужно не теоретический, а для совершенно конкретно заданной последовательности, которая получается при запуске приведенного кода.
Ratings: 0 negative/0 positive

Re: Максимум суммы
Prudivus

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

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



Исправлено: Prudivus, 21.01.08 15:27
Ratings: 0 negative/0 positive

Re: Максимум суммы
leonid
Автор

Сообщений: 2617
Откуда: Рига
Дата: 21.01.08 16:09:58ОтветитьЦитировать
Собственно задание - получить результат (число), каким способом - все равно. Если теоретические построения помогут - ради бога. Если программа справится - тоже хорошо.
Ratings: 0 negative/0 positive

Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата: 21.01.08 18:28:05ОтветитьЦитировать
Ну вот решение "в лоб":
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

Сообщений: 32506
Дата: 21.01.08 19:53:10ОтветитьЦитировать
Привет Вадим!

Как я понимаю у тебя частичное решение - для случая отбора именно 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
Откуда: Кишинев
Дата: 22.01.08 08:05:34ОтветитьЦитировать
Привет, Игорь!

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

Re: Максимум суммы
leonid
Автор

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

Re: Максимум суммы
Prudivus

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

Re: Максимум суммы
leonid
Автор

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

Re: Максимум суммы
Prudivus

Сообщений: 4283
Откуда: Кишинев
Дата: 23.01.08 11:45:38ОтветитьЦитировать
Я думаю что уже пора раскрыть секрет фокуса.
Лично я - пас.
Ratings: 0 negative/0 positive

Re: Максимум суммы
Бураков Сергей

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

Re: Максимум суммы
leonid
Автор

Сообщений: 2617
Откуда: Рига
Дата: 24.01.08 09:32:22ОтветитьЦитировать
А нельзя ли пояснить работу данного алгоритма хотя бы на такой простой последовательности -2, -1, -3?
Ratings: 0 negative/0 positive

Re: Максимум суммы
Бураков Сергей

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

Re: Максимум суммы
leonid
Автор

Сообщений: 2617
Откуда: Рига
Дата: 24.01.08 11:48:17ОтветитьЦитировать
Бураков Сергей
Минимум суммы дотигается при m=3. Отсюда - последовательность начинается с 4-го числа, то есть состоит из 0 членов.
Но ведь для этой последовательности как раз очевидно, что максимум суммы равен -1 и достигается при суммировании чисел со второго по второе.
Ratings: 0 negative/0 positive

Re: Максимум суммы
Igor Korolyov

Сообщений: 32506
Дата: 24.01.08 17:20:38ОтветитьЦитировать
Привет Леонид!

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

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


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

Re: Максимум суммы
leonid
Автор

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

Re: Максимум суммы
Prudivus

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

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



Исправлено: Prudivus, 24.01.08 18:03
Ratings: 0 negative/0 positive

Re: Максимум суммы
Igor Korolyov

Сообщений: 32506
Дата: 24.01.08 20:14:25ОтветитьЦитировать
Привет Леонид!

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

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: 19 Simple777 dimuhametov  and Guests: 17


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