2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Задачка про программиста Карла
Сообщение05.06.2011, 20:43 


24/01/11
207

(Оффтоп)

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

Программист Карл только что спаял процессор. В процессоре всего 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!

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение06.06.2011, 15:14 


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

Код:
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


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение06.06.2011, 15:59 


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение06.06.2011, 21:54 


24/01/11
207
e2e4,
в а) вроде похоже на правду
в б) напрасно рискнули :-)

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

(Подсказка)

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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 06:16 


21/03/06
1545
Москва
Equinoxe, так как ломать голову уже надоело, буду благодарен за решение в личку.

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 15:20 


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 15:32 


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 16:27 


24/01/11
207
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

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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 16:35 


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 16:38 


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

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

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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 20:05 


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

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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение07.06.2011, 21:25 


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение09.06.2011, 21:06 


21/03/06
1545
Москва
Задачка по мотивам:

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

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

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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение09.06.2011, 21:38 


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

 Профиль  
                  
 
 Re: Задачка про программиста Карла
Сообщение09.06.2011, 22:15 


21/03/06
1545
Москва
Equinoxe, это не важно. Вопрос же про логические функции.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group