Алгоритм поиска наибольшего среднего арифметического некой последовательности - страница 2

Новый комментарий
 
sanyooooook:
цикл повторится 2000 раз, ведь сумма первых 20 элементов не просчитана и цикл должен прокрутиться и там, делить необязательно достаточно найти сумму.

Но нам не нужны ПОСЛЕДНИЕ 20 циклов. Там элементов будет уже меньше N

Последние 19, 18, 17 и до конца массива 

 
AndreiFAN:

>>>>Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.

Да доли миллисекунды это )))

НомерПервогоЭлемента=0

МаксЗнач=0 

Цикл повторяется РазмерМассива - КолЭлементовСложения

в каждой итерации суммируем все КолЭлементовСложения с очередного номера элементов в массиве, делим на КолЭлементовСложения 

Если Результат > МаксЗнач, то МаксЗнач=Результат, запоминаем НомерПервогоЭлемента из КолЭлементовСложения на текущей итерации. 

Продолжаем цикл.

По завершении цикла имеем номер элемента буфера, с которого будет наибольшее среднее МаксЗнач

==

Всё это работает быстрее чем я печатаю одну букву ))) 

достаточно знать сумму на предыдущей итерации и (i-n) итерации, т.е. сумму предыдущей итерации нужно записать в массив

делить не обязательно, т.к. количество элементов одинаково.

ЗЫ: я может не правильно понял алгоритм, но Вы на каждой итерации суммируете все элементы массива, до текущего i-того?

 
AndreiFAN:

Но нам не нужны ПОСЛЕДНИЕ 20 циклов. Там элементов будет уже меньше N

Последние 19, 18, 17 и до конца массива 

т.е. Вы возьмёте и не просмотрите последние 20 элементов, которые в среднем оказались самые большие? )
 
sanyooooook:
т.е. Вы возьмёте и не просмотрите последние 20 элементов, которые в среднем оказались самые большие? )

Последняя итерация будет иметь номер 2000-20

т.е. последние Двадцать я просмотрю, а вот сумма последних 19 нам уже не нужна, как и все следующие... 

Нам же нужны суммы подряд 20 элементов. 19 нас уже не интересуют

 
ALXIMIKS:

Имеем массив Muss[1000] рандомных  значений (min =  -100, max =100).

Нужно найти последовательность, длина которой не короче n = 45 элементов,

чтобы среднее арифметическое элементов найденной последоавательности было наибольшим из всех возможных вариантов последовательностей.

 

Тупой перебора всех среднеарифметичных значений даст квадратичную скорость, что очень долго в виду повторяемости задачи.

Хотелось бы находить за линейную скорость, но как? 

Максимум машки с периодом 45 (стандартный алгоритм расчёта машки достаточно оптимизирован, следующее значение вычисляется на основе предыдущей суммы за минусом числа не входящего в новый отрезок и плюс новое число, таким образом при расчёте оптимизированным алгоритмом мы получаем N сложений и N делений те 3N операций, а не квадратичную как толкует автор).

Строим машку SMA, затем ArrayMaximum от массива с данными машки. 

 
sanyooooook:


ЗЫ: я может не правильно понял алгоритм, но Вы на каждой итерации суммируете все элементы массива, до текущего i-того?

Я имел ввиду что-то типа этого:

///////////////////////////////

double Buffer[1000];

// тут присваиваем значения элементам буфера...

// 

// далее находим то что нам нужно

int N=20;

double MaxSumm=0;

int IndexFind=0;

for(int i=0; i<ArraySize(Buffer)-N; i++)

{

   double Summ=0;

   for(int ii=0; ii<N; ii++)

   {

      int iii=i+ii;

      Summ=Summ+Buffer[iii];

   }

   if(Summ>MaxSumm)

   {

      MaxSumm=Summ;

      IndexFind=i;

   }

}

Alert("Максимальная сумма элементов с "+IndexFind+" элемента в массиве"); 

 

ПЫ.СЫ.  Делить не обязательно. Ведь все суммы делим на одинаковое число...  Среднее будет 100% коррелировано. 

 

вот мой вариант, получается i-1 проход:

void OnStart()
  {
//---
   double a[2000];
   double sum[2000];
   int n=45;//количество в последовательности
   double MaxSumm=-20000000;//сюда запоминаем найденную максимальную сумму элементов
   //---
   //заполняем массв а[]
   //---
   sum[1]=a[0];
   for(int i=1;i<2000;i++)
   {
      sum[i]=sum[i-1]+a[i];
      if(i>=n)
      {
         if(sum[i]-sum[i-n]>MaxSumm)
         {
            MaxSumm=sum[i]-sum[i-n];
            Maxi=i;
         }
      }
   }
   Print("Последователность с максимальным средмин лежит в пределах от ",Maxi-n,"до",Maxi);
  }
//+------------------------------------------------------------------+
 
Urain:
Максимум машки с периодом 45.

а вдруг максимум машки с периодом 50 больше?

Вот пример 

 

об одном и том же спорили, но количество проходов i-1 по любому )

ЗЫ: а нет, у меня быстрее обработает ))

 
sanyooooook:

вот мой вариант:

не совсем понял...  45 и 20...  опечатка?

Так вот, а зачем вам суммы нескольких первых элементов, количественно меньше ? Сумма первых пяти например, зачем? 

Потому я и сделал i<ArraySize(Buffer)-N   чтобы не смотреть последние...

Ок. Наверно можно и так. 

Кстати, да, в моём примере тоже можно не складывать 20 элементов, а отнимать один элемент (начальный в предыдущей итерации), и прибавлять следующий в массиве....  

Сложение 20-ти только один раз, в начале цикла 

Не знаю что быстрее...  пробежаться по циклу, или писать ещё в один массив. 

12345
Новый комментарий
Причина обращения: