Решения школьной задачки

Решение задачки было на самом деле простым, если присмотрется к условию 🙂 Суть ведь не в том чтобы определить кто из них больше, на сколько, а лишь вывести на экран один из трех вариантов, а для простоты из двух.

Вариант 1

Допустим у нас есть массив из двух элементов ["А больше чем Б","Б больше чем А"]. Осталось вычислить номер элемента массива. Тут нашлось множество вариантов:

sign(a-b)
У Жени (whtiger)
((((a - b) & 0×80000000) >> 31) & 1) ^ 1
У Д. Уланова
(int) ((y%x) && (y%x)) — C или int(bool(int(y/x))) — Python
У Андрея Сафронова. Суть в том что преобразование булевого выражения в int выдает 0 или 1
1 + (b - a >> 31) - (a - b >> 31)
У Владимира Суркова
(b / a) / (b / a)
у Максима (mdemm)
abs((x - y)>>sizeof(int)*8) — C
У Александра Панова
round((((a mod b)-(b mod a))/abs((a mod b)-(b mod a))+1)) — Pascal
У Сергея Бердикова
(int)(Math.signum(x - y) + 1)
У Андрея Ставринова

Игорь Лобанов посчитал что использование функции sign () не совсем честно, так как внутри она может иметь ветвление. Я лично посчитал что ее можно использовать, т.к. даже если внутри и есть ветвление, то ее всегда можно заменить другой функцией вычисление знака без ветвления. Игорем собственно и был предложен вариант на ASM'е, реализующий ( sign ( a div b ) — sign ( b div a ) ):

; регистр eax содержит первое число, а регистр ebx - второе
MOV ecx, 0     ; используем регистр ecx как счётчик, начиная с нуля
PUSH eax       ; сохраним текущее значение eax, которое будет потеряно после
следующей инструкции
SUB eax, ebx   ; если результат отрицательный, carry flag установится в 1
ADC ecx, 0     ; фактически прибавляем 1, если carry flag установлен
POP eax        ; восстановим прежнее значение eax
SUB ebx, eax   ; если результат отрицательный, carry flag снова установится
в 1
SBB ecx, 0     ; фактически отнимаем 1, если carry flag установлен

Регистр ECX имеет значение 1 если большее значение было в регистре EAX, -1
если в EBX и 0 если значения равны.

Можно и без массива, лишь вычислив код буквы именующей переменную. Так как они идут по порядку (A-B, X-Y, А-Б) то тут все тоже самое. Я, кстати, тогда сделал именно так. Или просто позиция символа из строки.

Вариант 2

Денис Чумаков предложил еще один интересный вариант: вычисляем для каждой буквы больше она или нет (т.е. x2 = (x — y) / abs (x — y) и обратное для y2), а потом вывести n символов строки «А больше Б» где n = x * длинна этой строки, и тоже самое для «Б больше А». А т.к. одно из значений будет 0 а второе 1 то полностью выведется правильная строка, а вторая не будет выведена вообще. У Дениса было даже немного сложней, было учтено что цифры одинаковые и соответственно введена 3я строка, но суть думаю понятна.
Предложенный код на паскале:

x := (A - B + 1) div (ABS(A - B) + 1);
y := (B - A + 1) div (ABS(B - A) + 1);

z := (x + y) div 2;
x := x - z;
y := y - z;

s1 := 'Наибольшее значение в первой переменной';
s2 := 'Наибольшее значение во второй переменной';
s3 := 'Значения в переменных равны';
SetLength(s1, x * Length(s1));
SetLength(s2, y * Length(s2));
SetLength(s3, z * Length(s3));
Writeln(s1, s2, s3);

Вариант 3

А. Ефимов также предложил вариант с заполненностью строк/массива, но наоборот 🙂 Подход такой: создается последовательность символов состоящая поочереди из A и B, количество этих символов совпадает с введенным для него числом. Далее просто берется символ посередине. Т.е. вот так:

char[] names = new char[a + b];
Arrays.fill(names, 0, a, ‘a’);
Arrays.fill(names, a, a + b, ‘b’);
return names[(a + b) >> 1];

Если расчитывать лишь на положительные числа то вариант очень интересный.

  • http:// tuzzeg

    А мне сразу пришло в голову использовать signum (). Решение тогда элементарно:

    String A[] = {"A", «eq», «B»};

    return A[sign(a - b) + 1];

    Но как реализовать signum (a) без ветвления? Первая мысль: signum (a) = a/|a|, но это не подходит, так как эта функция не определена для a=0. Если в нашей задаче добавить ограничение на то, что числа разные, то это решение подходит.

    Потом я подумал, и соорудил функцию: signum (x) = (|x+1| — |x-1|)/2 для всех чисел, кроме (-1;0), (0;1) исключительно. Для целых чисел это решение подойдет.