|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 07 Aug 2003 16:29:14
To : Oleg Khovayko [SPAM trap - don't re
Subject : поиск локальных max и min в массиве
--------------------------------------------------------------------------------
Or> Hа основании этой идеи написан приведенный ниже код, который
Or> к каждой ячейке массива производит обращение идет
Or> только дважды. То есть в среднем будет работать втрое быстрее.
Or> А проверка на конец массива делается барьерным методом, что позволяет
Or> не проверять конец массива на каждой итерации, а ограничиться
Or> только проверкой в конце нахождения каждого минимума.
Or> #include <stdio.h>
Or> #define EOM 32000
Or> 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};
Or> main() {
Or> int *p = mas;
Or> do {
Or> do p++; while(p[-1] <= p[0]); printf("MAX: %d\n", p[-1]);
Or> do p++; while(p[-1] >= p[0]); printf("MIN: %d\n", p[-1]);
Or> } while(*p != EOM);
Or> }
При int mas[] = { 1, 1, ..., 1, 0, 1, ..., 1, 0, EOM } оно выдаст:
MAX: 1; MIN: 0; MAX: 1; MIN: 0. Hе много ли максимумов? :) А если 0 перед EOM
убрать, то вообще упадет. Барьер нужно делать так, чтобы на нем все внутренние
циклы завершались.
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
