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

Список Форумов  :: Игры Разума
  

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

Сообщений: 4283
Откуда: Кишинев
Дата: 25.01.08 08:55:10
Маловато будет. Еще одного внутреннего цикла не хватает.
Ratings: 0 negative/0 positive

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

Сообщений: 2718
Откуда: Рига
Дата: 25.01.08 10:37:37
Сейчас нет времени подробно писать. Вобщем, решение такое
s1=-1000  
  s2=-1000  
  SCAN  
  	s2=MAX(f1,s2+f1)  
  	s1=MAX(s1,s2)  
  ENDSCAN  
  ?s1
Вечером напишу подробнее.
Ratings: 0 negative/0 positive

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

Сообщений: 4283
Откуда: Кишинев
Дата: 25.01.08 12:47:40
Prudivus
Маловато будет. Еще одного внутреннего цикла не хватает.
Был неправ. Вспылил. (с)
Все работает, скорость сравнимая. Но, признаться, пока так и не понял почему.
Ratings: 0 negative/0 positive

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

Сообщений: 2718
Откуда: Рига
Дата: 25.01.08 17:45:45
Игорь!

Вчера вечером посмотрел твой алгоритм, и конечно-же и твой и мой алгоритмы по-существу идентичны. Главная разница в том, как объясняется, что полученный результат - это то, что нужно. Попробую более ли менее подробно изложить свои рассуждения.

Хорошей скорости можно достичь, если количество выполняемых действий будет пропорционально N, где N - это число элементов в последовательности (в крайнем случае сошло бы и N*ln(N), но в данном случае у нас получится именно N). Этого можно достичь, если в цикле, который пробегает по всем элементам последовательности, количество выполняемых действий не будет зависеть от n. А этого можно достичь только, если на каждом шаге научиться использовать расчеты, проведенные на предыдущем шаге. Например, допустим мы знаем требуемую сумму для последовательности, состоящей из n элементов, не поможет ли нам эта информация рассчитать требуемую сумму, если к этой последовательности добавить еще один элемент. Как нетрудно догадаться, для новой последовательности эта сумма будет или такой же, или больше. Опять же понятно, что в последнем случае в сумму обязательно будет входить вновь добавленный элемент. Т.е. сумма для последовательности из n+1 элементов будет или равна сумме для последовательности из n элементов, или максимальной сумме элементов, с некоторого элемента и до конца последовательности, собственно нужная сумма будет максимум из этих двух чисел. Жаль только, что для того, чтобы посчитать второе число опять-таки нужно выполнить слишком много вычислений. А нельзя ли и тут попробовать использовать то, что уже вычислено на предыдущем шаге. Допустим, нам известна максимальная сумма с участием последнего элемента для последовательности с n элементами. Оказывается, что для последовательности с добавленным элементом для такой суммы возможны тоже только два варианта: или она будет равна сумме от предыдущей последовательности + последний добавленный элемент, или она будет равна самому последнему добавленному элементу, в зависимости от того, какое из этих двух чисел больше. Получается, что зная две суммы (искомую сумму и такую же сумму с условием включения последнего элемента) для последовательности из n элементов, мы легко и быстро можем найти эти же суммы для последовательности с еще одним добавленным элементом. Поскольку для последовательности, состоящей из одного элемента ити суммы равны самому элементу, то все остальное - дело техники. В результате получаем следующий код
s1=-1000    
    s2=-1000    
    SCAN    
    	s2=MAX(f1,s2+f1)    
    	s1=MAX(s1,s2)    
    ENDSCAN    
    ?s1
Здесь s1 - это текущее значение искомой суммы, а s2 - текущее значение суммы с условием включения последнего элемента.
В SQL-ном варианте у меня этот алгоритм выглядит так
SELECT RECNO() as rn, f1, CAST(0 as N(14,4)) as s1, CAST(0 as N(14,4)) as s2 ;  
  	FROM tmp INTO CURSOR tmp1 READWRITE  
    
  UPDATE tmp1 SET s2=IIF(NVL(t.s2,-1000)<=0,tmp1.f1,t.s2+tmp1.f1), s1=IIF(NVL(t.s1,-1000)<tmp1.s2, tmp1.s2, t.s1) ;  
  	from tmp1 left join tmp1 t on tmp1.rn=t.rn+1  
  SELECT tmp1  
  GO BOTTOM   
  ?tmp1.s1
Ratings: 0 negative/0 positive

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

Сообщений: 4283
Откуда: Кишинев
Дата: 25.01.08 18:01:30
Все равно это фокус. Простота кода восхищает, но объяснения ничего, по сути, не объясняют. По крайней мере для меня.

Леонид, если можно, то же самое, но без лирики и чуть больше математики в доказательстве... Но именно чуть, без фанатизма!
Ratings: 0 negative/0 positive

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

Сообщений: 2718
Откуда: Рига
Дата: 28.01.08 10:28:31
Вот так вот понятней будет?

Пусть задана последовательность
a1, a2, ... aN
Положим
s(k,m)= ak+ ak+1+...+ am, где m Є (1,N), k Є (1,m),
P(m)=Max(s(k,m)) по всем k Є (1,m),
S(m)=Max(P(k)) по всем k Є (1,m).
Тогда, очевидно, что S(1)=P(1)=a1
Далее пойдем по индукции. Предположим, что для некоторого k Є (1,N), P(k) и S(k) уже вычислены и попробуем, зная эти значения, вычислить P(k+1) и S(k+1). Не стану объяснять подробно, но нетрудно понять, что P(k+1) будет равно P(k)+ ak+1, если P(k)>0, и будет равно ak+1, если P(k)<=0, а это то же самое, что P(k+1)=Max(P(k)+ ak+1, ak+1). А из определения видно, что S(k+1)=Max(S(k), P(k+1)). Вот эти формулы собственно и запрограммированы. S(N) – это то значение, которое требуется найти.
Ratings: 0 negative/0 positive

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

Сообщений: 32911
Дата: 28.01.08 21:06:52
Привет Леонид!

Они похожи но не идентичны - у тебя отсечение "плохого" хвоста реализовано алгоритмически проще (зато логически сложнее - в смысле понять это сложнее )... Ты отсекаешь его просто сравнивая полную сумму (хвост+новое число) с новым числом. Я же делаю отсечение за 1 шаг до того, сравнивая полную сумму с 0 - ну т.е. когда очевидно что сумма будет плохая (отрицательная) и хвост надо резать


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



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

On-line: 42 Yss-FYI Божья_коровка Simple777  (Гостей: 39)

20.08.2019 17:34:33 exec: 0.15
Mem: 1.246 Mb

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