|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko [SPAM trap - don't re 2:5020/400 07 Aug 2003 01:20:40
To : Evgenij Masherov
Subject : Re: поиск локальных max и min в массиве
--------------------------------------------------------------------------------
Evgenij Masherov wrote:
> Максимум:
1 2
> (x[i]>x[i-1]) AND (x[i]>x[i+1])
> (поскольку для выбранного формата вероятность совпадения значений достаточно
> высока, одно из неравенств лучше сделать нестрогим)
> Минимум:
3 4
> (x[i]<x[i-1]) AND (x[i]<x[i+1])
>
Hу этот пример выше - прямо как из школьных уроков информатики.
Это же неинтересно, когда к каждому элементу входного массива
в среднем шесть раз обращаться приходится!
Почему 6? Да потому, что операции 1,3 выполняются со 100% вероятностью
дважды для каждого элемента массива (ибо i шагает подряд), да еще с
50% вероятностью по 2 раза будут выполнены операции сравнения 2,4.
Итого выходит 6 обращений. Да еще как я понимаю, неявно предлагается
на каждой итерации проверять на конец массива....
Hа самом деле, алгоритм существенно можно ускорить, вспомнив старую
песню нашей молодости "после радости - неприятности, по теории
вероятности". Здесь то же самое - после максимума обязательно должен
идти минимум - двух максимумов подряд быть не может. Если два максимума
подряд, то один из них - не максимум! Аналогично и для минимумов.
Hа основании этой идеи написан приведенный ниже код, который
к каждой ячейке массива производит обращение идет
только дважды. То есть в среднем будет работать втрое быстрее.
А проверка на конец массива делается барьерным методом, что позволяет
не проверять конец массива на каждой итерации, а ограничиться
только проверкой в конце нахождения каждого минимума.
#include <stdio.h>
#define EOM 32000
int mas[] = {0,1,1,2,3,4,5,6,7,5,4,3,2,3,4,5,8,6,5,4,3,2,1, EOM};
main() {
int *p = mas;
do {
do p++; while(p[-1] <= p[0]); printf("MAX: %d\n", p[-1]);
do p++; while(p[-1] >= p[0]); printf("MIN: %d\n", p[-1]);
} while(*p != EOM);
}
PS:
Тут только надо правильно обработать две крайние точки - первую и
последнюю (у них нет полного ансамбля окружающих точек). Так как в
условиях задачи не определено, что с ними делать,
я с ними поступаю достаточно вольно в этом примере.
Однако нетрудно устранить этот недостаток, либо модифицировав алгоритм,
либо скорректировав входной или выходной массив - в зависимости от того,
ложить или не ложить крайнюю точку на выход.
--
#include <best/regards>
Oleg Khovayko http://olegh.spedia.net
PS/ATTN: Reply to reverted address net.comcast@olegh
--- ifmail v.2.15dev5
* Origin: http://www.ftc.gov/opa/2001/04/spam.htm (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: поиск локальных max и min в массиве 