Как стать автором
Обновить

Немного логики…

Занимательные задачки
image

Задача #2 «Позитивные автоматы»



Для тех, кто не хочет читать:

Найти значение выражения: |x — |y||
X, Y — любые целые ( и отрицательные тоже )

Ограничение: нельзя пользоваться sub, dec… и любое другое вычитание, нельзя пользоваться регистрами флагов и бинарными операциями. (в частности сдвигами)
Все что у вас есть: je, cmp (нельзя смотреть флаги), jmp, inc, mov. (я же сказал, немного)

Для того, что бы лучше разобраться в задаче:

Есть такая замечательная штуковина, называется:
Машина с неограниченными регистрами (МНР)
Итак, зачем это? Лично для меня — расшевелить мозги.

Теперь попробуем в деле!


Как ей можно пользоваться? Пример: сложите два числа, в R0-первое число, в R1-второе число. Ответ записать в R0, при том r0, r1 >= 0

Замечание: я пишу имена регистров rn, а не Rn, и имена команд тоже маленькими, имхо удобнее.

Решение:
с1) s(r0); x = x+1
c2) s(r2); r2 = r2+1
c3) j(r2,r1,c1); если r2=r1, тогда прыгнуть на с1.
с4)

Как видно, если не произойдет прыжок на метке c3, то программа остановиться и в регистре r0 будет ответ.

Вольности:
— давать меткам любые имена (то что перед скобкой)
— можно писать пустые метки (что бы ссылаться на них и выходить из программы.)
— делать прыжки типа J(1,1,), это эквивалент безусловного прыжка
— делать записи типа T(, ), например: T ( r1, 5) (вообще этого нельзя делать, но ....)
— комментраии после ";", но вы как хотите уж

Ограничения:
— прыгать можно только на метки (нельзя делать адрес переменным)
— класть в регистры отрицательные числа

Если на МНР писать большие программы (например ОС), удобно сделать эквивалентные команды для ассемблера (тестирование).

Заметка:
r0.....rn — это зарезервированные в памяти слова. Пример: r0 dw 0
При том все «регистры» сначала в нуле.

МНР команды / АСМ. эквивалент

T(r1,r2) <=> mov ax,r2
mov r1,ax

S(r1) <=> inc r1

Z(r1) <=> mov r1,0

J(r1,r2,c1) <=> mov ax,r2
cmp r1,ax
je c1

J(1,1,c1) <=> jmp c1

В общем идея: завязать себе правую руку на ноге, склеить 3 пальца на левой руке и пойти прогить на асме. Ну ничего, у нас целые 4 команды.


Хватит теории, пора задачи решать.

Задача 1. Найти ошибку в моем примере.
Задача 2. Вычесть одно число из другого, при том первое больше. r0 — первое, r1- второе. Результат в r0
Задача 3. Найти значение выражения: |x — |y||
X, Y — любые целые ( и отрицательные тоже )
r0 — x; r1-y. Результат записать в r0. В комментариях привести аналог на ассемблере или на МНР.

P.S. все это я написал, надеясь, что у вас тоже появятся интересные задачи, с такими же ограничениями.
P.P.S. В комментариях находится решение Ayay на МНР, после этого мое, на ASM.
P.P.P.S. я сознательно расширил возможности МНР. По определению, она (МНР) вообще работает только с натуральными числами; я ввел пересылку в T(rn,), т.е. это пересылка числа в регистр сразу. До этого можно было только из регистра в регистр, но нельзя пересылать отрицательные числа.
Теги:Машина с неограниченными регистрамиавтоматызадачи на смекалкуассемблер
Хабы: Занимательные задачки
Всего голосов 20: ↑16 и ↓4 +12
Просмотры1.6K

Похожие публикации

Факультет разработки на С++
21 июня 202184 000 ₽GeekBrains
Разработчик игр на Unity
22 июня 2021108 000 ₽SkillFactory
Backend- разработчик на Go
23 июня 202181 000 ₽SkillFactory
Профессия QA-инженер на Java
23 июня 202159 400 ₽SkillFactory
Python для работы с данными
25 июня 202131 500 ₽Нетология

Лучшие публикации за сутки