?

Log in

задачка, компьютерное - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка, компьютерное [фев. 14, 2010|02:18 pm]
Anatoly Vorobey
Убил на нее немало времени сегодня, но очень понравилась:

Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.

Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.
СсылкаОтветить

Comments:
[User Picture]From: unsignedlong
2010-02-14 12:57 pm
сделать новый "my_not"

1)x xor 1 = not x

2)z or (not z ) = 1 (это для единички в xor)
3)xor = not(z) * y + not(y)+z

not(z) можно использовать из единички, которую получили в формуле 2
(Ответить) (Thread)
[User Picture]From: avva
2010-02-14 01:35 pm
с третьим пунктом что-то не так, вам же надо вычислять не y xor z, а x xor 1, т.е. по формуле третьего пункта нужно будет еще отдельно not x.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2010-02-14 01:51 pm
неинтересно, слишком много условий.
(Ответить) (Thread)
[User Picture]From: unsignedlong
2010-02-14 01:55 pm
это не условия
(Ответить) (Parent) (Thread)
[User Picture]From: burrru
2010-02-14 02:44 pm
На ум сразу приходят фамилии: Карацуба и Штрассен...
(Ответить) (Thread)
[User Picture]From: avva
2010-02-14 02:45 pm
Я их кстати так и не изучил, все эти быстрые умножения :(
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: alexeybobkov
2010-02-14 03:36 pm
О, я её лет десять назад решил аналитически.
Что интересно, вначале я доказал, что это невозможно :). Потом понял, что не учёл, что выход с одного инвертора можно завести на другой (через промежуточную логику, разумеется). Когда понял, задача сразу решилась.
Одно время схема у меня даже висела на стенке.
Могу восстановить, если надо.

В общем, в мире есть всего два инвертора. Не дай Бог один сгорит.
(Ответить) (Thread)
[User Picture]From: avva
2010-02-14 03:40 pm
В общем, в мире есть всего два инвертора. Не дай Бог один сгорит.

О!
(Ответить) (Parent) (Thread) (Развернуть)
From: renivid
2010-02-14 03:53 pm
Заводим A, B, C на AND, результ - на NOT, получаем !A+!B+!C дальше можно отделить A, B и С с помощью ИЛИ и пар B+C, A+C и A+B. Или я неправльно понял условия :).
(Ответить) (Thread)
[User Picture]From: avva
2010-02-14 04:16 pm
попробуйте выписать точнее, и увидите, что это не так просто :)
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2010-02-14 04:41 pm
Любую логическую схему можно реализовать на двух NOT.
(Ответить) (Thread)
From: (Anonymous)
2010-02-14 04:53 pm
Ну то есть да, конечно. Если три инвертора можно построить из двух, то и больше тоже можно. Duh.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: adp.myopenid.com
2010-02-14 07:12 pm
Не буду портить удовольствия решения :-) Замечу только, что это - частный случай более общей задачи: как реализовать при неограниченном количестве AND и OR n отрицаний NOT x_1, ..., NOT x_n. Можно доказать, что для этого достаточно целой части сверху log_2 (n+1). Справедлива аналогичная нижняя оценка.
(Ответить) (Thread)
[User Picture]From: spamsink
2010-02-14 07:17 pm
not_A = (A+B+C) == 0 || (A+B+C) == 1 && (B || C) || (A+B+C) == 2 && B && C

Дальше подсказывать не буду.

(Ответить) (Thread)
[User Picture]From: adp.myopenid.com
2010-02-14 07:30 pm

У вас ошибка

Если приоритет операций классический, то правая часть равна 1 при A = 1, B = 1, C = 0, а левая - нет.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: g00d
2010-02-14 10:21 pm
X1 = not (A * C)
X2 = not (B + C)

not C = (X1 * X2)

X3 = X1 * (not C)
X4 = X2 + (not C)

not A = (X1 * X3)
not B = (X2 * X4)
(Ответить) (Thread)
[User Picture]From: adp.myopenid.com
2010-02-14 10:26 pm

Неверно

A = 1, B = 1, C = 0 => X1 = 1, X2 = 0, X1 * X2 = 0 = C.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ao_terekhov
2010-02-15 10:41 am
А как эта задача решается компьютерным перебором?
(Ответить) (Thread)
[User Picture]From: avva
2010-02-15 10:44 am
Думаю об этом отдельную запись написать.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: avva
2010-02-16 09:48 am
nice.
(Ответить) (Parent) (Thread)
[User Picture]From: burivykh
2010-02-17 07:46 pm
Ну, поскольку "и" и "или" позволяют делать монотонные функции, то первый инвертор вешается на "A+B+C >= 2"; после этого выясняется, что XOR всех трёх A,B,C от них и от первого инвертора монотонна, и второй инвертор вешаем на неё. А теперь на каждом "возрастающем" ребре хоть один из инверторов, да убывает, поэтому все отрицания можно собрать.

Формально:
X=NOT (AB OR AC OR BC)
Y=NOT (((A OR B OR C) X) OR ABC).

NOT A = (X (Y OR B OR C)) OR (YBC)

Вроде, так...
(Ответить) (Thread)
[User Picture]From: oxfv
2010-02-18 01:42 am
Поленился решать головой и написал программу. Работает 15 секунд, наверняка можно улучшить.

a = 0x0f
b = 0x33
c = 0x55

# three stages of list proliferation: before the first ~, after the first ~, after the second ~
# the stage counts picked empirically
stages = [3,2,2]

# adds to the list l all values that could be computed out of its elements with & and |
def proliferate_list(l, stage, d = None):

    for i in range(stages[stage]):
        lset = frozenset(l)
        for v1 in lset:
            for v2 in lset:
                if v1 < v2:     # for all unique pairs in l
                    if not (v1 & v2) in l:     l.append( v1 & v2 )
                    if not (v1 | v2) in l:     l.append( v1 | v2 )

                    if d:
                        # wraps operand in round brackets only when needed
                        def wrap_operand( s, operation ):
                            balance = 0
                            for c in s:
                                if c in ['&','|'] and balance==0:
                                    return (c==operation) and s or '(%s)'%s
                                elif c=='(':    balance += 1
                                elif c==')':    balance -= 1
                            return s

                        # keep the most concise expression for each value
                        s = wrap_operand(d[v1],'&') + '&' + wrap_operand(d[v2],'&')
                        if not d.has_key(v1&v2) or len(d[v1&v2])>len(s):  d[v1&v2] = s

                        s = wrap_operand(d[v1],'|') + '|' + wrap_operand(d[v2],'|')
                        if not d.has_key(v1|v2) or len(d[v1|v2])>len(s):  d[v1|v2] = s
    if d:
        return l, d
    else:
        return l


try:
    l = proliferate_list([a,b,c],0)
    for v1 in l:
        x = 0xff & ~v1
        l1 = proliferate_list(l+[x], 1)
        for v2 in l1:
            y = 0xff & ~v2
            if not y in l1:
                l2 = proliferate_list(l1+[y], 2)

                if len(set([0xf0, 0xcc, 0xaa]) & set(l2)) == 3:   # all three of ~a,~b,~c are found
                    # repeat the proliferation steps, this time keeping the dictionary of expressions
                    d = { a:'a', b:'b', c:'c', x:'x', y:'y' }
                    l3,d = proliferate_list([a,b,c],0,d)
                    print '  x = ~(%s)' % d[v1]   # have to print x here lest the more concise but y-dependent expression replaces it
                    l3,d = proliferate_list(l3+[x],1,d)
                    print '  y = ~(%s)' % d[v2]
                    l3,d = proliferate_list(l3+[y],2,d)

                    for v in [a, b, c]:
                        print '  ~%s: %s' % (d[v], d[0xff&~v])
                    raise Exception
except:
    pass

Вот её результат:
  x = ~((a&b)|((a|b)&c))
  y = ~((a&b&c)|((a|b|c)&x))
  ~a: ((b|c)&x)|(y&((b&c)|x))
  ~b: ((a|c)&x)|(y&((a&c)|x))
  ~c: ((a|b)&x)|(y&((a&b)|x))


(Ответить) (Thread)
[User Picture]From: gurka_ju
2010-02-18 09:23 pm

7 минут

муж случайно нашел эту задачку

если А Б С принять за 0 1 2 ...
тогда
А&(Б||C)= ^B || ^C
B&C = ^A....

на этом, кажется, все...
(Ответить) (Thread)
[User Picture]From: adp.myopenid.com
2010-02-19 06:40 am

Re: 7 минут

Что такое А&(Б||С), когда A Б С = 0 1 2?
(Ответить) (Parent) (Thread) (Развернуть)
From: ijon_ru
2010-02-22 04:31 am
x4 = B and C
x6 = A and C
x7 = A and B
n1 = not (x4 or x6 or x7)
z2 = n1 and C
z3 = n1 and B
z5 = n1 and A
n2 = not (z2 or z3 or z5 or (A and B and C))
z1 = n1 and n2
z4 = x4 and n2
z6 = x6 and n2
z7 = x7 and n2
notA = z1 or z2 or z3 or z4
notB = z1 or z2 or z5 or z6
notC = z1 or z3 or z5 or z7

По совместительству код на Питоне:
c = 2
s = ''
for A in range(c):
for B in range(c):
for C in range(c):
...
s += '%i %i %i | %i %i %i | %i %i %i\n' % \
(A, B, C, not A, not B, not C, notA, notB, notC)
print s
(Ответить) (Thread)
From: (Anonymous)
2010-04-01 08:23 pm
X = NOT(A AND B)
NOT(A) = B OR X
NOT(B) = A OR X
NOT(C) = NOT(C)
Как то уж очень просто.
(Ответить) (Thread)
From: (Anonymous)
2010-04-01 08:28 pm
даже так:
X=NOT(A AND B AND C)
NOT(A) = X OR B OR C
NOT(B) = X OR A OR C
NOT(C) = X OR A OR B
(Ответить) (Parent) (Thread) (Развернуть)