Поиск максимума и минимума

Тема в разделе "WASM.A&O", создана пользователем Yashin_Sergey, 15 июн 2007.

  1. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Atlantic
    Код (Text):
    1.  for(i=M;i<N;i++)    //O(N)
    2.     {
    3.         if(i%M==0)
    4.         {
    5.             m=a[i-1];
    6.             for(j=1;j<=M;j++)
    7.             {
    8.                 if(a[i-j]<m)
    9.                     m=a[i-j];
    10.                 b[M-j]=m;
    11.             }
    12.             m=a[i];
    13.         }
    14.         if(a[i]<m)
    15.             m=a[i];
    16.         printf("%2d ",b[i%M]<m?b[i%M]:m);
    17.     }
    в этом коде массив b просто заполняется на этом его использование оканчивается, так что он бажный.
    из твоего описания я понял следующее, поправь меня, коли я не прав, плзззззззззз: идёт сравнение текущего элемента с текушим минимумом в окне, а потом с минимумом за пределами окна.
    ---------------------------------
    СПАСИБО ЗА ОПИСАНИЕ.
    Чёрное_Зеркало
    Код и впрямь ГЕНИАЛЕН -у тебя талант займись факторизацией - ты решишь эту задачу, потом расскажи, мне - ламеру, ПЛЗЗЗЗЗЗЗЗ;)
     
  2. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Он используется: printf("%2d ",b[i%M]<m?b[i%M]:m);

    Окно разбивается на две части: та, что попадает в массив b, и та, что в него не попадает (минимум по этой части - число m).
     
  3. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Atlantic
    точно:-D - не доглядел
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    попытался реализовать стратегию ведущий/ведомый: один массив юзается - другой заполняется, но колво операций не уменьшилось. Чемпион, по всей видимости, идеален.
     
  5. Nouzui

    Nouzui New Member

    Публикаций:
    0
    Регистрация:
    17 ноя 2006
    Сообщения:
    856
    Black_mirror, ты просто гений!

    Miller Rabin
    см. #102, там увидишь и свой алг, и его приблизительную оценку в числах
    если без чисел, то получается O(N*log2(k))