Re: Ускорение поиска максимума...

From

Sergey Andrianov (2:5020/1507.400)

To

Alexandr A. Redchuck

Date

2002-12-30T22:59:32Z

Area

RU.ALGORITHMS

Здравствуй, Alexandr!

Однажды 29-Dec-02  в 00:40   Alexandr A. Redchuck (via gate)
написал       Sergey Andrianov    по поводу
-=-   Re: Ускорение поиска максимума...  -=-

AAR> From: "Alexandr A. Redchuck" <real@real.kiev.ua>

AAR> 26-Dec-02 23:13 Sergey Andrianov wrote to Alexander Chelmodeev:

AC>>>   max:= (max+ar[n] + Abs(max-ar[n])) div 2 ;
AC>>>   min:= (min+ar[n] - Abs(min-ar[n])) div 2 ;
AC>>> end;

SA>>    А как ты собираешься реализовать Abs() без сравнений? На поразрядной
SA>> логике что ли? :)
AAR> Именно на ней.
AAR> Для представления целых знаковых чисел с дополнением до 2:
    ; выяснение условия val<0
AAR>  <вспомогательный регистр> := <расширение знака рабочего регистра>
    ; "услованая инверсия"
AAR>  <рабочий регистр> := <рабочий регистр> XOR <вспомогательный регистр>
    ; "условный инкремент"
AAR>  <рабочий регистр> := <рабочий регистр> - <вспомогательный регистр>

	Это все очевидно. На самом деле вопрос даже не в этом, а в том, что ни арифметических, ни логических операций над исследуемыми данными может попросту не существовать. Дан массив данных, дана процедура, которая, получая два элемента на входе, может принимать одно из трех значений: больше, меньше и равно. И никаким другим способом определить, что больше, а что меньше, нельзя. Требуется разработать алгоритм, который бы обеспечивал минимальное количество вызовов этой процедуры. 


                  До свидания,  в  22:54 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)