Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2014.12.14;
Скачать: CL | DM;

Вниз

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

 
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]

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


 
SergeyIT ©   (2014-04-16 23:36) [29]

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


 
Rouse_ ©   (2014-04-16 23:37) [30]

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

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


 
Rouse_ ©   (2014-04-16 23:38) [31]


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

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


 
Dimka Maslov ©   (2014-04-16 23:42) [32]

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


 
Inovet ©   (2014-04-16 23:43) [33]

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

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


 
Rouse_ ©   (2014-04-16 23:44) [34]


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

В виде кода будет гораздо наглядней, чем на словах :)


 
Rouse_ ©   (2014-04-16 23:48) [35]


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

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

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


 
Ega23 ©   (2014-04-17 00:06) [36]


> Есть массив чисел. Размер массива 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;


 
Ega23 ©   (2014-04-17 00:11) [37]

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


 
Inovet ©   (2014-04-17 00:22) [38]

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

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

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


 
Ega23 ©   (2014-04-17 00:27) [39]


> А, понял. Дубликатов 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;



Страницы: 1 2 3 4 5 6 7 вся ветка

Текущий архив: 2014.12.14;
Скачать: CL | DM;

Наверх




Память: 0.57 MB
Время: 0.01 c
1-1328811083
istok20
2012-02-09 22:11
2014.12.14
динамический листвью..


6-1274251810
Dmitriy
2010-05-19 10:50
2014.12.14
контроль (учет) трафика WinInet


3-1301760583
worldmen
2011-04-02 20:09
2014.12.14
Запрос списка уволенных


15-1400013003
Юрий
2014-05-14 00:30
2014.12.14
С днем рождения ! 14 мая 2014 среда


3-1301462832
vlgrig1961
2011-03-30 09:27
2014.12.14
HELP!!!Странная сортировка при GROUP BY