masterrr Sep 11 2011 at 16:48

Найти большее значение без сравнения и условий

1 min

11K

Entertaining tasks

+14

Comments 72

tzlom Sep 11 2011 at 16:56

a*a+b*b+1 всегда больше и a и b

Tibr Sep 11 2011 at 17:04

abs(a+b) — abs(a-b)?

Tibr Sep 11 2011 at 17:07

2 минуты.

masterrr Sep 11 2011 at 17:09

Верно, есть еще один вариант решения :)

Shedal Sep 11 2011 at 17:58

Погодите, как же верно? Решение не работает даже для положительных чисел (пример с 10 и 3 — чуть ниже).

Tibr Sep 11 2011 at 18:00

А если это выражение, что я отписал ниже поделить на 2?
Пока сломать не могу.

Tibr Sep 11 2011 at 18:00

То есть (abs(a+b)-abs(a-b))/2

Sing Sep 11 2011 at 18:03

Ну так на том же примере с 10 и 3 получится 3. Это неправильный ответ.

Tibr Sep 11 2011 at 18:03

Черт, ломается на первом примере :-)

masterrr Sep 11 2011 at 18:25

Да, неправильно проверил, простите.

barker Sep 11 2011 at 17:16

a=-3, b=-6
abs(a+b)-abs(a-b) = abs(-3+(-6))-abs(-3-(-6)) = 6

Tibr Sep 11 2011 at 17:17

Ага, с отрицательными не работает.

Volkman Sep 11 2011 at 17:23

abs() — по сути условный оператор, так что это не решение.

из java.lang.Math например:

public static int abs(int a) {

 return (a < 0) ? -a : a;

}

Tibr Sep 11 2011 at 17:26

Не, ну сказано же, что задача математическая, а не по программированию.

Volkman Sep 11 2011 at 17:29

Ну в определении модуля для вещественных чисел все равно фигурирует условие. Поэтому и написал «по сути».

Shedal Sep 11 2011 at 17:34

Модуль тоже можно выразить простой математикой. Например:
int abs(int a) { return sqrt(a*a); }

Volkman Sep 11 2011 at 17:42

Безусловно, вы правы. Но, на мой взгляд, когда пишут просто abs(a) подразумевают |a|.

kk86 Sep 12 2011 at 03:03

Полагаю, для целых чисел ничто не мешает реализовать операцию модуля как принудительное выставление старшего разряда (бита) в состояние «0». Если я заблуждаюсь, поправьте.

Если такое возможно, то операция abs() не будет требовать сравнения.

UFO landed and left these words here

Shedal Sep 11 2011 at 17:43

abs(10+3) — abs(10-3) = 13 — 7 = 6. Не работает.

Volkman Sep 11 2011 at 17:09

(a/b) * (a — b) + b

masterrr Sep 11 2011 at 17:12

((3 / 6) * (3 — 6)) + 6 = 4.5

Volkman Sep 11 2011 at 17:14

если a и b — int, то результат a/b будет 0, если a < b, или 1, если a > b.

barker Sep 11 2011 at 17:17

Задача математическая, а не на Си)

Tibr Sep 11 2011 at 17:14

Есть:
a = 4; b = 2;

Формула:
(4/2)*(4-2) + 2

Ответ: 6

Неверно…

Volkman Sep 11 2011 at 17:16

Ох да, конечно. Воскресение — мозг отдыхает. За глупость прошу прощения.

Shedal Sep 11 2011 at 17:38

a * (a — b + |a — b|) / 2 + b * (b — a + |b — a|) / 2

Sing Sep 11 2011 at 17:43

Пусть а = -3, b = 2

-3 * (-3 — 2 + |-3 — 2|) / 2 + 2 * (2 +3 * (2 +3 + |2 + 3|)/2 = 32

Shedal Sep 11 2011 at 17:46

А что, есть решение, которое работает и для отрицательных чисел?

Sing Sep 11 2011 at 17:50

Я не знаю, но в условии задачи не говорилось, что а и b — неотрицательные.

Andrew1000000 Sep 11 2011 at 17:59

((a-b)-|a-b|)/(2*(a-b))*b+((b-a)-|b-a|)/(2*(b-a))*a

Andrew1000000 Sep 11 2011 at 18:04

Работает для любых чисел, не обязательно целых :)

xanep Sep 11 2011 at 23:51

Я так же сделал как и вы. В одном направлении думали. Вот только я дальше это монстровое выражение упрощать начал и осталось только (a+b+|a-b|)/2

Sing Sep 12 2011 at 10:57

Это, в общем, и есть ответ Fil ниже, только подведенный под общий знаменатель.

Tibr Sep 11 2011 at 18:06

Ядерная жесть :-)

Shedal Sep 11 2011 at 18:07

Отлично :) Элегантно решили проблему с отрицательными числами.
Единственная проблема — деление на нуль в случае, когда a = b.

shadowalone Sep 11 2011 at 18:16

что-то непонятно, выражение ((a-b)-|a-b|), при положительных числах, если a>b дает 0.

Fil Sep 11 2011 at 18:15

Так как оба числа находятся на расстоянии полуразности от их среднего:
(a+b)/2 + abs(a-b)/2
среднее + абсолютная полуразность

masterrr Sep 11 2011 at 18:24

Вот это мое решение! :)

Shedal Sep 11 2011 at 18:29

Опять-таки, не учитывает, что числа могут быть отрицательными. Но красиво :)

tvv Sep 11 2011 at 18:30

Отрицательные числа в данном случае учитываются. Это хорошее решение.

Shedal Sep 11 2011 at 18:42

-3 и -4.
|-3-4|/2 + |-3+4|/2 = 7/2 + 1/2 = 4
Для этого примера решение не работает.

shadowalone Sep 11 2011 at 18:43

Работает
Вы неправильно посчитали

-7/2 + 1/2 = -3
все правильно

Shedal Sep 11 2011 at 18:50

Черт, я думал, что первая сумма тоже в модуле :)
Извиняюсь, действительно, все правильно. Очень красивое решение :)

masterrr Sep 11 2011 at 18:44

На всякий случай посчитал в калькуляторе гугла:
(((-3) + (-4)) / 2) + (abs((-3) — (-4)) / 2) = -3

Все правильно.

masterrr Sep 11 2011 at 18:29

Но и в этом решении есть минус. Подставьте, например, -5 и 4.

tvv Sep 11 2011 at 18:32

Подставил. Получил правильный ответ: (-5+4)/2 + abs(-5-4)/2 = 4

Tibr Sep 11 2011 at 18:33

На этом примере нормально:
(a+b)/2 + abs(a-b)/2 = (-5+4).2 + abs(-5-4)/2 = -0.5 + 4.5 = 4

masterrr Sep 11 2011 at 18:36

Да, неправильно считаю. Воскресенье делает свое дело. *отмазка*

Получается, это единственное элегантное решение.

За решение этой задачи за 10 минут преподаватель поставил бы 10, но никто не решил… Только на следующей паре додумался… :)

ComodoHacker Sep 11 2011 at 21:19

Отлично, но я удивлен, что это не 1-5 комментарий.
Молодеет Хабр.

masterrr Sep 11 2011 at 21:35

Всмысле, — удивлены? Я решил эту задачу позавчера, просто было бы глупо сразу ответ в топике написать :)

ComodoHacker Sep 11 2011 at 22:22

В смысле удивлен, что так много комментариев до правильного ответа.
Обычно об этой задаче узнают на первом курсе (те кто еще не знал). Отсюда я заключаю, что большинство заглянувших в топик либо моложе, либо учатся(лись) в непрофильном вузе. :)

masterrr Sep 11 2011 at 21:54

Кстати, можно записать так
((a+b) + abs(a-b))/2

tvv Sep 11 2011 at 18:37

Так-с, удалось избавиться от модуля. Вот программерское решение для 32-разрядных чисел:

a — ((a — b) >> 31) * (a — b)

Tibr Sep 11 2011 at 18:46

a=-5
b=4
Ответ: 36

ЧЯДНТ?

tvv Sep 11 2011 at 18:52

Я не знаю, каким образом Вы получили 36. На данном примере должно быть так:

a - ((a - b) >> 31) * (a - b) = -5 - ((-5 - 4) >> 31) * (-5 - 4) = -5 - (-9 >> 31) * -9 =-5 - -9 = 4

Ответ правильный.

Tibr Sep 11 2011 at 18:58

Извините, ответил ниже:
-5 — (-9 >> 31) * -9 = -5 — (-1) * -9 = -14

Tibr Sep 11 2011 at 19:00

Я тоже обсчитался — ответ не 36, а -14.

tvv Sep 11 2011 at 19:02

-9 >> 31 = 1, а Вы почему-то получили -1

Tibr Sep 11 2011 at 19:04

Это -1. Проверьте в вашем любимом компиляторе.

tvv Sep 11 2011 at 19:11

Точно, я забыл сделать & 1. Тогда вот новое решение, без этого недостатка:

a - (((a - b) >> 31) & 1) * (a - b)

Tibr Sep 11 2011 at 19:15

Подтверждаю, теперь всё верно.

Lockal Sep 11 2011 at 19:26

Как вариант можно сделать

a + ((a - b) >> 31) * (a - b);

tvv Sep 11 2011 at 19:28

Кстати, интересно. Я только что проверил -9 >> 31 на разных компиляторах:

C: -1
PHP: -1
Perl: 1 (только тут я делал -9 >> 63, так как используются 64 разрядные числа)

my $a = -5;

my $b = 4;

print $a - (($a - $b) >> 63) * ($a - $b);

Данный код на Perl вернул правильный результат: 4.

Но в любом случае, конечно, вариант с &1 использовать предпочтительнее, так как он более универсален.

Tibr Sep 11 2011 at 19:30

Java 6 и C++ тоже дают -1, так что я согласен насчет "&".

tvv Sep 11 2011 at 20:09

В Java можно использовать беззнаковый сдвиг вправо. Тогда выражение будет таким:

a - ((a - b) >>> 31) * (a - b)

Tibr Sep 11 2011 at 18:58

-5 — (-9 >> 31) * -9 = -5 — (-1) * -9 = -14

maovrn Sep 11 2011 at 19:02

Наверное не по правилам, но
return last_value(sort(array(a,b)));

Goder Sep 11 2011 at 19:17

При сортировке, скорее всего, используются условные операторы.

Levsha100 Sep 11 2011 at 19:30

Решение на плюсах без сравнения и условий:

char getMax(char a, char b)

{

 char m[2];

 m[0]=b;

 m[1]=a;

 a-=b; 

 return m[(a>>8)+1];

}

eugenius_nsk Sep 12 2011 at 15:59

Не заглядывая в комментарии: a*(1 + (a-b)/|a-b|)/2 + b*(1 + (b-a)/|b-a|)/2

eugenius_nsk Sep 12 2011 at 16:11

PS. После упрощения сводится к (a+b + |a-b| ) / 2