Задачка про программиста Карла

[Equinoxe]

(Оффтоп)

Несмотря ни на что, эта задачка-таки математическая!

Программист Карл только что спаял процессор. В процессоре всего 26 регистров по 8 бит, обозначающихся буквами от A до Z, а ещё он поддерживает следующие инструкции:
(в инструкциях используются такие обозначения: R — регистр, C — константное число, X — или регистр, или константное число)
1. and R X — посчитать двоичное И чисел R (значение в регистре) и X, а затем записать его в R
2. or R X — посчитать двоично ИЛИ чисел R и X и записать его в R
3. not R — посчитать двоичное НЕ от R и записать его в R
4. shl R C — произвести двоичный сдвиг влево числа в R
5. shr R C — произвести двоичный сдвиг вправо числа в R
6. mov R X — записать в R значение X
7. get R — считать число и записать его в R
8. put R — написать число, хранящееся в R
Пояснение: произвести двоичный сдвиг влево 8-битного числа означает отрезать самую левую двоичную цифру, а справа приписать 0 (сдвиг вправо аналогичен).
not инвертирует все 8 бит, а не только какой-то один

Программист Карл решил написать программу, которая считывает число 0 или 1, инвертирует последний бит и выводит (0->1, 1->0), у него получился следующий код:

get A
not A
and A 1
put A

а) Теперь программист Карл задумался, можно ли сделать аналогичное для 8-ми чисел (нулей и единиц)? К сожалению, процессор получился довольно медленным, поэтому он не может выполнять больше одной инструкции not за программу. Учитывая это, ответье на его вопрос
б) Ура! Программист Карл сделал свой процессор в два раза мощнее и теперь он может выполнять до двух not за программу. Карла интересует, можно ли для 19 чисел (нулей и единиц) вывести их инверсии?

(Оффтоп)

Задачка повзаимствована из только что окончившегося соревнования IPSC :) venco, Вы не участвовали? И с проходом Вас в Р3!

[e2e4]

Глупый процессор, не имеет ни одной проверки условия :).
а) Если требуется порядок вывода такой же, как и порядок ввода, то:

get A
shl A 1; get B; or A B
shl A 1; get B; or A B
shl A 1; get B; or A B
shl A 1; get B; or A B
shl A 1; get B; or A B
shl A 1; get B; or A B
shl A 1; get B; or A B
not A
mov B A; shr B 7; put B
mov B A; shr B 6; and B 1; put B
mov B A; shr B 5; and B 1; put B
mov B A; shr B 4; and B 1; put B
mov B A; shr B 3; and B 1; put B
mov B A; shr B 2; and B 1; put B
mov B A; shr B 1; and B 1; put B
and A 1; put A

б) Рискну предположить, что нельзя

[Lunatik]

Я сначала подумал, а что, сложно все эти числа в регистр один запихать, но т. к. задача была бы слишком лёгкая, я решил, что неверно понял условие... но раз я правильно понял условие, то можно... Насчёт второго пункта я думаю, что можно... например занять регистры так, чтобы один, скажем, показывал, одинаковые ли пара (1 и 2, 3 и 4, и т.д.) цифр или разная, а другой - какой цифрой начинается эта пара... но как это реализовать, не вижу...

[Equinoxe]

e2e4,
в а) вроде похоже на правду
в б) напрасно рискнули

Lunatik, насчет первого Вы не ошиблись, он тривиален и сделан больше для понимания условия
Насчёт второго Вы также не ошибились (в отличие от большинства!) — способ есть.
За это Вам полагается подсказка:

(Подсказка)

Используйте всё данное максимально, а затем смотрите на задачу как математик (лишних знаний не требуется, требуется лишь определённый взгляд). Решение Вас не разочарует!

[e2e4]

Equinoxe, так как ломать голову уже надоело, буду благодарен за решение в личку.

[Equinoxe]

e2e4, выслала. Быть может, Lunatik сможет решить сам (тем более, что он так близок)? Или мне запостить решение уже и здесь?

[Lunatik]

У меня на уме только тот вариант, который я написал выше, в нём только нужно придумать, как узнавать, одинакова ли пара или нет (был бы xor ). А так я не знаю, за что зацепиться. В общем сдаюсь

[Equinoxe]

Lunatik, обидно! Вот оно решение:

(Решение)

Эта часть задачи далеко не тривиальна. На первый взгляд кажется, что используя not только дважды, мы не сможем инвертировать более 16 бит. Удивительно, но это не так!
Сначала рассмотрим, как решить более простую задачу: каждый регистр содержит только 1 бит, можем ли мы инвертировать 3 бита, используя 2 операции not?
Конечно можем! Например, так: (x, y, z — так назовём три этих регистра. Вся идея лишь в том, чтобы научиться считать 4-ре переменных, определяющих кол-во единичек)
1. Посчитаем lst2=(x and y) or (y and z) or (z and x), т.е. «не менее двух 1чек»
2. Посчитаем mst1=not lst2, т.е. «не более одной 1-чки»
3. Посчитаем lst1=x or y or z, т.е. «есть ли хоть одна 1чка»
4. Посчитаем ex1=lst1 and mst1, т.е. «единичка одна»
5. Посчитаем ex3=x and y and z, т.е. «единичек три»
6. Посчитаем ex13=ex1 or ex2, т.е. «или 1, или 3»
7. Посчитаем ex02=not ex13, т.е. «или 0, или 2»
8. Посчитаем ex0=mst1 and x02, т.е. «нет единичек»
9. Посчитаем ex2=lst2 and ex02, т.е. «ровно 2 единички»

Используя всего два not, мы получили четыре переменные — от ex0 до ex3. Используя их, мы уже можем однозначно восстановить ответ! (это сделать уже совсем элементарно)
8. not x = ex0 or (ex1 and (y or z)) or (ex2 and (y and z))
9. not y = ex0 or (ex1 and (x or z)) or (ex2 and (x and z))
10. not z = ex0 or (ex1 and (x or y)) or (ex2 and (x and y))
Теперь мы уже можем решить начальную задачу. Если мы будем использовать не 1-битные, а 8-битные (как в условии) регистры, то мы сможем решить эту же задачу параллельно для 8 троек битов = 24 чисел. Этого уже достаточно, чтобы решить для 19.

-- Вт июн 07, 2011 16:33:39 --

Кстати, пока я придумывала решение к этой задаче, я научилась решать эту задачу, если поменять условие так:

Цитата:

4. shl R X — произвести двоичный сдвиг влево числа в R
5. shr R X — произвести двоичный сдвиг вправо числа в R

Только здесь она решается вообще элементарно :) Я только потом поняла, насколько заблуждалась

[Lunatik]

Не... до такого я не дорос ... есть куда расти))). Но не жалею, ибо я бы не смог написать программку для 8-битных регистров))).

[Equinoxe]

Lunatik, ну, надеюсь, решение Вам понравилось? Сейчас я размышляю над тем, можно ли сделать его короче.

-- Вт июн 07, 2011 16:39:44 --

Т.е. ясное дело, что ex3 там вообще не нужен, а в остальном я сокращений пока не вижу

[e2e4]

Lunatik, Вы выкладки проверили? У меня все еще большие сомнения, однако сейчас времени нет разобраться до конца, буду завтра думать.

Equinoxe, в любом случае поздравления, если сами решили!

[Equinoxe]

e2e4, спасибо :) Правда, решила уже не на самом контесте — но всё же решила!

[e2e4]

Задачка по мотивам:

Программист Карл спаял еще более простой процессор, умеющий выполнять только команду вида:

nand R1, R2 - посчитать побитовое И-НЕ чисел R1(значение в регистре R1) и R2(значение в регистре R2), а затем записать его в регистр R1 (R1 и R2 могут совпадать).

Вопросы:
1. Какие логические функции (из 16 возможных, см. таблицу в подразделе logic gates) программист Карл сможет реализовать на своем процессоре при условии неограниченной длины программы? Почему именно их?
2. Изменится ли что-нибудь, если вместо nand будет доступна функция nor?
3. Изменится ли что-нибудь, если будут доступны обе функции nand и nor?

[Equinoxe]

e2e4, т.е. нельзя даже mov R X? Тогда закономерен вопрос: чем забиты регистры вначале? Нулями?

[e2e4]

Equinoxe, это не важно. Вопрос же про логические функции.