2014 dxdy logo

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

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




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


20/05/11
152
e2e4 в сообщении #456469 писал(а):
TRUE можно достигнуть за 4 шага, FALSE за 5.


nand A, B
nand B, B
nand A, A
nand A, B - TRUE
nand A, A - FALSE

Меня возможность построения операторов интересует, а не их наименьший размер... а вот над простым лог. доказательством я честно говоря не думал... Ща подумаю!

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


21/03/06
1545
Москва
Equinoxe писал(а):
Сначала рассмотрим, как решить более простую задачу: каждый регистр содержит только 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))
Теперь мы уже можем решить начальную задачу.

Чтож, дошли руки до проверки Вашего решения.

Смотрите:
шаг 6: ex13=ex1 or ex2
должно быть ex13 = ex1 or ex3

-- Сб июн 11, 2011 11:57:55 --

В остальном все верно.

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


21/03/06
1545
Москва
Такой же фокус вроде бы не проходит с условием: инвертировать два числа, используя только один НЕ.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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