Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
 максимум без if  [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 49544
напомните, есть ли алгоритм вычисления максимума из двух чисел без if
20 ноя 14, 20:07    [16881432]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 49544
+ - * / and or xor
20 ноя 14, 20:11    [16881456]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
miksoft
Member

Откуда:
Сообщений: 37248
Придумать-то можно, но зачем?

Псевдокод:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}
sign можно реализовать без if, например, сдвигами и бинарными операциями.
20 ноя 14, 20:39    [16881560]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
miksoft
Member

Откуда:
Сообщений: 37248
Поправка:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return t[sign(sign(b-a)+1)];
}
20 ноя 14, 20:40    [16881567]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
White Owl
Member

Откуда:
Сообщений: 12339
c = a<b ? b : a;

c = max(a,b);

c=0;
while(a>0 && b>0) {
    c++;
    a--;
    b--;
}


Ну а если Си не любишь, то можно и на SQL сделать.
select @c = case when @a<@b then @b else @a end

select @c = max(v) from (select v=a union select b) t
20 ноя 14, 20:41    [16881569]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
miksoft
Member

Откуда:
Сообщений: 37248
White Owl
case when
Да, это не if, там и буковок-то таких нету!
20 ноя 14, 20:43    [16881579]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
no56892
Member

Откуда:
Сообщений: 582
andreymx
напомните, есть ли алгоритм вычисления максимума из двух чисел без if

А на брейнфаке генератор случайных чисел слабо?
20 ноя 14, 21:59    [16881960]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 38359
MaytonsFuckenMaximumFunction.lisp
(defun maximum(x y) 
  (cond ((= x y) x) ((> x y) x) ((< x y) y)))
20 ноя 14, 22:26    [16882034]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Яростный Меч
Member [скрыт]

Откуда:
Сообщений: 28868
(a + b + abs(a-b)) / 2
21 ноя 14, 00:46    [16882400]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
На самом деле все предложенные алгоритмы содержат неявный if. Если вы видите знак больше или меньше, то мы уже говорим о каком-либо условии. Казалось бы вариант предложенный Яростным мечом подходит, но и это не так. Ибо вычисление модуля подразумевает условие, кроме того, модуль не был в числе допустимых операций

andreymx
+ - * / and or xor


потому, ответа на поставленный вопрос никто пока не дал.
21 ноя 14, 02:51    [16882533]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Можно было сделать так:

int t=a%b;

если а больше b то t>=1, в противном случае 0. Нужно установить t в 1, в том случае, если t>1. Это можно сделать следующим образом
t=(t+2)%(t+1);

если t было равно 0, то получим 2, если больше нуля, то получим число вида , это число не является целым, потому следующей операцией будет следующая
t=t%2;

Если t было равно 2, то мы получим 0, в противном случае, мы получим остаток 1. Таким образом, если a>b, то t=1, в противном случае, 0. Выражение вида
int max=t*(a-b)+(1-t)(b-a);

даст вам то, что требуется.

PS
скорее всего, в реализации операции % тем или иным образом присутствует условие, но в данном случае, оно менее явное чем в остальных случаях. И тут я так-же не использовал только те операции что вы предлагали. Код не тестировал, проверьте сами
21 ноя 14, 03:14    [16882543]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
miksoft
Придумать-то можно, но зачем?

Псевдокод:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}
sign можно реализовать без if, например, сдвигами и бинарными операциями.


тогда уже
 a*sign[a-b]+b*(1-sign[a-b]);

так читабельней. Может и можно реализовать, не помню. Надеюсь автор доведёт дело до конца, и напомнит как это сделать.
Хотя тут и думать не нужно, это элементарно, вот так:
int sign(int x)
{
    return x>>31;
}

данная функция вернёт 1 если число отрицательно и 0 в противном случае, таким образом, получим следующий результирующий код
int a,b;
int max=sign(a-b)*b+(1-sign(a-b))*a;


В общем мысль и идея понятны, тестируйте, не проверял этот код.

PS
но опять таки, в данном коде присутствуют лишние операции
21 ноя 14, 03:26    [16882556]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13032
SashaMercury
На самом деле все предложенные алгоритмы содержат неявный if. Если вы видите знак больше или меньше, то мы уже говорим о каком-либо условии. Казалось бы вариант предложенный Яростным мечом подходит, но и это не так. Ибо вычисление модуля подразумевает условие, кроме того, модуль не был в числе допустимых операций

abs() можно реализовать так sqrt(x*x)
21 ноя 14, 07:11    [16882649]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Dima T,

покажите как вы реализуете корень :)
21 ноя 14, 07:13    [16882651]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Второй вариант получить множитель 1 для положительного, -1 для отрицательного, т.е. sign()
в двоичном представлении 00000001 и 11111111 соответственно, старший бит это знак для типов со знаком.
далее
int my_sign(int x)
{
	unsigned int u = x & 0x80000000; // берем старший бит исходного числа
	for(int i = 0; i < 31; i++) { // заполняем им все биты
		u |= (u >> 1);
	}
	return u | 1; // устанавливаем младший бит в 1 для положительных
}
21 ноя 14, 07:39    [16882665]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
i < 31


явный if
21 ноя 14, 07:48    [16882679]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71140
SashaMercury
Dima T,

покажите как вы реализуете корень :)

Корень можно вычислить как-то так:
#lang racket
(define (average x y)
  (/ (+ x y) 2))
(define tolerance 0.00000001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
(try first-guess))
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(sqrt 1024)

32.0
>
21 ноя 14, 07:49    [16882682]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13032
SashaMercury
i < 31


явный if

а так?
int my_sign(int x)
{
	unsigned int u = x & 0x80000000; // берем старший бит исходного числа
	// заполняем им все биты
	u |= (u / 2);
	u |= (u / 2);
	... и еще 29 раз повторить эту строчку
	return u | 1; // устанавливаем младший бит в 1 для положительных
}

21 ноя 14, 07:50    [16882683]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71140
andreymx
напомните, есть ли алгоритм вычисления максимума из двух чисел без if

А вообще, по идее на scheme просто
(max 3 5)
5
>
21 ноя 14, 07:54    [16882685]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
XDiaBLo
SashaMercury
Dima T,

покажите как вы реализуете корень :)

Корень можно вычислить как-то так:
#lang racket
(define (average x y)
  (/ (+ x y) 2))
(define tolerance 0.00000001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
(try first-guess))
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(sqrt 1024)

32.0
>


вы используете тернарный оператор, значит используете if
21 ноя 14, 07:55    [16882688]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13032
Dima T
	u |= (u / 2);
	u |= (u / 2);
	... и еще 29 раз повторить эту строчку


Кстати можно обойтись 8-ю строчками
21 ноя 14, 07:55    [16882689]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71140
SashaMercury
вы используете тернарный оператор, значит используете if

Да там и if есть самый настоящий. Но по сабжу я уже ответил
Программа:(max 5 3)
Результат: 5
21 ноя 14, 07:56    [16882690]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
Dima T
Dima T
	u |= (u / 2);
	u |= (u / 2);
	... и еще 29 раз повторить эту строчку


Кстати можно обойтись 8-ю строчками




а чем это лучше предложенного кода ранее
SS
int sign(int x)
{
    return x>>31;
}
21 ноя 14, 07:58    [16882693]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2639
XDiaBLo
SashaMercury
вы используете тернарный оператор, значит используете if

Да там и if есть самый настоящий. Но по сабжу я уже ответил
Программа:(max 5 3)
Результат: 5


а вы посмотрите как в Scheme реализована эта функция :)
21 ноя 14, 08:02    [16882700]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13032
SashaMercury
а чем это лучше предложенного кода ранее
SS
int sign(int x)
{
    return x>>31;
}

Тем что я его не заметил выше :)

Только правильно так
int sign(int x)
{
    return (x>>31) | 1;
}
21 ноя 14, 08:05    [16882707]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить