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 --В остальном все верно.
