Задачка для разминки мозга

← →
Rouse_ © (2014-04-16 21:37) [0]

Итак, дано, есть функция вида:

function T(A, B: Byte): Boolean; begin Result := ??? end;

Данной функции могут быт переданы любые значения параметров А/В, но только на два из них она должна вернуть результат False, это должно случится при условии что (A = 90 и В = 77) или наоборот (A = 77 и В = 90). Во всех остальных случаях данная функция должа вернуть True.

Важный нюанс, код функции не должен содержать логических переходов.
Т.е. нельзя использовать метки и операторы GOTO, нельзя использовать условия IF..THEN, нельзя использовать циклы (т.к. переход на след итерацию происходит именно ввиде сравнения и перехода).
Нельзя использовать блоки CASE или SET, т.к. они также основаны на проверках.

Т.о. вот такой код не валиден:

function T(A, B: Byte): Boolean; begin Result := not ((A in [77, 90]) and (B in [77, 90]) and (A <> B)); end;

и такой тоже:

function T(A, B: Byte): Boolean; begin Result := True; if (A = 90) and (B = 77) then Result := False else if (A = 77) and (B = 90) then Result := False; end;

Победит тот кто напишет наименее краткий и понятный код.

ЗЫ: особое условие.
Огромная просьба не писать варианты решений нашим мэтрам (ИШ/ЮЗ/Sha/0xFFFF) вам это как семечку пощелкать, а народу станет не интересно :)

← →
Rouse_ © (2014-04-16 21:41) [1]

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

← →
SergP © (2014-04-16 21:46) [2]

А так тоже нельзя:

result:=((a=77) and (b=90)) or ((a=90) and (b=77))

?

← →
Rouse_ © (2014-04-16 21:59) [3]

Да, так тоже нельзя, ибо тоже будут логические переходы (под ними я подразумеваю условные переходы в виде инструкций JXX в асм коде, где нужно будет купировать результаты вычислений двух блоков - первой и второй проверки, чтобы над ними выполнить OR)

← →
Rouse_ © (2014-04-16 22:00) [4]

В оригинале задача стояла так - написать алгритм сравнения на ассемблере без использования операторов JXX, а тут я уже причесал постановку задачи под Delphi

← →
Rouse_ © (2014-04-16 22:07) [5]

Грубо чтоб понять смысл, вот дизасм этой функции:

Project6.dpr.17: Result := ((a=77) and (b=90)) or ((a=90) and (b=77)); 00418A02 807DFF4D cmp byte ptr [ebp-$01],$4d 00418A06 7506 jnz $00418a0e <<< нельзя 00418A08 807DFE5A cmp byte ptr [ebp-$02],$5a 00418A0C 7410 jz $00418a1e <<< нельзя 00418A0E 807DFF5A cmp byte ptr [ebp-$01],$5a 00418A12 7506 jnz $00418a1a <<< нельзя 00418A14 807DFE4D cmp byte ptr [ebp-$02],$4d 00418A18 7404 jz $00418a1e <<< нельзя 00418A1A 33C0 xor eax,eax 00418A1C EB02 jmp $00418a20 00418A1E B001 mov al,$01 00418A20 8845FD mov [ebp-$03],al Project6.dpr.18: end; 00418A23 8A45FD mov al,[ebp-$03] 00418A26 59 pop ecx 00418A27 5D pop ebp 00418A28 C3 ret

← →
Rouse_ © (2014-04-16 22:17) [6]

ЗЗЫ: в догонку

> SergP © (16.04.14 21:46) [2]

оператор OR в данном случае эквивалентен блоку ELSE из второго примера.

← →
Германн © (2014-04-16 22:32) [7]

Интересные числа 90 и 77. У каждого тетрады зеркальны в негативе.

← →
Павиа (2014-04-16 22:36) [8]

А в чём прикол детской задачке?

← →
Rouse_ © (2014-04-16 22:37) [9]

> Германн © (16.04.14 22:32) [7]
> Интересные числа 90 и 77. У каждого тетрады зеркальны в
> негативе.

Таких чисел много, могу выбрать и другие если хочешь :)
А так эти числа обозначают инициалы Марка Збиковски "MZ" или "ZM", т.е. то что должно находится в _IMAGE_DOS_HEADER.e_magic каждого уважающего себя экзешника:)

← →
Rouse_ © (2014-04-16 22:38) [10]

> Павиа (16.04.14 22:36) [8]
> А в чём прикол детской задачке?

Дык эта... в ее решении.

← →
имя (2014-04-16 22:48) [11]

Удалено модератором

← →
имя (2014-04-16 22:52) [12]

Удалено модератором

← →
Inovet © (2014-04-16 22:54) [13]

A xor B = 23
коротко?

← →
Inovet © (2014-04-16 22:55) [14]

> [13] Inovet © (16.04.14 22:54)

или чё там джамп будет?
ну -23 тогда

← →
Jeer © (2014-04-16 23:03) [15]

>Длиннее по условию

У тебя очень короткий, но вот длиннее или длиньше?

Result := boolean((A and $7F)*(B and $7F) mod ($1B12));

← →
Inovet © (2014-04-16 23:06) [16]

> [15] Jeer © (16.04.14 23:03)
> and $7F

Не пойдёт

← →
Rouse_ © (2014-04-16 23:08) [17]

> Jeer © (16.04.14 23:03) [15]

Решение не верное, есть коллизии.

← →
Rouse_ © (2014-04-16 23:10) [18]

Для простоты, можно проверить свои варианты сразу вот таким кодом:

var A, B: Integer; begin for A := 0 to 255 do for B := 0 to 255 do if not T(A, B) then Writeln(IntToHex(A, 2), IntToHex(B, 2)); Readln; end.

Если выведет:

4D5A 5A4D

Значит все сделано правильно.

← →
Dimka Maslov © (2014-04-16 23:11) [19]

function T(A, B: Byte): Boolean;
var
F: Byte;
N: Integer;
begin
F := (A + B) + 90;
N := F * A * B - 6930 + (A xor B) - 23;
Result := N = 0;
end;

← →
Rouse_ © (2014-04-16 23:15) [20]

> Dimka Maslov © (16.04.14 23:11) [19]

Решение практически верное (в последней строчке ты перепутал, и в итоге результат инвертирован).

← →
Rouse_ © (2014-04-16 23:16) [21]

ЗЫ: можно сделать еще проще, ждем варианты :)

← →
Dimka Maslov © (2014-04-16 23:16) [22]

Вернее N <> 0, и без это сравнения никак, из представления boolean в дельфе

← →
Дмитрий К © (2014-04-16 23:18) [23]

Result := Boolean(((a + b) xor 167) or (abs(a - b) xor 13) or ((a or b) xor 95));

← →
Dimka Maslov © (2014-04-16 23:18) [24]

Ну да, первая строка не нужна, остаётся только

N := A * B - 6930 + (A xor B) - 23;

← →
Rouse_ © (2014-04-16 23:21) [25]

> Дмитрий К © (16.04.14 23:18) [23]

Класс, да это практически что и ожидается, но... Abs?

← →
Rouse_ © (2014-04-16 23:26) [26]

> Dimka Maslov © (16.04.14 23:18) [24]

You Win :))

function T(A, B: Byte): Boolean; begin Result := (A * B - 6930 + (A xor B) - 23) <> 0; end;

← →
Dimka Maslov © (2014-04-16 23:30) [27]

Я вот что подумал, это новая тенденция в программировании такая что ли пошла - избавляться от if. Мне вот тут на днях тоже задачку задали, где условием правильности решения являлось минимально возможное количество проверок, ибо они "очень медленные" ???

← →
Dimka Maslov © (2014-04-16 23:34) [28]

А ещё забавно, что подобное прокатывает не для всех пар чисел...

Учат писать код, чтобы никто не разобрался что он делает (есть много примеров на Си)

Раз уж ты так быстро все решил, то подкину для разминки еще одну задачку, а то ветка скучная получится :)))

Есть массив чисел. Размер массива 2N+1. В этом массиве 2N дубликаты, а 1 значение уникально. Надо написать код, который найдет значение этого уникального числа за одну итерацию, т.е. за один проход. Пример ряда: "3, 1, 5, 1, 3".
В этом ряду {3, 3}, {1,1} дубликаты, а 5 — уникальное.

> SergeyIT © (16.04.14 23:36) [29]
> Учат писать код, чтобы никто не разобрался что он делает
> (есть много примеров на Си)

Нивкоем разе - этож чистая алгоритмика. Если так писать в боевой задаче, то нафих вон из профессии... (кто это будет сопровождать?)

Как я понимаю решение с предварительной сортировкой не канает? В любом случае эта задача на завтра, а то уже спать пора.

> [30] Rouse_ © (16.04.14 23:37)

Идём по массиву, сравниваем текущее с предыдущими 2-мя, если отличается - значит, нашлось. Ну или тоже с XOR, если надо хуже читаемость.

> Inovet © (16.04.14 23:43) [33]

Да, ну и не забывай, что у нас массив в виде 2N+1 элементов, т.е. это может быти и такое:

"1, 2, 3, 4, 5, 1, 2, 3, 4"

> Есть массив чисел. Размер массива 2N+1. В этом массиве 2N
> дубликаты, а 1 значение уникально. Надо написать код, который
> найдет значение этого уникального числа за одну итерацию,
> т.е. за один проход.

function Foo(arr: array of Integer): Integer; var i: Integer; begin Result := arr[0]; for i := 1 to Length(arr) - 1 do Result := Result xor arr[i]; end;

Первая, ИМХО, интереснее была. Правда меня не в ту степь понесло, я с shr начал экспериментировать. Ну, типа, ((a shr 2) or (b shr 2)) <> (a xor b)

> [35] Rouse_ © (16.04.14 23:48)
> "1, 2, 3, 4, 5, 1, 2, 3, 4"

А, понял. Дубликатов 2N. Они упорядочены? Тогда просто максимальное ищем. Нет тогда в другой массив что ли пихать с индексом нового уникального, тут подумать надо.

ПС. Писать сейчас нет времени.

> А, понял. Дубликатов 2N. Они упорядочены? Тогда просто максимальное
> ищем. Нет тогда в другой массив что ли пихать с индексом
> нового уникального, тут подумать надо.

Да тут всё просто.
1. X xor X = 0;
2. X xor 0 = X;
3. xor - коммутативен.

← →
тупой компилятор (2014-04-17 00:27) [40]

> Dimka Maslov © (16.04.14 23:34) [28]
> А ещё забавно, что подобное прокатывает не для всех пар чисел...

//прокатывает для всех пар Result:=(A*B-(77*90)) or ((A+B)-(77+90))<>0;

Задачка для разминки мозга Найти похожие ветки