Суботняя головоломка от Розыча

← →
Rouse_ © (2015-08-22 12:24) [0]

Кстати вот вам еще одна задачка, автор не я:

"Для первого класса церковно-приходской школы.
Написать алгоритм, сравнивающий строку из двух символов на равенство "MZ" или "ZM", используя не более одного if (т.е. else if использовать нельзя)."

К примеру, перефразируя, пусть это будет функция в которую передается 2 симфола, которая должна вернуть True в случае если один из символов равен "M" а второй "Z" (порядок не важен).

function Check_IsMZorZM(A, B: AnsiChar): Boolean; begin //код писать здесь... end;

Мой вариант решения был в 9 строчек ASM кода, впрочем не обязательно писать на ассемблере :)

ЗЫ: поясню, вот написать нельзя:

function Check_IsMZorZM2(A, B: AnsiChar): Boolean; begin Result := ((A = "M") and (B = "Z") ) or ((A = "Z") and (B = "M")); end;

ибо тут будет 4 сравнения:

cmp al, $4D jnz 5 cmp dl, $5A Jz $C cmp al, $5A jnz 5 cmp dl, $4D jz 3 xor eax, eax ret mov al, 1 ret

← →
palva © (2015-08-22 13:56) [1]

{$APPTYPE CONSOLE} function Check_IsMZorZM(A, B: AnsiChar): Boolean; var x,y,t: Integer; begin //код писать здесь... x := ord(A); y := ord(B); t := (x+y)*256 + abs(x-y); Result := t = 42765; end; begin WriteLn(Check_IsMZorZM("M","Z")); WriteLn(Check_IsMZorZM("Z","M")); WriteLn(Check_IsMZorZM("N","Y")); end.

← →
Rouse_ © (2015-08-22 14:02) [2]

> palva © (22.08.15 13:56) [1]

Правильно, можно немного подоптимизировать, но правильно.

← →
DayGaykin © (2015-08-22 15:42) [3]

Не интересно. Давай-те вообще без сравнений!

← →
Sha © (2015-08-22 15:43) [4]

> Rouse_ © (22.08.15 12:24)

Их море, не считая банальной a*a+b*b.
Например, среди таких (a op1 c) op2 (b op1 c),
где c - константа, а (op1, op2) = (*, xor), (*, or), (+, *), (xor, *).

← →
Rouse_ © (2015-08-22 15:57) [5]

> DayGaykin © (22.08.15 15:42) [3]
> Не интересно. Давай-те вообще без сравнений!

Напиши

← →
Rouse_ © (2015-08-22 16:00) [6]

> Sha © (22.08.15 15:43) [4]

IMUl + SUB - будут коллизии

← →
Rouse_ © (2015-08-22 16:01) [7]

ЗЫ: хоть решение уже и показано - но оно не самое эффективное.
Можно проще.

← →
DayGaykin © (2015-08-22 16:01) [8]

Я ASM не знаю. Дай мне немного времени.

← →
Sha © (2015-08-22 16:02) [9]

Вот это мне нравится

(4*a+b+115) or (4*b+a+115)=553

← →
Sha © (2015-08-22 16:04) [10]

> Rouse_ © (22.08.15 16:00) [6]
> IMUl + SUB - будут коллизии

Не всегда.
Если сюда писать начну все те, что без коллизий, места не хватит )

← →
DayGaykin © (2015-08-22 16:10) [11]

> Sha © (22.08.15 16:02) [9]

Я короче нашел. (X+101) * (Y+101) = 33998

← →
Sha © (2015-08-22 16:15) [12]

> DayGaykin © (22.08.15 16:10) [11]

В [4] еще куча таких коротких. Но и там, и у тебя есть умножение.
А в [9] умножения нет )

← →
DayGaykin © (2015-08-22 16:20) [13]

function Check_IsMZorZM2(A, B: Byte): Boolean; asm add al, $65 add dl, $65 mul dl xor ax, $84CE jz @x mov ax, 1 @x: not ax and eax, 1 end;

> Sha © (22.08.15 16:15) [12]

Умножение так страшно?

← →
Sha © (2015-08-22 16:21) [14]

> DayGaykin © (22.08.15 16:10) [11]

Кстати, там есть константы и поменьше, например (X+77) * (Y+77) = 25718

← →
Sha © (2015-08-22 16:24) [15]

> DayGaykin © (22.08.15 16:20) [13]
> Умножение так страшно?

Нет, сейчас не страшно уже. Это раньше было.

← →
DayGaykin © (2015-08-22 16:29) [16]

> Кстати, там есть константы и поменьше, например (X+77) *
> (Y+77) = 25718

Я подобрал методом "тыка". Мне сразу повезло со 101 :)

Как в EAX положить значение флагового регистра?

← →
Sha © (2015-08-22 16:36) [17]

Result:=((X+101) * (Y+101) = 33998)

← →
Rouse_ © (2015-08-22 16:40) [18]

> DayGaykin © (22.08.15 16:20) [13]

Вах, даже красивее чем у меня :)
Правда чутка помедленней (разучились процессоры эффективно с 8-битными L/H работать, просадочка будет небольшая, но красивее)

Вот мой вариант:

> function Check_IsMZorZM(A, B: AnsiChar): Boolean;
> asm
> and eax, $FF
> and edx, $FF
> mov ecx, eax
> xor ecx, edx
> sub ecx, $17
> imul edx
> lea ecx, [eax + ecx - $1B12]
> cmp ecx, 0
> setz al
> end;

зы:

> Как в EAX положить значение флагового регистра?

Через setz после компарации.

← →
DayGaykin © (2015-08-22 16:42) [19]

Про SETZ не нашел. Нашел LAHF. Получилось вот так:

function Check_IsMZorZM2(A, B: Byte): Boolean;
asm
add al, $65
add dl, $65
mul dl
xor ax, $84CE
lahf
and eax, $4000 // ZF
shr eax, 14
end;

Сравнение, конечно, все-равно осталось.

← →
Rouse_ © (2015-08-22 16:43) [20]

> Sha © (22.08.15 16:02) [9]
> Вот это мне нравится
>
> (4*a+b+115) or (4*b+a+115)=553

Да, естественно это тоже верно (кто бы сомневался :)

← →
DayGaykin © (2015-08-22 16:44) [21]

С твоими задачами я скоро ASM начну понимать :)

← →
Rouse_ © (2015-08-22 16:44) [22]

> DayGaykin © (22.08.15 16:42) [19]

Мдя, пошел пить коньяк и посыпать голову пеплом - молоток :)

← →
Rouse_ © (2015-08-22 16:50) [23]

> DayGaykin © (22.08.15 16:44) [21]

Блин, этож Дима :))
Я то думаю кто это такой хитрый на форуме появился :)))

← →
DayGaykin © (2015-08-22 17:06) [24]

С SETZ интереснее, да:
function Check_IsMZorZM2(A, B: AnsiChar): boolean; asm add al, $65 add dl, $65 mul dl xor ax, $84CE setz al end;

> Блин, этож Дима :))
> Я то думаю кто это такой хитрый на форуме появился :)))

С тем ником, видимо, покончено :)

← →
Rouse_ © (2015-08-22 17:14) [25]

> DayGaykin © (22.08.15 17:06) [24]

Ты победил :))

← →
Sha © (2015-08-22 17:17) [26]

> Rouse_ © (22.08.15 17:14) [25]

и не он один, см. [4] )

← →
Rouse_ © (2015-08-22 17:35) [27]

Саш, ну я тебя никогда не считал - бо с твоей квалификацией... :)

← →
SergP © (2015-08-24 19:06) [28]

Попробовал обойтись без умножения... Правда кол-во инструкций на 1 больше чем [24]

function Check_IsMZorZM_SergP(A, B: AnsiChar): boolean; asm mov ah,dl sub ax,$53d4 sbb dx,dx xor ax,dx cmp ax,$679 setz al end;

не совсем "угу"

> DayGaykin © (22.08.15 16:29) [16]
>
>
> > Кстати, там есть константы и поменьше, например (X+77)
> *
> > (Y+77) = 25718
>
> Я подобрал методом "тыка". Мне сразу повезло со 101 :)

для подбора константы ИМХО чисто теоретически достаточно чтобы t+$4d или t+$5a было простым числом, большим чем 128
ближайшее к 128 и большее него простое число 131, так что похоже что минимальная константа будет 131-$5a=41

хотя нет, наверно, "угу", надо проверить...

Я проверял:

procedure TForm1.Button1Click(Sender: TObject); var x,y:byte; begin for x:=0 to 255 do for y:=0 to 255 do if Check_IsMZorZM_Sergp(ansichar(x),ansichar(y)) then Memo1. Lines.Add(IntToHex(y*256+x,4)); end;

ИМХО единственное " не совсем" может заключатся в том что результат
setz al
возможно не совсем соответствует boolean

> возможно не совсем соответствует boolean

Соответствует.

> Rouse_ © (24.08.15 20:03) [36]
>
>
> > возможно не совсем соответствует boolean
>
> Соответствует.

хз. я ассемблера не знаю. Просто в инете полазил и прочитал что setz al делает al=1 если установлен флаг нуля, но по идее для boolean оно должно быть не 1, а $FF , хотя мож я чего-то и забыл уже...

кстати, вопрос по ассемблеру:
можно ли использовать старшие слова регистров EAX, EBX, ECX, EDX в качестве операндов? если да, то как?

> можно ли использовать старшие слова регистров EAX, EBX,
> ECX, EDX в качестве операндов?

нет

Суботняя головоломка от Розыча Найти похожие ветки